A Survey on the Densest Subgraph Problem and Its Variants
The Densest Subgraph Problem requires to find, in a given graph, a subset of vertices whose induced subgraph maximizes a measure of density. The problem has received a great deal of attention in the algorithmic literature since the early 1970s, with many variants proposed and many applications built on top of this basic definition. Recent years have witnessed a revival of research interest in this problem with several important contributions, including some groundbreaking results, published in 2022 and 2023. This survey provides a deep overview of the fundamental results and an exhaustive coverage of the many variants proposed in the literature, with a special attention to the most recent results. The survey also presents a comprehensive overview of applications and discusses some interesting open problems for this evergreen research topic.
Code (0)
등록된 구현이 없습니다.
Tasks
SurveySimilar Papers 제목 키워드 기반
Fast and Simple Densest Subgraph with Predictions
We study the densest subgraph problem and its variants through the lens of learning-augmented algorithms. For this problem, the greedy algorithm by Charikar (APPROX 2000) provides a linear-time $ 1/2 $-approximation, whi…
Differentially Private Densest Subgraph Detection
Densest subgraph detection is a fundamental graph mining problem, with a large number of applications. There has been a lot of work on efficient algorithms for finding the densest subgraph in massive networks. However, i…
Graph MiningConvex optimization for the densest subgraph and densest submatrix problems
We consider the densest $k$-subgraph problem, which seeks to identify the $k$-node subgraph of a given input graph with maximum number of edges. This problem is well-known to be NP-hard, by reduction to the maximum cliqu…
Faster Algorithms for Generalized Mean Densest Subgraph Problem
The densest subgraph of a large graph usually refers to some subgraph with the highest average degree, which has been extended to the family of $p$-means dense subgraph objectives by~\citet{veldt2021generalized}. The $p$…
Parallel Algorithms for Densest Subgraph Discovery Using Shared Memory Model
The problem of finding dense components of a graph is a widely explored area in data analysis, with diverse applications in fields and branches of study including community mining, spam detection, computer security and b…
Computer SecuritySpam detection