Seeded PageRank solution paths
Seeded PageRank solution paths
复制标题
DOI：
10.1017/s0956792516000280
复制
发表时间：
2016-12-01
影响因子：
1.9
通讯作者：
Kloster, K.
中科院分区：
文献类型：
--
作者：
Gleich, D. F.;Kloster, K.
我们研究了基于PageRank从一组种子节点随机游走的网络扩散行为。众所周知，这些扩散可以揭示小的、局部的集群（或群落），也可以通过改变一个参数来揭示大型宏观集群，该参数具有双重解释，即作为精度界限和正则化水平。我们提出了一种新的方法，可以快速逼近该参数所有值的扩散结果。我们的方法有效地生成了与PageRank扩散相关的近似解路径或正则化路径，并在大小之间的多个尺度上揭示了簇的结构。我们正式证明了该方法的运行时边界与网络的大小无关，并且我们研究了在某些情况下更实用的方法的多种优化。我们证明了这些方法在许多具有多达20亿个边的真实网络上识别出精细的聚类结构。
We study the behaviour of network diffusions based on the PageRank random walk from a set of seed nodes. These diffusions are known to reveal small, localized clusters (or communities), and also large macro-scale clusters by varying a parameter that has a dual-interpretation as an accuracy bound and as a regularization level. We propose a new method that quickly approximates the result of the diffusion for all values of this parameter. Our method efficiently generates an approximate solution path or regularization path associated with a PageRank diffusion, and it reveals cluster structures at multiple size-scales between small and large. We formally prove a runtime bound on this method that is independent of the size of the network, and we investigate multiple optimizations to our method that can be more practical in some settings. We demonstrate that these methods identify refined clustering structure on a number of real-world networks with up to 2 billion edges.