Large Structures Seminar: Nikolaj Tatti

Discovering dense subgraphs is one the fundamental problems in graph mining. A known result states that if we use average degree to measure density, then we can discover the densest subgraph in polynomial time. We extend this result by considering the problem of discovering multiple dense subgraphs. More specifically, we consider discovering subgraphs whose density cannot be improved by adding or replacing nodes. We show that these subgraphs form a chain and that each subgraph is the densest subgraph containing properly the previous subgraph. We demonstrate that these subgraphs can be discovered in polynomial time and provide a linear-time 1/2-approximation algorithm that bridges k-core decomposition and discovering dense subgraphs.