Optimal de-anonymization in random graphs with community structure

Efe Onaran; Siddharth Garg; Elza Erkip

doi:10.1109/ACSSC.2016.7869137

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

Anonymized social network graphs published for academic or advertisement purposes are subject to de-anonymization attacks by leveraging side information in the form of a second, public social network graph correlated with the anonymized graph. This is because the two are from the same underlying graph of true social relationships. In this paper, the maximum a posteriori (MAP) estimates of user identities for the anonymized graph are characterized and sufficient conditions for successful de-anonymization for underlying graphs with community structure are provided. The results generalize prior work that assumed underlying graphs of Erdíís-Renyi type, and prove the optimality of the attack strategy adopted in the literature.

Original language	English (US)
Title of host publication	Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016
Editors	Michael B. Matthews
Publisher	IEEE Computer Society
Pages	709-713
Number of pages	5
ISBN (Electronic)	9781538639542
DOIs	https://doi.org/10.1109/ACSSC.2016.7869137
State	Published - Mar 1 2017
Event	50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016 - Pacific Grove, United States Duration: Nov 6 2016 → Nov 9 2016

Publication series

Name	Conference Record - Asilomar Conference on Signals, Systems and Computers
ISSN (Print)	1058-6393

Other

Other	50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016
Country/Territory	United States
City	Pacific Grove
Period	11/6/16 → 11/9/16

ASJC Scopus subject areas

Signal Processing
Computer Networks and Communications

Access to Document

10.1109/ACSSC.2016.7869137

Cite this

Onaran, E., Garg, S., & Erkip, E. (2017). Optimal de-anonymization in random graphs with community structure. In M. B. Matthews (Ed.), Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016 (pp. 709-713). Article 7869137 (Conference Record - Asilomar Conference on Signals, Systems and Computers). IEEE Computer Society. https://doi.org/10.1109/ACSSC.2016.7869137

Optimal de-anonymization in random graphs with community structure. / Onaran, Efe; Garg, Siddharth ; Erkip, Elza.
Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016. ed. / Michael B. Matthews. IEEE Computer Society, 2017. p. 709-713 7869137 (Conference Record - Asilomar Conference on Signals, Systems and Computers).

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

Onaran, E, Garg, S & Erkip, E 2017, Optimal de-anonymization in random graphs with community structure. in MB Matthews (ed.), Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016., 7869137, Conference Record - Asilomar Conference on Signals, Systems and Computers, IEEE Computer Society, pp. 709-713, 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016, Pacific Grove, United States, 11/6/16. https://doi.org/10.1109/ACSSC.2016.7869137

Onaran E, Garg S , Erkip E. Optimal de-anonymization in random graphs with community structure. In Matthews MB, editor, Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016. IEEE Computer Society. 2017. p. 709-713. 7869137. (Conference Record - Asilomar Conference on Signals, Systems and Computers). doi: 10.1109/ACSSC.2016.7869137

@inproceedings{b9baa9f80ef94a5699f11314e5d94d19,

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

abstract = "Anonymized social network graphs published for academic or advertisement purposes are subject to de-anonymization attacks by leveraging side information in the form of a second, public social network graph correlated with the anonymized graph. This is because the two are from the same underlying graph of true social relationships. In this paper, the maximum a posteriori (MAP) estimates of user identities for the anonymized graph are characterized and sufficient conditions for successful de-anonymization for underlying graphs with community structure are provided. The results generalize prior work that assumed underlying graphs of Erd{\'i}{\'i}s-Renyi type, and prove the optimality of the attack strategy adopted in the literature.",

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

note = "Funding Information: This research was funded in part by NSF Grant 1527072.; 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016 ; Conference date: 06-11-2016 Through 09-11-2016",

year = "2017",

month = mar,

day = "1",

doi = "10.1109/ACSSC.2016.7869137",

language = "English (US)",

series = "Conference Record - Asilomar Conference on Signals, Systems and Computers",

publisher = "IEEE Computer Society",

pages = "709--713",

editor = "Matthews, {Michael B.}",

booktitle = "Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016",

}

TY - GEN

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

AU - Onaran, Efe

AU - Garg, Siddharth

AU - Erkip, Elza

N1 - Funding Information: This research was funded in part by NSF Grant 1527072.

PY - 2017/3/1

Y1 - 2017/3/1

N2 - Anonymized social network graphs published for academic or advertisement purposes are subject to de-anonymization attacks by leveraging side information in the form of a second, public social network graph correlated with the anonymized graph. This is because the two are from the same underlying graph of true social relationships. In this paper, the maximum a posteriori (MAP) estimates of user identities for the anonymized graph are characterized and sufficient conditions for successful de-anonymization for underlying graphs with community structure are provided. The results generalize prior work that assumed underlying graphs of Erdíís-Renyi type, and prove the optimality of the attack strategy adopted in the literature.

AB - Anonymized social network graphs published for academic or advertisement purposes are subject to de-anonymization attacks by leveraging side information in the form of a second, public social network graph correlated with the anonymized graph. This is because the two are from the same underlying graph of true social relationships. In this paper, the maximum a posteriori (MAP) estimates of user identities for the anonymized graph are characterized and sufficient conditions for successful de-anonymization for underlying graphs with community structure are provided. The results generalize prior work that assumed underlying graphs of Erdíís-Renyi type, and prove the optimality of the attack strategy adopted in the literature.

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

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

U2 - 10.1109/ACSSC.2016.7869137

DO - 10.1109/ACSSC.2016.7869137

M3 - Conference contribution

AN - SCOPUS:85016303470

T3 - Conference Record - Asilomar Conference on Signals, Systems and Computers

SP - 709

EP - 713

BT - Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016

A2 - Matthews, Michael B.

PB - IEEE Computer Society

T2 - 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016

Y2 - 6 November 2016 through 9 November 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