# European Institute for Statistics, Probability, Stochastic Operations Research and their Applications

About | Research | Events | People | Reports | Alumni | ContactHome

September 19 - 22, 2016

CCS 2016

Complex Systems Society

Beurs van Berlage, Amsterdam

SUMMARY

The Conference on Complex Systems (CCS) has become a major venue for the Complex Systems community since 2003.
After last year success in USA, we are now back in Europe.
AMSTERDAM CCS 2016, will be the major international conference and event for complex systems and interdisciplinary science.

ORGANISING COMMITTEE  CCS

 Peter Sloot (chair) University of Amsterdam / Nanyang Technological University, Singapore Stephan Lansin Nanyang Technilogical University, Singapore Stephan Thurner Medical University of Vienna Saskia Werners Wageningen University Rick Quax University of Amsterdam

******************************************************************************************************

The conference will consist of keynote lectures, parallel sessions and 49 satellite sessions.

Satellite session 49 will be on

"Fundamentals of Networks"

Organised by Remco van der Hofstad (TU/e), Frank den Hollander (UL), Diego Garlaschelli (UL)

WEDNESDAY SEPTEMBER 21

 14-15 - 14.45 Michel Mandjes UvA Scaling Limits for Stochastic Networks 14.45 - 15.15 Lex Schrijver UvA + CWI The partial disjoint paths problem 15.15 - 15.45 Dmitri Krioukov Northeastern University Networks with strong homogeneous clustering are geometric 15.45 - 16.15 break 16.15 - 16.45 Diego Garlaschelli Leiden University Breaking of Ensemble Equivalence in Networks 16.45 - 17.15 Frank den Hollander Leiden University Mixing times of random walks on dynamic configuration models

## ABSTRACTS

Diego Garlaschelli

Breaking of Ensemble Equivalence in Networks

It is generally believed that, in the thermodynamic limit, the microcanonical description as a function of energy coincides with the canonical description as a function of temperature. However, various examples of systems for which the microcanonical and canonical ensembles are not equivalent have been identified. A complete theory of this intriguing phenomenon is still missing. Here we show that ensemble nonequivalence can manifest itself also in random graphs with topological constraints. We find that, while graphs with a given number of links are ensemble equivalent, graphs with a given degree sequence are not. This result holds irrespective of whether the energy is nonadditive (as in unipartite graphs) or additive (as in bipartite graphs). In contrast with previous expectations, our results show that (1) physically, nonequivalence can be induced by an extensive number of local constraints, and not necessarily by long-range interactions or nonadditivity, (2) mathematically, nonequivalence is determined by a different large-deviation behavior of microcanonical and canonical probabilities for a single microstate, and not necessarily for almost all microstates. The latter criterion, which is entirely local, is not restricted to networks and holds in general.
(joint work with Tiziano Squartini, Joey de Mol and Frank den Hollander)

Frank den Hollander

Mixing times of random walks on dynamic configuration models

The mixing time of a Markov chain is the time it needs to approach its stationary distribution. For random walks on graphs, the characterisation of the mixing time has been the subject of intensive study. One of the motivations is the fact that the mixing time gives information about the geometry of the graph. In the last few years, much attention has been devoted to the analysis of mixing times for random walks on random graphs, which poses interesting challenges.
Many real-world networks are dynamic in nature. It is therefore natural to study random walks on dynamic random graphs. In this talk we investigate what happens for simple random walk on a dynamic version of the configuration model in which, at each unit of time, a fraction $\alpha_n$ of the edges is randomly relocated, where $n$ is the number of nodes. For degree distributions that converge and have a second moment that is bounded in $n$, we show that the mixing time is of order $1/\sqrt{\alpha_n}$, provided $\lim_{n\to\infty} \alpha_n(\log n)^2=\infty$. We identify the sharp asymptotics of the mixing time when we additionally require that $\lim_{n\to\infty} \alpha_n=0$, and relate the relevant proportionality constant to the average probability of escape from the root by a simple random walk on an augmented Galton-Watson tree that is obtained by taking a Galton-Watson tree whose offspring distribution is the size-biased version of the limiting degree distribution and attaching to its root another Galton-Watson tree with the same offspring distribution. Proofs are based on a randomised stopping time argument in combination with coupling estimates.
(joint work with Luca Avena (Leiden), Hakan Guldas (Leiden) and Remco van der Hofstad (Eindhoven))

Dmitri Krioukov

Networks with strong homogeneous clustering are geometric

Two common features of many large real networks are that they are sparse and that they have strong clustering, i.e., large number of triangles homogeneously distributed across all nodes. In many growing networks for which historical data is available, the average degree and clustering are roughly independent of the growing network size. Recently, latent-space random graph models, also known as (soft) random geometric graphs, have been used successfully to model these features of real networks, to predict missing and future links in them, and to study their navigability, with applications ranging from designing optimal routing in the Internet, to identification of the information-transmission skeleton in the human brain. Yet it remains unclear if latent-space models are indeed adequate models of real networks, as these models may have properties that real networks do not have, or vice versa.

We show that maximum-entropy random graphs in which the expected numbers of edges and triangles at every node are fixed to constants, are approximately soft random geometric graphs on the real line. The approximation is exact in the limit of standard random geometric graphs with a sharp connectivity threshold and strongest clustering. This result implies that a large number of triangles homogeneously distributed across all vertices is not only necessary but also a sufficient condition for the presence of a latent/effective metric space in large sparse networks. Strong clustering, ubiquitously observed in real networks, is thus a reflection of their latent geometry.

Michel Mandjes

Scaling Limits for Stochastic Networks

In this talk I will sketch a body of recent results obtained in the context of stochastic networks of dependently operating resources. These could be thought of to represent real-life networks of all sorts, such as traffic or communication networks, but I¹ll point out that this setup is also highly relevant in economic and biological applications. The underlying model can be thought of as a network of interacting resources, which can be modeled in a discrete state-space context through coupled queues, and in a continuous state-space context through specific systems of stochastic differential equations; the individual resources operate dependently as they react to the same environmental process.

For such large networks, one would typically like to describe their dynamic behavior, and to devise procedures that can deal with various undesired events (link failures, sudden overload, etc.). I¹ll show how for systems that do not allow explicit analyses, various parameter scalings help shedding light on their behavior. More specifically, I'll discuss situations in which the time-scale corresponding to the fluctuations of the available resources differs from that of the fluctuations of the customer's demand, leading to various appealing limit results.

Lex Schrijver

The partial disjoint paths problem

The partially disjoint paths problem asks for connections between given pairs of terminals in a network, while certain prescribed pairs of connections are required to be disjoint.
We show that, for any fixed number of terminals, this problem can be solved in polynomially bounded time for planar directed graphs.
It is based on combinatorial group theory.
We also discuss related problems. No specific pre-knowledge is assumed.

#### Last updated 05-09-16, by PK

P.O. Box 513, 5600 MB Eindhoven, The Netherlands
tel. +31 40 2478100
e-mail: info@eurandom.tue.nl