In Person

Abstract

In the first part of this talk, I will present work on shotgun assembly of random graphs (joint work with Elchanan Mossel). Motivated by DNA shotgun assembly, graph shotgun assembly is the problem of reconstructing a graph from the collection of local neighborhoods. We study this question for Erdos-Renyi random graphs G(n,p). We find conditions for p under which reconstruction is possible, given the collection of distance-1 or distance-2 neighborhoods of the vertices. Conversely, we find conditions under which no algorithm can reconstruct the graph given the collection of distance-1 or distance-2 neighborhoods.

In the second part of the talk, I will discuss community detection in the censored stochastic block model (joint work with Souvik Dhara, Elchanan Mossel, and Colin Sandon). The problem of community detection is an important question in network science since many networks exhibit community structure. That is, there are subsets of vertices that are more strongly connected internally than externally to the rest of the network. The stochastic block model (SBM) is a popular random graph model in the community detection literature. We consider a censored version of the SBM, where many edge observations are missing. We show that a simple spectral algorithm exactly recovers the communities, down to the information-theoretic threshold.

Finally, I will mention some research directions in the areas of community detection and graph alignment, which is the problem of matching the vertices of two related graphs. The graph alignment problem has numerous applications in areas such as computer vision, social networks, and natural language processing.

Biography

Julia Gaudio joined Northwestern University in June 2021, as a Research Assistant Professor (Patrick and Amy McCarter Fellow). Prior to that she completed her PhD at the MIT Operations Research Center in 2020, advised by Patrick Jaillet and David Gamarnik and supported by a Microsoft Research PhD Fellowship. She was then an Applied Mathematics Instructor at the MIT Mathematics Department for one year, working in the group of Elchanan Mossel.