cdlib.algorithms.label_propagation_raghavan

cdlib.algorithms.label_propagation_raghavan(g_original: object, weights: str | None = None) → NodeClustering

The Label Propagation algorithm (LPA) detects communities using network structure alone. The algorithm doesn’t require a pre-defined objective function or prior information about the communities. It works as follows: -Every node is initialized with a unique label (an identifier) -These labels propagate through the network -At every iteration of propagation, each node updates its label to the one that the maximum numbers of its neighbours belongs to. Ties are broken uniformly and randomly. -LPA reaches convergence when each node has the majority label of its neighbours.

Supported Graph Types

Undirected	Directed	Weighted
Yes	No	No

Parameters:

g_original – a networkx/igraph object

Returns:

EdgeClustering object

Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> coms = algorithms.label_propagation_raghavan(G)

References:

Raghavan, U.N. and Albert, R. and Kumara, S. Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76:036106, 2007. http://arxiv.org/abs/0709.2938.

Parameters

weights