Key Insights and Future Directions for PageRank on Dynamic Graphs

The study introduces Dynamic Frontier, a highly efficient algorithm for updating PageRank on dynamic graphs. It identifies and iteratively expands affected vertices, achieving speedups of up to 8.3× for edge insertions and 7.6× for mixed updates on a 64-core server. With a 1.8× performance boost per thread doubling, it delivers scalable performance. Future work will explore the optimal frontier expansion for varied batch updates.

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 ...