NETWORKS

Day 2 (Wednesday 12 April) @ 11:15–12:45

Wioletta Ruszel (Utrecht University)

Sandpile models on graphs with conductances

The sandpile model (aka chip-firing game) is a toy model for studying self-organized criticality. There has been a lot of activity and progress in understanding connections to spanning trees, Abelian groups, studying existence of infinite volume measures or avalanche size distributions of the model on different lattices.

In this talk we will discuss ongoing progress in studying the sandpile model on general graphs with conductances. We will introduce the notion of two-phase burning algorithm, minimal configurations and the transfer current matrix.

This is joint work with Cedric Boutillier (University Paris Sorbonne).

Tom van der Zanden (Maastricht University)

Efficiently Computing the Shapley Value of Connectivity Games in Low-Treewidth Graphs

Game-theoretic centrality measures are a powerful tool to identify key players in covert networks (that model, e.g., the interactions between suspected terrorists or criminals). Unfortunately, such measures are often NP-hard to compute and thus intractable, even for small graphs. We show that, for three connectivity games, their Shapely value can be efficiently computed if the underlying graph has low treewidth. Using this method, we are able to compute the Shapley Value for several graphs for which this was previously infeasible (including, notably, the 69-vertex graph of the terrorists involved in the 9-11 attacks studied in previous work on Shapley value-based centrality).​

Wojciech Samotij (Tel Aviv University)

Large deviations in random graphs

Suppose that Y1,…,YN are i.i.d. (independent, identically distributed) random variables and let X =Y1++YN. The classical theory of large deviations allows one to accurately estimate the probability of the tail events X<(1-c)E[X] and X>(1+c)E[X] for any positive c. However, the methods involved strongly rely on the fact that X is a linear function of the independent variables Y1,…,YN. There has been considerable interest − both theoretical and practical − in developing tools for estimating such tail probabilities also when X is a nonlinear function of the Yi. One archetypal example studied by both the combinatorics and the probability communities is when X is the number of triangles in the binomial random graph G(n,p). I will discuss recent developments in the study of the tail probabilities of this random variable. The talk is based on joint works with Matan Harel and Frank Mousset and with Gady Kozma.