2015/10/09 by Ramezan Paravi Torghabeh, Torghabeh, Ramezan Paravi, Narayana Santhanam +2
Computer Science · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Computer and information sciences #Opinion Dynamics and Social Influence #Peer-to-Peer Network Technologies #Social and Information Networks (cs.SI) #cs.SI
paper · pdf · doi:10.48550/arxiv.1510.02583
arxiv created 2015/10/09 · openalex publication_date 2015/10/09 · arxiv updated 2015/10/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The task of community detection in a graph formalizes the intuitive task of grouping together subsets of vertices such that vertices within clusters are connected tighter than those in disparate clusters. This paper approaches community detection in graphs by constructing Markov random walks on the graphs. The mixing properties of the random walk are then used to identify communities. We use coupling from the past as an algorithmic primitive to translate the mixing properties of the walk into revealing the community structure of the graph. We analyze the performance of our algorithms on specific graph structures, including the stochastic block models (SBM) and LFR random graphs.