2015 EfficientPageRankTrackinginEvol

• (Ohsaka et al., 2015) ⇒ Naoto Ohsaka, Takanori Maehara, and Ken-ichi Kawarabayashi. (2015). “Efficient PageRank Tracking in Evolving Networks.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783297

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Efficient+PageRank+Tracking+in+Evolving+Networks
• http://dl.acm.org/citation.cfm?id=2783258.2783297&preflayout=flat#citedby

Quotes

Author Keywords

• Data mining; dynamic graphs; online algorithms; personalized pagerank

Abstract

Real-world networks, such as the World Wide Web and online social networks, are very large and are evolving rapidly. Thus tracking personalized PageRank in such evolving networks is an important challenge in network analysis and graph mining.

In this paper, we propose an efficient online algorithm for tracking personalized PageRank in an evolving network. The proposed algorithm tracks personalized PageRank accurately (i.e., within a given accuracy ε > 0). Moreover it can update the personalized PageRank scores in amortized O (1/ε) iterations for each graph modification. In addition, when m edges are randomly and sequentially inserted, the total number of iterations is expected to be O (log m / ε).

We evaluated our algorithm in real-world networks. In average case, for each edge insertion and deletion, our algorithm updated the personalized PageRank in 3us in a web graph with 105M vertices and 3.7B edges, and 20ms in a social network with 42M vertices and 1.5B edges. By comparing existing state-of-the-arts algorithms, our algorithm is 2 -- 290 times faster with an equal accuracy.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 EfficientPageRankTrackinginEvol	Ken-ichi Kawarabayashi Takanori Maehara Naoto Ohsaka			Efficient PageRank Tracking in Evolving Networks				10.1145/2783258.2783297		2015