"""Functions for detecting communities based on Leiden Community Detection
algorithm.
These functions do not have NetworkX implementations.
They may only be run with an installable :doc:`backend </backends>`
that supports them.
"""
import itertools
from collections import deque
import networkx as nx
from networkx.utils import not_implemented_for, py_random_state
__all__ = ["leiden_communities", "leiden_partitions"]
[docs]
@not_implemented_for("directed")
@py_random_state("seed")
@nx._dispatchable(edge_attrs="weight", implemented_by_nx=False)
def leiden_communities(G, weight="weight", resolution=1, max_level=None, seed=None):
r"""Find a best partition of `G` using Leiden Community Detection (backend required)
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 :any:`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
----------
G : NetworkX graph
weight : string 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.
resolution : float, optional (default=1)
If resolution is less than 1, the algorithm favors larger communities.
Greater than 1 favors smaller communities.
max_level : int 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.
seed : integer, random_state, or None (default)
Indicator of random number generation state.
See :ref:`Randomness<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`.
Examples
--------
>>> import networkx as nx
>>> G = nx.petersen_graph()
>>> nx.community.leiden_communities(G, backend="example_backend") # doctest: +SKIP
[{2, 3, 5, 7, 8}, {0, 1, 4, 6, 9}]
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
See Also
--------
leiden_partitions
:any:`louvain_communities`
"""
partitions = leiden_partitions(G, weight, resolution, seed)
if max_level is not None:
if max_level <= 0:
raise ValueError("max_level argument must be a positive integer or None")
partitions = itertools.islice(partitions, max_level)
final_partition = deque(partitions, maxlen=1)
return final_partition.pop()
[docs]
@not_implemented_for("directed")
@py_random_state("seed")
@nx._dispatchable(edge_attrs="weight", implemented_by_nx=False)
def leiden_partitions(G, weight="weight", resolution=1, seed=None):
"""Yield partitions for each level of Leiden Community Detection (backend required)
Leiden Community Detection is an algorithm to extract the community
structure of a network based on modularity optimization.
The partitions across levels (steps of the algorithm) form a dendrogram
of communities. A dendrogram is a diagram representing a tree and each
level represents a partition of the G graph. The top level contains the
smallest communities and as you traverse to the bottom of the tree the
communities get bigger and the overall modularity increases making
the partition better.
Each level is generated by executing the three phases of the Leiden Community
Detection algorithm. See :any:`leiden_communities`.
Parameters
----------
G : NetworkX graph
weight : string 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.
resolution : float, optional (default=1)
If resolution is less than 1, the algorithm favors larger communities.
Greater than 1 favors smaller communities.
seed : integer, random_state, or None (default)
Indicator of random number generation state.
See :ref:`Randomness<randomness>`.
Yields
------
list
A list of disjoint sets (partition of `G`). Each set represents one community.
All communities together contain all the nodes in `G`. The yielded partitions
increase modularity with each iteration.
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
See Also
--------
leiden_communities
:any:`louvain_partitions`
"""
raise NotImplementedError(
"'leiden_partitions' is not implemented by networkx. "
"Please try a different backend."
)
