La tesi si prefigge di scoprire interazioni periodiche frequenti tra i membri di una popolazione il cui comportamento viene studiato in un certo arco di tempo. Le interazioni tra i membri della popolazione sono rappresentate da archi E tra vertici V di un grafo. Una rete dinamica consiste in una serie di T timestep per ciascuno dei quali esiste un grafo che rappresenta le interazioni attive in quel dato istante. Questa tesi presenta ListMiner, un algoritmo per il problema dell’estrazione di sottografi periodici. La complessità computazionale di tale algoritmo è O((V+E) T2 ln (T /σ)), dove σ è il minimo numero di ripetizioni periodiche necessarie per riportare il sottografo estratto in output. Questa complessità propone un miglioramento di un fattore T rispetto l’unico algoritmo noto in letteratura, PSEMiner. Nella tesi sono inoltre presenti un’analisi dei risultati ottenuti e una presentazione di una variante del problema

Periodic subgraph mining in dynamic networks

Barbares, Manuel
2010/2011

Abstract

La tesi si prefigge di scoprire interazioni periodiche frequenti tra i membri di una popolazione il cui comportamento viene studiato in un certo arco di tempo. Le interazioni tra i membri della popolazione sono rappresentate da archi E tra vertici V di un grafo. Una rete dinamica consiste in una serie di T timestep per ciascuno dei quali esiste un grafo che rappresenta le interazioni attive in quel dato istante. Questa tesi presenta ListMiner, un algoritmo per il problema dell’estrazione di sottografi periodici. La complessità computazionale di tale algoritmo è O((V+E) T2 ln (T /σ)), dove σ è il minimo numero di ripetizioni periodiche necessarie per riportare il sottografo estratto in output. Questa complessità propone un miglioramento di un fattore T rispetto l’unico algoritmo noto in letteratura, PSEMiner. Nella tesi sono inoltre presenti un’analisi dei risultati ottenuti e una presentazione di una variante del problema
2010-12-07
79
data mining
File in questo prodotto:
File Dimensione Formato  
Barbares_604065.pdf

accesso aperto

Dimensione 945.34 kB
Formato Adobe PDF
945.34 kB Adobe PDF Visualizza/Apri

The text of this website © Università degli studi di Padova. Full Text are published under a non-exclusive license. Metadata are under a CC0 License

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12608/14259