Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Functions for detecting communities based on Leiden Community Detection
2algorithm.
4These functions do not have NetworkX implementations.
5They may only be run with an installable :doc:`backend </backends>`
6that supports them.
7"""
9import itertools
10from collections import deque
12import networkx as nx
13from networkx.utils import not_implemented_for, py_random_state
15__all__ = ["leiden_communities", "leiden_partitions"]
18@not_implemented_for("directed")
19@py_random_state("seed")
20@nx._dispatchable(edge_attrs="weight", implemented_by_nx=False)
21def leiden_communities(G, weight="weight", resolution=1, max_level=None, seed=None):
22 r"""Find a best partition of `G` using Leiden Community Detection (backend required)
24 Leiden Community Detection is an algorithm to extract the community structure
25 of a network based on modularity optimization. It is an improvement upon the
26 Louvain Community Detection algorithm. See :any:`louvain_communities`.
28 Unlike the Louvain algorithm, it guarantees that communities are well connected in addition
29 to being faster and uncovering better partitions. [1]_
31 The algorithm works in 3 phases. On the first phase, it adds the nodes to a queue randomly
32 and assigns every node to be in its own community. For each node it tries to find the
33 maximum positive modularity gain by moving each node to all of its neighbor communities.
34 If a node is moved from its community, it adds to the rear of the queue all neighbors of
35 the node that do not belong to the node’s new community and that are not in the queue.
37 The first phase continues until the queue is empty.
39 The second phase consists in refining the partition $P$ obtained from the first phase. It starts
40 with a singleton partition $P_{refined}$. Then it merges nodes locally in $P_{refined}$ within
41 each community of the partition $P$. Nodes are merged with a community in $P_{refined}$ only if
42 both are sufficiently well connected to their community in $P$. This means that after the
43 refinement phase is concluded, communities in $P$ sometimes will have been split into multiple
44 communities.
46 The third phase consists of aggregating the network by building a new network whose nodes are
47 now the communities found in the second phase. However, the non-refined partition is used to create
48 an initial partition for the aggregate network.
50 Once this phase is complete it is possible to reapply the first and second phases creating bigger
51 communities with increased modularity.
53 The above three phases are executed until no modularity gain is achieved or `max_level` number
54 of iterations have been performed.
56 Parameters
57 ----------
58 G : NetworkX graph
59 weight : string or None, optional (default="weight")
60 The name of an edge attribute that holds the numerical value
61 used as a weight. If None then each edge has weight 1.
62 resolution : float, optional (default=1)
63 If resolution is less than 1, the algorithm favors larger communities.
64 Greater than 1 favors smaller communities.
65 max_level : int or None, optional (default=None)
66 The maximum number of levels (steps of the algorithm) to compute.
67 Must be a positive integer or None. If None, then there is no max
68 level and the algorithm will run until converged.
69 seed : integer, random_state, or None (default)
70 Indicator of random number generation state.
71 See :ref:`Randomness<randomness>`.
73 Returns
74 -------
75 list
76 A list of disjoint sets (partition of `G`). Each set represents one community.
77 All communities together contain all the nodes in `G`.
79 Examples
80 --------
81 >>> import networkx as nx
82 >>> G = nx.petersen_graph()
83 >>> nx.community.leiden_communities(G, backend="example_backend") # doctest: +SKIP
84 [{2, 3, 5, 7, 8}, {0, 1, 4, 6, 9}]
86 Notes
87 -----
88 The order in which the nodes are considered can affect the final output. In the algorithm
89 the ordering happens using a random shuffle.
91 References
92 ----------
93 .. [1] Traag, V.A., Waltman, L. & van Eck, N.J. From Louvain to Leiden: guaranteeing
94 well-connected communities. Sci Rep 9, 5233 (2019). https://doi.org/10.1038/s41598-019-41695-z
96 See Also
97 --------
98 leiden_partitions
99 :any:`louvain_communities`
100 """
101 partitions = leiden_partitions(G, weight, resolution, seed)
102 if max_level is not None:
103 if max_level <= 0:
104 raise ValueError("max_level argument must be a positive integer or None")
105 partitions = itertools.islice(partitions, max_level)
106 final_partition = deque(partitions, maxlen=1)
107 return final_partition.pop()
110@not_implemented_for("directed")
111@py_random_state("seed")
112@nx._dispatchable(edge_attrs="weight", implemented_by_nx=False)
113def leiden_partitions(G, weight="weight", resolution=1, seed=None):
114 """Yield partitions for each level of Leiden Community Detection (backend required)
116 Leiden Community Detection is an algorithm to extract the community
117 structure of a network based on modularity optimization.
119 The partitions across levels (steps of the algorithm) form a dendrogram
120 of communities. A dendrogram is a diagram representing a tree and each
121 level represents a partition of the G graph. The top level contains the
122 smallest communities and as you traverse to the bottom of the tree the
123 communities get bigger and the overall modularity increases making
124 the partition better.
126 Each level is generated by executing the three phases of the Leiden Community
127 Detection algorithm. See :any:`leiden_communities`.
129 Parameters
130 ----------
131 G : NetworkX graph
132 weight : string or None, optional (default="weight")
133 The name of an edge attribute that holds the numerical value
134 used as a weight. If None then each edge has weight 1.
135 resolution : float, optional (default=1)
136 If resolution is less than 1, the algorithm favors larger communities.
137 Greater than 1 favors smaller communities.
138 seed : integer, random_state, or None (default)
139 Indicator of random number generation state.
140 See :ref:`Randomness<randomness>`.
142 Yields
143 ------
144 list
145 A list of disjoint sets (partition of `G`). Each set represents one community.
146 All communities together contain all the nodes in `G`. The yielded partitions
147 increase modularity with each iteration.
149 References
150 ----------
151 .. [1] Traag, V.A., Waltman, L. & van Eck, N.J. From Louvain to Leiden: guaranteeing
152 well-connected communities. Sci Rep 9, 5233 (2019). https://doi.org/10.1038/s41598-019-41695-z
154 See Also
155 --------
156 leiden_communities
157 :any:`louvain_partitions`
158 """
159 raise NotImplementedError(
160 "'leiden_partitions' is not implemented by networkx. "
161 "Please try a different backend."
162 )