More Web Proxy on the site http://driver.im/

research-article

Link privacy in social networks

Authors:

Aleksandra Korolova,

Rajeev Motwani,

Shubha U. Nabar,

Ying XuAuthors Info & Claims

CIKM '08: Proceedings of the 17th ACM conference on Information and knowledge management

Pages 289 - 298

https://doi.org/10.1145/1458082.1458123

Published: 26 October 2008 Publication History

Abstract

We consider a privacy threat to a social network in which the goal of an attacker is to obtain knowledge of a significant fraction of the links in the network. We formalize the typical social network interface and the information about links that it provides to its users in terms of lookahead. We consider a particular threat where an attacker subverts user accounts to get information about local neighborhoods in the network and pieces them together in order to get a global picture. We analyze, both experimentally and theoretically, the number of user accounts an attacker would need to subvert for a successful attack, as a function of his strategy for choosing users whose accounts to subvert and a function of lookahead provided by the network. We conclude that such an attack is feasible in practice, and thus any social network that wishes to protect the link privacy of its users should take great care in choosing the lookahead of its interface, limiting it to 1 or 2, whenever possible.

References

[1]

Facebook Press Release. http://www.facebook.com/press/info.php?statistics, 2008.

[2]

TechCrunch. http://www.techcrunch.com/2008/05/17/facebooks-glass-jaw/, 2008.

[3]

Technology Review. http://www.technologyreview.com/Wire/20825/, 2008.

[4]

L. Adamic, R. Lukose, A. Puniyani, and B. Huberman. Search in power-law networks. Phys. Rev. E, 2001.

[5]

W. Aiello, F. Chung, and L. Liu. A random graph model for power law graphs. IEEE Symposium on Foundations of Computer Science, 2000.

[6]

L. Backstrom, C. Dwork, and J. Kleinberg. Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography. In WWW '07: Proceedings of the 16th international conference on World Wide Web, pages 181--190, New York, NY, USA, 2007. ACM Press.

Digital Library

[7]

A. Barabasi and R. Albert. Emergence of scaling in random networks. Science, (509), 1999.

[8]

E. A. Bender and E. R. Canfield. The asymptotic number of labeled graphs with given degree sequences. Journal of Combinatorial Theory, Series A 24, pp. 296--307, 1978.

Digital Library

[9]

B. Bollobas, C. Borgs, T. Chayes, and O. Riordan. Directed scale-free graphs. ACM-SIAM Sypmosium on Discrete Algorithms, 2003.

Digital Library

[10]

C. Cooper and A. Frieze. A general model of web graphs. Random Structures and Algorithms, 22(3), pp.311--335, 2003.

Digital Library

[11]

G. Csanyi and B. Szendroi. Structure of a large social network. Physical Review E 69, 2004.

[12]

C. Gkantsidis, M. Mihail, and A. Saberi. Conductance and congestion in power law graphs. Sigmetrics, 2003.

Digital Library

[13]

M. Hay, G. Miklau, D. Jensen, P. Weis, and S. Srivastava. Anonymizing social networks. University of Massachusetts, Amherst Technical Report, 2007.

[14]

M. Kelly. Facebook Security: Fighting the good fight. Facebook blog, http://blog.new.facebook.com/blog.php?post=25844207130, August 7, 2008.

[15]

J. Kleinberg. Navigation in a small world. Nature, (845), 2000.

[16]

B. Krebs. Account Hijackings Force LiveJournal Changes. Washington Post, January 20, 2006.

[17]

R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal. Stochastic models for the web graph. IEEE Symposium on Foundations of Computer Science, 2000.

Digital Library

[18]

J. Leskovec, D. Chakrabarti, J. M. Kleinberg, and C. Faloutsos. Realistic, mathematically tractable graph generation and evolution, using kronecker multiplication. In PKDD, pages 133--145, 2005.

Digital Library

[19]

K. Liu, K. Das, T. Grandison, and H. Kargupta. Privacy-preserving data analysis on graphs and social networks. In H. Kargupta, J. Han, P. Yu, R. Motwani, and V. Kumar, editors, Next Generation Data Mining. CRC Press, 2008.

[20]

M. Mihail, A. Saberi, and P. Tetali. Random walks with lookahead in power law random graphs. Internet Mathematics.

[21]

R. Motwani and P. Raghavan. Cambridge University Press New York, NY, USA, 1995.

[22]

H. von Schelling. Coupon collecting for unequal probabilities. Am. Math. Monthly, 61:306--311, 1954.

[23]

S. Wasserman and K. Faust. Cambridge University Press, Cambridge, USA, 1994.

[24]

D. Watts and S. Strogatz. Collective dynamics of small-world networks. Nature 393 440--442, 1998.

[25]

E. Zheleva and L. Getoor. Preserving the privacy of sensitive relationships in graph data. In Proceedings of the International Workshop on Privacy, Security and Trust in KDD, 2007.

[26]

B. Zhou and J. Pei. Preserving privacy in social networks against neighborhood attacks. In Data Engineering, 2008. ICDE 2008. IEEE 24th International Conference on, pages 506--515, 2008.

Digital Library

Cited By

