Networks, Graph Theory

The patient-zero problem with noisy observation

The patient-zero problem consists in finding the initial source of an epidemic outbreak given observations at a later time. In this seminar, I will describe a Bayesian method which is able to infer details on the past history of an epidemics based solely on the topology of the contact network and a single snapshot of partial and noisy observations. The method is built on a Bethe approximation for the posterior distribution, and is inherently exact on tree graphs. Moreover, it can be coupled to a set of equations, based on the variational expression of the Bethe free energy, to find the patient-zero along with maximum-likelihood epidemic parameters.
I will describe the method and some results for simulated epidemics on random graphs, and briefly mention future directions of research in the discrete-time setting, as well as a new method - currently in the test phase - that can perform inference on a continuous time spreading model and deal efficiently with real contact-time data.

Thu, 30/10/2014 - 14:30
Alessandro Ingrosso
HuGeF, Via Nizza 52

Bayesian inference of epidemics on network

I study inference problems for irreversible stochastic epidemic models on network via Belief Propagation algorithm. Previous works derive equations which allow to compute posterior distributions of the time evolution of the state of each node given some observation. It has already been shown that this method outperforms previous ones in the particular case of finding "patient zero" of a SIR epidemic given an observation at a later unknown time. I study performances of this method on the inference of the time evolution of a SIR epidemic subsequent a given observation.

Thu, 16/10/2014 - 14:30
Jacopo Bindi

A cavity-method based approach to the Steiner tree problem on graphs

The minimum weight Steiner tree problem (MST) is an important combinatorial optimization problem over networks that has applications in a wide range of fields. I will mainly focus my attention on two variants of the problem:
the Vertex-disjoint Steiner trees problem and Edges-disjoint Steiner trees problem on graphs. For each variant I will propose some efficient algorithms based on the Belief Propagation approximation scheme.

Thu, 23/10/2014 - 14:30
Anna Paola Muntoni

Spatial disorder in the Voter Model

When we try to study the organization and the properties of ecological systems, non-equilibrium statistical physics is a natural candidate to develop a unified framework for understanding the emergent properties of these kind of systems. Simple interacting particle systems, such as the Voter Model (VM), have found a surprisingly good agreement with empirical data and proved to be a useful null-model that can be treated analytically. Despite the recent progress in this field, still a major issue in ecology and conservation ecology is to understand the effects of habitat fragmentation and heterogeneities on the biodiversity of an ecosystem. Motivated by this open problem, we study the effects of quenched spatial disorder on the long-time behavior of the VM and its nonlinear generalizations.

Wed, 12/12/2012 - 15:00
Claudio Borile
Syndicate content