We show how to modify a small number of edges in a large social network in order to make the modified copy easy to identify, even if an adversary tries to hide the modification by permuting the vertices and flipping a much larger number of edges. The result depends on the random fluctuation of vertex degrees in such networks, and the ability to uniquely identify vertices by their adjacencies to a small number of high-degree landmark vertices. This paper won the best student paper award at ISC for its student co-authors Lam, Mamano, and Torres.
Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.