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 Example:
>>> 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.