关键点挖掘

关键点挖掘（一）

一、什么是关键点挖掘

1. 脆弱的互联网

假如删除 2% 的 top 节点，例如百度、腾讯等，很多其他的节点将无法使用。

2. 高效脆弱的电网

相互连通提高了效率、降低成本，一旦出现问题就会在系统中蔓延开来。

共同的特点（网络）：

• 很多个体，有些个体更加重要
• 个体之间相互联系

3. 社交网络

普通个体和微博大号。

4. 合作网络

当科学家共同写一篇论文，或者写一本书。通过网络连接，找出哪些科学家有更大的影响力。

5. 交通网络

火车线路、飞机线路、回家线路——比如通过研究飞机网络得出城市的重要性。

6. 金融投资网络

企业、银行等之间的投资合作关系，有点像电力系统：其中有一个企业发生经济问题，就会转嫁给其他节点。有助于预测金融风险和预测金融危机发生。

二、关键点挖掘基本术语和应用场景

节点的重要性指标（中心性指标）

基于邻居节点的结构化指标；基于路径的规划指标；基于迭代寻优的中心化指标；基于结点移除和收缩的中心化指标。

典型的应用场景

• 识别网络中的超级传播者
• 预测重要的蛋白质
• 衡量学术的影响力
• 检测金融风险
• 预测职业生涯
• 预测软件故障

关键点挖掘（二）：基于邻居节点的结构化指标

认识网络

• 节点： 人、企业、动物、蛋白质等
• 边： 节点之间的关系；有方向（如投资）、无方向（如合作）
• 节点的度： 和节点相连的数目
• 节点的一般规律： 社交网络呈现幂律分布，表示大部分用户的度都非常小，但存在非常大的节点，数目比较小。网络中节点的度分布是不均匀的
• 遇到的问题： 有可能邻居的传播能力比较大
• 问题转化： 一个节点有多少个邻居 → 一个节点有多少个高质量的邻居，用 H 指数来衡量高质量的大小

H 指数

例子： 学者 A 发表 100 篇文章，学者 B 发表 50 篇，然而学者 B 论文的引用次数更多，最终学者 B 的学术影响力更大。

定义： 一位学者的 H 指数为 h，当且仅当他最多有 h 篇「引用次数不小于 h 的文章」。

定义算子： y = H(x₁, x₂, …, xₙ)

于是节点 v 的 H 指标：v = H(k₁, k₂, …, kᵢ)

一个节点的 H 指标为 h，当且仅当他最多有 h 个「邻居数目不小于 h 的邻居」。

H 家族： 节点的度定义为 0 阶 H 指数 h = k；节点的一阶 H 指数即上面的公式；节点的 n 阶 H 指数当 n 无穷大时会收敛到核数。

核数

把网络中度为 1 的节点删除掉，记为 k₁；把网络中度为 2 的节点全部删除掉，记为 k₂；把网络中度为 3 的节点全部删除掉，记为 k₃……这个时候网络中没有节点了，就说明该网络的核数为三。节点在 k₃ 的节点越重要——即 k 壳分解，剥洋葱法。

应用：信息传播 — 选一个节点作为信息源，信息沿网络连边进行传播，信息源核数大传播的范围更广。

聚类系数

邻居都紧密地连在一起，信息多次传播；聚类高，只在小圈子传播，不利于广度传播。

聚类系数：邻居有多少连接，除去最大连接。

社团

社团内部相互全连接。假如传播多个信息源，分别把信息源放到不同的社团内部去，就要考虑社团的数目。

社团的数目并不是总是有效——假如社团不明显：

关键点挖掘（三）：基于路径的结构化指标

路径

完全图： 每两个节点都存在连边。节点的序列就是从一个节点到另外一个节点的路径，常常考虑最短的路径。

求最短路径算法

离心率：最大距离

接近中心性：

介数中心性

节点在最短路径中的重要程度。任意两个社团最短路径都会经过这个节点，那么这个节点就比较重要。比较耗时。

邻接矩阵 A

是对称矩阵，行相加等于节点的度。矩阵乘法 A×A 表示路径为 2 的路径数目；A×A×A 表示距离为 3 的路径数目。

Katz 中心性：考虑全部路径

子图中心性

节点从自己出发，再回到自己的路径数目。

关键点挖掘（四）：基于迭代寻优的中心化指标

思路：一个节点的重要性决定于邻居的重要性。不同算法的不同点在于邻居节点的作用方式不同，有多大程度的影响。

特征向量中心性

一个节点的中心性正比于他的邻居的中心性之和。

• 存在的问题 1： 大度节点会显著自我加强。解决办法 1： 无回溯矩阵。
• 存在的问题 2： 收敛速度慢。解决办法： 累计提名。

无回溯矩阵

保证不能重复计算，导致复杂性比较高。

加上无回溯矩阵后的差异：

算法：PageRank

特征向量中心性的变种，为了网页质量的排名。

基本思想： 一个网页越重要，会被更多重要的网页建立链接。

背景 01： 随机游走 — 从迷宫乱闯到互联网冲浪。迭代过程：从随机游走到 PageRank，引入随机跳转，加入经验值。

LeaderRank

为了解决陷阱问题，引入超节点：

HITS 算法

网页的 hub 属性和 authority 属性：

• 一个 authority 页面会被很多高质量 hub 所指向
• 一个高质量 hub（百度）会指向很多高质量 authority 页面

每次迭代需要进行归一化，要不然不会收敛。

关键点挖掘（五）：基于节点的移除和压缩的中心化指标

连通性敏感性的方法

• 最大连通集团的规模
• 连通集团的数目
• 节点之间的平均距离
• 被删除的节点与其他节点之间的距离变化
• 被删除节点之间的距离变化
• 节点被删除后，剩余节点之间的距离变化

稳定性敏感的方法

一个节点越重要，删除后对网络的损害越强。

残余接近中心性

不相交路径：

不共享任何一个中间的节点。

基于节点收缩的方法

将一个节点和他的邻点收缩为一个新的节点，更好凝缩在一起。

怎么度量凝聚度？

节点的数目乘以平均距离的导数。

凝聚程度的变化：