  Recently, graph matching algorithms have been successfully applied to the
problem of network de-anonymization, in which nodes (users) participating to
more than one social network are identified only by means of the structure of
their links to other members. This procedure exploits an initial set of seed
nodes large enough to trigger a percolation process which correctly matches
almost all other nodes across the different social networks. Our main
contribution is to show the crucial role played by clustering, which is a
ubiquitous feature of realistic social network graphs (and many other systems).
Clustering has both the effect of making matching algorithms more vulnerable to
errors, and the potential to dramatically reduce the number of seeds needed to
trigger percolation, thanks to a wave-like propagation effect. We demonstrate
these facts by considering a fairly general class of random geometric graphs
with variable clustering level, and showing how clever algorithms can achieve
surprisingly good performance while containing matching errors.
