PhD Graduate

PhD program:: XXXV

supervisor: Francesco Bonchi

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.

Research products

11573/1666597 - 2023 - Discovering Polarization Niches via Dense Subgraphs with Attractors and Repulsers
Fazzone, Adriano; Lanciano, Tommaso; Denni, Riccardo; Tsourakakis, Charalampos E.; Bonchi, Francesco - 01a Articolo in rivista
paper: PROCEEDINGS OF THE VLDB ENDOWMENT (New York, NY : Association for Computing Machinery) pp. 3883-3896 - issn: 2150-8097 - wos: WOS:000993588100006 (1) - scopus: 2-s2.0-85147799890 (2)

11573/1673923 - 2023 - Contrast subgraphs allow comparing homogeneous and heterogeneous networks derived from omics data
Lanciano, Tommaso; Savino, Aurora; Porcu, Francesca; Cittaro, Davide; Bonchi, Francesco; Provero, Paolo - 01a Articolo in rivista
paper: GIGASCIENCE (London : BioMed Central) pp. 1-10 - issn: 2047-217X - wos: WOS:001023600500001 (2) - scopus: 2-s2.0-85148972878 (3)

11573/1363326 - 2020 - Core Decomposition in Multilayer Networks: Theory, Algorithms and Applications
Galimberti, Edoardo; Bonchi, Francesco; Gullo, Francesco; Lanciano, Tommaso - 01a Articolo in rivista
paper: ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA (New York, NY : Association for Computing Machinery, c2007-) pp. 1-40 - issn: 1556-4681 - wos: WOS:000522551000011 (17) - scopus: 2-s2.0-85079231249 (26)

11573/1436722 - 2020 - Explainable Classification of Brain Networks via Contrast Subgraphs
Lanciano, Tommaso; Bonchi, Francesco; Gionis, Aristides - 04b Atto di convegno in volume
conference: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (Virtual Event)
book: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining - (978-1-4503-7998-4)

¬© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma