Scale-Free Networks beyond Power-Law Degree Distribution

Complex networks across various fields are often considered to be scale free---a statistical property usually solely characterized by a power-law distribution of the nodes' degree k. However, this characterization is incomplete. In real-world networks, the distribution of the degree--degree distance η, a simple link-based metric of network connectivity similar to k, appears to exhibit a stronger power-law distribution than k. While offering an alternative characterization of scale-freeness, the discovery of η raises a fundamental question: do the power laws of k and η represent the same scale-freeness? To address this question, here we investigate the exact asymptotic relationship between the distributions of k and η, proving that every network with a power-law distribution of k also has a power-law distribution of η, but not vice versa. This prompts us to introduce two network models as counterexamples that have a power-law distribution of η but not k, constructed using the preferential attachment and fitness mechanisms, respectively. Both models show promising accuracy by fitting only one model parameter each when modeling real-world networks. Our findings suggest that η is a more suitable indicator of scale-freeness and can provide a deeper understanding of the universality and underlying mechanisms of scale-free networks.