Inferring Community-driven Structure in Complex Networks

Despite a long tradition in the study of graphs and relational data, for decades the analysis of complex networks was limited by difficulties in data collection and computational burdens. The advent of new technologies in life sciences, as well as in our daily life, has suddenly shed light on the many interconnections that our world features, from friendships and collaborations between individuals or organizations, to functional couplings between cellular molecules. This has highly facilitated the collection of relational data, fostering an unprecedented interest in network science. Understanding relations encoded in complex networks, however, still represents a challenging task, and statistical methods that can help to summarize and simplify complex networks are needed. In this thesis we show that often one can gain a deep insight of a network by focusing their attention on communities, i.e. on clusters of nodes, and on the relations that exist between them. We begin by presenting NEAT, a network-based test that allows to assess relations between gene sets in a gene interaction network. NEAT extends traditional gene enrichment analysis tests by incorporating information on interactions between genes and it overcomes some limitations of existing network enrichment analysis approaches. Then, we propose two extended stochastic blockmodels that allow to infer the relations that exist between communities from relations between pairs of individuals in a social network. We advocate the use of penalized inference to estimate these models, with the aim of deriving a sparse reduced graph between communities. Application of these models to bill cosponsorship networks in the Italian Chamber of Deputies allows us to reconstruct the pattern of collaborations between Italian political parties from 2001 to 2015. Finally, we propose a novel clustering strategy for sequences of graphs, based on mixtures of generalized linear models. We show that the proposed clustering method not only is capable to retrieve subpopulations of networks within a cross-sectional or longitudinal sequence of networks, but it also allows to directly characterize them by considering each of the components that form the mixture model.

Per decenni, lo studio di reti complesse è stato limitato da difficoltà nella raccolta dei dati e computazionali. L’avvento di nuove tecnologie, tanto nelle scienze biologiche quanto nella nostra vita quotidiana, ha enormemente facilitato la raccolta di dati relazionali, alimentando un interesse nello studio di reti complesse senza precedenti. La comprensione delle relazioni rappresentate in reti complesse, tuttavia, è ancora oggi una sfida impegnativa, che richiede lo sviluppo di metodi statistici innovativi, in grado di riassumere e semplificare le informazioni contenute in reti complesse. In questa tesi discutiamo la possibilità di interpretare una rete attraverso lo studio delle relazioni fra gruppi di nodi. La trattazione comincia da NEAT, un test per lo studio delle relazioni fra gruppi di geni in reti biologiche. NEAT estende i test di gene enrichment analysis sfruttando informazioni sulle relazioni fra geni rappresentate tramite una rete, risolvendo al contempo le limitazioni dei test per network enrichment analysis preesistenti. Inoltre, proponiamo due estensioni di modelli stocastici a blocchi per lo studio delle relazioni fra gruppi di individui in reti sociali e l’utilizzo di metodi di inferenza penalizzata per derivare un grafo ridotto che sintetizzi le relazioni fra blocchi di nodi. L’applicazione di tali modelli a reti di cosponsorizzazione delle proposte di legge nel Parlamento Italiano ci consente di ricostruire le collaborazioni fra i partiti politici italiani dal 2001 al 2015. Infine, proponiamo una nuova strategia di clustering per sequenze di grafi basata su misture di modelli lineari generalizzati. Tale metodologia consente non solo di individuare sottopopolazioni di grafi in popolazioni di reti, ma anche di caratterizzare ciascuna di esse per mezzo delle componenti che formano la mistura.