NETWORK-ENSEMBLE COMPARISONS WITH STOCHASTIC REWIRING AND VON NEUMANN ENTROPY

作者：Li Zichao^*; Mucha Peter J; Taylor Dane

来源：SIAM Journal on Applied Mathematics, 2018, 78(2): 897-920.

DOI：10.1137/17M1124218

• network science
• von Neumann entropy
• network-ensemble comparison
• network rewiring
• null models
• mean field theory

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.

• 出版日期2018