Module org.jgrapht.core

Package org.jgrapht.alg.clustering

Class GirvanNewmanClustering<V,E>

java.lang.Object

org.jgrapht.alg.clustering.GirvanNewmanClustering<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

ClusteringAlgorithm<V>

public class GirvanNewmanClustering<V,E>
extends Object
implements ClusteringAlgorithm<V>

The Girvan-Newman clustering algorithm.

The algorithm is described in: Girvan, Michelle, and Mark EJ Newman. "Community structure in social and biological networks." Proceedings of the national academy of sciences 99.12 (2002): 7821-7826.

Running time is $O(m^2 n)$ or $O(m^2n + m n^2 \log n)$ for weighted graphs.

Author:

Dimitrios Michail

Nested Class Summary

Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ClusteringAlgorithm

ClusteringAlgorithm.Clustering<V>, ClusteringAlgorithm.ClusteringImpl<V>

Constructor Summary

Constructors

Constructor	Description
GirvanNewmanClustering(Graph<V,E> graph, int k)	Create a new clustering algorithm.
GirvanNewmanClustering(Graph<V,E> graph, int k, EdgeBetweennessCentrality.OverflowStrategy overflowStrategy, Iterable<V> startVertices)	Create a new clustering algorithm.

Method Summary

Modifier and Type	Method	Description
ClusteringAlgorithm.Clustering<V>	getClustering()	Computes a clustering.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

GirvanNewmanClustering

public GirvanNewmanClustering(Graph<V,E> graph,
                              int k)

Create a new clustering algorithm.

Parameters:

graph - the graph

k - the desired number of clusters

GirvanNewmanClustering

public GirvanNewmanClustering(Graph<V,E> graph,
                              int k,
                              EdgeBetweennessCentrality.OverflowStrategy overflowStrategy,
                              Iterable<V> startVertices)

Create a new clustering algorithm.

Parameters:

graph - the graph

k - the desired number of clusters

overflowStrategy - strategy to use if overflow is detected

startVertices - vertices from which to start shortest path computations when computing edge centralities. This parameter allows the user to compute edge centrality contributions only from a subset of the vertices of the graph. If null the whole graph vertex set is used.

Method Detail

getClustering

public ClusteringAlgorithm.Clustering<V> getClustering()

Description copied from interface: ClusteringAlgorithm

Computes a clustering.

Specified by:

getClustering in interface ClusteringAlgorithm<V>

Returns:

a clustering