This special mini-symposium at EURANDOM is organized on the occasion of Christian Borgs, Professor of Computer Science at UC Berkeley, receiving an honorary doctorate at TU/e during the celebrations of its 70^th anniversary: TU/e awards an honorary doctorate to Christian Borgs The mini-symposium starts on Monday June 22 around 9:30 and ends on Tuesday June 23 around lunch time, with a dinner being held on Monday night.  Participation is free of charge, but registration via the online form at the bottom of this page is required.  If you wish to attend the dinner on Monday night as a participant, the cost will amount to € 60. The honorary doctorate will be awarded to Prof. Christian Borgs in an official ceremony on Tuesday afternoon, where Remco van der Hofstad, professor of Probability, and Nelly Litvak, professor of Algorithms for Complex Networks, will act as the honorary promotors.  This ceremony is part of a broader event during the TU/e Research Day, for which you can separately register: Registration Research Day 23 June Organizers: Nelly Litvak & Remco van der Hofstad Confirmed speakers:

Bert Zwart	CWI/Eindhoven University of Technology
Clara Stegehuis	Twente University
Florian Henning	Eindhoven University of Technology
Frank den Hollander	Leiden University
Martijn Gösgens	Twente University
Michel Mandjes	Leiden University
Noela Müller	Eindhoven University of Technology
Peter Mörters	University zu Köln
Rajat Hazra	Leiden University
Serte Donderwinkel	University of Groningen

Programme 22-23 June

Registration is closed

Abstracts:

Serte Donderwinkel – Counting connected graphs

How many connected graphs have a prescribed degree sequence?
 This classical combinatorial question turns out to admit a natural probabilistic approach. In joint ongoing work with Sasha Bell and Remco van der Hofstad, we derive asymptotic formulas for the number of connected graphs with a given degree sequence. Our approach is an example of the probabilistic method: rather than counting directly, we introduce a suitable random graph model and study the likelihood that it exhibits a desired structure.

Concretely, we construct a random graph in which (an approximation of) the prescribed degree sequence appears with high probability inside a large connected component. This perspective allows us to translate questions about enumeration into probabilistic statements about random graphs. Along the way, I will discuss several key probabilistic tools, including the configuration model, branching process approximations, and local weak convergence, and explain how they combine to yield asymptotic counting results.

Martijn Gösgens – The Erdős–Rényi Random Graph Conditioned on Every Component Being a Clique

Motivated by an application in community detection, we consider an Erdős–Rényi random graph conditioned on the rare event that all connected components are fully connected. Such graphs can be considered as partitions of vertices into cliques, so that this conditional distribution defines a distribution over partitions. We show that a popular community detection method is equivalent to Bayesian inference with this distribution as prior over the community partitions.

Using tools from analytic combinatorics, we prove limit theorems for several graph observables in this conditional distribution: the number of cliques; the number of edges; and the degree distribution. We consider several regimes of the connection probability p as the number of vertices n diverges. For p=1/2, the conditioning yields the uniform distribution over set partitions, which is well-studied, but has not been studied as a graph distribution before. For p<1/2, we show that the number of cliques is of the order n/log(n)^0.5, while for p>1/2, we prove that the graph consists of a single clique with high probability. This shows that there is a phase transition at p=1/2.

We additionally study the near-critical regime p↓1/2, as well as the sparse regime p↓0. Finally, we discuss the implications of these results for community detection. Joint work with Lukas Lüchtrath, Elena Magnanini, Marc Noy and Élie de Panafieu (preprint available on arxiv).

Rajat Hazra – Generalized Friendship Paradox and Graph Convergence

The friendship paradox states that on an average, your friends have more friends than you do. While striking, this formulation does not fully capture the range of biases that appear in real networks when vertices are sampled through edges, paths, or centrality measures. In this talk, I will discuss several forms of such empirical biases, including higher-order friendship paradoxes, friendship paradoxes on trees, and generalized centrality paradoxes.

I will then explain how graph limits, through local weak convergence and graphon convergence, provide a natural framework to understand these biases explicitly in large networks. This is based on joint works with Frank den Hollander, Nelly Litvak, Azadeh Parvaneh and Evgeny Verbitskiy.

Frank den Hollander – Self-reinforced preferential attachment

