Network-ensemble comparisons with stochastic rewiring and von Neumann entropy

Abstract

Assessing whether a given network is typical or atypical for a random-network ensemble (i.e., network-ensemble comparison) has widespread applications ranging from null-model selection and hypothesis testing to clustering and classifying networks. We develop a framework for network-ensemble comparison by subjecting the network to stochastic rewiring. We study two rewiring processes, uniform and degree-preserved rewiring, which yield random-network ensembles that converge to the Erdos-Renyi and configuration-model ensembles, respectively. We study convergence through von Neumann entropy (VNE), a network summary statistic measuring information content based on the spectra of a Laplacian matrix, and develop a perturbation analysis for the expected effect of rewiring on VNE. Our analysis yields an estimate for how many rewires are required for a given network to resemble a typical network from an ensemble, offering a computationally efficient quantity for network-ensemble comparison that does not require simulation of the corresponding rewiring process.

24 pages, 6 figures

References in corpus (11)

• Finding community structure in networks using the eigenvectors of matrices
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• Layer aggregation and reducibility of multilayer interconnected networks
• On the uniform generation of random graphs with prescribed degree sequences
• Spectral entropies as information-theoretic tools for complex network comparison
• DELTACON: A Principled Massive-Graph Similarity Function
• Predicting percolation thresholds in networks
• Synchronization of heterogeneous oscillators under network modifications: Perturbation and optimization of the synchrony alignment function
• Super-resolution community detection for layer-aggregated multilayer networks
• The switch Markov chain for sampling irregular graphs
• Model Selection Framework for Graph-based data