Eight friends are enough: Social graph approximation via public listings

Joseph Bonneau; Jonathan Anderson; Ross Anderson; Frank Stajano

doi:10.1145/1578002.1578005

Eight friends are enough: Social graph approximation via public listings

Joseph Bonneau, Jonathan Anderson, Ross Anderson, Frank Stajano

Computer Science

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

Abstract

The popular social networking website Facebook exposes a "public view" of user profiles to search engines which includes eight of the user's friendship links. We examine what interesting properties of the complete social graph can be inferred from this public view. In experiments on real social network data, we were able to accurately approximate the degree and centrality of nodes, compute small dominating sets, find short paths between users, and detect community structure. This work demonstrates that it is difficult to safely reveal limited information about a social network.

Original language	English (US)
Title of host publication	Proceedings of the 2nd ACM EuroSys Workshop on Social Network Systems, SNS '09
Pages	13-18
Number of pages	6
DOIs	https://doi.org/10.1145/1578002.1578005
State	Published - 2009
Event	2nd ACM EuroSys Workshop on Social Network Systems, SNS '09 - Nuremberg, Germany Duration: Mar 31 2009 → Mar 31 2009

Publication series

Name	Proceedings of the 2nd ACM EuroSys Workshop on Social Network Systems, SNS '09

Other

Other	2nd ACM EuroSys Workshop on Social Network Systems, SNS '09
Country/Territory	Germany
City	Nuremberg
Period	3/31/09 → 3/31/09

Keywords

Data breaches
Graph theory
Privacy
Social networks
Web crawling

ASJC Scopus subject areas

Computational Theory and Mathematics
Computer Science Applications
Software

Access to Document

10.1145/1578002.1578005

Cite this

Eight friends are enough: Social graph approximation via public listings. / Bonneau, Joseph; Anderson, Jonathan; Anderson, Ross et al.
Proceedings of the 2nd ACM EuroSys Workshop on Social Network Systems, SNS '09. 2009. p. 13-18 (Proceedings of the 2nd ACM EuroSys Workshop on Social Network Systems, SNS '09).

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

Bonneau, J, Anderson, J, Anderson, R & Stajano, F 2009, Eight friends are enough: Social graph approximation via public listings. in Proceedings of the 2nd ACM EuroSys Workshop on Social Network Systems, SNS '09. Proceedings of the 2nd ACM EuroSys Workshop on Social Network Systems, SNS '09, pp. 13-18, 2nd ACM EuroSys Workshop on Social Network Systems, SNS '09, Nuremberg, Germany, 3/31/09. https://doi.org/10.1145/1578002.1578005

@inproceedings{4b704baa74ad4c92a4c2464f86776c74,

title = "Eight friends are enough: Social graph approximation via public listings",

abstract = "The popular social networking website Facebook exposes a {"}public view{"} of user profiles to search engines which includes eight of the user's friendship links. We examine what interesting properties of the complete social graph can be inferred from this public view. In experiments on real social network data, we were able to accurately approximate the degree and centrality of nodes, compute small dominating sets, find short paths between users, and detect community structure. This work demonstrates that it is difficult to safely reveal limited information about a social network.",

keywords = "Data breaches, Graph theory, Privacy, Social networks, Web crawling",

author = "Joseph Bonneau and Jonathan Anderson and Ross Anderson and Frank Stajano",

year = "2009",

doi = "10.1145/1578002.1578005",

language = "English (US)",

isbn = "9781605584638",

series = "Proceedings of the 2nd ACM EuroSys Workshop on Social Network Systems, SNS '09",

pages = "13--18",

booktitle = "Proceedings of the 2nd ACM EuroSys Workshop on Social Network Systems, SNS '09",

}

TY - GEN

T1 - Eight friends are enough

T2 - 2nd ACM EuroSys Workshop on Social Network Systems, SNS '09

AU - Bonneau, Joseph

AU - Anderson, Jonathan

AU - Anderson, Ross

AU - Stajano, Frank

PY - 2009

Y1 - 2009

N2 - The popular social networking website Facebook exposes a "public view" of user profiles to search engines which includes eight of the user's friendship links. We examine what interesting properties of the complete social graph can be inferred from this public view. In experiments on real social network data, we were able to accurately approximate the degree and centrality of nodes, compute small dominating sets, find short paths between users, and detect community structure. This work demonstrates that it is difficult to safely reveal limited information about a social network.

AB - The popular social networking website Facebook exposes a "public view" of user profiles to search engines which includes eight of the user's friendship links. We examine what interesting properties of the complete social graph can be inferred from this public view. In experiments on real social network data, we were able to accurately approximate the degree and centrality of nodes, compute small dominating sets, find short paths between users, and detect community structure. This work demonstrates that it is difficult to safely reveal limited information about a social network.

KW - Data breaches

KW - Graph theory

KW - Privacy

KW - Social networks

KW - Web crawling

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

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

U2 - 10.1145/1578002.1578005

DO - 10.1145/1578002.1578005

M3 - Conference contribution

AN - SCOPUS:70450193106

SN - 9781605584638

T3 - Proceedings of the 2nd ACM EuroSys Workshop on Social Network Systems, SNS '09

SP - 13

EP - 18

BT - Proceedings of the 2nd ACM EuroSys Workshop on Social Network Systems, SNS '09

Y2 - 31 March 2009 through 31 March 2009

ER -

Eight friends are enough: Social graph approximation via public listings

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this