Skip to main content
`Ctrl`+`K`

# fast_label_propagation_communities

fast_label_propagation_communities(G, *, weight=None, seed=None)

  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:
    G Graph, DiGraph, MultiGraph, or MultiDiGraph

      Any NetworkX graph.

    weight string, 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).

    seed integer, random_state, or None (default)

      Indicator of random number generation state. See Randomness.

  Returns:
    communities iterable

      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