Discrimination universally determines reconstruction of multiplex networks

Abstract

Network reconstruction is fundamental to understanding the dynamical behaviors of the networked systems. Many systems, modeled by multiplex networks with various types of interactions, display an entirely different dynamical behavior compared to the corresponding aggregated network. In many cases, unfortunately, only the aggregated topology and partial observations of the network layers are available, raising an urgent demand for reconstructing multiplex networks. We fill this gap by developing a mathematical and computational tool based on the Expectation-Maximization framework to reconstruct multiplex layer structures. The reconstruction accuracy depends on the various factors, such as partial observation and network characteristics, limiting our ability to predict and allocate observations. Surprisingly, by using a mean-field approximation, we discovered that a discrimination indicator that integrates all these factors universally determines the accuracy of reconstruction. This discovery enables us to design the optimal strategies to allocate the fixed budget for deriving the partial observations, promoting the optimal reconstruction of multiplex networks. To further evaluate the performance of our method, we predict beside structure also dynamical behaviors on the multiplex networks, including percolation, random walk, and spreading processes. Finally, applying our method on empirical multiplex networks drawn from biological, transportation, and social domains, corroborate the theoretical analysis.

References in corpus (21)

• The structure and function of complex networks
• Catastrophic cascade of failures in interdependent networks
• Epidemic processes in complex networks
• The spread of epidemic disease on networks
• Link Prediction in Complex Networks: A Survey
• Missing and spurious interactions and the reconstruction of complex networks
• Robustness of a Network of Networks
• Layer aggregation and reducibility of multilayer interconnected networks
• Random Walks on Multiplex Networks
• Emergence of network features from multiplexity
• The ground truth about metadata and community detection in networks
• Centrality in Interconnected Multilayer Networks
• Structure and inference in annotated networks
• Parsimonious module inference in large networks
• Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes
• Community detection, link prediction, and layer interdependence in multilayer networks
• Dynamic interdependence and competition in multilayer networks
• Activity clocks: spreading dynamics on temporal networks of human contact
• Dynamic vaccination in partially overlapped multiplex network
• Multiplex decomposition of non-Markovian dynamics and the hidden layer reconstruction problem
• Inferring propagation paths for sparsely observed perturbations on complex networks