CS18: Recent advances in generalised preferential attachment models.

date: 7/17/2025, time: 16:00-17:30, room: ICS 25

Organizer: Tejas Iyer (WIAS Berlin)

Chair: Tejas Iyer (WIAS Berlin)

The number of descendants in a preferential attachment graph

Tiffany Lo (Stockholm University)

In a standard preferential attachment graph, vertices are sequentially added, each born with outdegree \(m \ge 1\); the endpoint of each outgoing edge is chosen among previously added vertices with probability proportional to the current degree of the vertex plus some number \(\rho > −m\). Restricting ourselves to the case where \(m \ge 2\), we study the number \(X(n)\) of vertices that can be reached from the last added vertex \(n\) via a directed path. We show that after suitable rescaling, \(X(n)\) converges in distribution as \(n \to\infty\), and identify the limiting distribution. I will discuss this result and some proof ideas, which are based on joint work with Svante Janson.

Condensation and persistent hubs in generalised preferential attachment trees

Tejas Iyer (WIAS Berlin)

Consider a model of trees evolving in discrete time, where nodes arrive one at a time, and connect to an existing node with probability proportional to a function of its degree. We present natural sufficient conditions for a persistent hub to emerge - that is for a single node to have the maximal degree for all but finitely many time-steps. We also present ongoing work regarding condensation in this model, where a positive proportion of the mass of edges in the tree is lost to nodes of ‘large’ degree.

Persistence of hubs in preferential attachment trees with vertex death.

Bas Lodewijks (University of Augsburg)

We study a random tree model known as the Preferential Attachment tree with Vertex Death. Here, one can both add vertices to the tree as well as kill vertices. This model mimics the non-monotone growth of real-world networks, absent in classical preferential attachment models. One initialises the tree with a single root vertex labelled \(1\). At every step \(n\), either a new vertex labelled \(n+1\) is added to the tree and connected to an already present alive vertex selected preferentially according to a function \(b\), or an already present vertex is selected preferentially according to a function \(d\) and killed. Killed vertices can make no new connections. We are interested in the behaviour of the richest alive vertex \(I_n\) (with the largest degree) and the oldest alive vertex \(O_n\) (with the smallest label). When \(I_n\) converges almost surely, we say that a persistent hub exists. When \(I_n\) does not converge but \(\frac{I_n}{O_n}\) is tight, we say that persistence occurs, and when \(\frac{I_n}{O_n}\) diverges to infinity we say lack of persistence occurs. We uncover three distinct regimes in which behaviour is different: \((1)\) The infinite lifetime regime, where we provide conditions under which a persistent hub exists almost surely. \((2)\) The rich are old regime, in which \(O_n\) does not converge and where we provide conditions under which either persistence or lack of persistence occurs. \((3)\) The rich die young regime, in which \(O_n\) does not converge and where lack of persistence always occurs. We shall discuss how the three regimes can be identified and what drives the behaviour observed in each regime. Partly joint work with Markus Heydenreich.