Name
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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2339530.2339539 | KDD |
Keywords | Field | DocType |
round-robin fashion,naive algorithm,web graph,important feature,classical computational paradigm,provable performance guarantee,graph evolution,fixed data,true pagerank,random walks,social network,random walk | Strength of a graph,Computer science,Theoretical computer science,Distance-hereditary graph,Null graph,Clique-width,Random geometric graph,Voltage graph,Moral graph,Graph (abstract data type) | Conference |
Citations | PageRank | References |
29 | 1.03 | 24 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bahman Bahmani | 1 | 434 | 16.71 |
| Ravi Kumar | 2 | 13932 | 1642.48 |
| Mohammad Mahdian | 3 | 2689 | 226.62 |
| Eli Upfal | 4 | 4310 | 743.13 |