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 computing the Kernighan–Lin bipartition algorithm.

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

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

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 Communty 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#

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

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

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.