Consiglio Nazionale delle Ricerche

Tipo di prodottoArticolo in rivista
TitoloSocial Network De-Anonymization under Scale-Free User Relations
Anno di pubblicazione2016
Autore/iChiasserini C.-F.; Garetto M.; Leonardi E.
Affiliazioni autoriPolitecnico di Torino, Turin, 10129, , Italy; Institute of Electronics, Computer and Telecommunication Engineering, National Research Council of Italy, Turin, 10129, , Italy; University of Torino, Turin, 10124, , Italy
Autori CNR e affiliazioni
  • inglese
AbstractWe tackle the problem of user de-anonymization in social networks characterized by scale-free relationships between users. The network is modeled as a graph capturing the impact of power-law node degree distribution, which is a fundamental and quite common feature of social networks. Using this model, we present a de-anonymization algorithm that exploits an initial set of users, called seeds, that are known a priori. By employing the bootstrap percolation theory and a novel graph slicing technique, we develop a rigorous analysis of the proposed algorithm under asymptotic conditions. Our analysis shows that large inhomogeneities in the node degree lead to a dramatic reduction in the size of the seed set that is necessary to successfully identify all the other users. We characterize this set size when seeds are properly selected based on the node degree as well as when seeds are uniformly distributed. We prove that, given n nodes, the number of seeds required for network de-anonymization can be as small as n? , for any small ? >0. In addition, we discuss the complexity of our de-anonymization algorithm and validate our results through numerical experiments on a real social network graph.
Lingua abstractinglese
Altro abstract-
Lingua altro abstract-
Pagine da3756
Pagine a3769
Pagine totali-
RivistaIEEE/ACM transactions on networking (Print)
Attiva dal 1993
Editore: Institute of Electrical and Electronics Engineers, and the Association for Computing Machinery, - New York, NY
Paese di pubblicazione: Stati Uniti d'America
Lingua: inglese
ISSN: 1063-6692
Titolo chiave: IEEE/ACM transactions on networking (Print)
Titolo proprio: IEEE/ACM transactions on networking (Print)
Titolo abbreviato: IEEE/ACM trans. netw. (Print)
Titoli alternativi:
  • TON (Print)
  • Institute of Electrical and Electronics Engineers, Association for Computing Machinery transactions on networking (Print)
  • Transactions on networking (Print)
  • Networking (Print)
Numero volume della rivista24
Fascicolo della rivista-
Verificato da refereeSì: Internazionale
Stato della pubblicazionePublished version
Indicizzazione (in banche dati controllate)
  • Scopus (Codice:2-s2.0-84964597381)
Parole chiavede-anonymization, graphs, bootstrap percolation, Social networks
Link (URL, URI)
Titolo parallelo-
Data di accettazione-
Note/Altre informazioni-
Strutture CNR
  • IEIIT — Istituto di elettronica e di ingegneria dell'informazione e delle telecomunicazioni
Moduli CNR-
Progetti Europei-