# SuanShu, a Java numerical and statistical library

com.numericalmethod.suanshu.graph.community

## Class GirvanNewman<V,E extends UndirectedEdge<V>,G extends UnDiGraph<V,E>>

• java.lang.Object
• com.numericalmethod.suanshu.graph.community.GirvanNewman<V,E,G>
• Type Parameters:
V - vertex type
E - edge type
G - graph type
Direct Known Subclasses:
GirvanNewmanUnDiGraph

public class GirvanNewman<V,E extends UndirectedEdge<V>,G extends UnDiGraph<V,E>>
extends Object
The Girvan–Newman algorithm detects communities in complex systems. It progressively removes edges from the original graph. Those edges are the least central, i.e., most "between" communities.
Wikipedia: Girvan–Newman algorithm
• ### Nested Class Summary

Nested Classes
Modifier and Type Class and Description
static interface  GirvanNewman.EdgeBetweenessCtor<V>
This allows customization of the computation of edge-betweeness.
• ### Constructor Summary

Constructors
Constructor and Description
GirvanNewman(UnDiGraph<V,E> g, GirvanNewman.EdgeBetweenessCtor<V> ebCtor, GraphUtils.GraphFactory<G> gCtor)
Construct an instance of the Girvan-Newman algorithm.
• ### Method Summary

All Methods
Modifier and Type Method and Description
List<G> clusters()
Gets all the clusters, each of which is connected.
int maxClusterSize()
Get the size of the maximal cluster.
UndirectedEdge<V> maxEdge()
Gets the edge with the maximal edge-betweeness.
double maxValue()
Get the maximum of edge-betweeness.
int numberOfClusters()
Gets the number of connected clusters.
double removeMaxEdge()
Removes the edge with the highest edge-betweeness.
String toString()
double value(UndirectedEdge<V> edge)
Get the edge-betweeness of an edge.
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
• ### Constructor Detail

• #### GirvanNewman

public GirvanNewman(UnDiGraph<V,E> g,
GirvanNewman.EdgeBetweenessCtor<V> ebCtor,
GraphUtils.GraphFactory<G> gCtor)
Construct an instance of the Girvan-Newman algorithm.
Parameters:
g - an undirected graph
ebCtor - a customized constructor of edge-betweeness
gCtor - a factory to construct instances of the graph type
• ### Method Detail

• #### removeMaxEdge

public double removeMaxEdge()
Removes the edge with the highest edge-betweeness. Recalculate the betweenness of all edges affected by the removal.
Returns:
the highest edge-betweeness; Double.NaN if there is no edge to remove
• #### clusters

public List<G> clusters()
Gets all the clusters, each of which is connected.
Returns:
all the clusters
• #### numberOfClusters

public int numberOfClusters()
Gets the number of connected clusters.
Returns:
the number of connected clusters
• #### value

public double value(UndirectedEdge<V> edge)
Get the edge-betweeness of an edge.
Parameters:
edge - an edge
Returns:
the edge-betweeness
• #### maxEdge

public UndirectedEdge<V> maxEdge()
Gets the edge with the maximal edge-betweeness.
Returns:
the edge with the maximal edge-betweeness
• #### maxValue

public double maxValue()
Get the maximum of edge-betweeness.
Returns:
the maximum of edge-betweeness
• #### maxClusterSize

public int maxClusterSize()
Get the size of the maximal cluster.
Returns:
the size of the maximal cluster
• #### toString

public String toString()
Overrides:
toString in class Object