leiden_communities

leiden_communities(G, weight='weight', resolution=1, max_level=None, seed=None)

Find a best partition of G using Leiden Community Detection (backend required)

Attention

This function does not have a default NetworkX implementation. It may only be run with an installable backend that supports it such as “cugraph”.

Hint: use backend=... keyword argument to specify a backend or add backends to nx.config.backend_priority.

Leiden Community Detection is an algorithm to extract the community structure of a network based on modularity optimization. It is an improvement upon the Louvain Community Detection algorithm. See louvain_communities.

Unlike the Louvain algorithm, it guarantees that communities are well connected in addition to being faster and uncovering better partitions. [1]

The algorithm works in 3 phases. On the first phase, it adds the nodes to a queue randomly and assigns every node to be in its own community. For each node it tries to find the maximum positive modularity gain by moving each node to all of its neighbor communities. If a node is moved from its community, it adds to the rear of the queue all neighbors of the node that do not belong to the node’s new community and that are not in the queue.

The first phase continues until the queue is empty.

The second phase consists in refining the partition \(P\) obtained from the first phase. It starts with a singleton partition \(P_{refined}\). Then it merges nodes locally in \(P_{refined}\) within each community of the partition \(P\). Nodes are merged with a community in \(P_{refined}\) only if both are sufficiently well connected to their community in \(P\). This means that after the refinement phase is concluded, communities in \(P\) sometimes will have been split into multiple communities.

The third phase consists of aggregating the network by building a new network whose nodes are now the communities found in the second phase. However, the non-refined partition is used to create an initial partition for the aggregate network.

Once this phase is complete it is possible to reapply the first and second phases creating bigger communities with increased modularity.

The above three phases are executed until no modularity gain is achieved or max_level number of iterations have been performed.

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.

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 algorithm will run until converged.

seedinteger, random_state, or None (default)

Indicator of random number generation state. See Randomness.

Returns:

list

A list of disjoint sets (partition of G). Each set represents one community. All communities together contain all the nodes in G.

See also

leiden_partitions

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

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

Examples

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

Additional backends implement this function

cugraphGPU-accelerated backend.

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.