关键点挖掘（一）

一：什么是关键点挖掘

1.脆弱的互联网

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

2.高效脆弱的电网

• 相互连通提高了效率，降低成本，一旦出现问题就会在系统中蔓延开来。
  共同的特点（网络）：
• 很多个体，有些个体更加重要
• 个体之间相互联系

3.社交网络

普通个体和微博大号

4.合作网络

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

5.交通网络

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

6.金融投资网络

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

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

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

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

典型的应用场景：

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

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

认识网络

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

H指数

• 例子：学者A发表100篇文章，学者B发表50篇，然而学者B论文的引用次数更多，最终学者B的学术影响力更大。
• 定义：一位学者的H指数为h，当且仅当他最多有h篇“引用次数不小于h的文章”
• 定义算子：y=H(x1,x2...xn)
• 于是节点v的H的指标：v=H(k1,k2...ki)
• 一个节点的H指标为h，当且仅当当他最多有h个“邻居数目不小于h的邻居”
  H家族
  节点的度定义为0阶H指数 h=k
  节点的一阶H指数上面的公式
  节点的n阶H指数
  当n无穷大，节点的n阶H指数就会收敛到核数

核数

把网络中度为一的节点删除掉，记住k1
把网络中度为二的节点全部删除掉，记为k2
把网络中度为三的节点全部删除掉，记为k3
这个时候网络中没有节点了，就说明该网络的核数为三，节点在k3的节点越重要
——》k壳分解，剥洋葱法
应用：信息传播
选一个节点作为信息源
信息沿网络连边进行传播，信息源核数大传播的范围更广

image.png
核数越大传播越广

聚类系数

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

image.png

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

image.png

社团：社团内部相互全连接

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

• 社团的数目
  并不是总是有效，假如社团不明显

  
  image.png

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

路径：

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

求最短路径算法

image.png

离心率：最大距离

接近中心性

image.png

介数中心性：节点在最短路径中的重要程度。

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

红点
image.png

邻接矩阵A

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

katz中心性：考虑全部路径

image.png

子图中心性：节点从自己出发，再回到自己的路径数目。

image.png

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

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

特征向量中心性：一个节点的中心性正比于他的邻居的中心性之和。

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

image.png
image.png

无回溯矩阵：

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

image.png

加上无回溯矩阵后的差异

image.png

算法：pagerank

特征向量中心性的变种，为了网页质量的排名
基本思想：一个网页越重要，会被更多重要的网页建立链接。
背景01：随机游走
从迷宫乱闯到互联网冲浪
迭代过程
从随机游走到pagerank
引入随机跳转，加入经验值

随机游走到pagerank

leaderrank为了解决陷阱问题

• 引入超节点

  
  

HITS算法

网页的hub属性和authority属性
一个authority页面会被很多高质量hub质量所指向
一个高质量hub（百度）会指向很多高质量antuority页面
每次迭代需要进行归一化，要不然不会收敛。

image.png

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

连通性敏感性的方法

• 最大连通集团的规模
• 连通集团的数目
• 节点之间的平均距离
  被删除的节点与其他节点之间的距离变化
  被删除节点之间的距离变化
  节点被删除后，剩余节点之间的距离变化。
• 稳定性敏感的方法
  一个节点越重要，删除后对网络的损害越强

残余接近中心性

image.png

不相交路径

image.png

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

基于节点收缩的方法

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

怎么度量凝聚度？

节点的数目乘以平局距离的导数

image.png

凝聚程度的变化

image.png