Author:
(1) Subhajit Sahu, IIIT Hyderabad, Hyderabad, Telangana, India (subhajit.sahu@research.iiit.ac.in). Table of Links Abstract and 1 Introduction 2 Related Work 3 Preliminaries 4 Approach 5.1 Experimental Setup 5.2 Performance of Dynamic Frontier PageRank 5.3 Strong Scaling of Dynamic Frontier PageRan 6 Conclusion, Acknowledgments, and References 6. CONCLUSION ACKNOWLEDGMENTS I would like to thank Prof. Kishore Kothapalli, Prof. Sathya Peri, and Prof. Hemalatha Eedi for their support. REFERENCES [1] R. Andersen, F. Chung, and K. Lang. 2007. Local partitioning for directed graphs using pagerank. In in Proc. WAW. 166–178. [2] Bahman Bahmani, Abdur Chowdhury, and Ashish Goel. 2010. Fast incremental and personalized pagerank. arXiv preprint arXiv:1006.2880 (2010). [3] 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. 24–32. [4] Klaus Berberich, Srikanta Bedathur, Gerhard Weikum, and Michalis Vazirgiannis. 2007. Comparing apples and oranges: normalized pagerank for evolving graphs. In Proceedings of the 16th international conference on world wide web. 1145–1146. [5] Yen-Yu Chen, Qingqing Gan, and Torsten Suel. 2004. Local methods for estimating pagerank values. In Proceedings of the thirteenth ACM international conference on Information and knowledge management. 381–389. [6] S. Chien, C. Dwork, R. Kumar, and D. Sivakumar. 2001. Towards Exploiting Link Evolution. [7] P. Desikan, N. Pathak, J. Srivastava, and V. Kumar. 2005. Incremental Page Rank Computation on Evolving Graphs. In Special Interest Tracks and Posters of the 14th International Conference on World Wide Web (Chiba, Japan) (WWW ’05). Association for Computing Machinery, New York, NY, USA, 1094–1095. https://doi.org/10.1145/1062745.1062885 [8] L. Dhulipala, G.E. Blelloch, and J. Shun. 2019. Low-latency graph streaming using compressed purely-functional trees. In ACM SIGPLAN PLDI. 918–934. [9] H. Dubey and N. Khare. 2022. Fast parallel computation of PageRank scores with improved convergence time. IJDMMM 14, 1 (2022), 63–88. [10] A. Fender, N. Thejaswi, and B. Rees. [n. d.]. rapidsai/nvgraph. https://github. com/rapidsai/nvgraph/blob/main/cpp/src/pagerank.cu#L149 [11] P. Garg and K. Kothapalli. 2016. STIC-D: Algorithmic Techniques For Efficient Parallel Pagerank Computation on Real-World Graphs. In Proceedings of the 17th International Conference on Distributed Computing and Networking - ICDCN ’16. ACM Press, 1—10. [12] H. Giri, M. Haque, and D. Banerjee. 2020. HyPR: Hybrid Page Ranking on Evolving Graphs. In Proc. IEEE 27th International Conference on High Performance Computing, Data, and Analytics (HiPC). 62–71. [13] Kyung Soo Kim and Yong Suk Choi. 2015. Incremental iteration method for fast pagerank computation. In Proceedings of the 9th International Conference on Ubiquitous Information Management and Communication. 1–5. [14] S. Kolodziej, M. Aznaveh, M. Bullock, J. David, T. Davis, M. Henderson, Y. Hu, and R. Sandstrom. 2019. The SuiteSparse matrix collection website interface. The Journal of Open Source Software 4, 35 (Mar 2019), 1244. [15] A.N. Langville and C.D. Meyer. 2006. A reordering for the PageRank problem. SIAM SISC 27, 6 (2006), 2112–2120. [16] J. Leskovec and A. Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. (06 2014). [17] NVIDIA Corporation. 2019. nvGRAPH Library User’s Guide. https://docs.nvidia. com/cuda/archive/10.1/pdf/nvGRAPH_Library.pdf [18] Naoto Ohsaka, Takanori Maehara, and Ken-ichi Kawarabayashi. 2015. Efficient pagerank tracking in evolving networks. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining. 875–884. [19] L. Page, S. Brin, R. Motwani, and T. Winograd. 1999. The PageRank citation ranking: Bringing order to the web. Technical Report. Stanford InfoLab. [20] R.P. Pashikanti and S. Kundu. 2022. FPPR: fast pessimistic (dynamic) PageRank to update PageRank in evolving directed graphs on network changes. SNAM 12, 1 (2022), 141. [21] S.J. Plimpton and K.D. Devine. 2011. MapReduce in MPI for large-scale graph algorithms. Parallel Comput. 37, 9 (2011), 610–632. [22] Subhajit Sahu, Kishore Kothapalli, and Dip Sankar Banerjee. 2022. Dynamic Batch Parallel Algorithms for Updating PageRank. In 2022 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). IEEE, 1129–1138. [23] A. Sarma, A. Molla, G. Pandurangan, and E. Upfal. 2013. Fast Distributed PageRank Computation. In Distributed Computing and Networking. Springer Berlin Heidelberg, Berlin, Heidelberg, 11–26. [24] Zexing Zhan, Ruimin Hu, Xiyue Gao, and Nian Huai. 2019. Fast incremental pagerank on dynamic networks. In International Conference on Web Engineering. Springer, 154–168. [25] T. Zhang. 2017. Efficient incremental pagerank of evolving graphs on GPU. In IEEE ICCSEC. 1232–1236. This paper is available on arxiv under CC BY-NC-SA 4.0 DEED license. Author: (1) Subhajit Sahu, IIIT Hyderabad, Hyderabad, Telangana, India (subhajit.sahu@research.iiit.ac.in). Author: Author: (1) Subhajit Sahu, IIIT Hyderabad, Hyderabad, Telangana, India (subhajit.sahu@research.iiit.ac.in). Table of Links Abstract and 1 Introduction Abstract and 1 Introduction 2 Related Work 2 Related Work 3 Preliminaries 3 Preliminaries 4 Approach 4 Approach 5.1 Experimental Setup 5.1 Experimental Setup 5.2 Performance of Dynamic Frontier PageRank 5.2 Performance of Dynamic Frontier PageRank 5.3 Strong Scaling of Dynamic Frontier PageRan 5.3 Strong Scaling of Dynamic Frontier PageRan 6 Conclusion, Acknowledgments, and References 6 Conclusion, Acknowledgments, and References 6. CONCLUSION ACKNOWLEDGMENTS I would like to thank Prof. Kishore Kothapalli, Prof. Sathya Peri, and Prof. Hemalatha Eedi for their support. REFERENCES [1] R. Andersen, F. Chung, and K. Lang. 2007. Local partitioning for directed graphs using pagerank. In in Proc. WAW. 166–178. [2] Bahman Bahmani, Abdur Chowdhury, and Ashish Goel. 2010. Fast incremental and personalized pagerank. arXiv preprint arXiv:1006.2880 (2010). [3] 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. 24–32. [4] Klaus Berberich, Srikanta Bedathur, Gerhard Weikum, and Michalis Vazirgiannis. 2007. Comparing apples and oranges: normalized pagerank for evolving graphs. In Proceedings of the 16th international conference on world wide web. 1145–1146. [5] Yen-Yu Chen, Qingqing Gan, and Torsten Suel. 2004. Local methods for estimating pagerank values. In Proceedings of the thirteenth ACM international conference on Information and knowledge management. 381–389. [6] S. Chien, C. Dwork, R. Kumar, and D. Sivakumar. 2001. Towards Exploiting Link Evolution. [7] P. Desikan, N. Pathak, J. Srivastava, and V. Kumar. 2005. Incremental Page Rank Computation on Evolving Graphs. In Special Interest Tracks and Posters of the 14th International Conference on World Wide Web (Chiba, Japan) (WWW ’05). Association for Computing Machinery, New York, NY, USA, 1094–1095. https://doi.org/10.1145/1062745.1062885 [8] L. Dhulipala, G.E. Blelloch, and J. Shun. 2019. Low-latency graph streaming using compressed purely-functional trees. In ACM SIGPLAN PLDI. 918–934. [9] H. Dubey and N. Khare. 2022. Fast parallel computation of PageRank scores with improved convergence time. IJDMMM 14, 1 (2022), 63–88. [10] A. Fender, N. Thejaswi, and B. Rees. [n. d.]. rapidsai/nvgraph. https://github. com/rapidsai/nvgraph/blob/main/cpp/src/pagerank.cu#L149 [11] P. Garg and K. Kothapalli. 2016. STIC-D: Algorithmic Techniques For Efficient Parallel Pagerank Computation on Real-World Graphs. In Proceedings of the 17th International Conference on Distributed Computing and Networking - ICDCN ’16. ACM Press, 1—10. [12] H. Giri, M. Haque, and D. Banerjee. 2020. HyPR: Hybrid Page Ranking on Evolving Graphs. In Proc. IEEE 27th International Conference on High Performance Computing, Data, and Analytics (HiPC). 62–71. [13] Kyung Soo Kim and Yong Suk Choi. 2015. Incremental iteration method for fast pagerank computation. In Proceedings of the 9th International Conference on Ubiquitous Information Management and Communication. 1–5. [14] S. Kolodziej, M. Aznaveh, M. Bullock, J. David, T. Davis, M. Henderson, Y. Hu, and R. Sandstrom. 2019. The SuiteSparse matrix collection website interface. The Journal of Open Source Software 4, 35 (Mar 2019), 1244. [15] A.N. Langville and C.D. Meyer. 2006. A reordering for the PageRank problem. SIAM SISC 27, 6 (2006), 2112–2120. [16] J. Leskovec and A. Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. (06 2014). [17] NVIDIA Corporation. 2019. nvGRAPH Library User’s Guide. https://docs.nvidia. com/cuda/archive/10.1/pdf/nvGRAPH_Library.pdf [18] Naoto Ohsaka, Takanori Maehara, and Ken-ichi Kawarabayashi. 2015. Efficient pagerank tracking in evolving networks. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining. 875–884. [19] L. Page, S. Brin, R. Motwani, and T. Winograd. 1999. The PageRank citation ranking: Bringing order to the web. Technical Report. Stanford InfoLab. [20] R.P. Pashikanti and S. Kundu. 2022. FPPR: fast pessimistic (dynamic) PageRank to update PageRank in evolving directed graphs on network changes. SNAM 12, 1 (2022), 141. [21] S.J. Plimpton and K.D. Devine. 2011. MapReduce in MPI for large-scale graph algorithms. Parallel Comput. 37, 9 (2011), 610–632. [22] Subhajit Sahu, Kishore Kothapalli, and Dip Sankar Banerjee. 2022. Dynamic Batch Parallel Algorithms for Updating PageRank. In 2022 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). IEEE, 1129–1138. [23] A. Sarma, A. Molla, G. Pandurangan, and E. Upfal. 2013. Fast Distributed PageRank Computation. In Distributed Computing and Networking. Springer Berlin Heidelberg, Berlin, Heidelberg, 11–26. [24] Zexing Zhan, Ruimin Hu, Xiyue Gao, and Nian Huai. 2019. Fast incremental pagerank on dynamic networks. In International Conference on Web Engineering. Springer, 154–168. [25] T. Zhang. 2017. Efficient incremental pagerank of evolving graphs on GPU. In IEEE ICCSEC. 1232–1236. This paper is available on arxiv under CC BY-NC-SA 4.0 DEED license. This paper is available on arxiv under CC BY-NC-SA 4.0 DEED license. available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Key Insights and Future Directions for PageRank on Dynamic Graphs

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Comparative Analysis of Incremental Methods for Updating PageRank on Dynamic Graphs

A Comprehensive Examination of Algorithmic Behaviors in Diverse Grid Settings

Incremental Vertex Processing Boosts PageRank Update Efficiency on Dynamic Graphs

Python Web Development with Reflex: Creating Dynamic Graphs Easily

Dynamic Frontier PageRank Efficiently Updates Ranks on Dynamic Graphs

Comparative Analysis of Incremental Methods for Updating PageRank on Dynamic Graphs

Comparative Analysis of Incremental Methods for Updating PageRank on Dynamic Graphs

A Comprehensive Examination of Algorithmic Behaviors in Diverse Grid Settings

Incremental Vertex Processing Boosts PageRank Update Efficiency on Dynamic Graphs

Python Web Development with Reflex: Creating Dynamic Graphs Easily

Dynamic Frontier PageRank Efficiently Updates Ranks on Dynamic Graphs

Comparative Analysis of Incremental Methods for Updating PageRank on Dynamic Graphs

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps