Back to Details

algo-net-centrality

Compare original and translation side by side

🇺🇸

Original

English
🇨🇳

Translation

Chinese

Network Centrality Metrics

网络中心性指标（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.
Centrality指标用于量化网络中节点的重要性。四种经典指标：Degree（连接数）、Betweenness（桥接角色）、Closeness（邻近性）、Eigenvector（连接质量）。每种指标从不同维度体现节点的重要性。算法复杂度从Degree的O(V+E)到Betweenness的O(V×E)不等。

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.
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

阶段1：输入验证

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

阶段2：核心算法

  1. Degree centrality: C_D(v) = deg(v) / (N-1). O(V+E).
  2. Betweenness centrality: C_B(v) = Σ(σ_st(v) / σ_st) for all s,t pairs. Fraction of shortest paths through v. O(V×E).
  3. Closeness centrality: C_C(v) = (N-1) / Σd(v,u). Inverse of average shortest path. O(V×(V+E)).
  4. Eigenvector centrality: Score proportional to sum of neighbors' scores. Power iteration until convergence. O(k×E).
  1. Degree Centrality：C_D(v) = deg(v) / (N-1)。时间复杂度O(V+E)。
  2. Betweenness Centrality：C_B(v) = Σ(σ_st(v) / σ_st)，遍历所有s,t节点对。表示经过节点v的最短路径占比。时间复杂度O(V×E)。
  3. Closeness Centrality：C_C(v) = (N-1) / Σd(v,u)。即平均最短路径的倒数。时间复杂度O(V×(V+E))。
  4. Eigenvector Centrality：节点得分与其邻居得分之和成正比。通过幂迭代直至收敛。时间复杂度O(k×E)。

Phase 3: Verification

阶段3：验证

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.
检查：中心性值已归一化至[0,1]区间。不同指标得出的Top节点可能不同——这是正常现象且具有参考价值。结合领域知识对Top5节点进行合理性检查。 检查点： 所有指标计算完成，Top节点符合直觉逻辑。

Phase 4: Output

阶段4：输出

Return centrality scores with multi-metric comparison.
返回中心性得分及多指标对比结果。

Output Format

输出格式

json
{
  "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}
}
json
{
  "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):
NodeDegreeBetweennessClosenessEigenvector
A0.50 (2/4)0.0000.571 (4/7)0.452
B0.50 (2/4)0.0000.571 (4/7)0.452
C0.75 (3/4)0.6670.800 (4/5)0.628
D0.50 (2/4)0.5000.667 (4/6)0.386
E0.25 (1/4)0.0000.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.
输入： 5节点无向图（桥接拓扑）：边集合 = {(A,B), (A,C), (B,C), (C,D), (D,E)}
    A --- B
     \  /
      C
      |
      D --- E
预期中心性值（按N-1=4归一化）：
节点DegreeBetweennessClosenessEigenvector
A0.50 (2/4)0.0000.571 (4/7)0.452
B0.50 (2/4)0.0000.571 (4/7)0.452
C0.75 (3/4)0.6670.800 (4/5)0.628
D0.50 (2/4)0.5000.667 (4/6)0.386
E0.25 (1/4)0.0000.500 (4/8)0.201
验证：C是桥接节点——在所有四个指标中均为最高。E是边缘节点——所有指标均为最低。A和B对称（得分相同）。D的Betweenness非零（桥接C和E），但Degree低于C。

Edge Cases

边缘情况

InputExpectedWhy
Star graphCenter has max all centralitiesHub dominates in all metrics
Disconnected graphCloseness undefined for disconnected pairsUse harmonic centrality instead
Directed graphIn-degree ≠ out-degree centralityPopularity (in) vs activity (out)
输入预期结果原因
星型图中心节点的所有中心性指标均为最高中心枢纽在所有维度占主导
非连通图非连通节点对的Closeness未定义请改用调和中心性（harmonic centrality）
有向图入度中心性≠出度中心性受欢迎度（入度）vs 活跃度（出度）

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).
  • 非连通图：当节点无法相互到达时，Closeness Centrality未定义。可使用调和中心性替代：C_H(v) = Σ(1/d(v,u))。
  • 规模依赖性：原始中心性值取决于网络规模。跨网络比较时请使用归一化版本。
  • Betweenness计算成本高：O(V×E)的时间复杂度使其在超大规模网络（数百万节点）中不切实际。可使用近似算法（随机采样最短路径）。
  • 动态网络：快照中的中心性可能无法反映长期影响力。存在时间中心性指标，但复杂度更高。
  • 指标间相关性：在许多真实网络中，中心性指标存在相关性。但指标间的差异往往最具参考价值（高Degree但低Betweenness=本地枢纽，而非桥接节点）。

References

参考资料

  • For centrality metric comparison framework, see 
    references/metric-comparison.md
  • For approximate betweenness algorithms, see 
    references/approximate-betweenness.md
  • 中心性指标对比框架，请参考
    references/metric-comparison.md
  • 近似Betweenness算法，请参考
    references/approximate-betweenness.md