A Survey of Densest Subgraph Discovery on Large Graphs
For researchers in graph mining, this survey provides a structured overview of DSD methods and identifies open problems, but it is an incremental contribution as it does not introduce new algorithms or results.
This survey reviews around 50 papers on densest subgraph discovery (DSD) in large graphs, classifying solutions into groups and comparing models. It highlights DSD's applications in social media, DNA motif discovery, and fake follower detection, and outlines future research directions.
With the prevalence of graphs for modeling complex relationships among objects, the topic of graph mining has attracted a great deal of attention from both academic and industrial communities in recent years. As one of the most fundamental problems in graph mining, the densest subgraph discovery (DSD) problem has found a wide spectrum of real applications, such as discovery of filter bubbles in social media, finding groups of actors propagating misinformation in social media, social network community detection, graph index construction, regulatory motif discovery in DNA, fake follower detection, and so on. Theoretically, DSD closely relates to other fundamental graph problems, such as network flow and bipartite matching. Triggered by these applications and connections, DSD has garnered much attention from the database, data mining, theory, and network communities. In this survey, we first highlight the importance of DSD in various real-world applications and the unique challenges that need to be addressed. Subsequently, we classify existing DSD solutions into several groups, which cover around 50 research papers published in many well-known venues (e.g., SIGMOD, PVLDB, TODS, WWW), and conduct a thorough review of these solutions in each group. Afterwards, we analyze and compare the models and solutions in these works. Finally, we point out a list of promising future research directions. It is our hope that this survey not only helps researchers have a better understanding of existing densest subgraph models and solutions, but also provides insights and identifies directions for future study.