Communities#

Functions for computing and measuring community structure.

The community subpackage can be accessed by using networkx.community, then accessing the functions as attributes of community. For example:

>>> import networkx as nx
>>> G = nx.barbell_graph(5, 1)
>>> communities_generator = nx.community.girvan_newman(G)
>>> top_level_communities = next(communities_generator)
>>> next_level_communities = next(communities_generator)
>>> sorted(map(sorted, next_level_communities))
[[0, 1, 2, 3, 4], [5], [6, 7, 8, 9, 10]]

Bipartitions#

Functions for splitting a network into two communities (finding a bipartition).

`kernighan_lin_bisection`(G[, partition, ...])	Partition a graph into two blocks using the Kernighan–Lin algorithm.
`spectral_modularity_bipartition`(G)	Return a bipartition of the nodes based on the spectrum of the modularity matrix of the graph.
`greedy_node_swap_bipartition`(G, *[, ...])	Split the nodes into two communities based on greedy modularity maximization.

Divisive Communities#

`edge_betweenness_partition`(G, number_of_sets, *)	Partition created by iteratively removing the highest edge betweenness edge.
`edge_current_flow_betweenness_partition`(G, ...)	Partition created by removing the highest edge current flow betweenness edge.

K-Clique#

k_clique_communities(G, k[, cliques])

Find k-clique communities in graph using the percolation method.

Modularity-based communities#

Functions for detecting communities based on modularity.

`greedy_modularity_communities`(G[, weight, ...])	Find communities in G using greedy modularity maximization.
`naive_greedy_modularity_communities`(G[, ...])	Find communities in G using greedy modularity maximization.

Tree partitioning#

Lukes Algorithm for exact optimal weighted tree partitioning.

lukes_partitioning(G, max_size[, ...])

Optimal partitioning of a weighted tree using the Lukes algorithm.

Label propagation#

Label propagation community detection algorithms.

`asyn_lpa_communities`(G[, weight, seed])	Returns communities in G as detected by asynchronous label propagation.
`label_propagation_communities`(G)	Generates community sets determined by label propagation
`fast_label_propagation_communities`(G, *[, ...])	Returns communities in G as detected by fast label propagation.

Local Community Detection#

Local Community Detection Algorithms

Local Community Detection (LCD) aims to detected one or a few communities starting from certain source nodes in the network. This differs from Global Community Detection (GCD), which aims to partition an entire network into communities.

LCD is often useful when only a portion of the graph is known or the graph is large enough that GCD is infeasable

[1] Gives a good introduction and overview of LCD

References#

[1]

Baltsou, Georgia, Konstantinos Christopoulos, and Konstantinos Tsichlas. Local community detection: A survey. IEEE Access 10 (2022): 110701-110726. https://doi.org/10.1109/ACCESS.2022.3213980

greedy_source_expansion(G, *, source[, ...])

Find the local community around a source node.

Louvain Community Detection#

Detecting communities based on the Louvain Community Detection algorithm

`louvain_communities`(G[, weight, resolution, ...])	Find the best partition of a graph using the Louvain Community Detection Algorithm.
`louvain_partitions`(G[, weight, resolution, ...])	Yield partitions for each level of the Louvain Community Detection Algorithm

Leiden Community Detection#

Detecting communities based on the Leiden Community Detection algorithm

`leiden_communities`(G, *[, weight, ...])	Return best node communities of G.
`leiden_partitions`(G, *[, weight, metric, ...])	Yield partitions at each level of Leiden Community Detection

Infomap Community Detection#

Detecting communities based on the Infomap algorithm.

Infomap identifies communities as regions in which a random walk tends to remain; the literature calls them modules. It searches for a partition that compresses the walk: each module has its own codebook, so node codewords can be reused between modules, while transitions between modules require additional codewords. The map equation measures the resulting codelength in bits per step.

infomap_communities() searches for a flat, two-level partition. infomap_partitions() searches for a multilevel hierarchy. map_equation() scores a flat partition under the same flow model.

This module accepts first-order Graph, DiGraph, MultiGraph, and MultiDiGraph inputs. Specialized multilayer, higher-order or state, metadata-aware, and bipartite flow models are not exposed. A NetworkX bipartite graph is treated as an ordinary first-order graph.

Rosvall & Bergstrom (2008) introduce the method. Rosvall, Axelsson & Bergstrom (2009) derive the map equation in full. Rosvall & Bergstrom (2011) extend it to a multilevel hierarchy.

References#

Rosvall, M. & Bergstrom, C.T. Maps of random walks on complex networks reveal community structure. PNAS 105, 1118-1123 (2008). https://doi.org/10.1073/pnas.0706851105

Rosvall, M., Axelsson, D. & Bergstrom, C.T. The map equation. Eur. Phys. J. Special Topics 178, 13-23 (2009). https://doi.org/10.1140/epjst/e2010-01179-1

Rosvall, M. & Bergstrom, C.T. Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems. PLoS ONE 6(4), e18209 (2011). https://doi.org/10.1371/journal.pone.0018209

`infomap_communities`(G, *[, weight, seed, ...])	Find communities in G with the two-level Infomap heuristic.
`infomap_partitions`(G, *[, weight, seed, ...])	Return an iterator over the nested partitions of a multilevel Infomap hierarchy.

Fluid Communities#

Asynchronous Fluid Communities algorithm for community detection.

asyn_fluidc(G, k[, max_iter, seed])

Returns communities in G as detected by Fluid Communities algorithm.

Measuring partitions#

Functions for measuring the quality of a partition (into communities).

`modularity`(G, communities[, weight, resolution])	Returns the modularity of the given partition of the graph.
`map_equation`(G, communities, *[, weight, ...])	Return the two-level map equation codelength of a partition of G.
`overlapping_modularity`(G, communities, *[, ...])	Returns Shen et al.'s extended modularity for an overlapping cover.
`constant_potts_model`(G, communities[, ...])	Computes the Constant Potts Model, which is a measure of quality of a partition.
`partition_quality`(G, partition)	Returns the coverage and performance of a partition of G.

Partitions via centrality measures#

Functions for computing communities based on centrality notions.

girvan_newman(G[, most_valuable_edge])

Finds communities in a graph using the Girvan–Newman method.

Validating partitions#

Helper functions for community-finding algorithms.

`is_partition`(G, communities)	Returns True if communities is a partition of the nodes of G.
`is_cover`(G, communities)	Returns True if communities is a cover of the nodes of G.