cdlib.algorithms.girvan_newman¶
- cdlib.algorithms.girvan_newman(g_original: object, level: int) NodeClustering ¶
The Girvan–Newman algorithm detects communities by progressively removing edges from the original graph. The algorithm removes the “most valuable” edge, traditionally the edge with the highest betweenness centrality, at each step. As the graph breaks down into pieces, the tightly knit community structure is exposed and the result can be depicted as a dendrogram.
Supported Graph Types
Undirected
Directed
Weighted
Yes
No
No
- Parameters:
g_original – a networkx/igraph object
level – the level where to cut the dendrogram
- Returns:
NodeClustering object
- Example:
>>> from cdlib import algorithms >>> import networkx as nx >>> G = nx.karate_club_graph() >>> com = algorithms.girvan_newman(G, level=3)
- References:
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.