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

Sexual networks

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 .

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.   