2012 PageRankonAnEvolvingGraph

• (Bahmani et al., 2012) ⇒ Bahman Bahmani, Ravi Kumar, Mohammad Mahdian, and Eli Upfal. (2012). “PageRank on An Evolving Graph.” In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2012). ISBN:978-1-4503-1462-6 doi:10.1145/2339530.2339539

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222012%22+PageRank+on+An+Evolving+Graph
• http://dl.acm.org/citation.cfm?id=2339530.2339539&preflayout=flat#citedby

Quotes

Author Keywords

• Data mining; dynamic graphs; pagerank; random walks

Abstract

One of the most important features of the Web graph and social networks is that they are constantly evolving. The classical computational paradigm, which assumes a fixed data set as an input to an algorithm that terminates, is inadequate for such settings. In this paper we study the problem of computing PageRank on an evolving graph. We propose an algorithm that, at any moment in the time and by crawling a small portion of the graph, provides an estimate of the PageRank that is close to the true PageRank of the graph at that moment. We will also evaluate our algorithm experimentally on real data sets and on randomly generated inputs. Under a stylized model of graph evolution, we show that our algorithm achieves a provable performance guarantee that is significantly better than the naive algorithm that crawls the nodes in a round-robin fashion.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2012 PageRankonAnEvolvingGraph	Ravi Kumar Mohammad Mahdian Bahman Bahmani Eli Upfal			PageRank on An Evolving Graph				10.1145/2339530.2339539		2012