When Is Degree Enough? Bounds on Degree-Eigenvector Misalignment in Assortative Structured Networks
This work addresses the reliability of degree as a centrality measure in real-world networks, which is incremental as it builds on existing perturbation theory to provide specific bounds.
The paper tackles the problem of misalignment between degree and eigenvector centrality in networks with assortativity and local structures, deriving analytical bounds on the divergence and identifying 'spectral safety' regions where degree reliably indicates systemic importance.
A tight alignment between the degree vector and the leading eigenvector arises naturally in networks with neutral degree mixing and the absence of local structures. Many real-world networks, however, violate both conditions. We derive bounds on the divergence between the degree vector and the eigenvector in networks with degree assortativity and local mesoscopic structures such as communities, core-peripheries, and cycles. Our approach is constructive. We design sufficiently general degree-preserving rewiring algorithms that start from a neutral benchmark and monotonically increase assortativity and the strength of local structures, with each step inducing a perturbation of the adjacency matrix. Using the Stewart--Sun Perturbation Bound, together with explicit spectral-norm control of the rewiring steps, we derive upper bounds on the angle between the eigenvector and the degree vector for modest levels of assortativity and local structures. Our analytical bounds delineate regions of `spectral safety' in which a node's degree can be used as a reliable measure of its systemic importance in real-world networks. We also substantiate our analytical bounds with numerical simulations that compute the exact angles of deviation.