Centrality Measures in Networks

Why This Matters

When you're analyzing networks—whether social media platforms, transportation systems, or the web itself—the fundamental question is always: which nodes actually matter? Centrality measures give you the mathematical toolkit to answer that question, but here's the catch: "importance" means different things in different contexts. A node that spreads information fastest isn't necessarily the one controlling information flow, and the most connected node might not be the most influential. You're being tested on your ability to select the right centrality measure for the right question and to understand why each measure captures a different dimension of network importance.

These concepts connect directly to core themes in networked life: information cascades, network resilience, influence dynamics, and search algorithms. When an exam question asks about identifying influential users, finding network vulnerabilities, or explaining how Google ranks pages, you need to know which centrality measure applies and what it reveals. Don't just memorize formulas—know what structural property each measure captures and when you'd choose one over another.

---

Counting Connections: Direct Relationship Measures

The simplest way to measure importance is to count how many connections a node has. These measures focus on a node's immediate neighborhood in the network.

Degree Centrality

• Counts the number of direct edges connected to a node—the most intuitive measure of network prominence
• High-degree nodes are local hubs that can reach many others in a single step, making them natural candidates for spreading information quickly
• Limitation: treats all connections equally, ignoring whether a node connects to influential players or peripheral ones

Katz Centrality

• Extends degree by counting all paths reaching a node, with longer paths weighted less heavily using a damping factor $\alpha$
• Captures indirect influence by recognizing that a node reachable through many routes has structural importance beyond its immediate neighbors
• Useful when indirect connections matter—like in networks where information or resources flow through intermediaries

---

Position in the Network: Path-Based Measures

Some nodes matter not because of how many connections they have, but because of where they sit in the network structure. These measures examine a node's position relative to all other nodes.

Closeness Centrality

• Measures average shortest path distance to all other nodes—lower average distance means higher closeness centrality
• High-closeness nodes can reach everyone quickly, making them efficient broadcasters of information or disease
• Calculated as the inverse of average path length: $C_C(v) = \frac{n-1}{\sum_{u \neq v} d(v,u)}$ where $d(v,u)$ is the shortest path between nodes

Betweenness Centrality

• Counts how often a node appears on shortest paths between other node pairs—identifies bridges and brokers
• High-betweenness nodes control information flow and can act as gatekeepers, bottlenecks, or points of failure
• Critical for network resilience analysis: removing high-betweenness nodes can fragment a network even if they have few direct connections

---

Quality Over Quantity: Influence-Weighted Measures

Being connected to important nodes makes you more important. These recursive measures define centrality in terms of the centrality of a node's neighbors.

Eigenvector Centrality

• Weights connections by neighbor importance—your centrality score is proportional to the sum of your neighbors' scores
• Solves the recursive problem mathematically using the principal eigenvector of the adjacency matrix
• Reveals "hidden influencers" who may have moderate degree but connect to powerful nodes in the network

PageRank

• Google's adaptation of eigenvector centrality for directed networks, adding a damping factor to model random web surfing
• Nodes receive "votes" from incoming links, with each vote weighted by the linking page's own importance divided by its out-degree
• The damping factor (typically $d = 0.85$) accounts for users randomly jumping to new pages rather than following links indefinitely

---

Distinguishing Roles: The HITS Framework

Not all important nodes play the same role. The HITS algorithm recognizes that some nodes are valuable for what they link to, while others are valuable for who links to them.

Hub and Authority Scores

• Authorities are nodes that many hubs point to—they contain valuable content or resources that others reference
• Hubs are nodes that point to many authorities—they serve as curators or directories that help users find good content
• Mutually reinforcing definitions: good hubs link to good authorities, and good authorities are linked by good hubs, solved iteratively

---

Quick Reference Table

---

Self-Check Questions

1. A social network analyst wants to find users who could spread a rumor to the entire network in the fewest steps. Which centrality measure should they use, and why would degree centrality be insufficient?

2. Compare betweenness centrality and closeness centrality: both involve shortest paths, but what different structural properties do they capture? Give an example of a node that would score high on one but low on the other.

3. Why might a node with relatively low degree still have high eigenvector centrality? What does this reveal about network influence that simple connection counting misses?

4. If you were analyzing a citation network to find the most authoritative papers, would you use PageRank or HITS? Explain the tradeoff and when you might prefer the alternative.

5. A network engineer needs to identify which routers, if removed, would most disrupt communication across the network. Which centrality measure directly addresses this question, and what structural role do these critical nodes play?