网络与图分析

几乎所有分析都把记录当作彼此独立的——每个人、每宗案件、每笔交易一行。但一些最有价值的信息不在行里；而在它们之间的连接里。谁打电话给谁、哪些账户把钱转给哪些、哪些人一起出现。网络分析把那些关系当作研究的首要对象，而数量惊人的、逐行看不见的洞见，一旦你看向结构便变得显而易见。

这是我在情报工作中直接倚靠的一门学科，那里的问题常常是「这里谁是关键的连接者，隐藏的群组是什么？」——一个不为链路建模就字面上无法回答的问题。这一页是实用的工具箱：如何表示一个网络、找出重要节点的那几个度量、如何找出社区，以及让网络分析撒谎的那些陷阱。

关系即数据

一个图（或网络）不过是两样东西：一组节点（实体——人、账户、地点）和一组边（它们之间的关系）。就这样——然而这样表示数据，解锁了表格数据无法表达的问题：两个人通过中间人相距多远？谁坐在中心？某人属于哪个紧密的群组？

心态的转变正是全部要点：别再问「这个节点的属性是什么？」，而开始问「这个节点在结构中的位置是什么？」两个档案完全相同的人，会因他们与谁相连而扮演截然不同的角色——而角色往往才是要紧的。

节点、边与结构

边承载着意义，而边的种类会改变分析：

有向 vs 无向——「打了电话给」有方向（A → B）；「一起出现」则没有。方向对「谁影响谁」要紧。
加权 vs 无权——一条边可以携带一个强度（通话次数、转移的金额），而不只是存在与否。
路径与连通性——一条路径是沿着边在两个节点间的一条路线；最短路径（分隔度）支撑着下面几个度量。一个网络也可能断裂成互不相连的分量。

有了那套词汇，核心的实用问题就变成：哪些节点重要，为什么？「重要」有几个不同的含义，而功夫在于挑出与你的问题相符的那一个——那就是中心性。

谁忙碌：度中心性

最简单的度量是度中心性——只数一个节点的连接。节点 $i$ 的度 $k_i$ 是触及它的边的数量。高度意味着一个枢纽：一个与许多其他人相连的人。

它是个不错的第一遍——而单独看常常误导。一个节点可以有一百个连接，却坐在网络的边缘，而一个只有三个连接的节点，却坐在它唯一的桥上。度数的是数量，而非位置。接下来的两个度量修好这点。

谁是中间人：介数中心性

介数中心性衡量一个节点多频繁地位于其他节点之间的最短路径上。形式上，它对所有其他节点的对求和，累加经过节点 $v$ 的最短路径所占的比例：

C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}

其中 $\sigma_{st}$ 是从 $s$ 到 $t$ 的最短路径数，而 $\sigma_{st}(v)$ 是其中经过 $v$ 的数量。一个高介数的节点是一个中间人或桥：信息、金钱或影响必须流经它，才能在网络的各部分之间往来。这些往往是所有节点中最有后果的——移除一个，网络就可能断裂——哪怕它们的原始度数并不高。

介数找出中间人。被高亮的节点只有不高的度，但左簇与右簇之间的每一条路径都经过它——一个割点，移除它便把网络分开。单凭度会错过它。

谁有影响力：特征向量与 PageRank

特征向量中心性捕捉一个更微妙的想法：要紧的不只是你有多少连接，而是它们有多重要。如果你与有影响力的人相连，你就有影响力。这是有意设计的循环，而数学优雅地解开了这个循环——一个节点的分数正比于它邻居分数之和：

x_i = \frac{1}{\lambda} \sum_{j \in N(i)} x_j

为整个网络写出来就是 $A\mathbf{x} = \lambda \mathbf{x}$ ——这些分数是网络邻接矩阵的一个特征向量（故而得名，也是对线性代数页的一个巧妙回呼）。PageRank——最初为网页排名的算法——是一个著名的变体：如果重要的页面链向某个页面，它就重要。同样的逻辑找出中间人捕捉不到的那个安静而有力的节点：不是最忙的，不是那座桥，而是嵌在有影响力者之中的那一个。

找出群组：社区发现

在单个节点之外，网络还有社区结构——彼此之间比与其余更密集相连的节点簇。找出它们，便揭示了一个网络内部的小团体、派系或利益集团，而它是聚类在图上的表亲。

标准的目标是模块度：当组内有许多边、组间很少时——相比你凭偶然会预期的——一个网络的划分得分就高。像 Louvain 与 Leiden 这样的算法高效地优化它，而标签传播方法提供一个快速的替代。其输出——「这二十个节点构成一个紧密的、与其余几乎不相连的群组」——往往是网络分析所产出的、在作业上单一最有用的东西。

它在哪里误导

网络诱人，且容易被过度解读。陷阱有：

中心性不是重要性。一个高分是一个结构性的事实，而非一个裁决。最中心的节点也许是一个总机接线员，而非一个头目。中心性提名节点以引起关注；它不定罪它们。
缺边偏倚。你的网络只是你碰巧记录下来的那些连接。缺失的边（一段未被观测的关系）能彻底改变谁看起来居中，而一条边的缺席很少是一段联系不存在的证据。
毛球图。一个被画成一团交叉线缠结的大网络，看起来唬人，却什么都没显示。倚靠那些度量（中心性表、社区标签），而非那幅漂亮却读不懂的图。
伪节点。一个共用的出租车站或一条客服热线，能让不相关的人看起来相连。垃圾边产生看起来自信、却错误的结构。

它在我工作中的体现

60 秒回顾

中心性的定义、现代的社区发现方法，以及「中心性不是重要性」的告诫，反映了当前的网络分析参考文献，以及亲身的链路分析。