Correlation between weighted spectral distribution and average path length in evolving networks

Chaos. 2016 Feb;26(2):023110. doi: 10.1063/1.4941727.

Abstract

The weighted spectral distribution (WSD) is a metric defined on the normalized Laplacian spectrum. In this study, synchronic random graphs are first used to rigorously analyze the metric's scaling feature, which indicates that the metric grows sublinearly as the network size increases, and the metric's scaling feature is demonstrated to be common in networks with Gaussian, exponential, and power-law degree distributions. Furthermore, a deterministic model of diachronic graphs is developed to illustrate the correlation between the slope coefficient of the metric's asymptotic line and the average path length, and the similarities and differences between synchronic and diachronic random graphs are investigated to better understand the correlation. Finally, numerical analysis is presented based on simulated and real-world data of evolving networks, which shows that the ratio of the WSD to the network size is a good indicator of the average path length.