Network Centrality Metrics 網路中心性指標
Released已發布Calculate network centrality metrics to identify important nodes in graphs. Use this skill when the user needs to find key influencers, critical infrastructure nodes, or central actors in a network — even if they say 'who is most important in this network', 'key nodes', or 'network influence measurement'.
演算法技能：Network Centrality Metrics 分析與應用。
Overview概述
Centrality measures quantify node importance in a network. Four classical metrics: degree (connections), betweenness (bridge role), closeness (proximity), eigenvector (connection quality). Each captures a different aspect of importance. Complexity ranges from O(V+E) for degree to O(V×E) for betweenness.
When to Use使用時機
Trigger conditions:
- Identifying key influencers or critical nodes in social/organizational networks
- Analyzing network vulnerabilities (which node failure causes most damage)
- Comparing node importance across different dimensions
When NOT to use:
- For group/community detection (use community detection algorithms)
- For information spread modeling (use epidemic models)
Algorithm 演算法
IRON LAW: Different Centrality Metrics Answer DIFFERENT Questions
- Degree: Who has the most connections? (popularity)
- Betweenness: Who bridges communities? (brokerage)
- Closeness: Who can reach everyone fastest? (efficiency)
- Eigenvector: Who is connected to important people? (prestige)
Using the WRONG metric answers the WRONG question. Choose based on
what "important" means in your context.
Phase 1: Input Validation
Build network graph from edge list or adjacency matrix. Determine: directed vs undirected, weighted vs unweighted, connected vs disconnected. Gate: Graph is well-formed, largest connected component identified.
Phase 2: Core Algorithm
- Degree centrality: C_D(v) = deg(v) / (N-1). O(V+E).
- Betweenness centrality: C_B(v) = Σ(σ_st(v) / σ_st) for all s,t pairs. Fraction of shortest paths through v. O(V×E).
- Closeness centrality: C_C(v) = (N-1) / Σd(v,u). Inverse of average shortest path. O(V×(V+E)).
- Eigenvector centrality: Score proportional to sum of neighbors' scores. Power iteration until convergence. O(k×E).
Phase 3: Verification
Check: centrality values normalized [0,1]. Top nodes by each metric may differ — this is expected and informative. Sanity check top-5 against domain knowledge. Gate: All metrics computed, top nodes make intuitive sense.
Phase 4: Output
Return centrality scores with multi-metric comparison.
Output Format輸出格式
{
"centralities": [{"node": "Alice", "degree": 0.85, "betweenness": 0.42, "closeness": 0.71, "eigenvector": 0.90}],
"metadata": {"nodes": 500, "edges": 2000, "directed": false, "connected_components": 1}
}
Examples範例
Sample I/O
Input: 5-node undirected graph (bridge topology): edges = {(A,B), (A,C), (B,C), (C,D), (D,E)}
A --- B
\ /
C
|
D --- E
Expected centralities (normalized by N-1 = 4):
| Node | Degree | Betweenness | Closeness | Eigenvector |
|---|---|---|---|---|
| A | 0.50 (2/4) | 0.000 | 0.571 (4/7) | 0.452 |
| B | 0.50 (2/4) | 0.000 | 0.571 (4/7) | 0.452 |
| C | 0.75 (3/4) | 0.667 | 0.800 (4/5) | 0.628 |
| D | 0.50 (2/4) | 0.500 | 0.667 (4/6) | 0.386 |
| E | 0.25 (1/4) | 0.000 | 0.500 (4/8) | 0.201 |
Verify: C is the bridge — highest in ALL four metrics. E is the periphery — lowest in all metrics. A and B are symmetric (identical scores). D has nonzero betweenness (bridges C to E) but lower degree than C.
Edge Cases
| Input | Expected | Why |
|---|---|---|
| Star graph | Center has max all centralities | Hub dominates in all metrics |
| Disconnected graph | Closeness undefined for disconnected pairs | Use harmonic centrality instead |
| Directed graph | In-degree ≠ out-degree centrality | Popularity (in) vs activity (out) |
Gotchas注意事項
- Disconnected graphs: Closeness centrality is undefined when nodes can't reach each other. Use harmonic centrality: C_H(v) = Σ(1/d(v,u)) as an alternative.
- Scale dependence: Raw centrality values depend on network size. Use normalized versions for cross-network comparison.
- Betweenness is expensive: O(V×E) makes it impractical for very large networks (millions of nodes). Use approximation algorithms (random sampling of shortest paths).
- Dynamic networks: Centrality in a snapshot may not reflect influence over time. Temporal centrality metrics exist but are more complex.
- Correlation between metrics: In many real networks, centrality metrics are correlated. But the DIFFERENCES are often the most informative (high degree but low betweenness = local hub, not broker).
References參考資料
- For centrality metric comparison framework, see
references/metric-comparison.md - For approximate betweenness algorithms, see
references/approximate-betweenness.md