On the Analysis of a Label Propagation Algorithm for Community Detection

DOI10.1007/978-3-642-35668-1_18MaRDI QIDQ5507403zbMATHOpenAlexFDO

Authors Kishore Kothapalli, Vivek B. Sardeshmukh, Sriram Pemmaraju

Publication date 19 December 2016

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

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

Mathematics Subject Classification ID

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

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$.

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

Cited in

(15)

• Random graphs: combinatorics, complex networks and disordered systems. Abstracts from the workshop held March 26--31, 2023
• Step-by-step community detection in volume-regular graphs
• scientific article; zbMATH DE number 6746529 (Why is no real title available?)
• Practical minimum cut algorithms
• Distributed Community Detection in Dynamic Graphs
• Find Your Place: Simple Distributed Algorithms for Community Detection
• A label propagation-based method for community detection in directed signed social networks
• Find your place: simple distributed algorithms for community detection
• On the relationship between Gaussian stochastic blockmodels and label propagation algorithms
• Community detection in networks using new update rules for label propagation
• The Maximum Label Propagation Algorithm on Sparse Random Graphs
• scientific article; zbMATH DE number 7028498 (Why is no real title available?)
• Partitioning (hierarchically clustered) complex networks via size-constrained graph clustering
• Distributed community detection in dynamic graphs
• 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)