演讲人：Hanzhi Wang [University of Melbourne]
时间：14:00-15:00, Nov 28, 2025 (Fri)
地点： RM 1-222, FIT Building
内容：
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.
个人简介:
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, working with Prof. Mikkel Thorup. She received her PhD in July 2024 from Renmin University of China, under the supervision of Prof. Zhewei Wei. 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.
