Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

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 graph using Clauset-Newman-Moore greedy modularity maximization.

_naive_greedy_modularity_communities(G)

Find communities in graph using the 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

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

Returns the modularity of the given partition of the graph.

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.