Subgraphs in preferential attachment models. (September 2019)

• Record Type: Journal Article
• Authors: Garavaglia, Alessandro; Stegehuis, Clara
• Is Part Of: Advances in applied probability. Volume 51:Number 3(2019)
• Page Start: 898
• Page End: 926
• Publication Date: 2019-09
• Subjects: Preferential attachment, -- subgraph, -- triangle, -- clustering; Primary 05C80, -- Secondary 60F05; Probabilities -- Periodicals; Stochastic models -- Periodicals; Electronic journals; Periodicals; 519.2
• DOI: 10.1017/apr.2019.36
• Languages: English
• ISSNs: 0001-8678

Abstract

Abstract: We consider subgraph counts in general preferential attachment models with power-law degree exponent $\tau > 2$ . For all subgraphs H, we find the scaling of the expected number of subgraphs as a power of the number of vertices. We prove our results on the expected number of subgraphs by defining an optimization problem that finds the optimal subgraph structure in terms of the indices of the vertices that together span it and by using the representation of the preferential attachment model as a Pólya urn model.