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.

Impact of Clustering on the Performance of Network De-anonymization / Chiasserini, Carla Fabiana; Garetto, Michele; Leonardi, Emilio. - STAMPA. - (2015), pp. 83-94. (Intervento presentato al convegno ACM CONFERENCE ON ONLINE SOCIAL NETWORKS (COSN'15) tenutosi a Stanford University, California (USA) nel November 2015) [10.1145/2817946.2817953].

Impact of Clustering on the Performance of Network De-anonymization

CHIASSERINI, Carla Fabiana;LEONARDI, Emilio
2015

Abstract

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.
2015
978-1-4503-3951-3
File in questo prodotto:
Non ci sono file associati a questo prodotto.
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: https://hdl.handle.net/11583/2645383
 Attenzione

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