A Tractable Approach to Finding Closest Truncated-commute-time Neighbors in Large Graphs
A Tractable Approach to Finding Closest Truncated-commute-time Neighbors in Large Graphs
复制标题
DOI：
--
复制
发表时间：
2007-07
期刊：
影响因子：
--
通讯作者：
Purnamrita Sarkar;A. Moore
中科院分区：
文献类型：
--
作者：
Purnamrita Sarkar;A. Moore
最近，人们对基于图的学习非常感兴趣，在推荐网络的协同过滤、社交网络的链接预测和欺诈检测方面都有应用。这些网络可以由数百万个实体组成，因此开发高效的技术非常重要。我们特别感兴趣的是加速随机漫步方法来计算这类图的一些非常有趣的接近度量。经验表明，这些措施效果良好（Liben-Nowell & Kleinberg, 2003; Brand, 2005）。我们引入了一个众所周知的度量的截断变异，即由图上随机行走引起的通勤时间。我们提出了一种新颖的算法来计算截断通勤时间内所有感兴趣的近似近邻对，而无需计算所有对之间的近邻对。我们展示了模拟和真实图形的结果，大小可达100；000个实体，这表明计算时间接近线性缩放。
Recently there has been much interest in graph-based learning, with applications in collaborative filtering for recommender networks, link prediction for social networks and fraud detection. These networks can consist of millions of entities, and so it is very important to develop highly efficient techniques. We are especially interested in accelerating random walk approaches to compute some very interesting proximity measures of these kinds of graphs. These measures have been shown to do well empirically (Liben-Nowell & Kleinberg, 2003; Brand, 2005). We introduce a truncated variation on a well-known measure, namely commute times arising from random walks on graphs. We present a very novel algorithm to compute all interesting pairs of approximate nearest neighbors in truncated commute times, without computing it between all pairs. We show results on both simulated and real graphs of size up to 100; 000 entities, which indicate near-linear scaling in computation time.