Source-linked AI summary
Distinct types of eigenvector localization in networks
Romualdo Pastor-Satorras, Claudio Castellano
TL;DR
The paper examines how the principal eigenvector localizes in heterogeneous networks, a question relevant to centrality and network dynamics. It presents evidence for hub localization at γ>5/2 and mesoscopic maximum-K-core localization at γ<5/2, with a similar twofold pattern argued for real networks.
Problem
Earlier accounts allowed for hub localization or delocalization, leaving the localization picture for heterogeneous networks incomplete despite the principal eigenvector’s relevance to centrality and dynamics.
Source: Introduction · pp. 1–2Method
The authors use finite-size scaling for uncorrelated synthetic power-law networks and numerical analysis to assess localization modes in real networks.
Source: Introduction · p. 2Results
For synthetic networks, the principal eigenvector localizes on hubs for γ>5/2 and on the maximum-index K-core for γ<5/2; the authors also argue for these two modes in real networks.
Source: Introduction · pp. 2–3, Discussion · p. 10Takeaways & Limitations
The results indicate that eigenvector centrality can add no more information than degree centrality for γ<5/2 and exhibits hub localization as a topological artifact for γ>5/2.
Source: Discussion · p. 11The roles of degree correlations, clustering, and community structure in localization, and the nature of the non-backtracking centrality’s mesoscopic localization for γ>5/2, remain open questions.
Source: Discussion · p. 11
Abstract
from arXiv · showhide
The spectral properties of the adjacency matrix provide a trove of information about the structure and function of complex networks. In particular, the largest eigenvalue and its associated principal eigenvector are crucial in the understanding of nodes centrality and the unfolding of dynamical processes. Here we show that two distinct types of localization of the principal eigenvector may occur in heterogeneous networks. For synthetic networks with degree distribution $P(q) \sim q^{-\gamma}$, localization occurs on the largest hub if $\gamma>5/2$; for $\gamma<5/2$ a new type of localization arises on a mesoscopic subgraph associated with the shell with the largest index in the $K$-core decomposition. Similar evidence for the existence of distinct localization modes is found in the analysis of real-world networks. Our results open a new perspective on dynamical processes on networks and on a recently proposed alternative measure of node centrality based on the non-backtracking matrix.
Introduction
The paper argues that principal-eigenvector localization in heterogeneous networks has two modes, including a mesoscopic mode missed by a hub-versus-delocalized picture. This matters because eigenvector centrality and the principal eigenvector also inform network structure and dynamical processes.
Introduction
- Eigenvector centrality defines a node’s centrality by its component in the adjacency matrix’s principal eigenvector, which is relevant to network structure and dynamical processes.The principal eigenvector and largest eigenvalue are used in theoretical studies of synchronization and spreading.Source: Introduction · p. 1
- Localization asks whether a finite fraction of the principal eigenvector’s normalized weight lies on a non-extensive subset, which may be finite or mesoscopic.A mesoscopic subset can scale as N^β with β<1; delocalization instead involves an extensive number of nodes.Source: Introduction · p. 2
- Earlier work found hub localization for γ>5/2 but argued for delocalization below that threshold, considering localization on a finite node set.The paper identifies the mesoscopic K-core mode as what that earlier framing missed.Source: Introduction · p. 2
- For power-law networks, prior work linked the leading eigenvalue to either ⟨q²⟩/⟨q⟩ or √qmax, with the threshold at γ=5/2 separating those regimes.Here qmax is the network’s largest degree.Source: Introduction · p. 2
- For synthetic networks, the principal eigenvector localizes on the largest hub for γ>5/2 and on the maximum-index K-core for γ<5/2; real networks show the same twofold scenario.The γ<5/2 mode is associated with eigenvector components correlated with node degree.Source: Introduction · pp. 2–3
Results
The inverse participation ratio (IPR) distinguishes delocalization from localization as network size grows. Synthetic and real networks show two localization modes: on a hub or across the maximum K-core; non-backtracking centrality also remains localized.
Eigenvector localization and the inverse participation ratio
- The IPR’s size dependence diagnoses localization: delocalized components scale as N^−1/2 and yield an IPR decay exponent α = 1, while α < 1 indicates localization.For localization over a subextensive support of size N^β, the expected IPR decay exponent is α = β.Source: Eigenvector localization and the… · p. 3
Eigenvector localization in synthetic networks
- For γ < 5/2, the IPR decays with effective exponents α < 1/2 rather than the α = 1 decay expected for a delocalized principal eigenvector; for large γ it tends to a constant.The simulations are compatible with a transition at γ = 5/2, though slow crossover effects prevent a firm numerical determination of its precise location.Source: Eigenvector localization in synthetic… · p. 4, Figure 1 · p. 4
- The principal eigenvector (PEV) is effectively localized on the maximum K-core, whose size grows sublinearly as N^(3−γ)/2, while more than half of normalized PEV weight resides there in the large-network limit.Source: Eigenvector localization in synthetic… · p. 6
- For γ > 5/2, the hub carries a finite fraction of the eigenvector weight; for 5/2 < γ < 3, this accumulation occurs only at sufficiently large network sizes.At γ = 2.8, hub weight is small below N = 10^6 and increases to overtake the max-K-core weight for N > 10^7.Source: Eigenvector localization in synthetic… · pp. 6–7, Figure 4 · p. 7
The non-backtracking centrality
- Non-backtracking centrality is not delocalized for any tested γ; for γ < 5/2 it strongly correlates with adjacency-matrix centrality, while above that threshold it is uncorrelated with it.Its IPR decreases more slowly than N^−1, indicating localization on a sublinear mesoscopic subset; above γ = 5/2 this localization is not strongly correlated with node degree.Source: The non-backtracking centrality · pp. 7–8
Eigenvector localization in real networks
- Real networks show evidence of both hub and max-K-core localization, but degree correlations complicate using the leading eigenvalue to distinguish the modes.HEP and Movies suggest max-K-core localization, while Internet and Amazon suggest hub localization; P2P and WWW do not permit a clear conclusion from the eigenvalue comparison.Source: Eigenvector localization in real… · pp. 8–9
Discussion
The paper reports distinct PEV localization patterns in heterogeneous networks and argues that localization affects how eigenvector centrality and network dynamics should be understood. Some influences on localization, and the nature of a related NBTC-localized subgraph, remain open questions.
Discussion
- For synthetic networks, PEVs localize on maximum-degree hubs when γ > 5/2, but for γ < 5/2 they localize on a sublinear max K-core despite its size.In the high-heterogeneity case, components scale as f_i ∼ q_i, and the max K-core holds a finite fraction of normalized PEV weight.Source: Discussion · p. 10
- In real networks, localization on the max K-core is expected when Λ1 is close to ⟨q^2⟩/⟨q⟩, and localization on hubs when it is close to √qmax.The paper describes the real-network evidence as less clearcut than the synthetic-network results.Source: Discussion · p. 10
- For γ < 5/2, eigenvector centrality provides no more information than degree centrality; for γ > 5/2, hub localization arises as a topological artifact.The paper also notes that non-backtracking-matrix centrality measures are not free from localization effects.Source: Discussion · p. 11
- Degree correlations, clustering, and community structure may affect PEV localization, while the mesoscopic subgraph underlying NBTC localization for γ > 5/2 remains unresolved.The authors identify clarifying these effects and the subgraph's nature as open questions.Source: Discussion · p. 11
Methods
The analysis uses real-world networks spanning communication, collaboration, social, web, and commerce settings. Directed datasets were symmetrized for analysis.
Real networks analyzed
- The remaining datasets are Amazon products linked by frequent co-purchases and Internet autonomous systems linked by BGP peer connections.The Internet map is at the Autonomous System level.Source: Real networks analyzed · p. 12
- The datasets include Enron email addresses linked by exchanged email and Gnutella hosts linked by connections.The email network connects addresses that exchanged at least one email; the Gnutella network represents host connections.Source: Real networks analyzed · p. 12
- The collaboration datasets represent co-starring actors in movies and coauthoring scientists in high-energy physics papers.The movie network is based on the Internet Movie Database; the physics network covers papers submitted to arXiv's High Energy Physics section.Source: Real networks analyzed · pp. 11–12
- The study also includes the Notre Dame web graph, a PGP user network, and Slashdot users connected by friend-or-foe tagging.Web pages are linked by hyperlinks; PGP users are linked when each has signed the other's encryption key.Source: Real networks analyzed · p. 12
- Some datasets were directed and were symmetrized to make them undirected for analysis.Source: Real networks analyzed · p. 12