fast_label_propagation_communities#
- fast_label_propagation_communities(G, *, weight=None, seed=None)[source]#
Returns communities in
G
as detected by fast label propagation.The fast label propagation algorithm is described in [1]. The algorithm is probabilistic and the found communities may vary in different executions.
The algorithm operates as follows. First, the community label of each node is set to a unique label. The algorithm then repeatedly updates the labels of the nodes to the most frequent label in their neighborhood. In case of ties, a random label is chosen from the most frequent labels.
The algorithm maintains a queue of nodes that still need to be processed. Initially, all nodes are added to the queue in a random order. Then the nodes are removed from the queue one by one and processed. If a node updates its label, all its neighbors that have a different label are added to the queue (if not already in the queue). The algorithm stops when the queue is empty.
- Parameters:
- GGraph, DiGraph, MultiGraph, or MultiDiGraph
Any NetworkX graph.
- weightstring, or None (default)
The edge attribute representing a non-negative weight of an edge. If None, each edge is assumed to have weight one. The weight of an edge is used in determining the frequency with which a label appears among the neighbors of a node (edge with weight
w
is equivalent tow
unweighted edges).- seedinteger, random_state, or None (default)
Indicator of random number generation state. See Randomness.
- Returns:
- communitiesiterable
Iterable of communities given as sets of nodes.
Notes
Edge directions are ignored for directed graphs. Edge weights must be non-negative numbers.
References
[1]Vincent A. Traag & Lovro Šubelj. “Large network community detection by fast label propagation.” Scientific Reports 13 (2023): 2701. https://doi.org/10.1038/s41598-023-29610-z