Università degli studi di Catania
Algoritmi avanzati per il Subgraph Isomorphism, Motif Discovery, e Graph Embedding su reti complesse
Abstract
dc:descriptionI 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.
Degree
thesis:*- Grantor dc:publisher
- Università degli studi di Catania
- Year dc:date
- 2024
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- GRASSO, ROBERTO
- Contributors dc:contributor
-
- PULVIRENTI, ALFREDO
Subjects
dc:subject × 9Rights
dc:rights- Statement dc:rights
-
- info:eu-repo/semantics/openAccess
- license:PUBBLICO - Pubblico con Copyright
- license uri:iris.PUB02
- Language dc:language
- ita
Identifiers
dc:identifier.*- Handle dc:identifier
- https://hdl.handle.net/20.500.11769/657971
- OAI identifier oai:identifier
- oai:www.iris.unict.it:20.500.11769/657971