本文大多数内容摘自实验室一位 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 秒。

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


Yu

Ideals are like the stars: we never reach them, but like the mariners of the sea, we chart our course by them.

6 Comments

Mark · September 23, 2016 at 11:25

Google Chrome 53.0.2785.116 Google Chrome 53.0.2785.116 Mac OS X  10.10.5 Mac OS X 10.10.5

你好,跑panther的时候,在make的过程中出现snappy找不到的报错,要怎么处理呀?可以讲一下吗,搜了一下没有找到很好的解决方案。

    yu · September 23, 2016 at 20:28

    Google Chrome 53.0.2785.116 Google Chrome 53.0.2785.116 Mac OS X  10.11.6 Mac OS X 10.11.6

    @Mark 很抱歉,因为 LevelDB 更新,它需要依赖 snappy,然后我没有及时更新它。

    LevelDB 是用来存放中间结果,少占一点内存用的,虽然残念还是要很多内存。
    Snappy 是嵌入的快速压缩/解压工具。

    你重新 clone 或者 pull 一份即可

      Mark · September 24, 2016 at 11:26

      Google Chrome 53.0.2785.116 Google Chrome 53.0.2785.116 Mac OS X  10.10.5 Mac OS X 10.10.5

      @yu 可以的 大神效率是高。。。点了star 祝好运!

        yu · September 24, 2016 at 11:29

        Google Chrome 53.0.2785.116 Google Chrome 53.0.2785.116 Mac OS X  10.11.6 Mac OS X 10.11.6

        @Mark 多谢!希望它能在某个时候能够对谁有一点用就好。

szz · November 23, 2018 at 01:28

Google Chrome 67.0.3396.62 Google Chrome 67.0.3396.62 Windows 10 x64 Edition Windows 10 x64 Edition

您好!我可以向您请教一下Panther: Fast Top-k Similarity Search in Large Networks这篇论文的一些东西么?看了很多天然后还是很不懂,特别是那个shatter那块,不知道是如何shatter的。很焦虑,实在没有办法。希望可以交流一下。

    yu · November 28, 2018 at 17:25

    Google Chrome 70.0.3538.110 Google Chrome 70.0.3538.110 Mac OS X  10.14.1 Mac OS X 10.14.1

    @szz 抱歉一直没注意到。代码枝干逻辑就是这个位置: https://github.com/yuikns/panther/blob/master/lib/rdsextr/rdsextr_ctrl.cc#L79

    步骤很简单,就是随便找个点,然后按照概率走 T 步,这个步骤重复 R 次。论文就是想证明当采样路径数达到[latex]R = \frac{c}{\varepsilon^2} (log_2(_2^T) +1 + ln \frac{1}{n} )[/latex]时,和全集整体跑一遍相比,可以 1−η 的概率得到错误率 ε。

    这个本身应该很 straightforward 才对。

    代码比较杂乱这个一个是想要并行+复用代码,外加想要故意准备一些断点来给各种可能准备和确认数据,所以看起来搓搓的。这个深感抱歉。

Leave a Reply

Your email address will not be published. Required fields are marked *