# Synwalk -- Community Detection via Random Walk Modelling

arXiv: https://arxiv.org/abs/2101.08623 · HTML: https://mlsanity.com/paper/2101.08623/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 53 references that are in the map.
- First posted on arXiv 21 Jan 2021.

## Builds on (most cited first, 13 of 13)

- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models](https://mlsanity.com/paper/2005.07959/) (2020)
- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [The ground truth about metadata and community detection in networks](https://mlsanity.com/paper/1608.05878/) (2016)
- [Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models](https://mlsanity.com/paper/1310.4378/) (2013)
- [Random walks and diffusion on networks](https://mlsanity.com/paper/1612.03281/) (2016)
- [Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks](https://mlsanity.com/paper/1502.04381/) (2015)
- [A Comparative Analysis of Community Detection Algorithms on Artificial Networks](https://mlsanity.com/paper/1608.00763/) (2016)
- [Spectral State Compression of Markov Processes](https://mlsanity.com/paper/1802.02920/) (2018)
- [Modeling sequences and temporal networks with dynamic community structures](https://mlsanity.com/paper/1509.04740/) (2015)
- [Different approaches to community detection](https://mlsanity.com/paper/1712.06468/) (2017)
- [A Generalized Framework for Kullback-Leibler Markov Aggregation](https://mlsanity.com/paper/1709.05907/) (2017)
- [Identifying Sparse Low-Dimensional Structures in Markov Chains: A Nonnegative Matrix Factorization Approach](https://mlsanity.com/paper/1909.12898/) (2019)

## Abstract (arXiv)

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.