ABSTRACT
We propose and analyze two algorithms for maintaining approximate Personalized PageRank (PPR) vectors on a dynamic graph, where edges are added or deleted. Our algorithms are natural dynamic versions of two known local variations of power iteration. One, Forward Push, propagates probability mass forwards along edges from a source node, while the other, Reverse Push, propagates local changes backwards along edges from a target. In both variations, we maintain an invariant between two vectors, and when an edge is updated, our algorithm first modifies the vectors to restore the invariant, then performs any needed local push operations to restore accuracy.
For Reverse Push, we prove that for an arbitrary directed graph in a random edge model, or for an arbitrary undirected graph, given a uniformly random target node t, the cost to maintain a PPR vector to t of additive error ε as k edges are updated is O(k + d/ε, where d is the average degree of the graph. This is O(1) work per update, plus the cost of computing a reverse vector once on a static graph. For Forward Push, we show that on an arbitrary undirected graph, given a uniformly random start node s, the cost to maintain a PPR vector from s of degree-normalized error ε as k edges are updated is O(k + 1/ε, which is again O(1) per update plus the cost of computing a PPR vector once on a static graph.
Supplemental Material
- Reid Andersen, Christian Borgs, Jennifer Chayes, John Hopcraft, Vahab S Mirrokni, and Shang-Hua Teng. Local computation of pagerank contributions. In Algorithms and Models for the Web-Graph, pages 150--165. Springer, 2007. Google ScholarDigital Library
- Reid Andersen, Fan Chung, and Kevin Lang. Local graph partitioning using pagerank vectors. In Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium on, pages 475--486. IEEE, 2006. Google ScholarDigital Library
- Konstantin Avrachenkov, Nelly Litvak, Danil Nemirovsky, and Natalia Osipova. Monte carlo methods in pagerank computation: When one iteration is sufficient. SIAM Journal on Numerical Analysis, 2007. Google ScholarDigital Library
- Lars Backstrom and Jure Leskovec. Supervised random walks: predicting and recommending links in social networks. In Proceedings of the fourth ACM international conference on Web search and data mining. ACM, 2011. Google ScholarDigital Library
- Bahman Bahmani, Abdur Chowdhury, and Ashish Goel. Fast incremental and personalized pagerank. Proceedings of the VLDB Endowment, 4(3):173--184, 2010. Google ScholarDigital Library
- Shumeet Baluja, Rohan Seth, D Sivakumar, Yushi Jing, Jay Yagnik, Shankar Kumar, Deepak Ravichandran, and Mohamed Aly. Video suggestion and discovery for youtube: taking random walks through the view graph. In Proceedings of the 17th international conference on World Wide Web, pages 895--904. ACM, 2008. Google ScholarDigital Library
- Pavel Berkhin. Bookmark-coloring algorithm for personalized pagerank computing. Internet Mathematics, 3(1):41--62, 2006.Google ScholarCross Ref
- Soumen Chakrabarti. Dynamic personalized pagerank in entity-relation graphs. In Proceedings of the 16th international conference on World Wide Web, pages 571--580. ACM, 2007. Google ScholarDigital Library
- Dániel Fogaras, Balázs Rácz, Károly Csalogány, and Tamás Sarlós. Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments. Internet Mathematics, 2005.Google ScholarCross Ref
- David F Gleich. Pagerank beyond the web. SIAM Review, 57(3):321--363, 2015.Google ScholarDigital Library
- Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Zadeh. Wtf: The who to follow service at twitter. In Proceedings of the 22nd international conference on World Wide Web. International World Wide Web Conferences Steering Committee, 2013. Google ScholarDigital Library
- Taher H Haveliwala. Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search. Knowledge and Data Engineering, IEEE Transactions on, 15(4):784--796, 2003. Google ScholarDigital Library
- Glen Jeh and Jennifer Widom. Scaling personalized web search. In Proceedings of the 12th international conference on World Wide Web. ACM, 2003. Google ScholarDigital Library
- Peter Lofgren. On the complexity of the monte carlo method for incremental pagerank. Information Processing Letters, 114(3):104--106, 2014. Google ScholarDigital Library
- Peter Lofgren. Efficient algorithms for personalized pagerank. arXiv preprint arXiv:1512.04633, 2015.Google Scholar
- Peter Lofgren, Siddhartha Banerjee, and Ashish Goel. Bidirectional pagerank estimation: From average-case to worst-case. In Algorithms and Models for the Web Graph, pages 164--176. Springer, 2015. Google ScholarDigital Library
- Peter Lofgren, Siddhartha Banerjee, and Ashish Goel. Personalized pagerank estimation and search: A bidirectional approach. In WSDM, 2016. Google ScholarDigital Library
- Peter A Lofgren, Siddhartha Banerjee, Ashish Goel, and C Seshadhri. Fast-ppr: Scaling personalized pagerank estimation for large graphs. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1436--1445. ACM, 2014. Google ScholarDigital Library
- Ioannis Mitliagkas, Michael Borokhovich, Alexandros G Dimakis, and Constantine Caramanis. Frogwild!: fast pagerank approximations on graph engines. Proceedings of the VLDB Endowment, 8(8):874--885, 2015. Google ScholarDigital Library
- Naoto Ohsaka, Takanori Maehara, and Ken-ichi Kawarabayashi. Efficient pagerank tracking in evolving networks. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 875--884. ACM, 2015. Google ScholarDigital Library
- Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: bringing order to the web. 1999.Google Scholar
- Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground-truth. In Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, page 3. ACM, 2012. Google ScholarDigital Library
Index Terms
Approximate Personalized PageRank on Dynamic Graphs
Recommendations
Some Insights on Dynamic Maintenance of Gomory-Hu Tree in Cactus Graphs and General Graphs
Algorithms and Discrete Applied MathematicsAbstractFor any flow network, min(s, t)-cut query is a fundamental graph query that asks for a minimum weight cut that separates vertices s and t. Gomory and Hu [13] proposed a data structure which is an undirected weighted tree that compactly stores min(...
A dynamic distributed approach to representing proper interval graphs
First studied by Brodal and Fagerberg [G.S. Brodal, R. Fagerberg, Dynamic representation of sparse graphs, in: Algorithms and Data Structures, Proceedings of the 6th International Workshop, Vancouver, Canada, in: Lecture Notes in Computer Science, vol. ...
Efficient Densest Subgraph Computation in Evolving Graphs
WWW '15: Proceedings of the 24th International Conference on World Wide WebDensest subgraph computation has emerged as an important primitive in a wide range of data analysis tasks such as community and event detection. Social media such as Facebook and Twitter are highly dynamic with new friendship links and tweets being ...
Comments