- Remco van der Hofstad: Processes on random graphs: routing and attack vulnerability
Empirical findings have shown that many real-world networks share
fascinating features. Indeed, many real-world networks are small worlds, in
the sense that typical distances are much smaller than the size of the
network. Further, many real-world networks are scale-free in the sense
that there is a high variability in the number of connections of the elements of
the networks. Therefore, such networks are highly inhomogeneous.
Spurred by these empirical findings, models have been proposed
for such networks. In this talk, we shall discuss empirical findings
of real-world networks, and describe some of the models proposed for them.
In the real-world, we are not only interested in the topology of networks,
but also in processes living on them. Think of routing on the Internet,
the spread of information and disease on social networks, and searching on
the World-Wide Web. In this talk, we discuss two of such processes
in detail.
The first example is first-passage percolation on random graphs,
which is a simple model for shortest-weight routing on complex networks.
We discuss how random edge weight change the structure of shortest-weight
paths, and derive precise limiting results for the weight and
number of edges in the shortest-weight path between two uniform
vertices. The results show that adding i.i.d. exponential weights
on the edges has a marked effect on the structure of shortest-weight paths.
We close this part by discussing various open problems and conjectures.
The second example is percolation on random graph, which is a simple
model for the attack vulnerability of networks. We discuss the connectivity
behavior at and close to the critical value.
Our results show that, for inhomogeneous random graphs with
highly variable vertex degrees, the critical behavior admits
a transition when the third moment of the degrees turns from
finite to infinite. When the third moment is finite,
the largest clusters in a graph of n vertices have size n2/3 and
the scaling limit equals that on the Erdoes-Renyi random graph.
When the third moment is infinite, the largest clusters have size
to nα for some α ∈ (1/2,2/3), and the scaling
limit is rather different. Similar phase transitions have been shown
to occur for typical distances in such random graphs when
the variance of the degrees turns from finite to infinite.
We finally discuss some of the ingredients used in the proofs, namely
the tree-like nature of the random graphs under consideration and
the use of (continuous- and discrete-time) branching processes.
This is joint work with:
Gerard Hooghiemstra, Shankar Bhamidi, Johan van Leeuwaarden, Piet Van Mieghem, Henri van den Esker
and Dmitri Znamenski.
- Charles Bordenave: How to scotch a rumor in a network ?
We will present an epidemic dynamics which has a different qualitative behavior from the usual SIR dynamics. On a large complete graph, this
epidemic boils down to the birth-and-assassination process which was
introduced by Aldous and Krebs in 1991. We will give formulas on the
total number of born particles in the stable birth-and-assassination
process, and prove that it has an heavy-tailed distribution. We will
also extend these results to the usual random graphs ensembles.
Finally, we will discuss some unsolved problems around this process.
- Nicolas Broutin: Metric structure of critical random graphs
The structure of the Erdos-Renyi random graph changes drastically when the average degree approaches one. One of the important parameters of random graphs is the distribution of distances between pairs of nodes. When the average degree is far enough from one, a number of results describe quite precisely the distribution of distances, in particular extreme distances like the diameter. In the critical regime, when the average degree is close to one, the structure of the graphs becomes more complex and classical approaches from graph theory do not allow a precise characterization of distances.
We will see how one can apply the ideas of Gromov and their applications to scaling limits of large random structures as in the work of Aldous, Evans, Le Gall, Pitman, and many others to obtain precise information about distances in critical random graphs. When dealing with distances, it is convenient to see a graph as a metric space endowed with the graph distance. We will see in which sense the Gromov-Hausdorff distance allows to define the convergence of graphs as metric spaces. We will also introduce a method based combinatorics (bijections) and probability (weak convergence and Brownian excursion and continuum random trees) that allows to define a limiting metric space for critical Erdos-Renyi random graphs. The distribution of distances in large random graphs can then be read directly on the limiting object. We will also discuss alternate constructions of the limiting metric space associated to a single connected component.
(This is joint work with L. Addario-Berry and C. Goldschmidt)
- Laurent Decreusefond: Beyond random graphs : random simplicial complexes. Application to sensor networks
Given a Poisson process on a d-dimensional torus, its random geometric simplicial complex is the complex whose vertices are the points of the Poisson process and simplices are given by the Cech complex associated to the coverage of each point. We compute explicitly the mean number of k-simplices as well as the mean of the Euler's characteristic. Then, by means of Malliavin calculus, we show that the number of any connected geometric simplicial complex converges to the Gaussian law when the intensity of the Poisson point process tends to infinity. We use a concentration inequality to find bounds for the for the distribution of the Betti number of first order in such simplicial complex.
- Gabor Lugosi: On the clique number of high-dimensional random geometric graphs
The talk is on the behavior of random geometric graphs in high dimensions. We show that as the dimension grows, the graph becomes similar to an
Erdös-Rényi random graph. We pay particular attention to the clique number of such graphs and show that it is very close to that of the corresponding Erdös-Rényi graph when the dimension is larger than log(n)3 where n is the number of vertices. We describe some statistical applications of
testing dependencies. The talk is based on joint work with Luc Devroye, András György, and Frederic Udina.
- Jean-François Marckert: To be announced
To be announced
- Catherine Matias: About some statistical models for random graphs
I will try to give a review of the models used by statisticians for random graphs. This will include the exponential
random graph model, a (short) presentation of the stochastic blockmodel
(see S. Robin's talk for more), overlapping blockmodels, latent space
models as well as dynamic extensions...
The focus will be on the statistical issues raised by network data.
- Stéphane Robin: Variational inference for the stochastic blockmodel
The statistical inference of several models for random graphs has received a great attention in the last decade. Among these models, the stochastic blockmodel (and variations around it) is one of the most popular as it provides a simple description of the heterogeneous structure observed in many networks. This model can be viewed as a mixture model where each node belongs to a class and edges are drawn between the nodes conditionally to they class they belong to.
As for most incomplete data model, the statistical inference is not straightforward and most methods require to retrieve the conditional distribution of the unobserved data (the classes) given the observed ones (the edges). Variational inference provides a general framework to provide an optimal approximation of this distribution, in the sense of the Küllback-Leibler divergence. We will show that, thanks a asymptotic framework that is specific to networks, the variational approximation is efficient.
We will illustrate these works with applications in molecular biology and ecology.
- Raphaël Rossignol : Sharp threshold for percolation on expanders
(joint work with Itai Benjamini, Stephane Boucheron and Gabor Lugosi)
This work can be seen as a sequel of an article by Alon, Benjamini and
Stacey (2005)
about percolation on finite graphs. Except for the complete graph and
random regular
graphs, percolation on finite graphs has not yet received so
attention. Probably the
first two properties to be investigated in percolation are the unicity
of the giant
component and the sharpness of the percolation transition. Alon,
Benjamini and Stacey
proved that unicity occurs on expanders. They also proved that for
d-regular expanders
with high girth, the percolation transition is sharp, around 1/(d-1).
The purpose of this
talk is to show how one can still prove some sharpness result for the
percolation
transition on expanders, without the two hypotheses of high girth and
regularity.
- Augusto Teixeira: Critical window for the vacant set left by random walk on random regular graphs
In this talk we will consider a random walk on a random regular graph with N vertices. We define the vacant set Vt as the set of sites not visited
by the random walk until time t. First we will describe the phase transition that the set Vt undergoes as the time t grows. Namely, the
size of its largest component Ct drops sharply from N to log(N), as t/N
crosses a critical threshold u*. We will then discuss some recent results
obtained for the size of Ct around this critical time u*. In particular
we will show that if t/N is contained in the so called critical window (of
radius N1/3 around u*), then |Ct| ~ N2/3. Such results and
critical exponents resemble the ones appearing in Erdös-Rényi random
graphs.
- Gaël Varoquaux: Graphical models of brain function across individuals
ognitive function arises from the interplay of specialized brain
regions. Yet mapping these interactions and their role in cognition is a
challenging task. Indeed, the tool of choice for brain mapping,
functional Magnetic Resonance Imaging (fMRI) allows for only a small
number of observations per experimental run and samples a variety of
confounding processes: task-driven and on-going brain activity as well as
structured physiological and imaging noise. Finally, subject-to-subject
variability in brain shape and function makes the use of multiple
datasets challenging. In these datasets, correlations in the fluctuations
of brain activity reveal functional interactions. We use Gaussian
graphical models to infer from these fluctuations graphical
representations of brain function. For medical applications, we are
interested capturing the variability of brain interactions in healthy and
patient populations. In this talk, I will present some results related to
statistical inference on graphical models estimated across different
subjects.
First, we consider the detection of pathology-specific changes in the
covariance structure between a small number of brain regions. We cast the
problem as a comparison of maximum-likelihood estimates, the graphs,
across different populations, the subjects, using the Fisher-Rao metric.
We build a model of subject-to-subject variability of the covariance
based on the Riemannian properties of the corresponding probabilistic
model space, the symmetric positive definite cone. In this formulation,
modifications of the graph edges can be detected efficiently with
univariate tests on a reparametrization of the covariances. We apply this
procedure to detecting reorganizations of brain function on a
inhomogeneous group of post-stroke patients.
Second, we introduce covariance selection to regularize the estimation of
large covariance matrices from the limited data at hand. To benefit from
multi-subject data, we use a mixed-norm penalization to learn a common
conditional independence structure across different subjects. This
penalization leads to a tractable convex optimization problem. We set the
penalization level with cross-validation and find that learning
subject-specific graphs with the help of group data yields sparser, more
contrasted, graphs than group-level estimates. From the neuroscientific
point of view, we find that these graphs reveal better the modular
organization of the brain. Indeed, brain regions work together in distant
functional networks to answer specific tasks, such as language
processing. We perform clustering on the functional-interaction graphs
and extract communities that maximize the ratio of intra-class versus
extra-class connections. We find that these communities match some of the
well-known task-specific functional networks, but only on the individual
sparse graphs.
This is joint work with Bertrand Thirion, Andreas Kleinschmidt,
Alexandre Gramfort and Pierre Fillard.
- Nicolas Verzelen: Tests for Gaussian graphical models
Given a size p Gaussian vector X and a graph g=(Γ,E) with p nodes, we say that X is Gaussian graphical model (GGM) with respect to g if for any couple (i,j)∉ E, Xi and Xj are independent conditionally to the remaining variables (Xk)k≠i,k≠j.
GGMs are promising tools for analyzing genetic networks. In practice, biologists often have some knowledge of the
genetic network and may want to assess the quality of their model using gene expression data. In statistical terms, we want to test whether a Gaussian vector X is a GGM with respect to a given graph g using a n-sample of X. I will introduce and analyze such a testing procedure. The test is feasible when the number of nodes p is possibly much larger than n, the only restriction being that the degree of the graph is smaller than log(p)/n.
Using minimax arguments, I will explain why this restriction is unavoidable in graph testing as well as in graph estimation.
