Source-linked AI summary
Localization and centrality in networks
Travis Martin, Xiao Zhang, M. E. J. Newman
TL;DR
The paper examines why eigenvector centrality can fail when its weight localizes on a few nodes, impairing distinctions among the rest. It proposes nonbacktracking centrality and finds that it preserves standard results in dense networks while avoiding localization where standard centrality fails.
Problem
Eigenvector centrality can undergo localization under common network conditions, concentrating most weight on a few nodes and impairing its usefulness for distinguishing others.
Method
The paper proposes a centrality measure based on the leading eigenvector of the Hashimoto, or nonbacktracking, matrix.
Results
The nonbacktracking measure is closely similar to standard eigenvector centrality in dense networks and avoids localization where the standard measure fails.
Takeaways & Limitations
Nonbacktracking centrality provides useful results in regimes where localization makes standard eigenvector centrality ineffective.
Abstract
from arXiv · showhide
Eigenvector centrality is a common measure of the importance of nodes in a network. Here we show that under common conditions the eigenvector centrality displays a localization transition that causes most of the weight of the centrality to concentrate on a small number of nodes in the network. In this regime the measure is no longer useful for distinguishing among the remaining nodes and its efficacy as a network metric is impaired. As a remedy, we propose an alternative centrality measure based on the nonbacktracking matrix, which gives results closely similar to the standard eigenvector centrality in dense networks where the latter is well behaved, but avoids localization and gives useful results in regimes where the standard centrality fails.
I. INTRODUCTION
Centrality measures quantify node importance, with eigenvector centrality assigning scores through neighbors’ scores. The paper argues that this widely used measure can localize, motivating a nonbacktracking alternative.
- Centrality measures quantify how important or influential a node is within a network.
- Eigenvector centrality assigns each node a score proportional to the scores of its network neighbors.The scores form the leading eigenvector of the network’s adjacency matrix under nonnegative centralities.
- The leading adjacency-matrix eigenvector can undergo a localization transition in which most of its weight concentrates on one or a few nodes.
- Localization diminishes eigenvector centrality’s effectiveness for quantifying node importance and can occur in networks with power-law degree distributions.
- The proposed nonbacktracking centrality remains close to standard eigenvector centrality in dense networks while avoiding localization where the standard measure fails.It is based on the leading eigenvector of the Hashimoto, or nonbacktracking, matrix.
II. LOCALIZATION OF EIGENVECTOR CENTRALITY
The paper formally demonstrates a localization transition in eigenvector centrality caused by high-degree hubs. Above a critical hub degree, centrality concentrates on the hub and its neighbors, leaving average non-hub nodes with vanishing weight.
- Numerical studies had previously found localization, and this paper formally establishes the transition using random matrix theory.The analysis calculates properties of the transition in a network model containing a random graph and a hub.
- In the random-graph model without the hub, eigenvector centrality is well behaved, with all vertex centralities O(1/√n) and modest fluctuations.The leading eigenvector is approximately uniform when the mean degree satisfies c ≫1.
- The full adjacency matrix is analyzed by separating the random-graph matrix X from the hub’s connection vector and solving the resulting eigenvalue equations.The eigenvalues of the full matrix interlace those of X, and the leading eigenvalue approaches c + 1 in the large-network limit.
- The eigenvalue solutions arise where the resolvent-based left-hand side crosses the diagonal right-hand side, with poles at the eigenvalues of X.The resulting eigenvalues satisfy an interlacing condition with the eigenvalues χ_i of X.
- The hub eigenvalue becomes leading when d > c(c + 1), approximately when the hub degree is the square of the mean degree.Below this threshold, the random graph’s leading eigenvector remains dominant; above it, the hub-generated eigenvector becomes leading.
- Above the transition, a non-vanishing fraction of centrality lies on the hub and its neighbors, while the average vertex receives only O(1/n).Below the transition, the average vertex receives O(1/√n); thus eigenvector centrality fails to distinguish relative importance among non-hub nodes in the localized regime.
A. Numerical results
Numerical tests in one-million-node model networks show that eigenvector centrality changes sharply as hub degree crosses the localization transition, while the inverse participation ratio tracks this transition.
- Model-network comparison: For c = 10 and n = 1 000 000, the model compares centralities of the hub, its neighbors, and all other nodes across hub degrees d = 70 and d = 120.The lower hub degree is below localization, whereas the higher degree is in the localized regime.
- Localization measure: S = O(1/n) when all eigenvector components are O(1/√n), but S = O(1) when one or more components are O(1).Thus S acts as an order parameter for localization in the large-n limit.
- Model-network comparison: Figure 2 uses a common scale for bar charts of centralities across three node categories in four model-network examples.Error bars are small enough to be invisible on the plotted scale.
B. Power-law networks
Power-law networks can contain hubs that trigger eigenvector-centrality localization, especially as network size grows, providing a realistic setting in which the measure can fail.
- Realistic network regimes: In realistic networks, localization is expected with high-degree hubs or low average degree, conditions common in many real-world networks.The paper specifically considers networks with power-law degree distributions and configuration-model realizations.
- Numerical comparison: Figure 3 evaluates S against hub degree d for n = 1 000 000 and average degree c ranging from 4 to 11, comparing eigenvector and nonbacktracking centralities.Solid curves denote eigenvector centrality, horizontal dashed curves denote nonbacktracking centrality, and vertical dashed lines mark predicted transitions.
- Power-law mechanism: For configuration-model networks, the bulk leading eigenvalue approaches ⟨k^2⟩/⟨k⟩, while a hub-generated eigenvalue is bounded below by its degree d.The hub eigenvector becomes leading whenever d > ⟨k^2⟩/⟨k⟩, possibly sooner but not later.
- Power-law mechanism: For power-law exponent α < 3, d grows with n while ⟨k^2⟩∼d^(3−α) and ⟨k⟩ remains constant.The paper uses these scalings to determine when the hub eigenvector dominates.
- Realistic network regimes: Eigenvector centrality is expected to fail from localization when α > 5/2, a condition reported to occur in many real-world networks.The paper also reports empirical localization measurements for real-world networks in Table I.
III. NONBACKTRACKING CENTRALITY
The paper proposes nonbacktracking centrality, which excludes a node’s contribution when evaluating its neighbors, preventing the feedback that drives localization while matching standard eigenvector centrality in dense networks.
- III. NONBACKTRACKING CENTRALITY: Nonbacktracking centrality computes each node’s importance from neighbor centralities calculated without that node’s contribution.This prevents neighbors from reflecting a hub’s influence back onto the hub.
- III. NONBACKTRACKING CENTRALITY: The modified measure approaches standard eigenvector centrality in dense networks but differs and is better behaved in sparse networks where localization can occur.This preserves the conventional measure’s behavior where it is reliable while addressing the hub-driven failure mode.
- III. NONBACKTRACKING CENTRALITY: The method uses the leading eigenvector of the Hashimoto, or nonbacktracking, matrix constructed from directed versions of the network’s edges.The matrix excludes transitions that immediately reverse direction along the same edge.
- III. NONBACKTRACKING CENTRALITY: The resulting vertex centrality sums leading-eigenvector values on directed edges entering each vertex, with each value ignoring the opposite neighbor.It can also be computed through the Ihara–Bass determinant formula using a 2n × 2n matrix whose sparsity is close to the adjacency matrix’s.
- III. NONBACKTRACKING CENTRALITY: For Poisson random graphs, the leading nonbacktracking eigenvalue is z = c, the average degree.Adding a hub does not introduce a new leading eigenvalue when its degree is constant and the network size grows.
- III. NONBACKTRACKING CENTRALITY: Large cliques can still generate outlying nonbacktracking eigenvalues and localized eigenvectors, creating a separate potential source of centrality problems.A clique of size k implies z ≥ k −2 and can supersede other leading eigenvalues when sufficiently large.
A. Numerical results
Numerical tests show that nonbacktracking centrality remains well behaved beyond the standard measure’s localization transition, across synthetic and real-world networks.
- A. Numerical results: Nonbacktracking centrality remains well behaved beyond the former localization transition, without a large jump in hub or neighbor centrality.The comparison uses the same networks examined for the standard centrality.
- A. Numerical results: Across eleven synthetic and real-world networks, eigenvector centrality shows localization where expected, whereas the nonbacktracking version shows no localization.The networks include random-graph-plus-hub and power-law configuration-model graphs, alongside several real-world networks.
- A. Numerical results: In the electronic circuit network, the highest-degree vertex and its neighbors dominate eigenvector centrality but not nonbacktracking centrality.Figure 4 encodes centrality through node size and color.
IV. CONCLUSIONS
Eigenvector centrality fails under common network conditions because localization concentrates centrality on a few vertices. A nonbacktracking-based measure reduces localization while remaining similar in well-behaved cases and practical for large networks.
- Conclusions: Eigenvector centrality fails under commonly occurring conditions when localization concentrates most centrality weight on a small number of vertices.The phenomenon is particularly visible in networks with high-degree hubs or power-law degree distributions.
- Conclusions: The proposed nonbacktracking spectral centrality gives values similar to standard eigenvector centrality when the latter is well behaved.
- Conclusions: The nonbacktracking measure significantly decreases localization on synthetic and real-world networks.
- Conclusions: The new measure can be calculated almost as quickly as the standard one, supporting analysis of very large networks.