{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T15:25:21Z","timestamp":1791127521349,"version":"4.1.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:p>In this paper, we analyze the efficiency of Monte Carlo methods for incremental computation of PageRank, personalized PageRank, and similar random walk based methods (with focus on SALSA), on large-scale dynamically evolving social networks. We assume that the graph of friendships is stored in distributed shared memory, as is the case for large social networks such as Twitter.<\/jats:p>\n          <jats:p>\n            For global PageRank, we assume that the social network has\n            <jats:italic>n<\/jats:italic>\n            nodes, and\n            <jats:italic>m<\/jats:italic>\n            adversarially chosen edges arrive in a random order. We show that with a reset probability of \u03b5, the expected total work needed to maintain an accurate estimate (using the Monte Carlo method) of the PageRank of every node at all times is [EQUATION]. This is significantly better than all known bounds for incremental PageRank. For instance, if we naively recompute the PageRanks as each edge arrives, the simple power iteration method needs [EQUATION] total time and the Monte Carlo method needs\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>mn<\/jats:italic>\n            \/\u03b5) total time; both are prohibitively expensive. We also show that we can handle deletions equally efficiently.\n          <\/jats:p>\n          <jats:p>\n            We then study the computation of the top\n            <jats:italic>k<\/jats:italic>\n            personalized PageRanks starting from a seed node, assuming that personalized PageRanks follow a power-law with exponent \u03b1 &lt; 1. We show that if we store\n            <jats:italic>R<\/jats:italic>\n            &gt;\n            <jats:italic>q<\/jats:italic>\n            ln\n            <jats:italic>n<\/jats:italic>\n            random walks starting from every node for large enough constant\n            <jats:italic>q<\/jats:italic>\n            (using the approach outlined for global PageRank), then the expected number of calls made to the distributed social network database is\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            \/(\n            <jats:italic>R<\/jats:italic>\n            <jats:sup>(1-\u03b1)\/\u03b1<\/jats:sup>\n            )). We also present experimental results from the social networking site, Twitter, verifying our assumptions and analyses. The overall result is that this algorithm is fast enough for real-time queries over a dynamic social network.\n          <\/jats:p>","DOI":"10.14778\/1929861.1929864","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"173-184","source":"Crossref","is-referenced-by-count":243,"title":["Fast incremental and personalized PageRank"],"prefix":"10.14778","volume":"4","author":[{"given":"Bahman","family":"Bahmani","sequence":"first","affiliation":[{"name":"Stanford University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Abdur","family":"Chowdhury","sequence":"additional","affiliation":[{"name":"Twitter Inc."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ashish","family":"Goel","sequence":"additional","affiliation":[{"name":"Stanford University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2010,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064009.1064010"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/050643799"},{"key":"e_1_2_1_3_1","unstructured":"B. Bahmani A. Chowdhury and A. Goel. Fast incremental and personalized PageRank http:\/\/arxiv.org\/abs\/1006.2880 2010.  B. Bahmani A. Chowdhury and A. Goel. Fast incremental and personalized PageRank http:\/\/arxiv.org\/abs\/1006.2880 2010."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_5_1","volume-title":"Survey: A survey on PageRank computing. Internet Mathematics, 2(1)","author":"Berkhin P.","year":"2005","unstructured":"P. Berkhin . Survey: A survey on PageRank computing. Internet Mathematics, 2(1) , 2005 . P. Berkhin. Survey: A survey on PageRank computing. Internet Mathematics, 2(1), 2005."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1052934.1052942"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972733.4"},{"key":"e_1_2_1_8_1","volume-title":"Towards exploiting link evolution","author":"Chien S.","year":"2001","unstructured":"S. Chien , C. Dwork , S. Kumar , and D. Sivakumar . Towards exploiting link evolution , 2001 . S. Chien, C. Dwork, S. Kumar, and D. Sivakumar. Towards exploiting link evolution, 2001."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242610"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376928"},{"key":"e_1_2_1_11_1","volume-title":"Towards scaling fully personalized PageRank: Algorithms, lower bounds, and experiments. Internet Mathematics, 2(3)","author":"Fogaras D.","year":"2005","unstructured":"D. Fogaras , B. R\u00e1cz , K. Csalog\u00e1ny , and T. Sarl\u00f3s . Towards scaling fully personalized PageRank: Algorithms, lower bounds, and experiments. Internet Mathematics, 2(3) , 2005 . D. Fogaras, B. R\u00e1cz, K. Csalog\u00e1ny, and T. Sarl\u00f3s. Towards scaling fully personalized PageRank: Algorithms, lower bounds, and experiments. Internet Mathematics, 2(3), 2005."},{"key":"e_1_2_1_12_1","volume-title":"Introduction to social network methods","author":"Hanneman R. A.","year":"2005","unstructured":"R. A. Hanneman and M. Riddle . Introduction to social network methods , chapter 10. published in digital form at http:\/\/faculty.ucr.edu\/hanneman\/, 2005 . R. A. Hanneman and M. Riddle. Introduction to social network methods, chapter 10. published in digital form at http:\/\/faculty.ucr.edu\/hanneman\/, 2005."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/511446.511513"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775191"},{"key":"e_1_2_1_15_1","volume-title":"Exploiting the block structure of the web for computing PageRank. Technical report","author":"Kamvar S.","year":"2003","unstructured":"S. Kamvar , T. Haveliwala , C. Manning , and G. Golub . Exploiting the block structure of the web for computing PageRank. Technical report , Stanford University , 2003 . S. Kamvar, T. Haveliwala, C. Manning, and G. Golub. Exploiting the block structure of the web for computing PageRank. Technical report, Stanford University, 2003."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775190"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324140"},{"key":"e_1_2_1_18_1","volume-title":"Updating PageRank using the group inverse and stochastic complementation. Technical report","author":"Langville A. N.","year":"2002","unstructured":"A. N. Langville and C. D. Meyer . Updating PageRank using the group inverse and stochastic complementation. Technical report , North Carolina State University , Mathematics Department , 2002 . A. N. Langville and C. D. Meyer. Updating PageRank using the group inverse and stochastic complementation. Technical report, North Carolina State University, Mathematics Department, 2002."},{"key":"e_1_2_1_19_1","volume-title":"Updating the stationary vector of an irreducible markov chain. Technical report","author":"Langville A. N.","year":"2002","unstructured":"A. N. Langville and C. D. Meyer . Updating the stationary vector of an irreducible markov chain. Technical report , North Carolina State University , Mathematics Department , 2002 . A. N. Langville and C. D. Meyer. Updating the stationary vector of an irreducible markov chain. Technical report, North Carolina State University, Mathematics Department, 2002."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129091"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1013367.1013491"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/382979.383041"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956972"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2007.10129293"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1394399"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060829"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1321440.1321465"},{"key":"e_1_2_1_28_1","unstructured":"Netflix cinematch. http:\/\/www.netflix.com.  Netflix cinematch. http:\/\/www.netflix.com."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/383952.384003"},{"key":"e_1_2_1_30_1","volume-title":"Stanford InfoLab","author":"Page L.","year":"1999","unstructured":"L. Page , S. Brin , R. Motwani , and T. Winograd . The PageRank citation ranking: Bringing order to the web. Technical report , Stanford InfoLab , 1999 . L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1135777.1135823"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972788.64"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1929861.1929864","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:07:15Z","timestamp":1672225635000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1929861.1929864"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["10.14778\/1929861.1929864"],"URL":"https:\/\/doi.org\/10.14778\/1929861.1929864","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2010,12]]}}}