Competing types in preferential attachment graphs with community structure (2025)

(With John Haslegrave and Mark Yarrow)

Electronic Journal of Probability, vol. 30, paper no. 90, pp.1-34.

Abstract: We extend the two-type preferential attachment model of Antunović, Mossel and Rácz to networks with community structure. We show that different types of limiting behaviour can be found depending on the choice of community structure and type assignment rule.

In particular, we show that, for essentially all type assignment rules where more than one limit has positive probability in the unstructured model, communities may simultaneously converge to different limits if the community connections are sufficiently weak. If only one limit is possible in the unstructured model, this behaviour still occurs for some choices of type assignment rule and community structure. However, we give natural conditions on the assignment rule and, for two communities, on the structure, either of which will imply convergence to this limit, and each of which is essentially best possible.

Although in the unstructured two-type model convergence almost surely occurs, we give an example with community structure which almost surely does not converge.

Link to paper on arXiv