Optimal de-anonymization in random graphs with community structure

Efe Onaran; Siddharth Garg; Elza Erkip

doi:10.1109/SARNOF.2016.7846734

Optimal de-anonymization in random graphs with community structure

Efe Onaran, Siddharth Garg, Elza Erkip

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Social network connectivity data that is anonymized and publicized for academic or commercial purposes are often vulnerable to de-anonymization attacks from attackers utilizing side information in the form of a second, public or crawled social network. Correlation between the two networks is the key factor allowing this attack scheme to work successfully. In this work, the best attack strategy available to de-anonymization attacker, namely the maximum a posteriori (MAP) estimate of the user identities, is identified for networks with community structure and sufficient conditions for perfect de-anonymization are obtained.

Original language	English (US)
Title of host publication	37th IEEE Sarnoff Symposium, Sarnoff 2016
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)	9781509015405
DOIs	https://doi.org/10.1109/SARNOF.2016.7846734
State	Published - Feb 7 2017
Event	37th IEEE Sarnoff Symposium, Sarnoff 2016 - Newark, United States Duration: Sep 19 2016 → Sep 21 2016

Publication series

Name	37th IEEE Sarnoff Symposium, Sarnoff 2016

Other

Other	37th IEEE Sarnoff Symposium, Sarnoff 2016
Country/Territory	United States
City	Newark
Period	9/19/16 → 9/21/16

ASJC Scopus subject areas

Computer Networks and Communications
Hardware and Architecture

Access to Document

10.1109/SARNOF.2016.7846734

Cite this

Onaran, E, Garg, S & Erkip, E 2017, Optimal de-anonymization in random graphs with community structure. in 37th IEEE Sarnoff Symposium, Sarnoff 2016., 7846734, 37th IEEE Sarnoff Symposium, Sarnoff 2016, Institute of Electrical and Electronics Engineers Inc., 37th IEEE Sarnoff Symposium, Sarnoff 2016, Newark, United States, 9/19/16. https://doi.org/10.1109/SARNOF.2016.7846734

@inproceedings{be4437b71ef74d2db04a219ff0f48d2e,

title = "Optimal de-anonymization in random graphs with community structure",

abstract = "Social network connectivity data that is anonymized and publicized for academic or commercial purposes are often vulnerable to de-anonymization attacks from attackers utilizing side information in the form of a second, public or crawled social network. Correlation between the two networks is the key factor allowing this attack scheme to work successfully. In this work, the best attack strategy available to de-anonymization attacker, namely the maximum a posteriori (MAP) estimate of the user identities, is identified for networks with community structure and sufficient conditions for perfect de-anonymization are obtained.",

author = "Efe Onaran and Siddharth Garg and Elza Erkip",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 37th IEEE Sarnoff Symposium, Sarnoff 2016 ; Conference date: 19-09-2016 Through 21-09-2016",

year = "2017",

month = feb,

day = "7",

doi = "10.1109/SARNOF.2016.7846734",

language = "English (US)",

series = "37th IEEE Sarnoff Symposium, Sarnoff 2016",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

booktitle = "37th IEEE Sarnoff Symposium, Sarnoff 2016",

}

TY - GEN

T1 - Optimal de-anonymization in random graphs with community structure

AU - Onaran, Efe

AU - Garg, Siddharth

AU - Erkip, Elza

PY - 2017/2/7

Y1 - 2017/2/7

N2 - Social network connectivity data that is anonymized and publicized for academic or commercial purposes are often vulnerable to de-anonymization attacks from attackers utilizing side information in the form of a second, public or crawled social network. Correlation between the two networks is the key factor allowing this attack scheme to work successfully. In this work, the best attack strategy available to de-anonymization attacker, namely the maximum a posteriori (MAP) estimate of the user identities, is identified for networks with community structure and sufficient conditions for perfect de-anonymization are obtained.

AB - Social network connectivity data that is anonymized and publicized for academic or commercial purposes are often vulnerable to de-anonymization attacks from attackers utilizing side information in the form of a second, public or crawled social network. Correlation between the two networks is the key factor allowing this attack scheme to work successfully. In this work, the best attack strategy available to de-anonymization attacker, namely the maximum a posteriori (MAP) estimate of the user identities, is identified for networks with community structure and sufficient conditions for perfect de-anonymization are obtained.

UR - http://www.scopus.com/inward/record.url?scp=85015245607&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85015245607&partnerID=8YFLogxK

U2 - 10.1109/SARNOF.2016.7846734

DO - 10.1109/SARNOF.2016.7846734

M3 - Conference contribution

AN - SCOPUS:85015245607

T3 - 37th IEEE Sarnoff Symposium, Sarnoff 2016

BT - 37th IEEE Sarnoff Symposium, Sarnoff 2016

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 37th IEEE Sarnoff Symposium, Sarnoff 2016

Y2 - 19 September 2016 through 21 September 2016

ER -

Optimal de-anonymization in random graphs with community structure

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this