On the limiting behavior of parameter-dependent network centrality measures

Michele Benzi; Christine Klymko

Source-linked AI summary

On the limiting behavior of parameter-dependent network centrality measures

Michele Benzi, Christine Klymko

arXiv:1312.6722v7Dec 23, 2013math.NAcs.SIphysics.soc-ph

TL;DR

The paper asks how to compare and tune parameter-dependent centrality measures when different indices may rank nodes similarly but no parameter choice is obvious. It analyzes positive-coefficient functions of adjacency matrices and shows that tuning moves rankings between degree and eigenvector centrality, with spectral gap informing how quickly the transition occurs.

Problem
Choosing among many centrality measures and selecting their parameters is difficult because rankings may be similar without a clear basis for comparison.
Method
The paper analyzes a broad class of walk-based centralities defined by positive analytic functions of adjacency matrices, covering directed and weighted networks and discussing PageRank.
Results
Tuning the parameter interpolates between degree centrality at small values and eigenvector centrality at large values, while larger spectral gaps produce faster convergence toward eigenvector rankings.
Takeaways & Limitations
For exponential centrality, β = 1 is recommended as a default, while β outside [0.5, 2] yields rankings close to cheaper degree or eigenvector centrality.
Takeaways & Limitations
The practical distinction from degree or eigenvector centrality narrows as the spectral gap grows, making more expensive measures harder to justify in such networks.

Abstract

from arXiv · show

We consider a broad class of walk-based, parameterized node centrality measures for network analysis. These measures are expressed in terms of functions of the adjacency matrix and generalize various well-known centrality indices, including Katz and subgraph centrality. We show that the parameter can be "tuned" to interpolate between degree and eigenvector centrality, which appear as limiting cases. Our analysis helps explain certain correlations often observed between the rankings obtained using different centrality measures, and provides some guidance for the tuning of parameters. We also highlight the roles played by the spectral gap of the adjacency matrix and by the number of triangles in the network. Our analysis covers both undirected and directed networks, including weighted ones. A brief discussion of PageRank is also given.

1. Introduction.

The paper studies how parameterized centrality measures based on adjacency-matrix functions relate to degree and eigenvector centrality. It aims to explain correlated rankings and guide parameter selection while restricting attention to measures with linear-algebraic formulations.

Parameterized centralities are studied to explain why different measures often produce highly correlated rankings.
The paper analyzes degree, eigenvector, and adjacency-matrix-function centralities, including Katz, subgraph, total communicability, and related measures.
The analysis focuses on centrality measures expressible through functions of the adjacency matrix, excluding betweenness and closeness centrality.
The paper presents main results showing degree and eigenvector centrality as limiting cases of parameterized measures, alongside a discussion of PageRank.

2. Background and definitions.

This section introduces graphs, walks, adjacency matrices, and spectral properties used to analyze network centrality. It distinguishes directed and undirected structures and records the eigenvalue conditions relevant to later arguments.

The background treatment mainly uses unweighted loopless graphs, while noting that most results extend to positive weights and some extend to graphs with loops.
A digraph consists of nodes and directed edges, with out-degree counting edges leaving a node and in-degree counting edges entering it.
A walk is a sequence of adjacent nodes, while paths and cycles impose restrictions on repeated nodes; adjacency matrices represent graph edges.
For simple undirected graphs, the adjacency matrix is symmetric, so its eigenvalues are real and admit an orthogonal eigendecomposition.
For strongly connected digraphs, the adjacency matrix is irreducible and has a simple dominant eigenvalue with positive left and right eigenvectors.

3. Node centrality.

The section defines common centrality measures as walk-based scores derived from adjacency matrices. Their parameters weight walks of different lengths, connecting local degree information with broader network influence.

Common measures include degree, eigenvector, PageRank, Katz, subgraph, and total communicability centralities.
In directed networks, transposing the adjacency matrix switches broadcast measures to authority measures, while subgraph centralities remain unchanged under transposition.
Exponential subgraph centrality counts closed walks weighted by β^k/k!, while total communicability counts walks from a node to all nodes using the same weighting.
Resolvent subgraph and Katz centralities use (I − αA)^−1, whose power-series terms weight walks by α^k; convergence and positivity require parameter bounds.

4. A general class of functional centrality measures.

