Single-trajectory map equation
arXiv:2203.04044 · doi:10.1038/s41598-023-33880-y
Abstract
Community detection, the process of identifying module structures in complex systems represented on networks, is an effective tool in various fields of science. The map equation, which is an information-theoretic framework based on the random walk on a network, is a particularly popular community detection method. Despite its outstanding performance in many applications, the inner workings of the map equation have not been thoroughly studied. Herein, we revisit the original formulation of the map equation and address the existence of its ``raw form,'' which we refer to as the single-trajectory map equation. This raw form sheds light on many details behind the principle of the map equation that are hidden in the steady-state limit of the random walk. Most importantly, the single-trajectory map equation provides a more balanced community structure, naturally reducing the tendency of the overfitting phenomenon in the map equation.
arXiv comment20 pages, 14 figures
References in corpus (31)
- Fast unfolding of communities in large networks
- Community detection in graphs
- Finding community structure in very large networks
- From Louvain to Leiden: guaranteeing well-connected communities
- Maps of random walks on complex networks reveal community structure
- Resolution limit in community detection
- Hierarchical structure and the prediction of missing links in networks
- Community detection in networks: A user guide
- Mapping change in large networks
- Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
- Memory in network flows and its effects on spreading dynamics and community detection
- Phase transition in the detection of modules in sparse networks
- Nonparametric Bayesian inference of the microcanonical stochastic block model
- Community analysis in social networks
- Evaluating Overfit and Underfit in Models of Network Community Structure
- Mapping higher-order network flows in memory and multilayer networks with Infomap
- Ranking and clustering of nodes in networks with smart teleportation
- Encoding dynamics for multiscale community detection: Markov time sweeping for the Map equation
- Estimating the resolution limit of the map equation in community detection
- Efficient community detection of network flows for varying Markov times and bipartite networks
- Mapping flows on hypergraphs
- A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning
- Constrained information flows in temporal networks reveal intermittent communities
- Cross-validation estimate of the number of clusters in a network
- A Map Equation with Metadata: Varying the Role of Attributes in Community Detection
- Mapping flows on sparse networks with missing links
- Mapping flows on weighted and directed networks with incomplete observations
- Community Structures, Interactions and Dynamics in London's Bicycle Sharing Network
- Comparative analysis on the selection of number of clusters in community detection
- Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
- Mapping Flows on Bipartite Networks