Near-Optimal Fully Dynamic Densest Subgraph

Explore the concept of near-optimal fully dynamic densest subgraph algorithms in this 23-minute conference talk. Delve into the applications of dense subgraphs in correlation mining, fraud detection, and story identification. Learn about the definition of density and algorithms for static densest subgraph before understanding the need for dynamic algorithms. Examine the goal of developing a fully dynamic algorithm for Densest Subgraph, including LP formulation, dual LP, and load balancing visualization. Discover how the problem can be visualized as a graph orientation problem and how to deal with dynamic changes. Gain insights into runtime considerations and leave with a comprehensive understanding of this advanced topic in graph theory and algorithms.

Intro
Overview
Dense subgraphs
Motivation - correlation mining
Motivation - fraud detection
Motivation - story identification
Definition of density
Algorithms for static densest subgraph
Why dynamic algorithms
Our goal - fully dynamic algorithm for Densest Subgraph
Algorithms for dynamic densest subgraph
LP formulation
Dual of the LP
Dual LP: load balancing visualization
Dual LP: local optimality
We want approximate: allow some slack
Visualize as graph orientation problem
Dynamic graph orientation
Bounding number of flips
Dealing with dynamic
Runtime
Recap