Thesis title: Dense Subgraph Mining: Novel Concepts and Real-world Applications
Dense subgraphs, which are groups of highly interconnected nodes in a graph, can reveal crucial patterns and structures in the data. The process of uncovering these patterns, known as dense subgraph mining, has been a central topic in computer science since its emergence in the 1970s and continues to attract significant research attention due to multiple aspects.
One key aspect is its intuitive nature and simplicity. The potential applications of dense subgraph mining extend across a diverse range of crucial research domains, including biology, neuroscience, social networks, and more, making it a valuable tool for uncovering insights in these fields.
Additionally, the emergence of new research questions and graph models highlights the need for new definitions of dense structures.
However, despite the conceptual simplicity of dense subgraph mining, the process often presents complex combinatorial optimization challenges, emphasizing the need for efficient algorithms to effectively solve these problems.
In this thesis, we begin by revisiting the foundational problem in the field of dense subgraph mining: the Densest Subgraph problem. We provide a comprehensive overview of its long history and the different variants that have been developed over time.
Throughout the remainder of the thesis, we introduce two novel concepts of dense subgraphs, namely contrast subgraphs and niches, and demonstrate their utility in multiple research domains. We also present an efficient method for extracting frequent cross-graph quasi-cliques in multilayer networks, which enhances the capabilities of dense subgraph mining, making it easier to uncover deeper insights from multilayer network data.
Extensive experimental analysis confirms the validity of our results and highlights the relevance of this research topic in various domains. Our work in this field is featured in reputable conferences (i.e. KDD, VLDB) and journals (i.e. TKDD, GigaScience), demonstrating its significance for the scientific community.