Source-linked AI summary
Axioms for Centrality
Paolo Boldi, Sebastiano Vigna
TL;DR
The paper asks how centrality measures can be assessed when centrality lacks agreed conceptual and measurement foundations. It surveys classic indices, evaluates them axiomatically, and checks them through information-retrieval experiments. Harmonic centrality emerges as a simple measure that satisfies the axioms and provides a sensible notion for arbitrary directed graphs.
Problem
Centrality lacks consensus about its conceptual foundations and proper measurement procedures, despite its importance as a structural attribute of social networks.
Method
The paper surveys classic centrality measures, tests them against formal axioms, and evaluates their rankings in an information-retrieval setting using GOV2.
Results
Harmonic centrality is a simple distance-based measure that satisfies all proposed axioms, is almost identical to closeness on undirected connected networks, and applies sensibly to arbitrary directed graphs.
Takeaways & Limitations
Distance-based measures are relevant to information retrieval, and harmonic centrality is presented as a good general-purpose centrality index.
Takeaways & Limitations
Information-retrieval results may differ with other collections or ways of generating query-associated graphs.
Abstract
from arXiv · showhide
Given a social network, which of its nodes are more central? This question has been asked many times in sociology, psychology and computer science, and a whole plethora of centrality measures (a.k.a. centrality indices, or rankings) were proposed to account for the importance of the nodes of a network. In this paper, we try to provide a mathematically sound survey of the most important classic centrality measures known from the literature and propose an axiomatic approach to establish whether they are actually doing what they have been designed for. Our axioms suggest some simple, basic properties that a centrality measure should exhibit. Surprisingly, only a new simple measure based on distances, harmonic centrality, turns out to satisfy all axioms; essentially, harmonic centrality is a correction to Bavelas's classic closeness centrality designed to take unreachable nodes into account in a natural way. As a sanity check, we examine in turn each measure under the lens of information retrieval, leveraging state-of-the-art knowledge in the discipline to measure the effectiveness of the various indices in locating web pages that are relevant to a query. While there are some examples of this comparisons in the literature, here for the first time we take into consideration centrality measures based on distances, such as closeness, in an information-retrieval setting. The results match closely the data we gathered using our axiomatic approach. Our results suggest that centrality measures based on distances, which have been neglected in information retrieval in favour of spectral centrality measures in the last years, are actually of very high quality; moreover, harmonic centrality pops up as an excellent general-purpose centrality index for arbitrary directed graphs.
1 Introduction
The paper develops a formal framework for assessing centrality measures using axioms, then checks them in information retrieval. It argues that simple distance-based measures, especially harmonic centrality, perform surprisingly well.
- The paper seeks centrality measures that are robust on arbitrary directed, possibly disconnected graphs and have clear combinatorial interpretations.
- It compares popular centrality measures using axioms designed to capture specific intended properties.
- In an information-retrieval experiment, documents matching queries are extracted from GOV2 and ranked by centrality on the retrieved-document subgraph.
- Distance-based measures, particularly harmonic centrality, are suggested to outperform some sophisticated indices used in the literature.
- The axioms provide a formal conceptual framework for understanding centrality measures and organize scattered results from social and network sciences.
2 A Historical Account
Centrality is widely used to characterize influential nodes, but researchers lack consensus about its meaning and measurement. The paper surveys classical measures and contrasts combinatorial distance- and path-based approaches with spectral techniques.
- The literature includes many alternative proposals, while this paper focuses on ten classical centrality measures.
- Centrality research spans social, organizational, political, communication, biological, and network contexts, but its conceptual foundations and measurement procedures remain disputed.
- The star-center intuition supports multiple measures: largest degree, shortest average distance, and greatest shortest-path betweenness.
- Combinatorial measures: Degree counts incoming links, closeness uses reciprocal distance sums, betweenness counts shortest paths, and Katz weights incoming paths by β^t.
- Spectral measures: Spectral approaches derive centrality from linear algebra, including dominant eigenvectors, random-walk stationary distributions, PageRank, and HITS.
3 Definitions and conventions
The paper formalizes directed graphs and the graph-theoretic concepts needed to define centrality measures, including paths, components, distances, and normalized matrices.
- A directed graph consists of nodes and arcs, with x → y indicating an arc from source x to target y.
- Paths follow arc directions, whereas walks may traverse either direction.
- Strongly connected components require directed paths between every pair, and terminal components have no arcs toward other components.
- Distance is the shortest-path length, with ∞ assigned when no path exists; reachable and coreachable sets distinguish the two directions.
- Row ℓ1-normalization produces a stochastic matrix when no row is null, while Iverson notation represents predicates as zero-one values.
3.1 Geometric measures
Geometric centrality measures assign importance from distance structure, but classical closeness handles disconnected directed graphs poorly. Harmonic centrality replaces arithmetic distance aggregation with a harmonic formulation that incorporates unreachable nodes.
- Geometric measures depend only on how many nodes occur at each distance from a node.
- Indegree is a geometric baseline because it counts nodes at distance one, although it is easy to spam.
- Closeness: Bavelas’s closeness is the reciprocal of a distance sum, but its original definition requires strongly connected graphs.
- Closeness: Patching closeness by excluding unreachable nodes introduces bias toward nodes with small coreachable sets.
- Closeness: Lin’s index adjusts closeness using the number of coreachable nodes and was described as a reasonable solution to closeness’s infinite-distance problem.
- Harmonic centrality: Harmonic centrality uses the reciprocal of a denormalized harmonic mean of distances to address unreachable pairs.
- Harmonic centrality: Harmonic centrality is strongly correlated with closeness in simple networks while also accounting for nodes that cannot reach a target.
3.2 Spectral measures
Spectral measures derive centrality from dominant eigenvectors of graph-related matrices, with variants corresponding to different path-weighting or normalization choices. Their behavior can become problematic on graphs lacking strong connectivity, while Katz and PageRank are closely related through matrix normalization.
- Spectral measures: Spectral measures compute a left dominant eigenvector of a matrix derived from the graph.Different matrix modifications produce different centrality measures, with existence and uniqueness typically grounded in nonnegative-matrix theory.
- The left dominant eigenvector: The dominant eigenvector iteratively replaces each node’s score with the sum of predecessor scores, normalizing after each update until convergence.This process starts with equal scores for all nodes.
- The left dominant eigenvector: Dominant eigenvectors may be zero or nonzero on non-terminal strongly connected components, depending on component dominant eigenvalues.Thus, they fail to behave as expected on graphs that are not strongly connected.
- Seeley’s index: Seeley’s index divides each node’s reputation equally among successors, producing a stochastic matrix and a stationary Markov-chain interpretation.On symmetric graphs, Seeley’s index collapses to degree up to normalization, but only certain terminal components receive nonzero scores.
- Katz and PageRank: Katz sums incoming paths with attenuation factor β, requiring β < 1/λ for finiteness, while PageRank uses analogous path weighting with damping factor α and preference vector v.PageRank’s Markov-chain formulation may require patching null rows, whereas the paper adopts an unpatched definition with uniform preference by default.
- Katz and PageRank: Katz and PageRank differ only by a constant factor and the ℓ1 normalization applied to the adjacency matrix.The normalized limit of Katz as β → 1/λ becomes a dominant eigenvector, with dependence on v when that eigenvector is not unique.
- SALSA: SALSA can be computed without iteration by finding components in the symmetric graph induced by A^T A and combining indegree and component-size ratios.The intersection graph construction can still require time proportional to the relevant graph-product quantity.
3.3 Path-based measures
Path-based measures assess centrality through shortest paths or broader collections of paths entering a node. This perspective also gives spectral measures a combinatorial interpretation through path counts and weighted path sums.
- Path-based measures: Path-based measures examine all shortest paths or all paths entering a node, with indegree representing incoming paths of length one.Shortest-path measures therefore extend beyond merely detecting whether a path exists.
- Betweenness centrality: Betweenness centrality measures the fraction of shortest paths from y to z that pass through x.Its intuition is that nodes traversed by many shortest paths serve as important network junctions.
- Spectral measures as path-based measures: Spectral measures can also be interpreted as path-based because powers of the adjacency matrix encode suitable collections of paths.This connects algebraic centrality computations with combinatorial path structure.
- Spectral measures as path-based measures: The dominant eigenvector captures the relative growth of incoming path counts as path length k increases.The power-method vector 1A^k associates each node with the number of incoming paths of length k before normalization.
- Weighted paths: Seeley’s index sums weights of incoming paths, while Katz and PageRank replace limits with infinite sums and attenuate paths by β^t or α^t.HITS and SALSA admit analogous interpretations using alternate back-and-forth paths.
4 Axioms for Centrality
The paper evaluates centrality measures with formal axioms designed to capture predictable behavior under network-size, density, and arc changes. These axioms address the difficulty of comparing measures and are tested on structured graph families, including disconnected networks.
- Motivation: Comparing centrality measures is difficult because small social-science datasets limit conclusions, while larger networks lack ground truth and efficient implementations.The paper argues that some measures may reward nodes that are not genuinely central.
- Axiomatic approach: The paper uses axioms as necessary conditions for centrality measures to behave predictably without prescribing a single definition of centrality.The axioms provide formal, provable information more precise than informal claims about correlations or failure modes.
- Axiom design: Axiom design requires clear semantics, exact evaluability, avoidance of misleading finite counterexamples, and invariance under graph isomorphism.The measures are assumed to depend on graph structure rather than node labels.
- Axioms: The proposed axioms examine changes in graph size, local density, and arc additions, expecting larger groups, denser neighborhoods, and newly targeted nodes to gain importance.These reactions are intended as basic, intuitive properties of centrality scores.
- Evaluation strategy: The analysis evaluates measures exactly on representative network classes, using strongly connected vertex-transitive graphs such as cliques and directed cycles to simplify computation.These graph families span extreme density cases and support controlled comparisons.
- Size axiom: The size axiom requires sufficiently large cycle nodes to outrank fixed-size clique nodes, and sufficiently large clique nodes to outrank fixed-size cycle nodes.It tests both directions so measures cannot satisfy only one asymptotic case.
- Density axiom: The density axiom compares equal-sized clique and cycle communities joined by a bidirectional bridge, requiring the clique-side bridge node to outrank the cycle-side node.Although nearly all measures satisfy it on strongly connected graphs, it tests handling of partially disconnected structures.
- Score monotonicity: Rank monotonicity is left for future work because score monotonicity alone can permit an added arc to increase a target’s score while perversely lowering its rank.The omitted axiom would constrain the scores of nodes below or tied with the target.
5 Proofs and Counterexamples
The paper evaluates centrality measures against axioms using explicit score formulae, symmetry reductions, proofs, and counterexamples. The density axiom is established for several spectral measures, while score-monotonicity distinguishes harmonic centrality from measures with counterexamples or qualifications.
- Evaluation strategy: 33 statements are verified across eleven centralities and three axioms using closed-form calculations for size and density, plus proofs or counterexamples for score monotonicity.The analysis uses explicit formulae and direct arguments rather than a single computational test.
- Size analysis: Table 1 reduces the size-axiom analysis to two scores—one for clique nodes and one for cycle nodes—using graph symmetry.For some spectral measures with multiple solutions, the reported solution comes from the power method initialized uniformly.
- Density analysis: Table 2 analyzes the bridged clique-cycle graph, where strong connectivity removes uniqueness issues and supports explicit density-axiom proofs.Spectral indices require solving parametric equations, while geometric and path-based measures use finite summations.
- Density results: The dominant eigenvector, HITS, Katz’s index for β ∈(0 . . 1/λ), and PageRank with constant preference satisfy the density axiom.For spectral measures, the proof establishes the stronger inequality ℓ > r even when k ≠ p, provided k,p ≥3.
- Score monotonicity: Adding x →y increases harmonic centrality and Katz’s score of y, whereas closeness, Lin, betweenness, dominant-eigenvector-based measures, and SALSA have counterexamples or unchanged scores.For SALSA, y falls from 1/6 to 2/15; for closeness, y falls from 1 to 1/2.
- Score monotonicity: PageRank’s score-monotonicity behavior depends on normalization: its score can increase after adding x →y, while forced ℓ1-normalized scores may fail the axiom.The normalized two-node example leaves the second node’s score equal to 1/(1 + α) before and after the addition.
6 Roundup
The paper consolidates its axiomatic evaluation of centrality measures and finds that harmonic centrality uniquely satisfies all proposed axioms. The results also expose distinct shortcomings in closeness and spectral measures, while noting boundaries of some analyses.
- Table 3 reports, for each centrality measure and axiom, whether the axiom is satisfied.
- Only harmonic centrality satisfies all the axioms.
- Closeness has the worst axiomatic behavior, failing every proposed axiom because very far nodes can dominate its score.
- All spectral centrality measures are sensitive to density, while non-attenuated spectral measures are also non-monotone.
- Measures satisfying the density axiom have no watershed, whereas closeness, Lin’s index, and betweenness satisfy it only under restricted conditions.
- The geometric-index results extend from directed cycles to symmetric cycles when k > 3, but analogous spectral calculations remain difficult.
7 Sanity check via information retrieval
The paper uses information-retrieval evaluation on query-induced web graphs to test whether its axioms identify effective centrality measures. Harmonic centrality performs best overall, while results vary after removing intra-host links and simple measures can outperform sophisticated alternatives.
- The sanity check ranks query-induced subgraphs from the GOV2 web collection using centrality measures and compares them with information-retrieval effectiveness measures.The collection contains about 25 million documents and 149 queries; each Boolean query induces a graph of matching pages.
- The evaluation focuses on Precision at 10 (P@10) and NDCG@10, with additional results after removing intra-host links.
- The experiments have limited statistical significance because about half of the queries receive null scores even for the best documents.
- Harmonic centrality has the best overall scores, whereas removing nepotistic links makes SALSA and PageRank lead, with lower best performance.
- Closeness performs very badly, and betweenness performs essentially like an arbitrary document ordering.
- Four naive measures combine density-based scores with size-based scores, and all satisfy the proposed axioms.The density scores use indegree or the negative β-measure, while size scores count coreachable or weakly reachable nodes.
- These simple measures outperform most sophisticated alternatives in the test, supporting the usefulness of the proposed axioms for designing centralities.
8 Conclusions and future work
The paper evaluates ten classical centrality measures and harmonic centrality through axioms, finding harmonic centrality to be a simple, effective notion for arbitrary directed graphs. Information-retrieval experiments support these conclusions, while the authors acknowledge that the axioms are partly arbitrary and the experiments remain preliminary.
- The paper proves or disproves the proposed axioms for ten classical centrality measures and for harmonic centrality.
- Harmonic centrality is introduced as a variant of Bavelas’s closeness centrality and provides a sensible centrality notion for arbitrary directed graphs.It is almost identical to closeness centrality on undirected, connected networks.
- Information-retrieval experiments confirm the axiomatic findings and show that harmonic centrality is a very simple measure providing a good notion of centrality.
- The formulation of the axioms contains a measure of arbitrariness, which the authors regard as useful for developing an ecosystem of axioms.
- The information-retrieval experiments are only a beginning, and different collections or query-graph constructions may produce different results.