polito.it
Politecnico di Torino (logo)

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

Fabio Gennari

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

Rel. Emilio Leonardi. Politecnico di Torino, Corso di laurea magistrale in Communications And Computer Networks Engineering (Ingegneria Telematica E Delle Comunicazioni), 2018

[img]
Preview
PDF (Tesi_di_laurea) - Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives.

Download (26MB) | Preview
Abstract:

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.

Relatori: Emilio Leonardi
Anno accademico: 2018/19
Tipo di pubblicazione: Elettronica
Numero di pagine: 82
Soggetti:
Corso di laurea: Corso di laurea magistrale in Communications And Computer Networks Engineering (Ingegneria Telematica E Delle Comunicazioni)
Classe di laurea: Nuovo ordinamento > Laurea magistrale > LM-27 - INGEGNERIA DELLE TELECOMUNICAZIONI
Aziende collaboratrici: NON SPECIFICATO
URI: http://webthesis.biblio.polito.it/id/eprint/18680
Modifica (riservato agli operatori) Modifica (riservato agli operatori)