girvan_newman(g_original: object, level: int) → cdlib.classes.node_clustering.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
>>> from cdlib import algorithms >>> import networkx as nx >>> G = nx.karate_club_graph() >>> com = algorithms.girvan_newman(G, level=3)
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.