Source-linked AI summary
Centrality Measures in Networks
Francis Bloch, Matthew O. Jackson, Pietro Tebaldi
TL;DR
The paper addresses how to distinguish the many centrality measures used to represent network position. It introduces nodal statistics and characterizes prominent measures as additively separable weighted treatments of them, yielding a taxonomy and results on agreement among measures. It also identifies scope limits for the agreement characterization and develops directions for new measures.
Problem
Little is known about how to distinguish the diverse centrality measures used to capture different facets of network position.
Method
The paper defines nodal statistics and characterizes centrality measures through additively separable, linear aggregation with distance-dependent weighting.
Results
The framework yields seven types of standard centrality measures, characterizes trees where centrality rankings coincide, and identifies axioms for selected path-based measures.
Takeaways & Limitations
Centrality measures can be compared by the positional information they use and how they weight relationships at different distances.
Takeaways & Limitations
For networks that are not trees, characterizing all networks on which centrality measures coincide remains an open problem because cycles can make nodal statistics differ substantially.
Abstract
from arXiv · showhide
We show that prominent centrality measures in network analysis are all based on additively separable and linear treatments of statistics that capture a node's position in the network. This enables us to provide a taxonomy of centrality measures that distills them to varying on two dimensions: (i) which information they make use of about nodes' positions, and (ii) how that information is weighted as a function of distance from the node in question. The three sorts of information about nodes' positions that are usually used -- which we refer to as "nodal statistics" -- are the paths from a given node to other nodes, the walks from a given node to other nodes, and the geodesics between other nodes that include a given node. Using such statistics on nodes' positions, we also characterize the types of trees such that centrality measures all agree, and we also discuss the properties that identify some path-based centrality measures.
1 Introduction
The paper develops a taxonomy of prominent centrality measures by showing that they process nodal statistics additively and differ in the information used and its distance weighting.
- 1 Introduction: Nodal statistics capture a node’s position through paths to other nodes, walks to other nodes, or geodesics between other nodes that include it.Paths describe neighborhood structure, walks allow cycles, and geodesics measure intermediary roles.
- 1 Introduction: Each prominent centrality measure can be represented as an additively separable weighted average of a nodal statistic.The axioms involve monotonicity, anonymity, and additivity, with weights changing the relative importance of nearby and distant relationships.
- 1 Introduction: Prominent centrality measures differ according to which nodal statistics they use and how they weight information across distances.The framework reduces twelve possible combinations to seven types because some combinations are redundant or inappropriate.
- 1 Introduction: The taxonomy is intended to help determine which centrality measure is appropriate in different contexts.The paper emphasizes that the appropriate measure depends on the application and the aspect of network position being captured.
- 1 Introduction: The paper further characterizes degree centrality and a weighted-neighborhood measure through axioms concerning immediate connections, shortest paths, proximity, and marginal credit.These results are presented as an initial step toward characterizing additional centrality measures and nodal statistics.
- 1 Introduction: The framework identifies when all centrality rankings coincide by examining whether their corresponding nodal statistics generate the same order.This criterion is used to characterize the trees for which all centrality measures coincide.
2.1 Background Definitions and Notation
This section defines networks, paths, walks, geodesics, distances, and trees, establishing notation for centrality analysis on directed, undirected, weighted, and signed networks.
- 2.1 Background Definitions and Notation: A network is represented by an adjacency matrix g ∈ R^n×n, where nonzero entries indicate edges between nodes.The characterization results apply to directed and undirected networks, including weighted and signed links.
- 2.1 Background Definitions and Notation: The degree of a node is the number of incident edges in an undirected network, with corresponding outdegree and indegree notions for directed networks.Nodes are indexed from 1 through n, and λmax(g) denotes the largest right-hand-side eigenvalue of a nonnegative g.
- 2.1 Background Definitions and Notation: A walk may revisit nodes, whereas a path is a succession of distinct nodes connected by edges.Two nodes are connected when a path exists between them.
- 2.1 Background Definitions and Notation: A geodesic is a shortest path, and the distance between two nodes is the number of edges in such a path.The notation also records the number of geodesics and how many involve a specified node.
- 2.1 Background Definitions and Notation: In unweighted unsigned graphs, powers of the adjacency matrix provide information about walks of specified lengths.This connects matrix notation with path-based network statistics.
- 2.1 Background Definitions and Notation: A tree is an undirected unweighted graph with a unique path between every pair of nodes.Choosing a root induces an orientation by comparing nodes’ geodesic distances from that root.
2.2 Some Prominent Centrality Measures
The section surveys centrality measures based on degree, distances, walks, eigenvector prestige, diffusion, and intermediary geodesics, highlighting how each captures a different network position.
- 2.2 Some Prominent Centrality Measures: Degree centrality counts a node’s edges, capturing connectivity or popularity but omitting broader network architecture.In directed networks, indegree and outdegree have distinct interpretations related to receiving and broadcasting.
- 2.2 Some Prominent Centrality Measures: Closeness centrality aggregates distances from a node to others, with variants based on distance sums, inverses, and normalization.Harmonic centrality uses inverse distances to reduce the influence of very large or infinite distances.
- 2.2 Some Prominent Centrality Measures: As δ approaches 1, decay centrality measures component size; as δ approaches 0, it becomes proportional to degree centrality.The measure models effects transmitted along shortest paths that may decay with distance.
- 2.2 Some Prominent Centrality Measures: Katz-Bonacich centrality counts walks from a node using exponential discounting, giving shorter walks greater weight.Its interpretation depends on a discount factor because walk lengths are unbounded.
- 2.2 Some Prominent Centrality Measures: Eigenvector centrality assigns prestige through the summed centralities of a node’s neighbors and uses the associated largest-eigenvalue eigenvector.It is self-referential but has a well-defined fixed point under the stated network conditions.
- 2.2 Some Prominent Centrality Measures: As L → ∞, diffusion centrality converges to Katz-Bonacich centrality when δ < 1/λmax(g), and to eigenvector centrality when δ > 1/λmax(g).At L = 1, diffusion centrality is proportional to degree centrality.
- 2.2 Some Prominent Centrality Measures: Betweenness centrality measures a node’s role in connecting other nodes through the geodesics between them.It accounts for multiple geodesics by using the fraction that pass through the node, while standard betweenness weights geodesics equally by distance.
3 Developing a Taxonomy of Centrality Measures
The paper develops a taxonomy of centrality measures based on which nodal statistics they aggregate and how information across distances is weighted. It characterizes prominent measures through axioms that yield additively separable, discounted sums and identifies specialized path-based cases.
- 3 Developing a Taxonomy of Centrality Measures: Nodal statistics are vectors describing a node’s network position, reducing complex networks to data that capture distinct positional aspects.The paper treats these statistics as inputs to an aggregator that produces centrality measures.
- 3.2 A Characterization of Many Centrality Measures: Monotonicity and anonymity imply representation by a monotone aggregator, while independence further implies additive separability across statistic elements.Theorem 1 establishes the additive representation relative to an anonymous nodal statistic.
- 3.2 A Characterization of Many Centrality Measures: Monotonicity, anonymity, recursivity, and additivity characterize centrality as a discounted sum of successive nodal-statistic elements.The discount factor determines the relative importance of nearby versus distant relationships.
- 3.3 A Taxonomy of Centrality Measures: Standard centrality measures form seven types by combining the nodal statistics they use with their weighting approaches.The taxonomy reduces twelve possible combinations to seven because some combinations are redundant or nonsensical.
- 3 Developing a Taxonomy of Centrality Measures: The three main nodal statistics are neighborhood paths, walks, and intermediary geodesics, each capturing different information about network position.Paths count nodes at distances from a node, walks allow cycles, and intermediary statistics count geodesics between other nodes that include the node.
- 3.3 A Taxonomy of Centrality Measures: Degree centrality uses immediate connections, decay centrality extends reach through distance weighting, and closeness centrality uses hyperbolic rather than exponential weighting.Closeness weights distance ℓ by 1/ℓ, whereas exponential schemes use δ^ℓ.
- 3.4 Path-Based Nodal Statistics: Cycle independence and distance sensitivity characterize weighted neighborhood statistics, while adding long-distance insensitivity reduces the class to degree centrality.Theorem 5 states that the resulting measure is proportional to degree centrality.
4 When do Centrality Measures Agree?
The paper characterizes when centrality measures agree by comparing nodal statistics, first for trees and then for more restrictive regular monotone hierarchies. For non-tree networks, cycles can make neighborhood- and path-based statistics diverge, leaving the general characterization open.
- 4.1 Comparing Centrality Measures on Trees: For non-tree networks, the general class on which centrality measures coincide remains unknown because cycles can sharply separate neighborhood structure from overall path structure.The paper illustrates this issue by contrasting distances with numbers of paths connecting nodes.
- 4.1.1 Monotone Hierarchies: Centrality measures coincide on trees based on neighborhood statistics exactly for monotone hierarchies.The paper defines monotone hierarchies through root-based ordering and recursively ordered subtrees.
- 4.1.1 Monotone Hierarchies: In a monotone hierarchy, neighborhood statistics rank nodes by the paper’s hierarchy order, with ties exactly when the statistics are equal.Proposition 1 states both the ranking equivalence and its converse under the stated tree conditions.
- 4.1.2 Regular Monotone Hierarchies: Regular monotone hierarchies require equal degrees at each root distance, making nodes at the same level symmetric and including stars, lines, and Cayley trees.The hierarchy’s ranking then corresponds completely with distance from the root.
- 4.1.2 Regular Monotone Hierarchies: In regular monotone hierarchies, neighborhood, intermediary, and walk statistics produce the same node ranking, ordered by distance from the root.Proposition 2 also states that any tree outside this class has statistics that disagree in their ordering of some nodes.
5 Concluding Remarks: Potential for New Measures
The paper concludes that its additive framework suggests developing centrality measures with more general discounting, diffusion-based objectives, or multiplicative aggregation. These alternatives may generate rankings that differ from standard measures, although escaping the additive family remains difficult.
- 5 Concluding Remarks: Potential for New Measures: The framework motivates new measures using more general discounting, diffusion or contagion probabilities, and multiplicative aggregation.The proposed directions vary how path lengths are weighted or how nodes’ positional contributions are combined.
- 5 Concluding Remarks: Potential for New Measures: Multiplicative measures could treat nodes at different distances as complementary inputs and reward balanced positional profiles.The passage states that this class could produce rankings different from standard centrality measures.
- 5 Concluding Remarks: Potential for New Measures: Threshold-model extensions can evaluate a node’s marginal value when k other seeds are randomly distributed across the remaining nodes.This constructs a centrality measure around initiating cascades when multiple seeds are required.
- 5 Concluding Remarks: Potential for New Measures: The paper notes that even the proposed multiplicative class may yield rankings equivalent to an additive ordering, making it challenging to escape the additive family.Despite this difficulty, the authors describe the class as new and potentially interesting.
Appendix: Proofs
The appendix proves that anonymity and monotonicity make centrality depend on a node’s nodal statistic through a common monotone function. This establishes the functional representation used in the paper’s characterizations.
- Appendix: Proofs: If two networks give a node the same nodal statistic, monotonicity implies that its centrality must also be the same.The proof derives this by contradiction from the partial-order relation on statistics.
- Appendix: Proofs: Anonymity then ensures a common monotone function maps nodal statistics to centrality across nodes.The proof first constructs node-specific functions and then shows they coincide using a permutation argument.
Proof of Theorems 1-3
The proofs characterize centrality representations through independence, recursivity, and additivity, then use nodal-statistic comparisons to establish ranking results and identify when rankings fail to coincide.
- Representation characterization: Independence, recursivity, and additivity successively constrain the representation to separable functions, distance-based weights, and ultimately a linear form.The argument derives a common function scaled by distance and then uses additivity to establish linearity.
- Representation characterization: Strict sensitivity requires positive parameters δ > 0 and a > 0, while cycle independence reduces the characterization to minimal i-centered subtrees and then trees.The proof constructs line networks and adds links iteratively under the constant marginal values condition.
- Nodal-statistic comparisons: For monotone hierarchies, cumulative neighborhood counts satisfy Q(i,d) ≥ Q(j,d) for adjacent levels, with strict inequality at some distance, so n_i ≻ n_j.The proof compares distance counts along the paths from each node to the root and extends the result by repeated application.
- Nodal-statistic comparisons: In a monotone hierarchy, each node at a higher level has no more successors at any distance than its predecessor, yielding ordered neighborhood statistics.Claim 1 establishes p(i,ℓ) ≥ p(j,ℓ) for adjacent levels, and the resulting distance counts support the ranking comparison.
- Ranking failures: If the tree violates monotone-hierarchy conditions, nodes can have crossing neighborhood rankings, so neither centrality ranking dominates the other.This occurs when adjacent levels reverse degree ordering or when same-level subtrees have conflicting successor-degree orderings.
- Ranking failures: For regular monotone hierarchies, geodesic-path counts are compared by relating paths through a successor to paths through its predecessor.The proof shows that paths through the node farther from the root can be matched against paths through the closer node.
Appendix: Simulations – Differences in Centrality Mea-
The simulations compare five centrality measures across several 40-node network structures and average degrees. Rankings are highly correlated across measures, often above .9 and usually between .8 and 1.
- Simulation design: The study compares degree, decay, closeness, diffusion, and Katz-Bonacich centrality across simulated networks.Networks include Erdos-Renyi, homophilous, and homophilous networks with bridge nodes.
- Simulation design: The simulations use networks with 40 nodes and average degrees of 2, 5, or 10.
- Simulation design: The homophilous designs vary within-group and across-group link probabilities, with bridge nodes connecting across groups.Bridge nodes connect to other nodes with a uniform probability, while non-bridge nodes retain group-dependent probabilities.
- Results: Ranking correlations among centrality measures are often above .9 and usually range from .8 to 1 across simulations.
- Results: Closeness and betweenness are more differentiated from the other measures, while the remaining measures correlate above .98 in Table 2.The authors attribute the generally high correlations partly to nodal statistics moving in similar ways across measures.