Source-linked AI summary
Spectral centrality measures in complex networks
Nicola Perra, Santo Fortunato
TL;DR
Spectral centrality measures have been comparatively underexplored in physics despite their use for ranking nodes in heterogeneous complex networks. This paper reviews and compares PageRank, eigenvector centrality, and HITS hub/authority scores, deriving relations to node degree in selected limits and comparing their rankings.
Problem
Spectral centrality measures have not been extensively investigated in the physics literature, despite the diverse roles of nodes in heterogeneous networks.
Method
The paper reviews and compares PageRank, eigenvector centrality, and HITS hub/authority scores using spectral graph properties and degree-based analyses.
Results
The measures exhibit simple relations to indegree or degree in selected limits, including PageRank proportionality to indegree when outdegrees are equal and q →1.
Takeaways & Limitations
Spectral centrality measures provide self-consistent assessments of node importance based on neighboring nodes, with their distributions and rankings depending on graph structure and parameter limits.
Abstract
from arXiv · showhide
Complex networks are characterized by heterogeneous distributions of the degree of nodes, which produce a large diversification of the roles of the nodes within the network. Several centrality measures have been introduced to rank nodes based on their topological importance within a graph. Here we review and compare centrality measures based on spectral properties of graph matrices. We shall focus on PageRank, eigenvector centrality and the hub/authority scores of HITS. We derive simple relations between the measures and the (in)degree of the nodes, in some limits. We also compare the rankings obtained with different centrality measures.
I. INTRODUCTION · II. CENTRALITY MEASURES · A. PageRank
The paper reviews spectral centrality measures for heterogeneous complex networks, focusing on PageRank, eigenvector centrality, and HITS hub/authority scores. It introduces PageRank as a random-walk measure with occasional random jumps and examines its spectral formulation and dependence on network structure.
- I. INTRODUCTION: Complex systems can be represented as networks whose nodes are interacting units connected by edges.
- I. INTRODUCTION: Heterogeneous degree distributions create diverse structural roles for nodes, motivating centrality measures that rank their topological importance.
- I. INTRODUCTION: The paper reviews PageRank, eigenvector centrality, and Kleinberg’s HITS hub/authority scores, primarily for directed graphs with applicable extensions to undirected graphs.
- I. INTRODUCTION: The study presents the measures in Section II, analyzes particular graphs in Section III, compares real-graph rankings in Section IV, and reports conclusions in Section V.
- II. CENTRALITY MEASURES: For directed graphs, adjacency matrices distinguish incoming from outgoing links, yielding separate indegree and outdegree notions.
- A. PageRank: PageRank models Web browsing as a random walk with occasional jumps to randomly selected nodes, with damping factor q typically set to 0.15.
- A. PageRank: For any q > 0, PageRank reaches stationarity because the walker can escape dangling ends through random jumps.
- A. PageRank: PageRank is the principal eigenvector of the transition matrix M and is computed with the power method, also used for the other studied centrality measures.
B. Eigenvector centrality
Eigenvector centrality assigns each node a prestige proportional to the prestiges of neighboring nodes pointing to it, through an eigenvector of the transposed adjacency matrix. Its solutions can assign zero centrality to nodes with zero indegree, while α-centrality introduces a parameter weighting peer contributions against the node’s own contribution.
- Definition: Eigenvector centrality assigns node i a prestige proportional to the sum of the prestiges of neighboring nodes pointing to it.This relationship is more direct than in PageRank.
- Eigenvalue formulation: The centrality vector is a non-trivial eigenvector of the transposed adjacency matrix, associated with eigenvalue λ.The all-zero vector is always a trivial solution, so the true measure requires non-trivial solutions.
- Limitation: Nodes with indegree zero have zero eigenvector centrality, and nodes pointed to by zero-centrality nodes can also have zero centrality.This follows directly from the eigenvector relation described in the passage.
- α-centrality: α-centrality weighs the relative importance of peer contributions against the contribution of the node itself.Unlike PageRank, α-centrality solutions do not have a natural probability interpretation, so their sum need not equal 1.
C. HITS scores · III. RESULTS
The HITS algorithm ranks Web pages by distinguishing hubs from authorities, and its scores are principal eigenvectors of symmetric graph-derived matrices. The supplied passages do not report specific III. RESULTS findings.
- C. HITS scores: HITS was proposed shortly before Brin and Page’s seminal paper as another prestige measure for Web pages.The supplied passage identifies Jon Kleinberg as the proposer of HITS.
- C. HITS scores: HITS distinguishes two types of Web pages: hubs and authorities.The algorithm was proposed as a solution for ranking Web sites by importance.
- C. HITS scores: A relevant page may be pointed at by many other pages, but simple indegree cannot distinguish it from pages with similarly large indegree.The passage motivates HITS by identifying a limitation of indegree-based ranking.
- C. HITS scores: The HITS equations can be rewritten as simple eigenvalue equations for x and y by substitution.This reformulation connects the two score vectors to spectral equations.
- C. HITS scores: The hub and authority scores are eigenvectors of AAt and AtA, respectively.The passage derives this relationship from Eqs. (7) and (8).
- C. HITS scores: Both AAt and AtA are symmetric, regardless of whether A is symmetric.The symmetry property holds for the graph-derived matrices even when the original matrix is not symmetric.
- C. HITS scores: The score vectors x and y correspond to the principal eigenvectors of AAt and AtA.This identifies the spectral vectors used for the hub and authority scores.
A. PageRank · 1. The limit q →0
The PageRank analysis specializes to DMS growth graphs and examines the q →0 limit on tree-like networks. In this limit, PageRank is recursively determined by predecessors, changes locally under node addition, and follows a power-law distribution with exponent 2.
- A. PageRank: The analysis uses DMS graphs with power-law indegree exponent γ = 2 + a/m and focuses on m = 1, where each node has outdegree 1 and the network is a tree.The results are stated to be independent of m.
- 1. The limit q →0: For very small q, a node’s PageRank equals a constant plus the PageRank of its in-neighbors, enabling recursive calculation on simple trees.The recursion determines each node’s PageRank from its predecessors.
- 1. The limit q →0: All PageRank values are multiples of the elementary unit q/n.The distribution is therefore measured in units of q/n.
- 1. The limit q →0: PageRank increases along directed links, and node i’s PageRank in units of q/n equals the number of its predecessors.These properties follow directly from the recursive predecessor relation.
- 1. The limit q →0: Adding a new node changes only the nodes on its path to the root, increasing each affected PageRank by q/n while leaving other nodes unchanged.The affected path includes the root of the graph.
- 1. The limit q →0: The master-equation analysis balances transitions between PageRank levels by counting predecessors and adjacent links affected by the new node.For a node with PageRank l, the number of predecessors including itself is l, while the corresponding adjacent-link count is l−1.
- 1. The limit q →0: The PageRank distribution on a DMS tree is a power law with exponent 2 for any a, including a →∞, when the indegree distribution becomes exponential.Numerical simulations confirm the result and indicate that the tree assumption is unnecessary when every node has the same outdegree m.
- 1. The limit q →0: The same exponent-2 PageRank behavior was reported for Barabási-Albert preferential attachment and the Copying Model, and may extend to graphs whose flows converge toward a central root.The passage also notes agreement with a general result on the size distribution of supercritical trees.
2. The limit q →1
As q approaches 1, ordinary PageRank becomes nearly uniform, while the reduced PageRank isolates the small in-neighbor contribution. For graphs with equal outdegree, reduced PageRank is proportional to indegree and follows its distribution.
- The limit q →1: At q = 1, every node has the identical PageRank value 1/n, making the limit well defined but trivial.For q near 1, the in-neighbor contribution is much smaller than the constant term, which is close to 1/n.
- The limit q →1: The reduced PageRank distribution has the same trend as the indegree distribution, as verified numerically on a DMS graph with 10^6 nodes.In Fig. 4, the reduced PageRank curve matches the indegree distribution for m = 1 and a = 1.
- The limit q →1: For equal-outdegree graphs, reduced PageRank is proportional to a node’s indegree in the q →1 limit.The result follows from the leading-order form in the infinitesimal 1 −q and applies to any graph whose nodes share the same outdegree m.
3. Extension to undirected graphs
PageRank extends to undirected graphs, where bidirectional links eliminate dangling ends and make pure random walks stationary. Its random-walk contribution, reduced PageRank, follows the network’s degree distribution across damping values and graph examples.
- Extension to undirected graphs: PageRank extends directly to undirected graphs, with node degree replacing indegree in the corresponding equation.
- Extension to undirected graphs: Because undirected links are traversable in both directions, pure random walks reach stationarity without dangling ends, with stationary probability proportional to node degree.
- Extension to undirected graphs: For every tested q, reduced PageRank distributions follow the degree-distribution decay on a DMS graph with power-law exponent γ = 3.
- Extension to undirected graphs: The same reduced-PageRank trend was found across many other graphs, including a .gov web graph whose degree-distribution tail follows a power law with exponent 2.1.
- Extension to undirected graphs: The iterative expression groups nodes into successive shells and approximates neighbor contributions using node degree and the neighbors’ average inverse degree.
B. Eigenvector centrality · 1. Directed graphs
For directed graphs, eigenvector centrality shares the PageRank limit q →0 under broad conditions, and its distribution on several preferential-growth models has a power-law tail with exponent 2.
- 1. Directed graphs: Eigenvector centrality’s defining equation is formally analogous to PageRank’s, differing because its eigenvalue α is not 1.The correspondence is established by comparing Eqs. (4) and (10).
- 1. Directed graphs: When every node has the same outdegree m > 1, the Eq. (10) sum gains a multiplicative factor 1/m and becomes identical to Eq. (4).This extends the comparison beyond the m = 1 case.
- 1. Directed graphs: All PageRank results derived for q →0 therefore also hold for αEV.The stated correspondence transfers the PageRank limiting results to eigenvector centrality.
- 1. Directed graphs: The eigenvector-centrality result is more general because ε need not be very small.The argument also does not require equal outdegrees, although the analyzed graphs had equal outdegree.
- 1. Directed graphs: The analyzed graphs’ eigenvector-centrality distributions exhibit a power-law tail with exponent 2.Figure 7 shows αEV on a directed DMS graph with 10^6 nodes, m = 1, and a = 1; the dashed line marks the predicted slope.
- 1. Directed graphs: The exponent-2 tail also occurs for graphs generated by preferential attachment and the Copying Model.The passage states that this parallels PageRank behavior in the q →0 limit.
2. Extension to undirected graphs
For undirected graphs, eigenvector centrality is determined by the centralities of neighboring nodes, up to an additive constant. Its reduced form becomes proportional to node degree when the degree is sufficiently large, independently of the specific graph.
- Extension to undirected graphs: On undirected graphs, a node’s αEV is proportional to the sum of its neighbors’ αEV, up to an additive constant ǫ.This follows because A^t = A for undirected graphs.
- Extension to undirected graphs: The reduced αEV of a node is proportional to its degree when the degree is sufficiently large.The neighbor sum is approximated as k_i⟨x_r⟩, with accuracy improving as the number k_i of neighbors increases.
- Extension to undirected graphs: This degree-proportionality result is independent of the specific graph considered.The approximation relies on replacing the sum over a node’s k_i neighbors with k_i times the graph-wide average reduced αEV.
C. HITS scores
HITS assigns hub and authority scores through recursive neighbor relationships. With constant outdegree, authority-score tails follow indegree tails, whereas hub scores generally resist prediction from other graph variables; on undirected graphs, both scores coincide with eigenvector centrality.
- C. HITS scores: A node’s hub score sums hub scores of in-neighbors of its out-neighbors, while its authority score sums authority scores of out-neighbors of its in-neighbors.These relationships define the recursive HITS score equations.
- C. HITS scores: With constant outdegree, authority-score distributions have the same tail as indegree distributions, but hub scores generally cannot be predicted from other graph variables.The authority result is illustrated for DMS graphs with 105 nodes, m = 10 and m = 50, while no comparable hub-score prediction is available.
- C. HITS scores: For undirected graphs, hub and authority scores are identical and coincide with EV because A^tA = AA^t = A^2, whose eigenvectors match those of A.Thus extending HITS to undirected graphs adds no distinct centrality measure.
IV. RANKINGS · V. CONCLUSIONS
The paper compares node rankings produced by spectral centrality measures using Kendall’s τ, finding substantial differences for empirical blog and Web networks. It concludes by framing PageRank, eigenvector centrality, and HITS hub/authority scores as self-consistent measures of node importance.
- IV. RANKINGS: Kendall’s τ is used to compare rankings, ranging from 1 for perfect correlation to −1 for perfect anticorrelation.The comparison concerns rankings generated by different centrality measures.
- IV. RANKINGS: DMS graphs have regular structure, with centrality distributions related through simple relations between measures and node indegree.These relations arise at the level of individual nodes.
- IV. RANKINGS: In the political-blog network, small correlation coefficients indicate that rankings differ considerably according to the centrality measure.The paper illustrates these differences using Top Ten blog rankings.
- IV. RANKINGS: For the Web graph, Kendall’s τ values have the same magnitude as for the blog network, while Top Ten listings again differ considerably.The Web rankings are reported in Tables IV and V.
- V. CONCLUSIONS: The study examines PageRank, eigenvector centrality, and the hub and authority scores of HITS as centrality measures based on graph-matrix properties.These measures are presented as important for understanding node properties and topological roles.
- V. CONCLUSIONS: All three approaches infer node importance self-consistently from nearest-neighbor importance, with HITS also using next-to-nearest neighbors.The conclusion characterizes their shared mechanism for assigning importance.