Network-ensemble comparisons with stochastic rewiring and von Neumann entropy
arXiv:1704.01053
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.
arXiv comment24 pages, 6 figures
References in corpus (30)
- Emergence of scaling in random networks
- Finding and evaluating community structure in networks
- Epidemic spreading in scale-free networks
- Finding community structure in networks using the eigenvectors of matrices
- Resilience of the Internet to random breakdowns
- Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
- Community detection in complex networks using Extremal Optimization
- Self-similar community structure in organisations
- Reaction-diffusion processes and metapopulation models in heterogeneous networks
- Layer aggregation and reducibility of multilayer interconnected networks
- Entropy measures for complex networks: Toward an information theory of complex topologies
- The onset of synchronization in large networks of coupled oscillators
- On the uniform generation of random graphs with prescribed degree sequences
- Predicting criticality and dynamic range in complex networks: effects of topology
- Spectral entropies as information-theoretic tools for complex network comparison
- Optimal synchronization of complex networks
- Accuracy of Mean-Field Theory for Dynamics on Real-World Networks
- The Shannon and the Von Neumann entropy of random networks with heterogeneous expected degree
- The unreasonable effectiveness of tree-based theory for networks with clustering
- DELTACON: A Principled Massive-Graph Similarity Function
- Predicting percolation thresholds in networks
- Enhanced detectability of community structure in multilayer networks through layer aggregation
- Eigenvalue Spectra of Modular 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
- Tweaking Synchronisation by Link Addition
- Revealing effective classifiers through network comparison
- A network-specific approach to percolation in networks with bidirectional links
- Model Selection Framework for Graph-based data