Alsmadi IAhmad KNazzal MAlam FAl-Fuqaha AKhreishah AAlgosaibi A(2023)Adversarial NLP for Social Network Applications: Attacks, Defenses, and Research DirectionsIEEE Transactions on Computational Social Systems10.1109/TCSS.2022.321874310:6(3089-3108)Online publication date: Dec-2023
https://doi.org/10.1109/TCSS.2022.3218743
Liu YZhao SLiu YZhao DChen HLi C(2022)Collecting Triangle Counts with Edge Relationship Local Differential Privacy*2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00196(2008-2020)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00196
Zhang YWu TXian XXu Y(2022)A Brief Survey on Privacy-Preserving Methods for Graph-Structured DataThe International Conference on Image, Vision and Intelligent Systems (ICIVIS 2021)10.1007/978-981-16-6963-7_52(573-583)Online publication date: 3-Mar-2022
https://doi.org/10.1007/978-981-16-6963-7_52
Show More Cited By

Index Terms

Link privacy in social networks

Recommendations

Preservation of Centrality Measures in Anonymized Social Networks
SOCIALCOM '13: Proceedings of the 2013 International Conference on Social Computing

Social media sites became a pervasive presence in the nowadays society. We can learn a lot of useful information about human behavior and interaction by paying attention to the information and relations of social media users. This information can be ...
Revisiting link privacy in social networks
CODASPY '12: Proceedings of the second ACM conference on Data and Application Security and Privacy

In this paper, we revisit the problem of the link privacy attack in online social networks. In the link privacy attack, it turns out that by bribing or compromising a small number of nodes (users) in the social network graph, it is possible to obtain ...
Privacy preservation for social networks sequential publishing
Abstract
The proliferation of social networks allowed creating a big quantity of data about users and their relationships. Such data contain much private information. Therefore, anonymization is required before publishing the data for data ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '08: Proceedings of the 17th ACM conference on Information and knowledge management

October 2008

1562 pages

ISBN:9781595939913

DOI:10.1145/1458082

General Chair:
James G. Shanahan
Church and Duncan Group Inc, USA
,
Program Chairs:
Sihem Amer-Yahia
Yahoo! Research, USA
,
Ioana Manolescu
INRIA, France
,
Yi Zhang
University of California, Santa Cruz, USA
,
David A. Evans
JustSystems Evans Research, USA
,
Alek Kolcz
Microsoft Live Labs, USA
,
Key-Sun Choi
KAIST, Korea
,
Abdur Chowdury
Twitter, USA

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 October 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CIKM08

Sponsor:

CIKM08: Conference on Information and Knowledge Management

October 26 - 30, 2008

California, Napa Valley, USA

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

76
Total Citations
View Citations
1,577
Total Downloads

Downloads (Last 12 months)22
Downloads (Last 6 weeks)3

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Alsmadi IAhmad KNazzal MAlam FAl-Fuqaha AKhreishah AAlgosaibi A(2023)Adversarial NLP for Social Network Applications: Attacks, Defenses, and Research DirectionsIEEE Transactions on Computational Social Systems10.1109/TCSS.2022.321874310:6(3089-3108)Online publication date: Dec-2023
https://doi.org/10.1109/TCSS.2022.3218743
Liu YZhao SLiu YZhao DChen HLi C(2022)Collecting Triangle Counts with Edge Relationship Local Differential Privacy*2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00196(2008-2020)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00196
Zhang YWu TXian XXu Y(2022)A Brief Survey on Privacy-Preserving Methods for Graph-Structured DataThe International Conference on Image, Vision and Intelligent Systems (ICIVIS 2021)10.1007/978-981-16-6963-7_52(573-583)Online publication date: 3-Mar-2022
https://doi.org/10.1007/978-981-16-6963-7_52
Macwan KPatel S(2021)Privacy Preserving Approaches for Online Social Network Data PublishingDigital Transformation and Challenges to Data Security and Privacy10.4018/978-1-7998-4201-9.ch007(119-132)Online publication date: 2021
https://doi.org/10.4018/978-1-7998-4201-9.ch007
Zuo ZWatson MBudgen DHall RKennelly CAl Moubayed N(2021)Data Anonymization for Pervasive Health Care: Systematic Literature Mapping StudyJMIR Medical Informatics10.2196/298719:10(e29871)Online publication date: 15-Oct-2021
https://doi.org/10.2196/29871
Li WGao MWu FRong WWen JQin L(2021)Manipulating Black-Box Networks for Centrality Promotion2021 IEEE 37th International Conference on Data Engineering (ICDE)10.1109/ICDE51399.2021.00014(73-84)Online publication date: Apr-2021
https://doi.org/10.1109/ICDE51399.2021.00014
Wang JWan ZSong JHuang YLin YLin L(2021)Anonymizing Global Edge Weighted Social Network GraphsSecurity and Privacy in Social Networks and Big Data10.1007/978-981-16-7913-1_9(119-130)Online publication date: 15-Nov-2021
https://doi.org/10.1007/978-981-16-7913-1_9
Macwan KPatel S(2021)Privacy Preservation Approaches for Social Network Data PublishingArtificial Intelligence for Cyber Security: Methods, Issues and Possible Horizons or Opportunities10.1007/978-3-030-72236-4_9(213-233)Online publication date: 1-Jun-2021
https://doi.org/10.1007/978-3-030-72236-4_9
Beigi GLiu H(2020)A Survey on Privacy in Social MediaACM/IMS Transactions on Data Science10.1145/33430381:1(1-38)Online publication date: 12-Mar-2020
https://dl.acm.org/doi/10.1145/3343038
Jia JZhang Y(2020)Implicit Trust Recommendation Algorithm based on Item Meaning2020 IEEE 9th Joint International Information Technology and Artificial Intelligence Conference (ITAIC)10.1109/ITAIC49862.2020.9338889(1782-1791)Online publication date: 11-Dec-2020
https://doi.org/10.1109/ITAIC49862.2020.9338889
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents