diff options
Diffstat (limited to '.venv/lib/python3.12/site-packages/networkx/algorithms/community/leiden.py')
| -rw-r--r-- | .venv/lib/python3.12/site-packages/networkx/algorithms/community/leiden.py | 162 |
1 files changed, 162 insertions, 0 deletions
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/community/leiden.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/community/leiden.py new file mode 100644 index 0000000..f79c012 --- /dev/null +++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/community/leiden.py @@ -0,0 +1,162 @@ +"""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." + ) |