Synwalk -- Community Detection via Random Walk Modelling

Abstract

Complex systems, abstractly represented as networks, are ubiquitous in everyday life. Analyzing and understanding these systems requires, among others, tools for community detection. As no single best community detection algorithm can exist, robustness across a wide variety of problem settings is desirable. In this work, we present Synwalk, a random walk-based community detection method. Synwalk builds upon a solid theoretical basis and detects communities by synthesizing the random walk induced by the given network from a class of candidate random walks. We thoroughly validate the effectiveness of our approach on synthetic and empirical networks, respectively, and compare Synwalk's performance with the performance of Infomap and Walktrap. Our results indicate that Synwalk performs robustly on networks with varying mixing parameters and degree distributions. We outperform Infomap on networks with high mixing parameter, and Infomap and Walktrap on networks with many small communities and low average degree. Our work has a potential to inspire further development of community detection via synthesis of random walks and we provide concrete ideas for future research.

arXiv comment31 pages, 13 figures

References in corpus (27)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Maps of random walks on complex networks reveal community structure
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Defining and identifying communities in networks
• Community detection algorithms: a comparative analysis
• Statistical Mechanics of Community Detection
• Community detection in networks: A user guide
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• The map equation
• Random walks and diffusion on networks
• Mapping change in large networks
• A Comparative Analysis of Community Detection Algorithms on Artificial Networks
• The ground truth about metadata and community detection in networks
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Laplacian Dynamics and Multiscale Modular Structure in Networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Finding and testing network communities by lumped Markov chains
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• Different approaches to community detection
• A Generalized Framework for Kullback-Leibler Markov Aggregation
• State aggregations in Markov chains and block models of networks