Subgraphs in preferential attachment models

DOI10.1017/APR.2019.36MaRDI QIDQ5203960zbMATH OpenOpenAlexWikidataFDO

Authors Alessandro Garavaglia, Clara Stegehuis

Publication date 9 December 2019

Published in Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.10406

zbMATH Keywords

triangleclusteringpreferential attachmentsubgraph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Central limit and other weak theorems (60F05)

Abstract: We consider subgraph counts in general preferential attachment models with power-law degree exponent $au>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'olya urn model.

Recommendations

• Small subgraphs in preferential attachment networks
• On the number of subgraphs of the Barabási-Albert random graph
• Optimal subgraph structures in scale-free configuration models
• Isomorphism and embedding problems for infinite limits of scale-free graphs
• Scale-free property for degrees and weights in a preferential attachment random graph model

Cites work

• scientific article; zbMATH DE number 5070369 (Why is no real title available?)
• A polynomial of graphs on surfaces
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Asymptotic behavior and distributional limits of preferential attachment graphs
• Concentration of vertex degrees in a scale‐free random graph process
• Diameters in preferential attachment models
• Emergence of Scaling in Random Networks
• General results on preferential attachment and clustering coefficient
• Generalized preferential attachment: tunable power-law degree distribution and clustering coefficient
• Generating simple random graphs with prescribed degree distribution
• Local clustering coefficients in preferential attachment models
• Optimal subgraph structures in scale-free configuration models
• Random graphs and complex networks. Volume 1
• Relaxing the uniformity and independence assumptions using the concept of fractal dimension
• Statistical mechanics of complex networks
• Subgraphs in preferential attachment models
• Testing for Equivalence of Network Distribution Using Subgraph Counts
• The average distances in random graphs with given expected degrees
• The clustering coefficient of a scale-free random graph
• The degree sequence of a scale-free random graph process
• The degree sequences and spectra of scale-free random graphs

Cited in

(16)

• The topological behavior of preferential attachment graphs
• Dynamical fitness models: evidence of universality classes for preferential attachment graphs
• Subgraphs in preferential attachment models
• Distinguishing power-law uniform random graphs from inhomogeneous random graphs through small subgraphs
• On the number of subgraphs of the Barabási-Albert random graph
• Optimal subgraph structures in scale-free configuration models
• Investigation of triangle counts in graphs evolving by clustering attachment
• On the chromatic number of the preferential attachment graph
• Random graphs and their subgraphs
• Multivariate regular variation of preferential attachment models
• The asymptotics of the expected Betti numbers of preferential attachment clique complexes
• Degree counts in random simplicial complexes of the preferential attachment type
• Inferences for random graphs evolved by clustering attachment
• Sublinear Random Access Generators for Preferential Attachment Graphs
• Distribution of small subgraphs in Buckley-Osthus random graphs
• Small subgraphs in preferential attachment networks

Describes a project that uses

Uses Software

• FANMOD
• RAGE

This page was built for publication: Subgraphs in preferential attachment models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5203960)