Targeted sampling from massive block model graphs with personalized PageRank
Targeted sampling from massive block model graphs with personalized PageRank
复制标题
DOI：
10.1111/rssb.12349
复制
发表时间：
2019-12-31
影响因子：
5.8
通讯作者：
Rohe, Karl
中科院分区：
文献类型：
--
作者：
Chen, Fan;Zhang, Yini;Rohe, Karl
这篇论文为个性化PageRank(称为‘PPR’)提供了统计理论和直觉：这是一种流行的技术，从大规模网络中抽样一个小社区。我们研究这样一种设置，在这种情况下，彻底获得或维护整个网络的成本很高，但我们可以从感兴趣的种子节点开始，并通过它们的连接‘爬行’网络来寻找其他节点。通过以设计的方式爬行图形，可以在不查询整个海量图形的情况下近似计算PPR向量，使其成为滚雪球采样的替代方案。利用经次数修正的随机块模型，研究PPR向量是否可以选择与种子节点属于同一块的节点。我们为PPR向量提供了一种简单且可解释的形式，突出了其对目标块外的高度节点的偏向。我们研究了基于节点度的简单调整，并建立了允许有向图的PPR聚类的一致性结果。这些结果是由最近的技术进步实现的，这些技术进步表明了特征向量的元素收敛。我们使用大量的Twitter友谊图来说明该方法，我们使用Twitter应用程序编程接口爬行该图。我们发现，调整和未调整的PPR技术是互补的方法，其中调整使结果特别局限于种子节点，并且偏差调整极大地受益于程度正则化。
The paper provides statistical theory and intuition for personalized PageRank (called 'PPR'): a popular technique that samples a small community from a massive network. We study a setting where the entire network is expensive to obtain thoroughly or to maintain, but we can start from a seed node of interest and 'crawl' the network to find other nodes through their connections. By crawling the graph in a designed way, the PPR vector can be approximated without querying the entire massive graph, making it an alternative to snowball sampling. Using the degree-corrected stochastic block model, we study whether the PPR vector can select nodes that belong to the same block as the seed node. We provide a simple and interpretable form for the PPR vector, highlighting its biases towards high degree nodes outside the target block. We examine a simple adjustment based on node degrees and establish consistency results for PPR clustering that allows for directed graphs. These results are enabled by recent technical advances showing the elementwise convergence of eigenvectors. We illustrate the method with the massive Twitter friendship graph, which we crawl by using the Twitter application programming interface. We find that the adjusted and unadjusted PPR techniques are complementary approaches, where the adjustment makes the results particularly localized around the seed node, and that the bias adjustment greatly benefits from degree regularization.