Sublinear multi-type preferential attachment

arXiv:2611.06904 · math.PR · Submitted 2026-11-04 · Read on arXiv

math.PR

Submitted: 2026-11-04

Updated: 2026-11-04

License: http://creativecommons.org/licenses/by/4.0/

The gist: We consider a random growing graph model with two types, or communities, that belongs to the class of preferential attachment models.

Terminology

Abstract

We consider a random growing graph model with two types, or communities, that belongs to the class of preferential attachment models. Starting from an initial graph G 0 in which each node has a type, the graph G n+1 is generated by addition of a new node, which attaches through an edge to a node v of G n. The probability of attaching to v depends on the communities of both the new node and v, and is proportional to deg n(v) γ, where γ in[0, 1]. We establish a convergence result for the limiting proportion of vertices of each degree and in each community in a certain regime of the parameter γ. To this end, we first use stochastic approximation techniques to reduce the convergence problem to the study of a non-linear evolution equation. We then use a probabilistic coupling approach to investigate the long-time behavior of the unique solution to this evolution equation. We emphasize that the techniques previously used to handle the single-community case cannot be extended directly to our setting. Indeed, the associated continuous-time embedding is not a multitype branching process in the usual sense, since the transition rates at any given time t depend on the entire graph structure at that time.

Sources

Related papers