The Maximum Label Propagation Algorithm on Sparse Random Graphs

DOI10.4230/LIPIcs.APPROX-RANDOM.2019.58OpenAlexW2978173423MaRDI QIDQ5875518

Johannes Lengler, Pascal Pfister, Charlotte Knierim, Ulysse Schaller, Angelika Steger

Publication date: 3 February 2023

Full work available at URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.58

zbMATH Keywords

random graphsdistributed algorithmsconsensuscommunity detectionlabel propagation algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (1)

Random graphs: combinatorics, complex networks and disordered systems. Abstracts from the workshop held March 26--31, 2023

Cites Work

• Unnamed Item
• Fast consensus for voting on general expander graphs
• Contagious sets in random graphs
• On periodical behaviour in societies with symmetric influences
• Distributed community detection in dynamic graphs
• Opinion exchange dynamics
• Simple dynamics for plurality consensus
• Stabilizing Consensus with Many Opinions
• Finding overlapping communities in networks by label propagation
• Nearly-Tight Analysis for 2-Choice and 3-Majority Consensus Dynamics
• A Polylogarithmic Gossip Algorithm for Plurality Consensus
• Ignore or Comply?
• On the Analysis of a Label Propagation Algorithm for Community Detection

This page was built for publication: The Maximum Label Propagation Algorithm on Sparse Random Graphs