louvain_communities#

louvain_communities(G, weight='weight', resolution=1, threshold=1e-07, max_level=None, seed=None)[source]#

Find the best partition of a graph using the Louvain Community Detection Algorithm.

Louvain Community Detection seeks to extract the community structure of a network. It is a heuristic algorithm based on modularity optimization. [1]

The algorithm starts with every node in its own community and then repeatedly updates by merging communities. Each update consists of two phases. First, each node is examined to find the maximum positive modularity gain obtained by moving it to a different community. If no positive gain can be achieved the node remains in its original community. The next node is then considered. Nodes continue to be examined until no improvement in modularity can be obtained by moving nodes. The second phase builds an aggregated network where each community of the original network is a node in the new network with edges connecting then if nodes in those two communities connect to each other. The edge weights and node attributes of the new network are the sums of edge and node attributes from the communities in the previous network. These two phases are repeated until no modularity gain is achieved (or is less than a threshold, or until max_levels updates have occurred).

The modularity gain obtained by moving an isolated node \(i\) into a community \(C\) can be calculated by the following formula (combining [1] [2] and some algebra):

\[\Delta Q = \frac{k_{i,in}}{2m} - \gamma\frac{ \Sigma_{tot} \cdot k_i}{2m^2}\]

where \(m\) is the size of the graph; \(k_{i,in}\) is the sum of the edge weights from \(i\) to nodes in \(C\); \(k_i\) is the sum of the edge weights incident to node \(i\); \(\Sigma_{tot}\) is the sum of the edge weights incident to nodes in \(C\); and \(\gamma\) is the resolution parameter. Higher resolution produces smaller communities. Low resolution produces larger communities.

For the directed case the modularity gain can be computed (see [3]) using the formula:

\[\Delta Q = \frac{k_{i,in}}{m} - \gamma\frac{k_i^{out} \cdot\Sigma_{tot}^{in} + k_i^{in} \cdot \Sigma_{tot}^{out}}{m^2}\]

where \(k_i^{out}\), \(k_i^{in}\) are the outer and inner weighted degrees of node \(i\); \(\Sigma_{tot}^{in}\) and \(\Sigma_{tot}^{out}\) are the sum of in-going and out-going edge weights incident to nodes in \(C\).

Be careful with self-loops in the input graph. These are treated as previously reduced communities – as if the process had been started in the middle of the algorithm. Large self-loop edge weights thus represent strong communities and in practice may be hard to add other nodes to. If your input graph edge weights for self-loops do not represent already reduced communities you may want to remove the self-loops before using that graph.

Parameters:

GNetworkX graph
weightstring or None, optional (default=”weight”): The name of an edge attribute that holds the numerical value used as a weight. If None then each edge has weight 1.
resolutionfloat, optional (default=1): If resolution is less than 1, the algorithm favors larger communities. Greater than 1 favors smaller communities
thresholdfloat, optional (default=0.0000001): Modularity gain threshold for each level. If the gain of modularity between 2 levels of the algorithm is less than the given threshold then the algorithm stops and returns the resulting communities.
max_levelint or None, optional (default=None): The maximum number of levels (steps of the algorithm) to compute. Must be a positive integer or None. If None, then there is no max level and the threshold parameter determines the stopping condition.
seedinteger, random_state, or None (default): Indicator of random number generation state. See Randomness.

Returns:

list: A list of sets (partition of G). Each set represents one community and contains all the nodes in that community.

See also

louvain_partitions
leiden_communities

Notes

The order in which the nodes are considered can affect the final output. In the algorithm the ordering happens using a random shuffle.

References

[1] (1,2)

Blondel, V.D. et al. Fast unfolding of communities in large networks. J. Stat. Mech 10008, 1-12(2008). https://doi.org/10.1088/1742-5468/2008/10/P10008

[2]

Traag, V.A., Waltman, L. & van Eck, N.J. From Louvain to Leiden: guaranteeing well-connected communities. Sci Rep 9, 5233 (2019). https://doi.org/10.1038/s41598-019-41695-z

[3]

Nicolas Dugué, Anthony Perez. Directed Louvain : maximizing modularity in directed networks. [Research Report] Université d’Orléans. 2015. hal-01231784. https://hal.archives-ouvertes.fr/hal-01231784

Examples

>>> import networkx as nx
>>> G = nx.petersen_graph()
>>> nx.community.louvain_communities(G, seed=111)
[{0, 4, 5, 7, 9}, {1, 2, 3, 6, 8}]
----

Additional backends implement this function

cugraphGPU-accelerated backend.

seed parameter is currently ignored, and self-loops are not yet supported.

Additional parameters:

dtypedtype or None, optional: The data type (np.float32, np.float64, or None) to use for the edge weights in the algorithm. If None, then dtype is determined by the edge values.

neptuneNeptune computation backend for NetworkX.

Please note that the resolution and seed parameters are not supported at the moment.
For additional parameters, see awslabs/nx-neptune