Mapping flows on weighted and directed networks with incomplete observations

Jelena Smiljanic, Christopher Blöcker, Daniel Edler, Martin Rosvall

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.

Comparison of standard teleportation and regularized network flows on complete and incomplete networks.

Key components of the method include:

  1. 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.
  2. Continuous Configuration Model: The prior is constructed using a model that estimates expected network structure based on observed node strengths and degrees.
  3. 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.

Stability of community detection under data removal for standard vs. regularized methods.

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

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.
BibTeX
@article{smiljanic2021mapping,
  author = {Jelena Smiljanic and Christopher Blöcker and Daniel Edler and Martin Rosvall},
  title = {{Mapping flows on weighted and directed networks with incomplete observations}},
  journal = {J. Complex Networks},
  year = {2021},
  doi = {10.1093/comnet/cnab044},
}
Figure