The paper defines admissible analytic matrix functions through positive-coefficient power series and a parameter range ensuring valid centrality measures. It then develops asymptotic tools for showing dominance of the leading eigenvalue.

4.1. Admissible matrix functions.: The admissible class P consists of analytic functions with strictly positive Maclaurin coefficients, forming a positive cone suitable for walk-based centrality.
4.1. Admissible matrix functions.: The parameter t ensures convergence when |tλ_1(A)| < R_f and is restricted to positive values so f(tA) is entry-wise positive.
4.1. Admissible matrix functions.: For an irreducible adjacency matrix, f(tA) is strictly positive when 0 < t < R_f/λ_1(A), with no finite upper bound for entire functions.
4.1. Admissible matrix functions.: Exponential subgraph centrality uses an entire function and permits all positive parameters, whereas resolvent subgraph centrality requires a finite parameter interval.
4.2. Asymptotic behavior of the ratio of two power series.: The asymptotic lemmas show that, under the stated spectral separation and power-series conditions, contributions associated with non-dominant eigenvalues vanish relative to the leading term.

5. Limiting behavior of parameterized centrality measures.

Parameterized centrality measures based on analytic functions of adjacency matrices explain why rankings can remain correlated and stable across parameter choices. Under the stated assumptions, small parameters recover degree centrality, while large parameters recover eigenvector centrality, with directed networks distinguishing broadcast and receive rankings.

Parameter limits: As parameters approach limiting values, scores can become extremely sensitive while rankings stabilize quickly and change little.This behavior is reported near α → 1/λ1, β → ∞, and α, β → 0+ for Katz and subgraph centrality.
General framework: The framework generalizes Katz, subgraph centrality, total communicability, and related parameterized measures expressed through analytic functions of the adjacency matrix.The analysis is motivated by differing scores and often correlated, relatively stable rankings across parameter choices.
Parameter limits: The limiting ranking as the parameter tends to zero cannot be obtained by simply setting the parameter equal to zero because rankings need not vary continuously.The centrality measures themselves are continuous in the parameter, but their induced rankings are not.
Undirected networks: As the parameter tends to zero, undirected functional centrality rankings converge to degree centrality, while as it approaches its upper limit they converge to eigenvector centrality.The result applies to both diagonal-entry and row-sum measures under the theorem’s assumptions.
Directed networks: For directed networks, small parameters recover out-degree for broadcast centrality and in-degree for receive centrality.These are the directed analogues of the undirected degree limit.
Directed networks: For directed networks, large parameters recover the dominant right eigenvector for broadcast centrality and dominant left eigenvector for receive centrality.The same limiting results hold when the all-ones vector is replaced by any positive preference vector.

6. The case of PageRank.

PageRank balances graph structure against random teleportation, and its small-parameter limit recovers rankings based on weighted graph connectivity. Its large-parameter behavior can instead become problematic on graphs that are not strongly connected.

Parameter interpretation: The parameter α balances graph structure against random choice according to v, while smaller α values produce faster convergence to the Markov-chain steady state.The paper notes α = 0.85 as a commonly recommended practical choice.
Small-parameter limit: As α →0+, PageRank rankings converge to the row sums of H, equivalently the row sums of S, when personalization is uniform.The result also holds for the corresponding vector H1 and S1.
Small-parameter limit: The α →0+ limit requires a uniform personalization vector v; the broader arbitrary-preference-vector invariance stated for the other limits does not apply here.The PageRank theorem assumes v = 1/n·1.
Small-parameter limit: Because H1 is essentially weighted in-degree, graph structure continues influencing PageRank rankings for every sufficiently small nonzero α.The limiting ranking is therefore not determined solely by the personalization component.
Large-parameter limit: As α approaches 1, PageRank can assign zero scores to important nodes when the graph is not strongly connected, so values too close to 1 are not recommended.This behavior is associated with the generalized-inverse limiting vector.
Related diffusion methods: For diffusion-based rankings using e^{tP}, the rankings converge to PageRank as t →∞, identifying PageRank with the equilibrium distribution of a continuous-time diffusion process.The scaled matrix e^{-t}e^{tP} remains column-stochastic.

7. Discussion.

