cdlib.algorithms.label_propagation

cdlib.algorithms.label_propagation(g_original: object) → 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(G)

References:

Cordasco, G., & Gargano, L. (2010, December). Community detection via semi-synchronous label propagation algorithms. In 2010 IEEE international workshop on: business applications of social network analysis (BASNA) (pp. 1-8). IEEE.