Parallel SimRank computation on large graphs with iterative aggregation
Parallel SimRank computation on large graphs with iterative aggregation
复制标题
DOI：
10.1145/1835804.1835874
复制
发表时间：
2010-07
期刊：
影响因子：
--
通讯作者：
Guoming He;Haijun Feng;Cuiping Li;Hong Chen
中科院分区：
文献类型：
--
作者：
Guoming He;Haijun Feng;Cuiping Li;Hong Chen
最近，人们对基于图形的分析产生了浓厚的兴趣。基于图的分析最重要的方面之一是测量图中节点之间的相似性。SimRank是一种简单而有影响力的衡量标准，基于固体图形理论模型。然而，现有的SimRank计算方法存在两个局限性：1）实际计算成本可能非常高; 2）它们只能应用于静态图。在本文中，我们利用固有的并行性和高内存带宽的图形处理单元（GPU），以加速计算SimRank的大型图形。此外，基于SimRank本质上是一个一阶马尔可夫链的观察，我们建议利用迭代聚合技术解耦马尔可夫链并行计算SimRank分数的大型图。迭代聚合方法可以应用于动态图。此外，它不仅可以处理链路更新问题，而且节点更新问题。在人工数据集和真实的数据集上的大量实验验证了所提方法的有效性。
Recently there has been a lot of interest in graph-based analysis. One of the most important aspects of graph-based analysis is to measure similarity between nodes in a graph. SimRank is a simple and influential measure of this kind, based on a solid graph theoretical model. However, existing methods on SimRank computation suffer from two limitations: 1) the computing cost can be very high in practice; and 2) they can only be applied on static graphs. In this paper, we exploit the inherent parallelism and high memory bandwidth of graphics processing units (GPU) to accelerate the computation of SimRank on large graphs. Furthermore, based on the observation that SimRank is essentially a first-order Markov Chain, we propose to utilize the iterative aggregation techniques for uncoupling Markov chains to compute SimRank scores in parallel for large graphs. The iterative aggregation method can be applied on dynamic graphs. Moreover, it can handle not only the link-updating problem but also the node-updating problem. Extensive experiments on synthetic and real data sets verify that the proposed methods are efficient and effective.