YEP 2007(Young European Probabilists)
workshops
Workshop on
"Random Graphs and Complex Networks"
March 19-23, 2007
EURANDOM, Eindhoven, The Netherlands
ABSTRACTS
Birgitte Freiesleben de Blasio, University of Oslo
The Yule process and frailty
Many complex
networks are characterised by an uneven distribution of links, which is
described by a power law 
.
The emergence of the power law is commonly explained by growth through so-called
‘preferential attachment: New links are directed towards nodes with high degree.
The probability for a new node to connect to an existing node is proportional to
its current connectivity. The mechanistic preferential attachment model is
closely related to a stochastic branching process model formulated by Yule in
1925.
However, the preferential attachment scheme is not the only way of obtaining power law graphs. Indeed, in some cases the assumption of proportionate growth may not be appropriate. For instance, information about the connectivity (‘popularity’) of nodes may not be available to nodes when they decide where to direct new links in the system. Instead the power law graph can be generated from frailty considerations. In this case nodes are intrinsically very different in their propensity to form new links, but the average link formation rate is constant in time.
We study the
formation of such frailty power law graphs. The frailty distribution
is
derived from a general Yule process. In the talk I will discuss the difference
between the frailty graph and its Yule-graph counter part with use of various
topological metrics.
Tom Britton, Stockholm University
Random graphs, epidemics and vaccination
Social structures in a community plays an important role for infectious disease spread. Random graphs are suitable objects describing such social structures. An infectious disease in the community, i.e. on the graph, can then be modelled by thinning edges, where removal of an edge means (potential) transmission will not take place. The final outbreak is then all nodes connected to the index cases in the thinned graph. Prior to the arrival of the disease individuals may get vaccinated, which in the graph setting corresponds to thinning nodes in the graph. In the lecture we will describe these type of models and derive results about outbreak sizes, efficient vacination strategies and critical vaccination coverages.
Pierluigi Contucci, Universitŕ Bologna
Phase Transitions in Social Sciences: Two Populations Mean Field Theory
(Joint Work with Gallo, Ghirlanda and Menconi)
A mean field statistical mechanics model of two interacting groups of spins is introduced and the phase transition studied in terms of their relative size. A jump of the average magnetization is found for large values of the mutual interaction when the relative percentage of the two populations crosses a critical threshold. It is shown how the critical percentage depends on internal interactions and on the initial magnetizations. The model is interpreted as a prototype of resident-immigrant cultural interaction and conclusions from the social sciences perspectives are drawn.
Henri van den Esker, Technische Universiteit Delft
Universality for the distance in finite variance random graphs
The asymptotic behavior of the
graph distance between two uniformly chosen nodes in the configuration model
(CM) is extended to the Poissonian random graph. It is shown that the graph
distance for the finite variance case grows like
,
where 
is
some constant and 
is
the number of nodes of the graph. Furthermore, the fluctuations around this
asymptotic mean are given.
We will focus on how to extend these results to other random graph families, e.g. the expected degree random graph, the generalized random graph and the Erdös-Rényi graph. These random graphs have in common that the number of edges between pairs of nodes are mutually independent, which will be the key ingredient of the coupling.
Markus Heydenreich, Technische Universiteit Eindhoven
Critical percolation clusters on high-dimensional boxes.
We consider "critical" bond percolation on a high-dimensional (finite) box, and discuss the size of the largest connected component under bulk and periodic boundary conditions. Interestingly, the periodic case shows the same asymptotic behaviour like the random graph model, that is obtained by percolation on a complete graph. This is in contrast to the case with bulk boundary conditions, where maximal critical clusters are asymptotically much smaller. Hence boundary conditions play an essential role. (Based on joint work with Remco van der Hofstad.)
Petter
Holme, University of New Mexico
Two models of networking social agents
We discuss two models of socially interacting agents. In the first model we
consider a system of networking agents that seek to optimize their centrality in
the network while keeping their cost, the number of connections they are
participating in, low. Possible situations like that occur in diplomacy,
lobbying or other peerwise business relationships. Unlike other game-theory
based models for network evolution, the success of the agents is related only to
their position in the network. The agents use strategies based on local
information to improve their chance of success. In the second case we model
friendship networks by combining opinion spreading on the network with the "homophily
assumption" (that people with the same opinions, interests and other traits are
more likely than expected to become acquainted). We construct a model with a
single parameter controlling the balance of the two processes. We find that the
model undergoes a continuous phase transition as this parameter is varied, from
a regime in which opinions are arbitrarily diverse to one in which most
individuals hold the same opinion.
Gerard Hooghiemstra (Technische Universiteit Delft)
Distances and diameter in the configuration model
This talk(based on
joint work with various authors) is on distances and diameter in a random graph
called the configuration model. We take the degrees of the nodes equal to an
i.i.d. sequence with tail distribution given by a power law with exponent
.
All statements below hold with probability converging to
as
the number 
of
nodes goes to 
.
In the first half of the talk we
describe the typical distance between pairs of nodes that are connected. This
distance depends in an intrinsic way on the value of the exponent
.
For 
,
in which the case the variance of the degrees is finite, the typical path length
between two nodes is of order 
.
For 
,
the average path length, or typical distance is of order
,
and finally for 
,
in which case the expectation and the variance of the degrees are infinite, the
typical path length is either 
or
.
In the second half of the talk we present two results on the diameter. Observe that the above distance results imply lower bounds on the diameter.
For
,
and
we
will show that 
,
for some constant 
,
is a lower bound for the diameter. This result is most interesting for
,
because we see that in this case the diameter and the typical distance are of a
different order of magnitude.
A second result gives an upper
bound on the diameter for .
For 
and
,
a constant times is
an upper bound for the diameter. If time allows I will sketch a proof of the two
results on the diameter.
Mikael Huss, AlbaNova University Centre
Network analysis in biology - current topics and challenges
Since somewhere around the turn of the century, there has been a growing interest in adopting a network-based perspective on biological datasets and applying graph-theoretical methods to analyze them. This field is still very much in its infancy and many basic issues have not yet been fully addressed. Also, experimental biologists are asking how they can get concrete benefits from this type of abstract mathematical analysis. In this review-style talk, I will try to outline current efforts in the field and point out some important challenges as well as concrete applications. Among other topics, I will briefly address network-based identification of essential genes and prediction of protein function as well as decomposition of networks into modules.
Willemien Kets, Tilburg University
Network Games
There has been a recent surge of interest within game theory in the theory of random graphs. Game theory studies strategic interactions: individuals choose their actions so as to maximize their welfare, taking into account that others do the same. In the area of networks, two settings are studied by game theorists. Firstly, one could consider a setting in which individuals interact strategically on a given network. In such a situation, it is natural to assume that individuals cannot oversee the whole network. Random graph models can then be used to represent individuals' information and beliefs. The second setting is one in which individuals try to form connections to other individuals in order to obtain a favorable position in the network. A natural assumption is then that there is some randomness in the formation of links, urging for the use of random graph models. The combination of strategic interactions and random graphs give rise to several questions that are new to both game theory and to the theory of random graphs. In this talk, I will discuss the potential of this approach, and discuss some of the challenges of this new line of research.
Fredrik Liljeros, Stockholm University
Sexually transmitted infections continue to be a severe health problem in contemporary Western societies, despite the considerable funds allocated for control programs. In this seminar I will present and discuss a variety of explanations that have been advanced on why this type of disease is so hard to eradicate, despite the fact that the contact by which it is spread is far less frequent than is the case with most other infectious diseases. We conclude that several processes and mechanisms facilitate the spread of sexually infected diseases, and that both broad and targeted intervention is therefore needed to eradicate such diseases
Recent Progress in the Study of Large Empirical Contact Networks
Highly infectious communicable diseases can, in many contexts, accurately be modelled with simplified assumptions of random interaction and homogenous mixing within and between the individuals and groups forming the population. To model less infectious diseases such as Methicillin Resistant Staphylococcus aureus (MRSA), sexually transmitted infections and Small-pox, a more precise knowledge of the nature of social contact structure is required.In this seminar I will present empirical research concerning different contact networks, such as Internet dating, hospital in-patients and various types of contact between individuals in the society at large that may be of importance for the transmission of less infectious diseases.
Nelli Litvak, Twente University
On the relation between PageRank and in-degree in scale-free networks
PageRank is a popularity measure introduced by Google for Web ranking. It is well-known that PageRank exhibits a heavy-tailed behavior with the same power law exponent as in-degree (the number of incoming links on a page). In this work, we provide a probabilistic analysis for the relation between the distributions of PageRank and in-degree. We interrelate PageRank and in-degree through a stochastic equation inspired by the original definition of PageRank. Further, we use the theory of regular variation to prove that the tail behavior of PageRank and in-degree differ only by a multiplicative constant, which depends mainly on the average in-degree and the fraction of dangling nodes (the pages with out-degree zero). Our theoretical predictions show a good agreement with Web data.
Ronald Meester, Vrije Universiteit Amsterdam
Percolation in the signal to interference ratio graph
Continuum percolation models in which pairs of points of a two-dimensional
Poisson point process are connected if they are within some range to each other
have been extensively studied.
We consider a variation in which a connection between two points depends not
only on their Euclidean distance, but also on the positions of all other points
of the point process. This model has been recently proposed to model
interference in radio communication networks. Our main result shows that,
despite the infinite range dependencies, percolation occurs in the model when
the density of the Poisson point process is greater than the critical density
value of the independent model, provided that interference from other nodes can
be sufficiently reduced (without vanishing)
Peter Mörters, University of Bath
Large deviations for empirical measures of coloured random graphs
We discuss large deviation principles for empirical measures of a natural
class of sparse coloured random graphs. The rate functions in these principles
can be expressed explicitly in terms of relative entropies.
We also derive a large deviation principle for the degree distribution of
Erdoes-Renyi graphs near criticality.
Oliver Riordan, Cambridge University
The mathematics of the Barabási-Albert scale-free network
In the last 7 to 8 years, many new random graph models have been introduced, with the aim of modelling a very wide variety of complex large-scale networks in the real world. In contrast to most classical random graphs, these networks, and the new models, are highly inhomogeneous. This is most easily seen by looking at the degree sequence, which often follows a ‘scale-free’ power law. As is perhaps inevitable in even slightly realistic models, these new random graphs tend to be too complicated for rigorous mathematical analysis (although accurate heuristics can often be obtained). One of the main problems is that the models are almost all dynamic: they describe how the graph evolves in time, for example as vertices are added one by one. Even if ones main interest is the growth process, to understand this one needs to understand properties of the network at each given time. Unfortunately, the description of such a network given by an evolving model is very complicated - it is the result of iterating a certain random procedure many times. In these lectures I will focus on one particular model, the ‘growth with preferential attachment’ model of Barabási and Albert. This is one of the earliest and most studied models, although the usual formulation does not even make sense mathematically! A great advantage of the model is that it has a precise mathematical formulation which leads to a (relatively) simple static description of the graph produced after a certain number of steps, making mathematical analysis feasible. I will start by discussing basic properties, in particular the degree sequence (which changes in a simple way at each step, and can be analyzed without the static description), and then continue to more complicated properties, in particular the ‘robustness’ of the model, i.e., the question of how large a component remains if vertices or edges are deleted randomly. This last question is related to the general study of phase transitions in inhomogeneous random graphs.
Oskar Sandberg, Chalmers University
Double Clustering and Small World Navigation
We all know that it is a small world: starting from any person, one can find a short chain of friendships connecting him to anybody else. But why is this so? In this talk, I will show how small-world graphs arise when each node connects to those nodes that are similar to it in two different ways: a simple and natural rule that leads exactly to the dynamics that reality seems to predict.
Tom Snijders, University of Oxford; University of Groningen
Statistical methods for social network dynamics
Directed graphs (digraphs) are a fundamental data type for representing social networks. Nodes in the graph represent social actors, while arcs (directed lines) represent the ties between them. The dependence structures between arcs, e.g. tendencies to transitivity of ties, lead to complications in modelling such data. A family of probability models will be presented for longitudinal social network data: actor-oriented models, which can be motivated by assumptions about actors trying to optimize their situation with very limited foresight. Such assumptions often make sense as a simple approximation to social science ideas about network dynamics. These models are very flexible which is important for their use in statistical inference. Two methods of estimation will be discussed. The first is a method of moments, the second the maximum likelihood method. Both can be implemented by Markov chain Monte Carlo methods.
Tatyana Turova, Lund University
Random graphs with local and global connections
A typical example of a graph with local and global connections is a graph on a lattice which is a superposition of a bond percolation model and a classical random graph. We describe a phase transition for this type of graphs, and show how they are related to the "rank 1 case" of a general inhomogeneous graph model. Then for a subclass ("rank 1 case") of the inhomogeneous random graphs we derive the asymptotics of the size of the largest connected component in the subcritical phase.
Thomas Vallier, Lunds Universitet
Robustness of Preferential Attachment under Deletion of Edges
Recently, many new random graphs model have been introduced, inspired by certain features observed in many large-scale real-world networks such as "web graph", interaction between proteins, genetic network or social and business networks.
One of these scale-free random graph process is the model of Preferential Attachment introduced by A. Barabási and R. Albert where the new vertices attach with a preference for the vertices with high degree.
In order to test the
vulnerability of this graph and its properties, we propose a model where every
edge is deleted after a time 
which
gives us surprising results on the properties of the degree. In particular, we
show that the attractive vertices are no more the first ones. The expectation of
the degree is uniformly bounded by 
.
Andrew Wade, University of Bristol
Length of the random on-line nearest-neighbour graph
The on-line nearest-neighbour graph on a sequence of points in Euclidean space joins each point after the first by an edge to its nearest predecessor. This graph is one of the simplest models of spatial network evolution to capture some features of real-world spatial networks. We give some large-sample asymptotic results on the total length of the graph on random points. Some of this talk is based on joint work with Mathew Penrose.
This workshop is sponsored by
YEP (Young European Probabilists) workshops
2004 --
2005 --
2006
Last modified:
24-02-09
Maintained by Lucienne Coolen