大规模社会网络中个体之间影响力的度量

本文大多数内容摘自实验室一位 Paper Machine Jing ZHANG老师的博士论文，它涉及到我们投出的论文 Panther: Fast Top-k Similarity Search in Large Networks，本体可以参考此处。本文意在随意介绍给恰好路过此处的哪位一点在大规模社会网络结构数据中对个体之间的影响力进行快速度量的思路，若有兴趣看看原文，并对你当前的工作有所帮助，那实在太棒了。

本文的前提设定是，输入只有大规模社会网络结构。之所以忽略用户行为数据，是因为一些情境下，用户行为数据不易获得。在这种前提下，首先需要定义个体之间的影响力。相似性与影响力一直是研究者致力区分的影响用户行为的两个因素，然而大多数情况下，并不容易区分究竟是相似度还是影响力驱动了用户的行为。在缺失用户行为数据的情境下，可以近似采用相似度来代替影响力。其基本思想是，两个节点的网络相似度越高，则他们相互之间的影响力越强。因此，本章本质上是在解决大规模社会网络中节点相似度的计算问题。

计算节点相似度是网络分析的一个基本问题，也是许多数据挖掘算法，诸如聚类、图匹配以及对象检索等算法的核心问题。一般来讲，度量网络中两个节点的相似度可以遵循两种不同的原则。第一种原则是两个节点相似当且仅当它们的邻居相似。第二种原则是两个节点相似当且仅当它们的社会角色或者社会地位相等，而社会角色或者社会地位可以用中心度、紧密度以及簇系数等网络特性来衡 量。通常，基于第一种原则计算得出的相似节点一般在距离上比较近，因此将其称之为近邻相似度;而基于第二种原则计算得出的相似节点和距离远近没有关系，甚至可以是两个完全不连通的节点，但在拓扑结构上可能非常相似，因此将其 称之为结构相似度。尽管计算网络中节点之间的相似度已经被很多人研究过，例如 SimRank 是计算近邻相似度的典范，它的基本思想是两个节点相似，当且仅当它们的邻居节点相似，所以算法本质上是个迭代方法。ReFex 是计算结构相似度的典范，它的基本思想是两个节点相似，当且仅当它们的网络特性相似，例如中心度，以及一度、二度、三度等间接邻居的中心度的平均值或求和值。然而传统方法的效率一般非常低。例如 SimRank 的时间复杂度是 O(I|V|^2d^2)，其中 I 是迭代次数，|V| 是网络中的节点数，d 是节点的平均度数。ReFex 也是一个迭代算法， 时间复杂度随着探测邻居度数的增加呈指数增长。近年来也涌现出一批加速方法，但一般只对近邻相似度进行加速，例如 Lee 等人提出能够快速计算与任意一个节点具有最相似 SimRank 值的 k 个节点的算法。然而对于结构相似度的加速几乎没有相关研究。因此，本章的研究目标是设计一种相似度计算方法，能够统一 且快速地计算近邻相似度和结构相似度。

本文的研究思路是提出采样算法 Panther，能够快速计算网络中节点之间的近邻相似度。该算法的创新点在于随机路径采样。具体地，给定一个网络，在其中执行 R 次随机游走。每次随机选择一个起点开始执行 T 步随机游走。其基本思想是两个节点共同出现的路径越多，则它们之间越相似。理论上可以证明，当采样路径数达到R = \frac{c}{\varepsilon^2} (log_2(_2^T) +1 + ln \frac{1}{n} )时，便可以 1−η 的概率得到错误率 ε。进一步，为了计算远距离，甚至是不连通节点之间的相似度，在 Panther 算法的基础 上，为每个节点扩展一个向量，用来表示每个节点的结构特征。命名该扩展算法为 Panther++。

实验采用腾讯微博的关注网络验证本章提出方法的效率和效果。结果表明， 在一个 443,070 个节点、5,000,000 条边的腾讯微博网络上，Panther 和 Panther++ 方法比最快的比对方法提速 300 倍左右。同时，提出的方法可伸缩性很好，在一个 51,640,620 个节点和 1,000,000,000 条边的腾讯微博网络上为每个节点寻找最相似 的 5 个节点，每个节点平均耗时 0.0001 秒。

最后，基于本文的一个实现可以在此处获取：

Github:https://github.com/yuikns/panther