Parameterized walk-based centralities use a tuning parameter to move between local degree-based influence and global eigenvector-based influence. The spectral gap, triangles, clustering, and distance-two neighborhoods determine how quickly these limits are approached.

Parameter interpretation: Analytic-function centralities weight walks of all lengths, with longer walks penalized; decreasing t strengthens short-walk contributions and increasing t strengthens long-walk contributions.This weighting explains the continuous transition between local and global rankings.
Parameter interpretation: The parameter t interpolates between degree rankings from short walks and eigenvector rankings from long walks, with moderate values useful when both influences matter.Small t emphasizes edges, while t near the upper limit emphasizes effectively infinite-length walks.
Eigenvector limit: A large spectral gap accelerates convergence toward eigenvector-centrality rankings as t increases, whereas a small gap slows this approach.The parameter can also artificially widen or shrink the effective spectral separation.
Degree limit: For small t, nodes participating in many triangles approach degree centrality more slowly because triangle counts enter the leading correction through [A^3]ii.Low-clustering networks therefore reach the degree limit more rapidly than highly clustered networks.

8. Related work.

Earlier work established limiting relationships among Katz, α-centrality, HITS, and broader centrality families, but often under narrower matrix or network assumptions. This paper unifies and extends those results across a broader class of measures and networks.

Katz and α-centrality: Prior work showed eigenvector centrality as a Katz limit, while α-centrality was shown to approach degree at α →0+ and eigenvector centrality under symmetric-matrix assumptions.The cited results differ in their assumptions and generality.
Katz and α-centrality: A general Katz result without diagonalizability uses the Drazin inverse, but that technique is not easily generalized to other matrix-function centralities.This motivates the paper’s broader functional treatment.
Kernel-based methods: Earlier kernel-based methods include HITS as a limiting case, with AAT and ATA producing hub and authority vectors, respectively.The distinction corresponds to the two node roles represented in directed citation networks.
General frameworks: Romance’s general family includes degree, eigenvector, PageRank, α-centrality, Katz, and other measures, and explains degree–eigenvector correlation in some networks.The present paper places its results alongside this broader unifying framework.
Contribution: The paper’s framework covers a broader class of centrality measures and networks than earlier results, while providing parameter-selection rules for Katz and subgraph centrality.The authors present the analysis as unifying, extending, and completing scattered partial results.

9. Summary of numerical experiments.

Numerical tests across diverse directed and undirected networks support the predicted limiting behavior of exponential and resolvent centralities. They also motivate parameter ranges intended to preserve information beyond degree or eigenvector centrality.

Experimental setup: The experiments covered social, protein-interaction, computer, collaboration, and road networks, including both directed and undirected cases.The tests primarily monitored limiting behavior across exponential and resolvent measures.
Experimental findings: For exponential centralities, smaller β drives rankings toward degree centrality, while larger β drives them toward eigenvector centrality, especially for top-ranked nodes.Diagonal-entry exponential centrality generally approaches degree rankings faster than the row-sum version.
Experimental findings: Networks with large spectral gaps approach eigenvector-centrality rankings much faster as β increases than networks with small spectral gaps.The observed pattern holds for both exponential measures tested.
Experimental findings: The paper reports that analogous considerations apply to resolvent measures and directed networks, and that PageRank damping-parameter conclusions are broadly consistent with prior results.
Parameter guidance: The recommended exponential range is β ∈ [0.5, 2], with β = 1 as a reasonable default and smaller values for networks with relatively large spectral gaps.Below 0.5 rankings become close to degree centrality; above 2 they become close to eigenvector centrality.
Parameter guidance: For resolvent measures, α = τ/λ1 with τ ∈ [0.5, 0.9] is most informative, while smaller or larger τ values approach degree or eigenvector rankings.Smaller τ is recommended when the network has a large spectral gap.

10. Conclusions.

The paper analyzes parameterized centrality measures, showing how their rankings relate to degree and eigenvector centrality and how network structure guides parameter choice. It also identifies practical limits when expensive measures add little information and leaves computational aspects mostly untreated.

