Package dev.nm.graph.community
Class GirvanNewman<V,E extends UndirectedEdge<V>,G extends UnDiGraph<V,E>>
- java.lang.Object
-
- dev.nm.graph.community.GirvanNewman<V,E,G>
-
- Type Parameters:
V
- vertex typeE
- edge typeG
- 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.- See Also:
- Wikipedia: Girvan–Newman algorithm
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static interface
GirvanNewman.EdgeBetweenessCtor<V>
This allows customization of the computation of edge-betweeness.
-
Constructor Summary
Constructors Constructor 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 Instance Methods Concrete Methods Modifier and Type Method 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.
-
-
-
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 graphebCtor
- a customized constructor of edge-betweenessgCtor
- 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
-
-