Department of Mathematics and Computer Science, Probability
Eindhoven University of Technology
In the past two decades, it has become clear that many real networks share fascinating features in being small worlds and scale-free. Such networks are typically modeled using random graphs. Random graphs are closely related to percolation, the difference being that random graphs tend to have finite size, while percolation systems tend to be infinite. The empirical findings on real networks have ignited research on various models for complex networks. The focus of the research of the group was the study of distances in models of complex networks where power-law degrees are observed, as well as the behavior of stochastic processes on random graphs.
My research has primarily focussed on studying distances in random graphs and stochastic processes on them. These models include
– the configuration model
– various versions of generalized random graphs
– preferential attachment models.
Small-world nature of complex networks and random graphs
A common feature of many real-world networks is that they are small worlds. This means that, when taking two of the vertices, typically the number of edges needed to go from one to the other is rather small, even for networks having hundreds of thousands or millions of vertices. The small-world phenomenon is closely related to the illusive six-degrees-of-separation paradigm, stating that in social networks, one can go between any pair of individuals along the friendships in the social network using at most 6 intermediaries. In this talk, we examine such empirical data, and explain that small-world behavior is the norm rather than the exception in most complex networks, as well as in random graph models for them.
We further discuss a crucial methodology in random graph theory, namely, branching process approximations. While branching processes were invented to study populations trees, they naturally appear also as the probabilistic description of random graphs when viewed from a typical vertex. These branching processes are imperative to the mathematical study of networks, and understanding their behavior often gives enormous insight into what happens in random graphs. As a result, branching process approximations have grown into the method of choice to understanding random graphs. As an example, we explain how the small-world properties in random graphs can be understood using their branching process approximations.