Parameterized measures include subgraph, total communicability, and Katz centrality, while degree and eigenvector centrality arise as limiting cases.
Spectral gap and clustering coefficient govern how quickly parameterized rankings approach degree- and eigenvector-centrality rankings.
The parameter acts as a knob controlling the relative weight assigned to walks of different lengths.
For large spectral gaps, only a narrow parameter range yields rankings noticeably different from degree or eigenvector centrality.
Because degree and eigenvector centrality are cheaper than subgraph centrality, expensive measures may be difficult to justify on large-gap networks.
The paper focuses on theoretical relationships among rankings and mostly avoids computational aspects of the methods.

Appendix A. Supplementary materials to the paper.

The appendix contains supplementary numerical experiments intended to illustrate the paper’s theoretical results.

The supplementary document reports numerical experiments designed to illustrate the accompanying paper’s theoretical results.

A.1. Limiting behavior of PageRank for small α.

The appendix examines PageRank on a six-node directed graph as α becomes small. Rankings remain unchanged while scores converge toward the uniform distribution, making distinctions increasingly difficult to resolve.

The appendix constructs PageRank from a strictly positive matrix, ensuring a unique dominant eigenvector for each α in (0, 1).
As α approaches zero, PageRank scores move toward the uniform probability 1/6, reducing separation between nodes without changing the observed ranking.
For the six-node directed example, PageRank rankings remain unchanged as α decreases across the reported values.
Very small nonzero α values still preserve graph-structure effects, but ranking nodes requires greater numerical accuracy as scores converge.
The limiting analysis identifies the α → 0+ PageRank ranking with the ranking obtained from the vector H1, equivalently S1.
Row sums of H offer an inexpensive alternative ranking, but they are cruder than PageRank and can tie nodes that PageRank separates.

A.2. Numerical experiments on undirected networks.

The experiments use exponential- and resolvent-type centralities on varied undirected networks to compare their rankings with degree and eigenvector centrality. Ranking similarity is measured using top-k intersection distance.

The experiments study exponential- and resolvent-type centralities and their relationships to degree and eigenvector centrality on undirected networks.
Top-k intersection distance compares ranked lists through normalized symmetric differences, with zero indicating identical top-k orderings and one disjoint top-k sets.
Unless otherwise specified, the experiments compare rankings across the full set of nodes.
The network collection spans sources including the University of Florida Sparse Matrix Collection, collaboration networks, communication networks, and Minnesota roads.

A.2.1. Exponential subgraph centrality and total communicability.

Across the tested networks, parameterized centrality rankings move from degree-like behavior at small parameters toward eigenvector-like behavior at larger parameters. Spectral gaps govern how quickly rankings stabilize, while moderate parameter values provide the most additional ranking information.

Exponential subgraph centrality and total communicability: At β = 0.1, the largest degree-versus-exponential-subgraph intersection distance is slightly below 0.2, while increasing β rapidly reduces distances to eigenvector rankings.At β = 2, eigenvector intersection distances are essentially zero for all but the Minnesota road network.
Exponential subgraph centrality and total communicability: Networks with large relative spectral gaps stabilize rapidly, whereas Minnesota’s spectral gap below 0.001 produces much slower ranking convergence.The Minnesota road network also differs structurally through near-planarity, large diameter, and a more regular degree distribution.
Exponential subgraph centrality and total communicability: Successive exponential-based rankings differ little overall, with a maximum intersection distance of 0.25, occurring as β rises from 0.1 to 0.5 for exponential subgraph centrality on as-735.The largest successive-parameter changes generally occur as β increases to 2, after which distances drop.
Exponential subgraph centrality and total communicability: For β < 0.5, exponential subgraph centrality and total communicability closely match degree rankings, whereas for β ≥ 2 they are essentially identical to eigenvector rankings.The intermediate range 0.5 < β < 2 therefore provides the most ranking information beyond degree and eigenvector centrality.
Resolvent subgraph and Katz centrality: For resolvent subgraph and Katz centrality, rankings remain degree-like below roughly 0.5·1/λ1 and become eigenvector-like above roughly 0.9·1/λ1.The most additional ranking information is obtained at moderate α values; successive-α intersection distances remain below 0.08 overall.
Total communicability: In directed networks, broadcast total communicability approaches out-degree rankings as β approaches 0 and converges toward x1 rankings as β increases.On wiki-Vote, the compared rankings reach zero intersection distance by β = 0.5; on wb-cs-Stanford, the distance falls to about 0.04 by β = 5.