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
  • g_original – a networkx/igraph object
  • level – the level where to cut the dendrogram

NodeClustering object

>>> 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.