Program

10:00-10:45 Remco van der Hofstad (TU/e): 'Relating structure and function of complex networks'

11:00-11:45 Julia Komjathy (TU/e): 'Short weighted distances in scale-free spatial random graphs'

11:45-12:30 Luca Avena (Leiden University): 'Network data-sets: randomized decomposition through forests and some related tools'

12:30-13:30 Lunch
13:30-14:30 Ravi Kumar (Google)

 

More information

For questions please contact Nelly Litvak

 

Abstracts

Speaker: Remco van der Hofstad, TU/e

Title: Relating structure and function of complex networks

 

Abstract:

Many phenomena in the real world can be phrased in terms of networks. Examples include the World-Wide Web, social interactions and Internet, but also the interaction patterns between proteins, food webs and citation networks. Many large-scale networks have, despite their diversity in backgrounds, surprisingly much in common. Many of these networks are small worlds, in the sense that one requires few links to hop between pairs of vertices. Also the variability of the number of connections between elements tends to be enormous, which is related to the scale-free phenomenon. 

 

We are interested in the relations between the structure of complex networks and their functionality. Complex networks are generally modeled by random graphs, while their functionality is described in terms of stochastic processes living on them (such as information diffusion), or algorithms acting on them (such as PageRank). There obviously are strong relations between the structure of networks, such as their degree or community structures, and the behavior of stochastic processes and algorithms on them. 

 

In this lecture, we describe a few real-world networks and some of their empirical properties, as well as some of the simple models for them. We then give examples of how the degree distribution determines graph distances in some random graph models, and the behavior of stochastic processes such as percolation and rumor spread. We also discuss the behavior of two algorithms, PageRank and assortativity. We speculate on how models can be improved to better describe real-world networks, and on how this can change their functionality. Time permitting, we discuss the real-world example of citation networks.

 

Speaker: Julia Komjathy (TU/e)

Title: Short weighted distances in scale-free spatial random graphs

 

Abstract:

 

In the talk we describe the connection between two network models, and study distances in both models: hyperbolic random graphs (HRG), and geometric inhomogeneous random graphs (GIRG). In HRGs, n=Θ(eR/2) vertices are sampled independently from the hyperbolic disk with radius R and two vertices are connected either when they are within hyperbolic distance R, or independently with a probability depending on the hyperbolic distance. In GIRGs, each vertex is given an independent weight and location from an underlying measured metric space and Z_d, respectively, and two vertices are connected independently with a probability that is a function of their distance and weights. We describe a transformation that maps HRGs to a specific GIRG.

 

In the second part of the talk, we assign i.i.d. weights to the edges of the random graphs and study the weighted distance between two uniformly chosen vertices.

In particular, we study the case when the parameters are so that the degree distribution in the graph follows a power law with exponent τ∈(2,3) (infinite variance), and the edge-weight distribution is such that it produces an explosive age-dependent branching process with power-law offspring distribution. We show that in both models, typical distances within the giant component converge in distribution as the number of vertices tends to infinity, in particular, they do not tend to infinity with the size of the network.

This simplified model can explain why some videos, memes, etc can spread very quickly on the internet. 

 

Speaker: Luca Avena, Leiden University

Title: Network data-sets: randomized decomposition through forests and some related tools

 

Abstract:

I will discuss some probabilistic tools and related randomized algorithms to explore the architecture of a data set stored in a network structure (an arbitrary weighted finite graph).

The core idea is to decompose the network in a randomized multiscale fashion by using certain spanning rooted forests.

These objects are related to fundamental algebraic and probabilistic structures of a given weighted graph (or of the associated adjacency matrix). 

The applications I will present include:1) a procedure for downsampling sets of well-distributed nodes/vertices 2) coarse-graining or reduction schemes 3) pyramidal wavelets-like algorithms to process signals on graphs.

Joint work with Fabienne Castell, Alexandre Gaudilliere and Clothilde Melot.

 

Speaker: Ravi Kumar (Google)

Title: Random Walks and Network Properties

 

Abstract:

A random walk is a natural way to explore a network.  We will study the use of uniform random walks to estimate various properties such as the size of the network, average degree, number of triangles, etc. Less obvious random walks can also be designed to do other tasks such as uniformly generating a node or counting network motifs.  However, our perspective is that one has to be careful in using random walks for applications.