Abstract
We study the following fundamental graph problem that models the important task of deanonymizing social networks. We are given a graph representing an eponymous social network and another
graph, representing an anonymous social network,
which has been produced by the original one after
removing some of its nodes and adding some noise
on the links. Our objective is to correctly associate
as many nodes of the anonymous network as possible to their corresponding node in the eponymous
network. We present two algorithms that attack
the problem by exploiting only the structure of the
two graphs. The first one exploits bipartite matching computations and is relatively fast. The second one is a local search heuristic which can use
the outcome of our first algorithm as an initial solution and further improve it. We have applied our
algorithms on inputs that have been produced by
well-known random models for the generation of
social networks as well as on inputs that use real
social networks. Our algorithms can tolerate noise
at the level of up to 10%. Interestingly, our results
provide further evidence to which graph generation
models are most suitable for modeling social networks and distinguish them from unrealistic ones