Local Computation of PageRank: Simple and Optimal
- Dr. Hanzhi Wang, The University of Melbourne
- Time: 2025-11-25 15:00
- Host: Dr. Shaofeng Jiang
- Venue: Room 204, Courtyard No.5, Jingyuan
Abstract
PageRank is a classic node centrality measure in graphs, originally proposed by the co-founders of Google to rank web pages in their search engine. With the expansion of the web and modern networks, an important problem is the design of local algorithms that estimate a node’s PageRank score in sublinear time relative to the graph size. This problem, along with its variants, has been the focus of extensive research for over a decade. However, a polynomial gap remained between the previously best upper and lower bounds. In this talk, I will review basic techniques for estimating PageRank (or more generally, random-walk probabilities), and present simple algorithms that close the gap through concise analysis. Joint work (STOC 2024, SODA 2026) with Mikkel Thorup, Zhewei Wei, Ji-Rong Wen, and Mingji Yang.
Biography
Hanzhi Wang is a Lecturer at the School of Computing and Information Systems, The University of Melbourne. From November 2024 to October 2025, she was a Postdoc at Center for Basic Algorithms Research Copenhagen (BARC), University of Copenhagen. She received her PhD in July 2024 from Renmin University of China. Hanzhi’s research focuses on the design of scalable graph algorithms, with previous work emphasizing efficient estimation of random-walk probabilities on large graphs, such as fast PageRank estimation.