Social Network deanonymization - On the performance of the Percolation Graph Matching algorithm over synthetic graphs with community structure.

Several studies have been carried out on the graph matching problem, which is a generalization of the classic graph isomorphism problem. A graph-matching algorithm finds a map between the vertex sets of two similar graphs with only information about their topological structure. This has applications in many fields, especially in the deanonymization of social and information networks, which can be represented through graphs. It’s rather clear, from the whole body of work, that anonymizing node identities is not sufficient to guarantee privacy protection and can be overcome. In this thesis, the Percolation Graph Matching (PGM) algorithm is considered, a very simple algorithm, based on bootstrap percolation. It starts with a known seed set of matched node pairs and incrementally maps every pair of nodes with at least "r" neighboring already mapped pairs. The algorithm and some variants are tested over stochastic block model random graphs. This model is an important and, at the same time, simple one, useful for modelling networks that are characterized by a community structure, like social ones. The produced graphs contain communities, that are subsets of vertices characterized by being connected with one another with particular edge densities. The obtained simulation results show a phase transition in the size of the seed set, which has already been established and shown when the PGM is applied to Erdӧs-Rényi random graphs. Its good performance over this kind of graphs is also confirmed, despite its simplicity. Lastly, an attempt of modifying the PGM algorithm in order to exploit the degree similarity among nodes belonging to the same community, at least on average, is also proposed and tested. The results show that the traditional versions of PGM perform much better in all the considered cases.