2010 ParallelSimRankComputationonLar

• (He et al., 2010) ⇒ Guoming He, Haijun Feng, Cuiping Li, and Hong Chen. (2010). “Parallel SimRank Computation on Large Graphs with Iterative Aggregation.” In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2010). doi:10.1145/1835804.1835874

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%22Parallel+SimRank+computation+on+large+graphs+with+iterative+aggregation%22+2010
• http://portal.acm.org/citation.cfm?id=1835874&preflayout=flat#citedby

Quotes

Abstract

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.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2010 ParallelSimRankComputationonLar	Guoming He Haijun Feng Cuiping Li Hong Chen			Parallel SimRank Computation on Large Graphs with Iterative Aggregation		KDD-2010 Proceedings		10.1145/1835804.1835874		2010