中心性与社区
"谁最重要"这个问题没有唯一答案，因为"重要"至少有五种不同的意思：认识的人多、卡在关键路口、离谁都近、认识的人本身很重要、以及被重要的人指向。这一页把五种中心性画在同一张图上，再看社区是怎么被找出来的。
本页实验台
LAB 01
五种中心性
度、介数、接近、特征向量、PageRank 在同一张图上并排上色，排名差异一目了然
问题
"谁最重要"这个问题没有唯一答案——是认识的人最多的那个，还是卡在所有路径中间的那个，还是被重要的人认识的那个？五种中心性对应五种不同的"重要"，排名可以完全不同。
模型
五种定义：
度 CD(i) = ki 介数 CB(i) = Σs≠t σst(i)/σst
接近 CC(i) = (n−1) ⁄ Σj d(i,j) 特征向量 λx = Ax PageRank x = (1−d)/n + d ATD−1x
σst 是 s 到 t 的最短路条数，σst(i) 是其中经过 i 的条数；d 是阻尼系数。度只看邻居，介数看全局路径，特征向量看邻居的"质量"。接近 CC(i) = (n−1) ⁄ Σj d(i,j) 特征向量 λx = Ax PageRank x = (1−d)/n + d ATD−1x
第一名—
五种排名的一致度—
中心性的基尼系数—
介数第一名是不是度第一名—
两种排名差得最远的节点—
选"哑铃形"，再在度中心性与介数中心性之间来回切。桥上那个点（#26）只连了 6 条边，度中心性排在中下游；但两团之间的每一条路径都必须经过它，介数中心性直接排第一。这两种"重要"在现实里对应完全不同的角色：一个是团内熟人很多的人，一个是唯一能把两个圈子接上的人。要阻断传播就去掉后者，要在圈内快速扩散消息就找前者。顺便看一眼"五种排名的一致度"：空手道俱乐部是 0.83，哑铃形只有 0.55——结构越特殊，五种定义分歧越大。 新加的第二张图，是「五种中心性什么时候会分家」这个问题的答案。横轴是按度中心性的排名，纵轴是按介数中心性的排名，落在虚线上表示两种排名一致；偏离虚线最远的那个点被标成红色，编号和上面那张网络图是同一个。读数里的「一致度」是一个平均相关系数，它告诉你「大体上一致」，却永远不会让你想起某一个具体的节点——而中心性分析真正有用的时候，恰恰就是某一个节点分了家。请把网络换成「桥」那一张。实测一致度会从空手道俱乐部的 0.832 掉到 0.551，散点从贴着对角线散成一个明显的 L 形；度中心性的第一名是 #17，介数中心性的第一名却是 #26，而 #26 正是那个偏离对角线最远的点——两种排名差了 26 名。#26 邻居不多，但两个社群之间所有的最短路都得从它身上过。这类节点在现实里往往是最要紧的：它平时不显眼，一旦断掉，整张网络就被切成互不相通的两半。反过来，在 BA 无标度网络上两种排名的第一名是同一个（#2），一致度 0.719，因为那里的枢纽既有最多的邻居，也顺带垄断了最短路——这时候用哪种中心性都差不多，也就无所谓选哪一种了。所以「该用哪个中心性」这个问题没有通用答案，要看你关心的是「谁认识的人多」还是「谁一旦消失会把网络切开」。
LAB 02
PageRank 迭代
看分数怎么在迭代中重新分配直到收敛，阻尼系数的作用
问题
谷歌 1998 年的做法是：一个网页的重要性，来自指向它的网页的重要性。这是一个自我指涉的定义——它凭什么能算出来，又为什么需要一个"随机跳转"的阻尼系数？
模型
PageRank 是一条马尔可夫链的稳态分布：以概率 d 沿链接走，以 1−d 随机跳。
x = (1−d)/n · 1 + d · AT D−1 x， d ≈ 0.85
阻尼系数 d 有两个作用：让链不可约（跳出"死胡同"和"蜘蛛陷阱"），并保证唯一稳态；同时把收敛速度控制在 dn。d = 0.85 时约 50 次迭代就够。本轮最大变化—
第一名—
分数之和—
有效迭代轮数—
阻尼系数是干什么用的？把 d 调到 0.99 再勾上"黑洞节点"，看分数怎么全被吸进去。阻尼的本义是"冲浪者有 1−d 的概率不点链接而是随机跳走"，它同时解决了两个问题：保证迭代收敛，以及防止分数被没有出链的节点吸干。0.85 这个经典取值不是推导出来的，是工程上试出来的折中。
LAB 03
模块度与社区发现
Louvain 逐层合并，模块度 Q 随之上升
问题
"这张网里有几个圈子"——这个问题的难点不在于怎么分，而在于怎么判断一种分法比另一种好。模块度给了一把尺子，而有了尺子，贪心算法就能一层层合并上去。
模型
模块度 Q 衡量"社区内的边比随机情况下多多少"。
Q = (1/2m) Σij [ Aij − kikj/(2m) ] δ(ci, cj)
m 是总边数，kikj/(2m) 是度保持零模型下 i 与 j 相连的期望。Q 有"分辨率极限"：小于 √(2m) 的社区会被强行合并——这是它最著名的缺陷。模块度 Q—
社区数—
各社区规模—
同规模随机图的 Q—
模块度有个陷阱：随机图也能被切出不低的 Q。选"纯随机"跑一遍，看"同规模随机图的 Q"这个读数——它往往能到 0.3 以上。所以看到 Q=0.35 就宣布"发现了社区结构"是不成立的，必须和零模型比。另外调一下分辨率参数：同一张网络能被切成 2 个大社区或 8 个小社区，哪个"对"取决于你问的问题，而不取决于数据。
LAB 04
中心性与攻击
随机删点 vs 按中心性删点，网络崩解速度差几倍
问题
互联网可以承受大量路由器随机故障，却会被针对枢纽的少量攻击打瘫。这个"对随机鲁棒、对定向脆弱"的组合是无标度网络的特征，也是所有基础设施防护要面对的现实。
模型
渗流阈值判据（Molloy–Reed）：巨片存在当且仅当
κ = ⟨k²⟩ ⁄ ⟨k⟩ > 2， 随机删点的临界比例 fc = 1 − 1 ⁄ (κ − 1)
γ ≤ 3 的幂律网络 ⟨k²⟩ 发散，fc → 1：随机删几乎所有点都还连着。但按度数从高到低删，只需删掉百分之几就能把 κ 压到 2 以下。随机删：最大分量占比—
按度删：最大分量占比—
两者相差几倍—
按度删的崩解点—
无标度网络的"稳健而脆弱"。随机删掉四成节点，它基本没事——因为随机删中的大概率是度为 1、2 的小节点；但按度从大到小删，只要删掉百分之几，网络就散架了。互联网对随机故障的耐受和对定向攻击的脆弱，是同一个结构性质的两面。换成 ER 图再看，两条曲线几乎重合——因为那里没有枢纽可打。
这一页想说的
中心性和社区都是"给网络下结论"的工具，也都容易被过度解读。用的时候记住两条：第一，先说清楚你问的"重要"是哪一种，不同定义排出来的第一名常常不是同一个点；第二，任何结构性结论都要和零模型比一比——随机图也有社区、也有高中心性节点，不比不知道你发现的是不是结构。