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.

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 to w unweighted edges).

seedinteger, random_state, or None (default)

Indicator of random number generation state. See Randomness.


Iterable of communities given as sets of nodes.


Edge directions are ignored for directed graphs. Edge weights must be non-negative numbers.



Vincent A. Traag & Lovro Šubelj. “Large network community detection by fast label propagation.” Scientific Reports 13 (2023): 2701.