We address the problem of social network de-anonymization when relationships between people are described by scale-free graphs. In particular, we propose a rigorous, asymptotic mathematical analysis of the network de-anonymization problem while capturing the impact of power-law node degree distribution, which is a fundamental and quite ubiquitous feature of many complex systems such as social networks. By applying bootstrap percolation and a novel graph slicing technique, we prove that large inhomogeneities in the node degree lead to a dramatic reduction of the initial set of nodes that must be known a priori (the seeds) in order to successfully identify all other users. We characterize the size of this set when seeds are selected using different criteria, and we show that their number can be as small as n% for any small ε > 0. Our results are validated through simulation experiments on real social network graphs.

De-anonymizing scale-free social networks by percolation graph matching / Chiasserini, Carla Fabiana; Garetto, M.; Leonardi, Emilio. - STAMPA. - (2015), pp. 1571-1579. ((Intervento presentato al convegno 2015 IEEE Conference on Computer Communications (INFOCOM) tenutosi a Hong Kong nel April-May 2015 [10.1109/INFOCOM.2015.7218536].

De-anonymizing scale-free social networks by percolation graph matching

CHIASSERINI, Carla Fabiana;LEONARDI, Emilio
2015

Abstract

We address the problem of social network de-anonymization when relationships between people are described by scale-free graphs. In particular, we propose a rigorous, asymptotic mathematical analysis of the network de-anonymization problem while capturing the impact of power-law node degree distribution, which is a fundamental and quite ubiquitous feature of many complex systems such as social networks. By applying bootstrap percolation and a novel graph slicing technique, we prove that large inhomogeneities in the node degree lead to a dramatic reduction of the initial set of nodes that must be known a priori (the seeds) in order to successfully identify all other users. We characterize the size of this set when seeds are selected using different criteria, and we show that their number can be as small as n% for any small ε > 0. Our results are validated through simulation experiments on real social network graphs.
File in questo prodotto:
File Dimensione Formato  
Matching_graphs_v16_out.pdf

accesso aperto

Tipologia: 2. Post-print / Author's Accepted Manuscript
Licenza: PUBBLICO - Tutti i diritti riservati
Dimensione 222.1 kB
Formato Adobe PDF
222.1 kB Adobe PDF Visualizza/Apri
INFOCOM_2015_PostPrint.pdf

non disponibili

Descrizione: Articolo principale
Tipologia: 2. Post-print / Author's Accepted Manuscript
Licenza: Non Pubblico - Accesso privato/ristretto
Dimensione 384.36 kB
Formato Adobe PDF
384.36 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11583/2575346
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo