On the Analysis of a Label Propagation Algorithm for Community Detection

DOI10.1007/978-3-642-35668-1_18zbMATH Open1351.68303arXiv1210.3735OpenAlexW1831343635MaRDI QIDQ5507403FDOQ5507403

Authors: Kishore Kothapalli, Vivek B. Sardeshmukh, Sriram Pemmaraju 

Publication date: 19 December 2016

Published in: Distributed Computing and Networking (Search for Journal in Brave)

Abstract: This paper initiates formal analysis of a simple, distributed algorithm for community detection on networks. We analyze an algorithm that we call extsc{Max-LPA}, both in terms of its convergence time and in terms of the "quality" of the communities detected. extsc{Max-LPA} is an instance of a class of community detection algorithms called extit{label propagation} algorithms. As far as we know, most analysis of label propagation algorithms thus far has been empirical in nature and in this paper we seek a theoretical understanding of label propagation algorithms. In our main result, we define a clustered version of er random graphs with clusters $V_1,V_2,\mathrm{...},V_k$ where the probability $p$, of an edge connecting nodes within a cluster $V_i$ is higher than $p^{\prime }$, the probability of an edge connecting nodes in distinct clusters. We show that even with fairly general restrictions on $p$ and $p^{\prime }$ ($p=Omega(frac1n^{1/4-epsilon})$ for any $epsilon>0$, $p^{\prime }=O(p^2)$, where $n$ is the number of nodes), extsc{Max-LPA} detects the clusters $V_1,V_2,\mathrm{...},V_n$ in just two rounds. Based on this and on empirical results, we conjecture that extsc{Max-LPA} can correctly and quickly identify communities on clustered er graphs even when the clusters are much sparser, i.e., with $p=fracclognn$ for some $c>1$.

Full work available at URL: https://arxiv.org/abs/1210.3735

Recommendations

• Community detection with the label propagation algorithm: a survey
• scientific article; zbMATH DE number 7028498
• Community detection in networks using new update rules for label propagation
• Finding overlapping communities in networks by label propagation

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Social networks; opinion dynamics (91D30) Distributed algorithms (68W15)

Cited In (15)

• Practical minimum cut algorithms
• Distributed Community Detection in Dynamic Graphs
• Step-by-step community detection in volume-regular graphs
• Title not available (Why is that?)
• A label propagation-based method for community detection in directed signed social networks
• Title not available (Why is that?)
• Random graphs: combinatorics, complex networks and disordered systems. Abstracts from the workshop held March 26--31, 2023
• Distributed community detection in dynamic graphs
• Find Your Place: Simple Distributed Algorithms for Community Detection
• Partitioning (hierarchically clustered) complex networks via size-constrained graph clustering
• The Maximum Label Propagation Algorithm on Sparse Random Graphs
• On the relationship between Gaussian stochastic blockmodels and label propagation algorithms
• Community detection in networks using new update rules for label propagation
• Find your place: simple distributed algorithms for community detection
• Direction-optimizing Label Propagation Framework for Structure Detection in Graphs: Design, Implementation, and Experimental Analysis

This page was built for publication: On the Analysis of a Label Propagation Algorithm for Community Detection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5507403)