Communities#

Functions for computing and measuring community structure.

The functions in this class are not imported into the top-level networkx namespace. You can access these functions by importing the networkx.algorithms.community module, then accessing the functions as attributes of community. For example:

>>> from networkx.algorithms import community
>>> G = nx.barbell_graph(5, 1)
>>> communities_generator = 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 computing the Kernighan–Lin bipartition algorithm.

kernighan_lin_bisection(G[, partition, ...])

Partition a graph into two blocks using the Kernighan–Lin algorithm.

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

Louvain Community Detection#

Function for detecting communities based on 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, ...])	Yields partitions for each level of the Louvain Community Detection Algorithm

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

`coverage`(G, partition)	Returns the coverage of a partition.
`modularity`(G, communities[, weight, resolution])	Returns the modularity of the given partition of the graph.
`partition_quality`(G, partition)	Returns the coverage and performance of a partition of G.
`performance`(G, partition)	Returns the performance of a partition.

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.