YoVDO

Dynamic PageRank: Additive Error and Batch Recomputation

Offered By: Simons Institute via YouTube

Tags

Dynamic Graphs Courses Algorithm Design Courses Approximation Algorithms Courses

Course Description

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
Explore the challenges and solutions in maintaining PageRank distributions for dynamic graphs in this 51-minute lecture by Jakub Lacki from Google Research. Delve into the complexities of efficiently updating PageRank values as edges are inserted or deleted from a graph. Discover why achieving constant factor multiplicative approximations of PageRank in dynamic settings is provably hard, resolving a long-standing open question. Learn about a simple yet effective batch recomputation algorithm that maintains good approximations under the L1 error metric. Gain insights from empirical evaluations showing this approach can be up to two orders of magnitude faster than existing dynamic baselines. Understand the trade-offs between relative error goals and practical performance in dynamic graph algorithms.

Syllabus

Dynamic PageRank: Additive Error and Batch Recomputation


Taught by

Simons Institute

Related Courses

Data Visualization GUIs with Dash and Python
YouTube
How to Get Started With Graph ML - Blog Walkthrough
Aleksa Gordić - The AI Epiphany via YouTube
Temporal Graph Networks - GNN Paper Explained
Aleksa Gordić - The AI Epiphany via YouTube
Parallel Batch-Dynamic Graph Representations
Simons Institute via YouTube
Dynamic Algorithms for Center on Graphs
Simons Institute via YouTube