Mapping flows on sparse networks with missing links

Abstract

Unreliable network data can cause community-detection methods to overfit and highlight spurious structures with misleading information about the organization and function of complex systems. Here we show how to detect significant flow-based communities in sparse networks with missing links using the map equation. Since the map equation builds on Shannon entropy estimation, it assumes complete data such that analyzing undersampled networks can lead to overfitting. To overcome this problem, we incorporate a Bayesian approach with assumptions about network uncertainties into the map equation framework. Results in both synthetic and real-world networks show that the Bayesian estimate of the map equation provides a principled approach to revealing significant structures in undersampled networks.

References in corpus (26)

• Finding and evaluating community structure in networks
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Link Prediction in Complex Networks: A Survey
• Community detection algorithms: a comparative analysis
• Community Structure in Jazz
• Scale-free topology of e-mail networks
• Missing and spurious interactions and the reconstruction of complex networks
• Mapping change in large networks
• The ground truth about metadata and community detection in networks
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Laplacian Dynamics and Multiscale Modular Structure in Networks
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Network structure from rich but noisy data
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
• Bias Analysis in Entropy Estimation
• Mapping higher-order network flows in memory and multilayer networks with Infomap
• Reconstruction methods for networks: the case of economic and financial systems
• Estimating network structure from unreliable measurements
• Reconstructing networks with unknown and heterogeneous errors
• Consistencies and inconsistencies between model selection and link prediction in networks
• Structural inference for uncertain networks

Cited by in corpus (7)

• Mapping flows on weighted and directed networks with incomplete observations
• Robustness modularity in complex networks
• Cross-validation of correlation networks using modular structure
• Community Detection with the Map Equation and Infomap: Theory and Applications
• Flow-based Community Detection in Hypergraphs
• Single-trajectory map equation
• Emergence of network communities driven by local rules