cdlib.algorithms.girvan_newman

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

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.