3步锁定社交网络核心人物：数学教授用“枢纽”比喻，教你算透影响力！：典型例题精讲
适用年级
奥数
难度等级
⭐⭐⭐
资料格式
PDF 可打印
最近更新
2025-12-20
```html
💡 阿星精讲：网络科学 的本质
想象一下，你所在的班级微信群，谁是最核心的人物？是那个朋友最多、总能拉人进群的“社交达人”，还是那个虽然朋友不多，但却是两个小团体之间唯一沟通桥梁的“关键联系人”？网络科学，就是用数学的语言，来量化这些“影响力权重”。我们把每个人看作一个“节点”，把好友关系看作连接节点的“边”。
度中心性：就像统计一个人的直接好友数。节点 \( i \) 的度中心性 \( C_D(i) \) 就是它的连接数 \( k_i \)。朋友越多，影响力可能越大。
介数中心性：更像“信息桥梁”的衡量指标。它计算一个节点在所有其他节点对最短路径中出现的频率。节点 \( v \) 的介数中心性 \( C_B(v) \) 公式为：\( C_B(v) = \sum_{s eq v eq t} \frac{\sigma_{st}(v)}{\sigma_{st}} \)，其中 \( \sigma_{st} \) 是节点 \( s \) 到 \( t \) 的最短路径总数，\( \sigma_{st}(v) \) 是经过 \( v \) 的最短路径数。谁垄断了关键通道，谁就拥有战略影响力。
🔥 经典例题精析
题目：下图是一个简单的社交网络，节点代表人，边代表好友关系。请计算节点 \( A \) 和节点 \( D \) 的度中心性和归一化介数中心性（假设图中所有边权重为1）。网络结构：\( A-B, A-C, B-C, B-D, C-D, D-E \)。（提示：网络可视为无向图）。
阿星拆解：
第一步：理解网络。根据描述，我们可以画出5个节点（A, B, C, D, E）和6条边。这是一个连通图。
第二步：计算度中心性。直接统计每个节点的连接边数。
节点 \( A \) 的度 \( k_A = 2 \)（连接B和C）。
节点 \( D \) 的度 \( k_D = 3 \)（连接B, C, E）。
因此，度中心性 \( C_D(A)=2 \), \( C_D(D)=3 \)。
第三步：计算介数中心性。我们需要找出所有节点对之间的最短路径，并检查A和D出现在其中的比例。
1. 节点对总数（不包括自身）：\( \binom{5}{2} = 10 \)对。
2. 列出所有最短路径，并标记经过A或D的：
- (B, C): 路径有 B-A-C 和 B-C。经过A的占 \( \frac{1}{2} \)。
- (B, E): 唯一最短路径 B-D-E。经过D。
- (C, E): 唯一最短路径 C-D-E。经过D。
- (A, E): 最短路径有 A-B-D-E 和 A-C-D-E。两条都经过D，不经过A（起点不算中介）。
- (A, D): 最短路径有 A-B-D 和 A-C-D。不经过其他中介节点。
- 其他节点对（如A-B, A-C, B-D, C-D）的最短路径直接相连，不经过第三节点。
3. 计算 \( C_B(A) \)：只出现在(B,C)对中，且贡献 \( \frac{1}{2} \)。所以 \( C_B(A) = 0.5 \)。
4. 计算 \( C_B(D) \)：出现在(B,E)、(C,E)、(A,E)三对中。每对贡献1。所以 \( C_B(D) = 3 \)。
5. 归一化：对于无向图，介数中心性归一化常数为 \( \frac{(n-1)(n-2)}{2} \)，这里 \( n=5 \)，常数为 \( \frac{4 \times 3}{2} = 6 \)。
因此，归一化介数中心性：\( C'_B(A) = \frac{0.5}{6} \approx 0.0833 \)， \( C'_B(D) = \frac{3}{6} = 0.5 \)。
口诀：度中心性看连接，介数中心看桥接；好友多未必是关键，信息枢纽权重高。
🚀 举一反三：变式挑战
将社交网络背景转换为“城市间航班网络”，节点代表城市，边代表直飞航线（无向）。已知度中心性最高的城市 \( X \) 有 \( 8 \) 条直飞航线，而城市 \( Y \) 的归一化介数中心性为 \( 0.2 \)。若网络共有 \( 10 \) 个城市，请问城市 \( Y \) 的原始介数中心性 \( C_B(Y) \) 是多少？并解释 \( X \) 和 \( Y \) 可能分别代表哪种类型的航空枢纽。
在一个科研合作网络中，已知节点 \( P \)（某位学者）的归一化介数中心性为 \( 0.15 \)，且网络节点数 \( n = 20 \)。现发现该网络中所有最短路径的总“中介次数”（即所有节点介数中心性原始值之和）为 \( S \)。请问，若将网络规模扩大到 \( n = 25 \)（保持连接模式类似），你能推断出 \( S \) 的大致变化趋势吗？为什么？
考虑一个加权的邮件通信网络，节点是员工，边权重 \( w_{ij} \) 表示 \( i \) 向 \( j \) 发送邮件的频率。现在定义一种“流量负载中心性”：节点 \( v \) 的负载等于所有节点对之间按权重比例分配的最短路径通信量中，经过 \( v \) 的部分。请阐述如何将经典的介数中心性计算方法（基于最短路径条数）进行推广，以融入边权重 \( w_{ij} \) 来近似计算这种“流量负载”。（提示：思考权重如何影响“路径选择”的概率）。
答案与解析
经典例题答案：
度中心性：\( C_D(A) = 2 \)， \( C_D(D) = 3 \)。
归一化介数中心性：\( C‘_B(A) \approx 0.0833 \)， \( C’_B(D) = 0.5 \)。
解析：计算过程见“阿星拆解”。结果显示，尽管 \( D \) 的直接连接数（度）只比 \( A \) 多1个，但其作为网络“桥梁”的作用（介数中心性）远大于 \( A \)，说明 \( D \) 对信息流有更强的控制力。
举一反三解析：
变式一：归一化常数 \( \frac{(n-1)(n-2)}{2} = \frac{9 \times 8}{2} = 36 \)。由 \( C’_B(Y) = C_B(Y) / 36 = 0.2 \)，得 \( C_B(Y) = 7.2 \)。\( X \)（高度中心性）可能像区域航空中心（如芝加哥），直飞目的地多；\( Y \)（高介数中心性）可能像国际中转枢纽（如迪拜），连接多个不同区域的航线。
变式二：\( S \) 会显著增加。因为介数中心性原始值之和 \( S \) 与网络中节点对的数量 \( \binom{n}{2} \) 以及网络的“中介机会”大致成正比。节点数从 \( 20 \) 增至 \( 25 \)，节点对数量从 \( 190 \) 增至 \( 300 \)，增长约 \( 58\% \)，即使连接密度不变，最短路径数量和其中介节点的出现次数通常也会大幅增加。
变式三：经典介数中心性默认所有边平等，每条最短路径贡献相同（为1）。在加权网络中，可将边权重 \( w_{ij} \) 转化为距离 \( d_{ij} = 1 / w_{ij} \)（假设频率越高，“距离”越近）。然后计算基于距离 \( d_{ij} \) 的最短路径。更精细的“流量负载”模型可以引入随机游走或流量分配算法，例如，定义节点 \( s \) 到 \( t \) 选择某条路径的概率与该路径上所有边权重乘积成正比，然后计算节点 \( v \) 被经过的期望次数，作为其负载中心性。这超越了简单的最短路径计数，更贴近实际通信模式。
PDF 典型例题打印版
为了节省资源，点击后将为您即时生成 PDF