Graphs are powerful tools in computational science, modeling complex relationships across fields such as bioinformatics, social network analysis, and computational chemistry. This thesis addresses fundamental challenges in graph analysis, particularly within the subgraph isomorphism problem, multigraph matching, motif discovery in temporal graphs, and graph embedding in multiplex networks. We present ArcMatch, a novel algorithm for efficient subgraph matching in labeled graphs, enabling deeper insights into structures such as protein-protein interactions and social networks. Expanding this to multi-relational data, MultiGraphMatch tackles subgraph matching in multigraphs, introducing a bit-signature indexing structure to handle complex edge relationships effectively. For dynamic networks, we introduce MODIT, an innovative approach for motif discovery in temporal graphs. This enables the identification of recurring patterns in sequences of interactions, shedding light on temporal dynamics in social and biological systems. Lastly, MPXGAT is proposed as an attention-based deep learning model for embedding multiplex networks. This model captures intricate relationships across layered structures, enhancing applications in link prediction and community detection. Together, these advancements offer scalable, robust methodologies for querying and analyzing large-scale networks in diverse domains, contributing significantly to the fields of bioinformatics, social sciences, and chemistry.
I grafi sono strumenti potenti nelle scienze computazionali, in grado di modellare relazioni complesse in ambiti come la bioinformatica, l'analisi delle reti sociali e la chimica computazionale. Questa tesi affronta sfide fondamentali nell'analisi dei grafi, con particolare riferimento al problema dell'isomorfismo di sottografi, al matching in multigrafi, alla scoperta di motivi in grafi temporali e all'embedding di grafi multiplex. Presentiamo ArcMatch, un nuovo algoritmo per il matching efficiente di sottografi in grafi etichettati, che permette di ottenere informazioni dettagliate su strutture come le interazioni proteina-proteina e le reti sociali. Estendendo questo approccio ai dati multi-relazionali, MultiGraphMatch affronta il problema del matching in multigrafi, introducendo una struttura di indicizzazione a firma di bit per gestire in modo efficiente relazioni complesse tra gli archi. Per i grafi dinamici, introduciamo MODIT, un approccio innovativo per la scoperta di motivi nei grafi temporali, che permette di individuare schemi ricorrenti nelle sequenze di interazioni e di comprendere le dinamiche temporali in sistemi sociali e biologici. Infine, MPXGAT è proposto come un modello di deep learning basato sull'attenzione per l'embedding di grafi multiplex, catturando relazioni complesse tra i vari livelli del grafo e migliorando le applicazioni di predizione di link e rilevamento di comunità. Nel complesso, questi avanzamenti offrono metodologie scalabili e robuste per l'interrogazione e l'analisi di reti su larga scala in vari ambiti, fornendo un contributo significativo ai settori della bioinformatica, delle scienze sociali e della chimica.
Algoritmi avanzati per il Subgraph Isomorphism, Motif Discovery, e Graph Embedding su reti complesse / Grasso, Roberto. - (2024 Nov 19).
Algoritmi avanzati per il Subgraph Isomorphism, Motif Discovery, e Graph Embedding su reti complesse
GRASSO, ROBERTO
2024-11-19
Abstract
Graphs are powerful tools in computational science, modeling complex relationships across fields such as bioinformatics, social network analysis, and computational chemistry. This thesis addresses fundamental challenges in graph analysis, particularly within the subgraph isomorphism problem, multigraph matching, motif discovery in temporal graphs, and graph embedding in multiplex networks. We present ArcMatch, a novel algorithm for efficient subgraph matching in labeled graphs, enabling deeper insights into structures such as protein-protein interactions and social networks. Expanding this to multi-relational data, MultiGraphMatch tackles subgraph matching in multigraphs, introducing a bit-signature indexing structure to handle complex edge relationships effectively. For dynamic networks, we introduce MODIT, an innovative approach for motif discovery in temporal graphs. This enables the identification of recurring patterns in sequences of interactions, shedding light on temporal dynamics in social and biological systems. Lastly, MPXGAT is proposed as an attention-based deep learning model for embedding multiplex networks. This model captures intricate relationships across layered structures, enhancing applications in link prediction and community detection. Together, these advancements offer scalable, robust methodologies for querying and analyzing large-scale networks in diverse domains, contributing significantly to the fields of bioinformatics, social sciences, and chemistry.File | Dimensione | Formato | |
---|---|---|---|
to_upload.pdf
accesso aperto
Tipologia:
Tesi di dottorato
Licenza:
PUBBLICO - Pubblico con Copyright
Dimensione
4.83 MB
Formato
Adobe PDF
|
4.83 MB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.