Correlated randomly growing graphs

DOI10.1214/21-AAP1703MaRDI QIDQ2135266zbMATH OpenOpenAlexFDO

Authors Miklós Z. Rácz, Anirudh Sridhar

Publication date 6 May 2022

Published in The Annals of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

correlated random graphsinfluence of the seedpreferential attachmentrandom graphsrandomly growing graphsuniform attachment

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Abstract: We introduce a new model of correlated randomly growing graphs and study the fundamental questions of detecting correlation and estimating aspects of the correlated structure. The model is simple and starts with any model of randomly growing graphs, such as uniform attachment (UA) or preferential attachment (PA). Given such a model, a pair of graphs $(G_1,G_2)$ is grown in two stages: until time $t_{star}$ they are grown together (i.e., $G_1=G_2$), after which they grow independently according to the underlying growth model. We show that whenever the seed graph has an influence in the underlying graph growth model---this has been shown for PA and UA trees and is conjectured to hold broadly---then correlation can be detected in this model, even if the graphs are grown together for just a single time step. We also give a general sufficient condition (which holds for PA and UA trees) under which detection is possible with probability going to $1$ as $t_{star}oinfty$. Finally, we show for PA and UA trees that the amount of correlation, measured by $t_{star}$, can be estimated with vanishing relative error as $t_{star}oinfty$.

Recommendations

• scientific article; zbMATH DE number 5763194
• Consistent estimation in general sublinear preferential attachment trees
• Correlations in bipartite collaboration networks
• Continuity of the percolation threshold in randomly grown graphs.
• Growing Protean Graphs

Cites work

• Asymptotic behavior and distributional limits of preferential attachment graphs
• Basic models and questions in statistical network analysis
• Change point detection in network models: preferential attachment and long range dependence
• Discrete minimax estimation with trees
• Distances in random plane-oriented recursive trees
• Efficient random graph matching via degree profiles
• Emergence of Scaling in Random Networks
• Finding Adam in random growing trees
• Finding rumor sources on random trees
• Finding the seed of uniform attachment trees
• From trees to seeds: on the inference of the seed from large trees in the uniform attachment model
• Generalized Sphere-Packing Bounds on the Size of Codes for Combinatorial Channels
• Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs
• Hiding the Rumor Source
• Persistence of centrality in random growing trees
• Random Trees
• Rumors in a Network: Who's the Culprit?
• Scaling limits and influence of the seed graph in preferential attachment trees
• Seeded graph matching for correlated Erdős-Rényi graphs
• The degree sequence of a scale-free random graph process
• The graph matching problem
• The Maximum Degree of the Barabási–Albert Random Tree

Cited in

(9)

• Root finding algorithms and persistence of Jordan centrality in growing random trees
• Correlation of Paths Between Distinct Vertices in a Randomly Oriented Graph
• Testing correlation of unlabeled random graphs
• Matching recovery threshold for correlated random graphs
• Statistical limits of correlation detection in trees
• Inference in balanced community modulated recursive trees
• A polynomial-time approximation scheme for the maximal overlap of two independent Erdős-Rényi graphs
• Efficiently matching random inhomogeneous graphs via degree profiles
• A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation

Describes a project that uses

Uses Software

• IsoRank

This page was built for publication: Correlated randomly growing graphs

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