Preferential attachment random graphs are dynamic random graphs that grow over time in such a way that vertices with large degrees are favoured over vertices with small degrees to be the anchor for a newly incoming vertex. Such graphs are used to model the power-law degree distributions that are found to be abundantly present in real-world networks. Under standard preferential attachment, each time a new vertex comes in it attaches itself to an old vertex with a probability that is proportional to the degree of that old vertex. The resulting growing graph is a random tree whose vertices have degrees that grow polynomially fast in time, with a growth exponent that is computable.

In the present lecture we consider a version with self-reinforcement, where the attachment probability is proportional to the sum (!) of the degrees over all prior times, which means that the growth mechanism has memory. We compute the growth exponent, show that it is strictly larger than the growth exponent in the absence of self-reinforcement, and develop insight into how the self-reinforcement affects the growth. Joint work with Yogesh Dahiya (Mohali, India).

Florian Henning – Power-law hypothesis and (un)fairness of PageRank on undirected multi-type PAMs

The preferential attachment model (PAM) describes the sequential growth of a network based on the “rich-get-richer” principle. Several versions of it have become established for modeling, e.g., citation networks, capturing a power-law degree distribution.
Directed versions of the preferential attachment model where the edges are directed from the new to the old vertices have been a subject of extensive research and have been shown to exhibit remarkable properties such as heavier tails for the limiting graph-normalized PageRank than for the degrees.
To go beyond this rigid choice of orientation, in this talk we contrast known results on the PageRank asymptotics and fairness of PageRank in directed multitype PAMs, where each vertex has a color or type affecting the attachment mechanism, with their counterparts in the undirected set-up.
The talk is based on joint work with Christian Borgs, Remco van der Hofstad and Nelly Litvak.

Michel Mandjes – Inference problems in stochastic networks

The majority of the random graph literature focuses on inherently static models, in which features of the graph are considered only at a single point in time. Yet there are strong practical motivations to study stochastically evolving graphs, which capture the inherent dynamics of real-world networks. Moreover, one can even consider stochastic processes evolving on these dynamic graphs, further enriching the modeling framework.

The main focus of my talk is on estimating, in the framework discussed above, model parameters from partial information. For example, in a first basic variant, we demonstrate how the underlying parameters of a dynamic random graph can be inferred from snapshots of the subgraph counts. A second model is an age-structured branching process, the most elementary instance being a setting with just juveniles and adults. Remarkably, the model parameters can be estimated just observing the total population.

Next, I consider a static network of nodes represented as infinite-server queues. Our goal is to estimate key parameters — such as arrival rates, service-time distributions, and the routing matrix — using observations of the network’s population vector at Poisson-sampled time points. We propose a method-of-moments estimator and establish its consistency. Numerical experiments show that this approach provides accurate estimates even in high-dimensional settings.

We present two variants: one assuming a known parametric form for the service-time distributions, and a **model-free version** that does not rely on such assumptions. Finally, we study a population process evolving on a dynamic random graph. Using time series data on the number of individuals at each node, we successfully estimate parameters governing the graph dynamics. We prove that the estimator is asymptotically normal. (Joint work with Simone Baldassarri, Peter Braunsteins, Hritika Gupta, Liron Ravner, and Jiesen Wang)

Peter Mörters – The critical window in growing random graphs

We describe the critical window for percolation on sparse growing random graphs. We consider models in which vertices arrive sequentially and connect independently to each earlier vertex with a probability proportional to a power of its arrival time, continuing until the graph has n vertices. This includes the uniformly grown random graph as well as random graphs of preferential attachment type. Whenever the percolation threshold is positive, we show that the critical window has width of order (log n)−2 and a secondary phase transition at its finite upper boundary. Inside this window the largest component has size of order √n/ log n, and the susceptibility remains finite and independent of the position in the window. The proofs couple component explorations to branching random walks killed outside an interval of length log n, allowing sharp control of the barely subcritical and critical regimes.

The talk is based on joint work with Joost Jorritsma (Oxford) and Pascal Maillard (Toulouse). References 1. Jorritsma, J., Maillard, P., Mörters, P.: The critical percolation window in growing random graphs. Arxiv Preprint arXiv:2512.18937.

Noela Müller – Information-theoretic thresholds and algorithms for the threshold group testing problem

