Quantifying nonrandomness in evolving networks

Abstract

Complex systems have been successfully modeled as networks exhibiting the varying extent of randomness and nonrandomness. Network scientists contemplate randomness as one of the most desirable characteristics for real complex systems efficient performance. However, the current methodologies for randomness (or nonrandomness) quantification are nontrivial. In this article, we empirically showcase severe limitations associated with the state-of-the-art graph spectral-based quantification approaches. Addressing these limitations led to the proposal of a novel spectrum-based methodology that leverages configuration models as a reference network to quantify the nonrandomness in a given candidate network. Besides, we derive mathematical formulations for demonstrating the dependence of nonrandomness on three structural properties: modularity, clustering, and the highest degree nodes growth rate. We also introduce a novel graph signature (termed "cumulative spectral difference") to visualize the nonrandomness in the network. Later, this article also discusses the relationship between the proposed nonrandomness measure and the diffusion affinity of networks. Toward the end, this article extensively discusses observations emerging from these signatures for both real-world and simulated networks.