Models and Algorithms for graph motifs analysis

Nowadays we live in a world of data which can be massively detected and analyzed to improve knowledge of a particular non-trivial features. Often these complex systems can be represented like networks of interactions (e.g. biological, financial, social), where small subgraphs called motifs can be under or over-represented. Motifs are defined like the basic building blocks of a network since they cover particular functions. The process of network motif discovery requires graph isomorphism that is an NP-Hard problem. Computational time of these algorithms grows exponentially when network or motif size increase. There are two mainly approaches to motif discovery, computational and analytical. In this thesis, after a comprehensive review of available computational algorithm, we will focus on the most powerful category, analytical methods, which are efficient, precise enough but in any case biased. We propose two analytical model based on an existent one to extend and improve its performance. The first aim is to estimate motif significance through the first two moments calculation for induced topologies since that no computational feasible approaches are available up to date. We have developed a new data structure AdditiveSet and vector-based algorithms that allows to calculate fast an accurate induced probability of a motif on undirected networks. Even if analytical models are faster than computational ones and precise enough in estimation, most of the random null models used to randomize graphs are biased. To fill this gap we have developed and engineered an analytical model, based on the previous one, that uses a model of entropy maximization and soft constraint to calculate the probability of non-induced motif existence on undirected graphs. The results show how this random null model fit better observed occurrences and the way how microcanonical and canonical model affect them.

Oggi viviamo in un mondo in cui i dati possono essere acquisiti ed analizzati in grandi quantità, in modo da poter scoprire caratteristiche importanti dei sistemi analizzati. Spesso questi sistemi complessi possono essere rappresentati come reti di interazioni (ad esempio biologiche, finanziarie, sociali), dove piccoli sottografi chiamati "motivi" possono essere sotto o sovra-espressi. I "motivi" sono stati definiti come le fondamenta di una rete, dato che ricoprono delle funzioni particolari. Il processo di individuazione dei motivi richiede il calcolo dell'isomorfismo tra grafi che è un problema NP-Hard. Il tempo computazionale di questi algoritmi cresce esponenzialmente quando le dimensioni della rete o del motivo aumentano. Ci sono due principali approcci che si utilizzano per individuare i motivi: quello computazionale e quello analitico. In questa tesi, dopo un'analisi completa degli algoritmi computazionali, ci focalizzeremo sulla categoria più promettente, quella dei modelli analitici, dato che sono efficienti e precisi ma in certi casi affetti da bias. Abbiamo proposto due modelli analitici che estendono e migliorano le potenzialità e le performance di un modello esistente. Il primo obiettivo è stato quello di sviluppare un modello analitico per il calcolo della significatività dei motivi indotti attraverso il calcolo dei primi due momenti, dato che ad oggi nessun approccio ha costi computazionali accettabili. Abbiamo sviluppato una nuova struttura dati chiamata "AdditiveSet" e un algoritmo che esegue operazioni vettoriali che permettono di calcolare velocemente ed in modo preciso la probabilità di un motivo indotto in grafi non direzionati. Anche se i modelli analitici sono più veloci di quelli computazionali e abbastanza precisi nella stima dei risultati, la maggior parte dei modelli nulli utilizzati per randomizzare i grafi sono affetti da bias. Per porre rimedio a questo problema abbiamo sviluppato e ingegnerizzato un modello analitico, basato sul precedente, che sfrutta la massimizzazione dell'entropia e vincoli deboli per calcolare la probabilità di esistenza dei motivi non indotti in grafi indiretti. I risultati mostrano che il modello nullo approssima molto bene le occorrenze realmente osservate e come questi differiscano in base all'utilizzo di un modello microcanonico o canonico.