关键点挖掘

关键点挖掘(一)

一:什么是关键点挖掘

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壳分解,剥洋葱法 应用:信息传播 选一个节点作为信息源 信息沿网络连边进行传播,信息源核数大传播的范围更广

核数越大传播越广

聚类系数

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

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

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

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

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

关键点挖掘(三):基于路径的结构化指标

路径:

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

求最短路径算法

离心率:最大距离

接近中心性

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

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

红点

邻接矩阵A

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

katz中心性:考虑全部路径

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

关键点挖掘(四):基于迭代寻优的中心化指标

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

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

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

无回溯矩阵:

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

加上无回溯矩阵后的差异

算法:pagerank

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

随机游走到pagerank

leaderrank为了解决陷阱问题

  • 引入超节点

HITS算法

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

关键点挖掘(五):基于节点的移除和压缩的中心化指标

连通性敏感性的方法

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

残余接近中心性

不相交路径

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

基于节点收缩的方法

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

怎么度量凝聚度?

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

凝聚程度的变化

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券