Detecting Correlation In Uniform Attachment Trees

Abstract

Networks are a fundamental data structure for modelling association between pairs of agents in a system. There has been significant recent interest in the problem of detecting correlation between different networks, with applications in, for example, de- anonymizing social networks, and inferring function in biological networks.

A first fundamental approach to the problem is to derive sharp information-theoretic thresholds for detection in specific models. Most of the literature thus far has focussed on Erdös- Rényi and stochastic block models, where the random edges between pairs of nodes are independent. While these models form a good theoretical test bad, it is well-known that they are not good fits for empirical network data, and so extending this line of research to other network models is an important research avenue.

In this talk, we introduce and study a new model of correlated uniform attachment (UA) tress, where correlation is sprinkles throughout the time evolution of the process. We discuss the question of how well the correlation can be detected from a single pair of unlabelled correlated UA trees and show that this can be done with probability tending to one as the size of the trees goes to infinity, by constructing a statistic of the unlabelled trees that converges to the correlation parameter.

The construction of our statistic relies on two key ideas. The first is we can use a notion of centrality to identify subsets of vertices of each tree whose intersection has a sufficient number of common early vertices. The second idea is that across different scales, it is possible to approximately determine the labels of vertices that have attached to these early vertices, using the sizes of fringe subtrees. Our analysis includes quantitative bounds on the fraction of early vertices that remain most central, which may be of independent interest.

Short bio

Nathan Ross is an Associate Professor in the School of Mathematics at the University of Melbourne. He received his PhD from the University of Southern California and was a postdoc in the Department of Statistics at UC Berkeley. His research lies at the interface of probability, statistics, and data science, and focuses on the mathematical behaviour of models arising in modern statistical applications, such as random networks. He is the author of a widely used introduction to Stein’s method, which is a powerful tool for studying random systems. He currently serves as an Associate Editor of the Electronic Journal of Probability and the Journal of the Australian Mathematical Society.