Abstract
Detecting significant community structure in networks with incomplete observations is challenging because the evidence for specific solutions fades away with missing data. For example, recent research shows that flow-based community detection methods can highlight spurious communities in sparse undirected and unweighted networks with missing links. Current Bayesian approaches developed to overcome this problem do not work for incomplete observations in weighted and directed networks that describe network flows. To address this gap, we extend the idea behind the Bayesian estimate of the map equation for unweighted and undirected networks to enable more robust community detection in weighted and directed networks. We derive a weighted and directed prior network that can incorporate metadata information and show how an efficient implementation in the community-detection method Infomap provides more reliable communities even with a significant fraction of data missing.
Introduction
In network science, identifying "communities"—clusters of nodes with dense internal interactions—is fundamental to understanding system structure. A prominent approach is the map equation, which leverages information theory to find partitions that optimally compress the description of a random walker's path. However, the map equation is highly sensitive to data sparsity. In incomplete networks, it often overfits, interpreting accidental gaps as structural boundaries and "hallucinating" numerous tiny, spurious communities. While Bayesian regularization has been applied to simple undirected networks, real-world systems like transportation or citation networks involve complex, directed, and weighted flows that require a more sophisticated solution.
Methods: Empirical Bayes Regularization
The authors propose an empirical Bayes framework to regularize transition rates in weighted and directed networks. This approach moves beyond treating observed links as absolute truth by introducing a Dirichlet prior over transition probabilities.
Key components of the method include:
- Smart Teleportation: Standard models use uniform teleportation to ensure ergodicity. The Bayesian approach effectively implements node-dependent teleportation. For nodes with many observations, the walker follows the data; for sparse nodes, the walker relies on a "prior" network.
- Continuous Configuration Model: The prior is constructed using a model that estimates expected network structure based on observed node strengths and degrees.
- Metadata Integration: The framework can incorporate external node labels (e.g., department or species). As network data becomes sparser, the algorithm automatically shifts its reliance toward this metadata to maintain structural coherence.
Key Results
The method was evaluated on synthetic LFR benchmarks and diverse real-world datasets, including citation networks (CoRA, cit-HepTh), airport connectivity (Openflights), and social interactions.
The results demonstrate a significant improvement in stability:
- Robustness to Sparsity: In synthetic tests, the standard map equation began detecting hundreds of fake communities after 50% data removal. In contrast, the regularized version maintained the ground-truth community count (31) until nearly 80% of the data was missing.
- Accuracy: Adjusted Mutual Information (AMI) remained high for the regularized method even under extreme sparsity, while the standard method's accuracy plummeted.
- Real-World Reliability: On the cit-HepTh citation network, the standard method failed after losing just 5% of observations. The regularized version remained stable, proving its practical utility for noisy empirical data.
Discussion and Future Work
The regularized map equation fundamentally changes the algorithm's behavior from "finding too much" to "knowing when to stop." By using cross-validation to measure codelength savings, the authors show that their partitions better describe the underlying structure of unseen network components.
However, limitations remain. If metadata is poorly aligned with actual network flows, regularization can lead to underfitting. Future work could explore more specialized priors for biological or spatial networks and investigate the computational scaling limits for massive graphs with billions of edges.
Summary updated