TopolearnGrouping nodes into tightly knit clusters reveals structure such as friend circles, topics and functional modules.
A community is a group of nodes more densely connected to each other than to the rest of the graph. NetworkX's nx.community module offers several algorithms, each returning a list of node sets:
- Louvain (
nx.community.louvain_communities(G, weight="weight", resolution=1, seed=42)): greedy modularity optimization in levels. Fast and the usual first choice. Higherresolutiongives more, smaller communities. - Leiden (
nx.community.leiden_communities): an improved Louvain that guarantees well-connected communities. It is a recent addition to NetworkX, and backends such asnx-cugraphaccelerate it. - Label propagation (
nx.community.label_propagation_communitiesorasyn_lpa_communities): very fast, but results vary between runs. - Greedy modularity (
greedy_modularity_communities) and Girvan-Newman (girvan_newman, which removes high-betweenness edges; slow, small graphs only).
Modularity (nx.community.modularity(G, communities)) scores a partition: the fraction of edges inside communities minus what you'd expect at random. Values above about 0.3 suggest real structure.
Related local measures: the clustering coefficient (nx.clustering(G, n), nx.average_clustering(G)) is the fraction of a node's neighbour pairs that are themselves connected, i.e. how many triangles it sits in. nx.triangles(G) counts them.
Random algorithms need seed= for reproducible results.
Example
import networkx as nx
G = nx.karate_club_graph() # the classic 34-member club
parts = nx.community.louvain_communities(G, seed=42)
print(len(parts), sorted(map(len, parts))) # 4 [4, 6, 10, 14] (with this seed)
print(round(nx.community.modularity(G, parts), 2)) # 0.43 (edge weights used)
# Compare with the real split after the club broke up
truth = [{n for n, d in G.nodes(data=True) if d["club"] == c}
for c in ("Mr. Hi", "Officer")]
print(round(nx.community.modularity(G, truth), 2)) # 0.39
print(round(nx.average_clustering(G), 3)) # 0.571
print(nx.triangles(G, 0)) # 18Remember
- Louvain is the fast default; set
seed=for reproducibility - Modularity compares within-community edges to random expectation
- Clustering coefficient measures local triangle density
Watch out for
- Treating one run of a randomized community algorithm as the definitive answer.