asyn_lpa_communities

asyn_lpa_communities(G, weight=None, seed=None)

Returns communities in G as detected by asynchronous label propagation.

The asynchronous label propagation algorithm is described in [1]. The algorithm is probabilistic and the found communities may vary on different executions.

The algorithm proceeds as follows. After initializing each node with a unique label, the algorithm repeatedly sets the label of a node to be the label that appears most frequently among that nodes neighbors. The algorithm halts when each node has the label that appears most frequently among its neighbors. The algorithm is asynchronous because each node is updated without waiting for updates on the remaining nodes.

This generalized version of the algorithm in [1] accepts edge weights.

Parameters

GGraph

weightstring

The edge attribute representing the weight of an edge. If None, each edge is assumed to have weight one. In this algorithm, the weight of an edge is used in determining the frequency with which a label appears among the neighbors of a node: a higher weight means the label appears more often.

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 weight attributes must be numerical.

References

1(1,2)

Raghavan, Usha Nandini, Réka Albert, and Soundar Kumara. “Near linear time algorithm to detect community structures in large-scale networks.” Physical Review E 76.3 (2007): 036106.