The Threshold Group Testing (TGT) problem without a gap is a sparse statistical inference problem that goes back to the work of Damaschke (2006). We study TGT in the noiseless, non-adaptive setting, where the goal is to exactly recover a sparse binary vector from pooled test outcomes using as few tests as possible. In TGT, a test applied to a subset of items returns a positive outcome if the number of defective items in the subset reaches a prescribed threshold, and a negative outcome otherwise.

Under the assumption of an explicit analytic condition, we establish that TGT undergoes a sharp information-theoretic phase transition for exact recovery on the class of constant-column test designs. We further present  an efficient inference algorithm that achieves exact recovery with high probability using the minimum number of non-adaptive tests that are needed for the constant-column design, thereby matching the information-theoretic threshold of a natural benchmark test design. The algorithm is based on a spatially coupled test design and simplifies previous algorithms for other group testing problems that were based on a one step-simulation of the so-called belief propagation algorithm. The talk is based on joint work with Amin Coja-Oghlan, Remco van der Hofstad, Lena Krieg, Connor Riddlesden and Olga Scheftelowitsch.

Clara Stegehuis – Homophily within and across groups

Traditional social network analysis often models homophily, the tendency of similar individuals to form connections. using a single parameter. We will show that in many important applications, such as hypergraphs or temporal contact networks, homophily occurs at several different scales.  We present a model that combines these different homophily values through a random graph model with a maximum entropy approach. We show that the interaction between different levels of homophily has a non-trivial effect on percolation thresholds. Furthermore, we show that our model fits remarkably well on a wide range of data sets, capturing their homophily patterns accurately.

Bert Zwart – Large deviations in inhomogeneous random graphs with heavy tails

We investigate large deviation phenomena in a broad class of inhomogeneous random graphs with heavy-tailed degree distributions, motivated by their relevance as models for real-world networks. In these models, vertex degrees are imposed as soft constraints and typically follow a power-law distribution, leading to substantial analytical challenges due to strong inhomogeneities. Our work develops a unified framework to analyze rare events associated with key graph functionals, including subgraph counts — most notably triangles and cliques — as well as the size of the largest connected component. We show that large deviations in these settings are governed by the emergence of atypically large hubs and can be characterized by suitable optimization problems that identify the most likely configurations that produce such rare events. For triangle counts in scale-free inhomogeneous random graphs with degree exponent \alpha \in (1,2), we establish precise asymptotics for upper tail probabilities and identify a phase transition at $\alpha = 4/3$.

Beyond triangle counts, we extend the analysis to more general subgraph counts and show that when the expected number of subgraphs is sublinear in the graph size, large deviations occur at polynomial scale and admit sharp asymptotic characterizations, including for clique counts. We further establish a large deviation principle for the size of the largest connected component with logarithmic speed. In this case, the rare event that the largest component is linearly larger than typical is driven by the presence of a finite number of vertices with linear degrees. Conditioned on this event, we derive limiting distributions for both vertex weights and component sizes.

Our approach combines probabilistic and variational techniques, including tailored concentration inequalities for empirical processes adapted to heavy-tailed and nonlinear settings. These results provide a comprehensive picture of how extreme structural features in inhomogeneous random graphs emerge from the interplay between heavy-tailed degree distributions and rare-event mechanisms. This talk is based on joint work with Joost Jorritsma, Clara Stegehuis, and Riccardo Machielan, in particular, the preprints preprint1 ,  preprint2 , and preprint3

Florian Henning – Power-law hypothesis and (un)fairness of PageRank on undirected multi-type PAMs

The preferential attachment model (PAM) describes the sequential growth of a network based on the “rich-get-richer” principle. Several versions of it have become established for modeling, e.g., citation networks, capturing a power-law degree distribution.

Directed versions of the preferential attachment model where the edges are directed from the new to the old vertices have been a subject of extensive research and have been shown to exhibit remarkable properties such as heavier tails for the limiting graph-normalized PageRank than for the degrees.

To go beyond this rigid choice of orientation, in this talk we contrast known results on the PageRank asymptotics and fairness of PageRank in directed multitype PAMs, where each vertex has a color or type affecting the attachment mechanism, with their counterparts in the undirected set-up.

The talk is based on joint work with Christian Borgs, Remco van der Hofstad and Nelly Litvak.