Главная
Study mode:
on
1
Intro
2
Overview
3
Dense subgraphs
4
Motivation - correlation mining
5
Motivation - fraud detection
6
Motivation - story identification
7
Definition of density
8
Algorithms for static densest subgraph
9
Why dynamic algorithms
10
Our goal - fully dynamic algorithm for Densest Subgraph
11
Algorithms for dynamic densest subgraph
12
LP formulation
13
Dual of the LP
14
Dual LP: load balancing visualization
15
Dual LP: local optimality
16
We want approximate: allow some slack
17
Visualize as graph orientation problem
18
Dynamic graph orientation
19
Bounding number of flips
20
Dealing with dynamic
21
Runtime
22
Recap
Description:
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.

Near-Optimal Fully Dynamic Densest Subgraph

Association for Computing Machinery (ACM)
Add to list
0:00 / 0:00