en
0.25
0.5
0.75
1.25
1.5
1.75
2
Denser than the Densest Subgraph: Extracting Optimal Quasi-Cliques with Quality Guarantees
Published on Sep 27, 20134572 Views
Finding dense subgraphs is an important graph-mining task with many applications. Given that the direct optimization of edge density is not meaningful, as even a single edge achieves maximum density
Related categories
Chapter list
Denser than the Densest Subgraph: Extracting Optimal Quasi-Cliques with Quality Guarantees00:00
Team00:02
Denser than the densest00:07
Graph mining applications02:23
Measures - 103:04
Measures - 203:41
Contributions - 104:09
Contributions - 204:45
Cliques05:06
(Some) Density Functions05:32
Densest Subgraph Problem06:31
k-Densest subgraph06:55
Quasicliques07:19
Edge-Surplus Framework - 107:34
Edge-Surplus Framework - 208:20
Edge-Surplus Framework - 308:50
Hardness of OQC09:39
Multiplicative approximation algorithms10:17
Optimal Quasicliques10:40
Optimal Quasicliques: Local Search Heuristic11:45
Experiments - 112:16
Experiments - 212:30
Top-k densest subgraphs14:01
Constrained Optimal Quasicliques14:56
Application 115:38
Query 1, Papadimitriou and Abiteboul16:01
Query 2, Papadimitriou and Blum16:34
Application 216:53
Query, p5317:40
Future Work18:09
Untitled19:01