A sampling-guided unsupervised learning method to capture percolation in complex networks

Abstract

The use of machine learning techniques in classical and quantum systems has led to novel techniques to classify ordered and disordered phases, as well as uncover transition points in critical phenomena. Efforts to extend these methods to dynamical processes in complex networks is a field of active research. Network-percolation, a measure of resilience and robustness to structural failures, as well as a proxy for spreading processes, has numerous applications in social, technological, and infrastructural systems. A particular challenge is to identify the existence of a percolation cluster in a network in the face of noisy data. Here, we consider bond-percolation, and introduce a sampling approach that leverages the core-periphery structure of such networks at a microscopic scale, using onion decomposition, a refined version of the $k-$core. By selecting subsets of nodes in a particular layer of the onion spectrum that follow similar trajectories in the percolation process, percolating phases can be distinguished from non-percolating ones through an unsupervised clustering method. Accuracy in the initial step is essential for extracting samples with information-rich content, that are subsequently used to predict the critical transition point through the confusion scheme, a recently introduced learning method. The method circumvents the difficulty of missing data or noisy measurements, as it allows for sampling nodes from both the core and periphery, as well as intermediate layers. We validate the effectiveness of our sampling strategy on a spectrum of synthetic network topologies, as well as on two real-word case studies: the integration time of the US domestic airport network, and the identification of the epidemic cluster of COVID-19 outbreaks in three major US states. The method proposed here allows for identifying phase transitions in empirical time-varying networks.

arXiv comment16 pages, 6 figures

References in corpus (43)

• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• The science of fake news
• Random graphs with arbitrary degree distributions and their applications
• The spread of epidemic disease on networks
• Solving the Quantum Many-Body Problem with Artificial Neural Networks
• Structure and tie strengths in mobile communication networks
• Machine learning phases of matter
• Vital nodes identification in complex networks
• A high-bias, low-variance introduction to Machine Learning for physicists
• Learning phase transitions by confusion
• Discovering Phase Transitions with Unsupervised Learning
• Clique percolation in random networks
• Efficient Monte Carlo algorithm and high-precision results for percolation
• Unsupervised learning of phase transitions: from principal component analysis to variational autoencoders
• Machine learning quantum phases of matter beyond the fermion sign problem
• Percolation on sparse networks
• Random hypergraphs and their applications
• Machine Learning Phases of Strongly Correlated Fermions
• Mutual Information, Neural Networks and the Renormalization Group
• From the betweenness centrality in street networks to structural invariants in random planar graphs
• Machine learning vortices at the Kosterlitz-Thouless transition
• Unsupervised machine learning account of magnetic transitions in the Hubbard model
• Machine learning out-of-equilibrium phases of matter
• Machine learning for many-body physics: The case of the Anderson impurity model
• Identifying Quantum Phase Transitions with Adversarial Neural Networks
• Predicting percolation thresholds in networks
• Machine learning of phase transitions in the percolation and XY models
• Topological quantum phase transitions retrieved through unsupervised machine learning
• Hypergraph topological quantities for tagged social networks
• Unveiling phase transitions with machine learning
• Turing patterns mediated by network topology in homogeneous active systems
• Bicomponents and the robustness of networks to failure
• Deep Learning the Ising Model Near Criticality
• Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition
• Unsupervised machine learning of quantum phase transitions using diffusion maps
• Machine learning dynamical phase transitions in complex networks
• Efficient network immunization under limited knowledge
• Robustness of Network Measures to Link Errors
• Immunization Strategies in Networks with Missing Data
• Estimating the sensitivity of centrality measures w.r.t. measurement errors
• Learning epidemic threshold in complex networks by Convolutional Neural Network
• Renormalization group theory for percolation in time-varying networks
• Linguistic evolution driven by network heterogeneity and the Turing mechanism