label_propagation(g_original: object) → cdlib.classes.node_clustering.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
>>> from cdlib import algorithms
>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> coms = algorithms.label_propagation(G)

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.