Sublinear multi-type preferential attachment
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
- Rank-One HCIZ Integrals and Multiplicative Convolutions
- Repeated averaging on random d-regular graphs
- Precise cover times for branching random walks on Hamming graphs: (iterated) logarithmic corrections
- Markov Chain CLTs: Resolving Open Problems
- Marked stable L'evy processes in Brownian local time
- A Sharp Refinement of Samuels' Inequality via Cap Moves