163 lines
6.8 KiB
Python
163 lines
6.8 KiB
Python
|
"""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"]
|
|||
|
|
|
|||
|
|
|
|||
|
|
@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()
|
|||
|
|
|
|||
|
|
|
|||
|
|
@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."
|
|||
|
|
)
|