Abstract
Consider two identical copies of a G(n,p) graph and independently remove edges in each copy with probability s. This creates two correlated G(n, (1-s)p) graphs. Our aim is to match the vertices of these graphs. Such problem arise in particular in the study of social networks when one knows the identities of the people in one of the networks and wants to recover them in another one. We discuss a polynomial-time algorithm which allows to match the vertices of the two graphs with high probability whenever (1+epsilon) log n < np < n^o(1), and the noise level s does not exceed a constant depending on epsilon. Joint work with Cheng Mao and konstantin Tikhomirov.