ÍâÍøÌìÌÃ

I will introduce a new model of correlated randomly growing graphs andÌýdiscuss the 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Ìý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} \to \infty$. 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} \to \infty$.

This is based on joint work with Anirudh Sridhar.