Sublinear multi-type preferential attachment
Abstract
We consider a random growing graph model with two \emph{types}, or \emph{communities}, that belongs to the class of preferential attachment models. Starting from an initial graph G0 in which each node has a type, the graph Gn+1 is generated by addition of a new node, which attaches through an edge to a node v of Gn. The probability of attaching to v depends on the communities of both the new node and v, and is proportional to degn(v)γ, where γ∈[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.
Related
- Spatial preferential attachment models: robustness revisited
- Persistent Hubs and Sharp Asymptotics in Eigenvector Preferential Attachment Trees
- How Robust is Scale-Free Structure? Phase Transitions in Preferential Attachment Model under Attack?
- Asymptotic Normality of the Hill Estimator in Linear Preferential Attachment
- Cutoff for Simple Random Walk on Preferential Attachment Graphs
BibTeX
@misc{benhamou2026sublinear,
title = {{Sublinear multi-type preferential attachment}},
author = {Anna Ben-Hamou and Nicolas Broutin and Camille Cazaux},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06904},
eprint = {2611.06904},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06904},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sublinear multi-type preferential attachment
AU - Anna Ben-Hamou
AU - Nicolas Broutin
AU - Camille Cazaux
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06904
UR - https://arxiv.org/abs/2611.06904
AB - We consider a random growing graph model with two \emph{types}, or \emph{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 γ∈[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.
ER -