Top

Knowledge and Information Systems

Published in:

01-09-2018 | Regular Paper

k-Degree anonymity on directed networks

Authors: Jordi Casas-Roma, Julián Salas, Fragkiskos D. Malliaros, Michalis Vazirgiannis

Published in: Knowledge and Information Systems | Issue 3/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper, we consider the problem of anonymization on directed networks. Although there are several anonymization methods for networks, most of them have explicitly been designed to work with undirected networks and they cannot be straightforwardly applied when they are directed. Moreover, ignoring the direction of the edges causes important information loss on the anonymized networks in the best case. In the worst case, the direction of the edges may be used for reidentification, if it is not considered in the anonymization process. Here, we propose two different models for k-degree anonymity on directed networks, and we also present algorithms to fulfill these k-degree anonymity models. Given a network G, we construct a k-degree anonymous network by the minimum number of edge additions. Our algorithms use multivariate micro-aggregation to anonymize the degree sequence, and then, they modify the graph structure to meet the k-degree anonymous sequence. We apply our algorithms to several real datasets and demonstrate their efficiency and practical utility.

previous article Tag-based information access in image collections: insights from log and eye-gaze analyses

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

The source code for the paper is available at: https://jcasasr.wordpress.com/software/dga/.

DBLP Bibliography Server: http://dblp.uni-trier.de/xml/.

Adamic LA, Glance N (2005) The political blogosphere and the 2004 US election: divided they blog. In: LinkKDD ’05. ACM, Chicago, Illinois, USA, pp 36–43

Backstrom L, Dwork C, Kleinberg J (2007) Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography In: WWW ’07. ACM, New York, NY, USA, pp 181–190

Bhagat S, Cormode G, Krishnamurthy B, Srivastava D (2009) Class-based graph anonymization for social network data In: VLDB ’09, vol 2, no 1, pp 766–777CrossRef

Bredereck R, Froese V, Koseler M, Millani M.G, Nichterlein A, Niedermeier R (2017) A Parameterized algorithmics framework for degree sequence completion problems in directed graphs. In: Proceedings of the 11th international symposium on parameterized and exact computation (IPEC ’16). Schloss Dagstuhl - Leibniz-Zentrum fr Informatik, pp 10:1–10:14

Bredereck R, Froese V, Koseler M, Millani M.G, Nichterlein A, Niedermeier R (2018) A parameterized algorithmics framework for digraph degree sequence completion problems. arXiv:1604.06302v3

Cai BJ, Wang HY, Zheng HR, Wang H (2010) Evaluation repeated random walks in community detection of social networks In: ICMLC’10. IEEE, Qingdao, China, pp 1849–1854

Casas-Roma J, Herrera-Joancomartí J, Torra V (2013) An algorithm for \(k\)-degree anonymity on large networks. In: ASONAM ’13. IEEE, NiagaraFalls, ON, Canada, pp 671–675

Casas-Roma J, Herrera-Joancomartí J, Torra V (2015) Anonymizing graphs: measuring quality for clustering. Knowl Inf Syst 44(3):507–528CrossRef

Casas-Roma J (2015) An evaluation of edge modification techniques for privacy-preserving on graphs. In: MDAI ’15. Springer, Skövde, Sweden, pp 180–191CrossRef

10.

Casas-Roma J, Herrera-Joancomartí J, Torra V (2017) k-Degree anonymity and edge selection: improving data utility in large networks. Knowl Inf Syst 50(2):447–474CrossRef

11.

Chester S, Kapron BM, Ramesh G, Srivastava G, Thomo A, Venkatesh S (2013) Why Waldo befriended the dummy? \(k\)-Anonymization of social networks with pseudo-nodes. Soc Netw Anal Min 3(3):381–399. https://doi.org/10.1007/s13278-012-0084-6 CrossRef

12.

Clarkson KL, Liu K, Terzi E (2010) Towards identity anonymization in social networks. In: Yu P, Han J, Faloutsos C (eds) Link mining: models, algorithms, and applications. Springer, New York, pp 359–385CrossRef

13.

Cormode G, Srivastava D, Yu T, Zhang Q (2010) Anonymizing bipartite graph data using safe groupings. VLDB J 19(1):115–139CrossRef

14.

Das S, Egecioglu Ö, Abbadi A (2010) Anonymizing weighted social network graphs In: ICDE ’10. IEEE, Long Beach, CA, USA, pp 904–907

15.

Domingo-Ferrer J, Torra V (2005) Ordinal, continuous and heterogeneous \(k\)-anonymity through microaggregation. Data Min Knowl Discov 11(2):195–212MathSciNetCrossRef

16.

Domingo-Ferrer J, Mateo-Sanz JM (2002) Practical data-oriented microaggregation for statistical disclosure control. IEEE Trans Knowl Data Eng 14(1):189–201CrossRef

17.

Ferri F, Grifoni P, Guzzo T (2011) New forms of social and professional digital relationships: the case of Facebook. Soc Netw Anal Min 2(2):121–137CrossRef

18.

Hanhijärvi S, Garriga GC, Puolamäki K (2009) Randomization techniques for graphs. In: SDM ’09. SIAM, Sparks, Nevada, USA, pp 780–791

19.

Hansen SL, Mukherjee S (2003) A polynomial algorithm for optimal univariate microaggregation. IEEE Trans Knowl Data Eng 15(4):1043–1044CrossRef

20.

Hartung S, Hoffmann C, Nichterlein A (2014) Improved upper and lower bound heuristics for degree anonymization in social networks. In: SEA’14. Springer, Copenhagen, Denmark, pp 376–387CrossRef

21.

Hartung S, Nichterlein A, Niedermeier R, Suchý O (2015) A refined complexity analysis of degree anonymization in graphs. Inf Comput 243:249–262MathSciNetCrossRef

22.

Hay M, Miklau G, Jensen D, Towsley D, Weis P (2008) Resisting structural re-identification in anonymized social networks In: VLDB ’08, vol 1, no 1, pp 102–114CrossRef

23.

Liu L, Wang J, Liu J, Zhang J (2009) Privacy preservation in social networks with sensitive edge weights. In: SDM ’09. SIAM, Sparks, Nevada, USA, pp 954–965

24.

Liu K, Terzi E (2008) Towards identity anonymization on graphs. In: SIGMOD ’08. ACM, New York, NY, USA, pp 93–106

25.

Ley M (2002) The DBLP computer science bibliography: evolution, research issues, perspectives. In: SPIRE 2002. Springer, London, pp 1–10

26.

Leskovec J, Huttenlocher D, Kleinberg J (2010) Predicting positive and negative links in online social networks. In: WWW ’10. ACM, Raleigh, North Carolina, USA, pp 641–650

27.

Lu X, Song Y, Bressan S (2012) Fast identity anonymization on graphs. In: DEXA ’12. Springer, Vienna, Austria, pp 281–295

28.

Opsahl T, Panzarasa P (2009) Clustering in weighted networks. Soc Netw 31(2):155–163CrossRef

29.

Pons P, Latapy M (2005) Computing communities in large networks using random walks. Lecture notes in computer science (LNCS), vol 3733, pp 284–293CrossRef

30.

Richardson M, Agrawal R, Domingos P (2003) Trust management for the semantic web. In: ISWC, pp 351–368

31.

Rossi L, Musolesi M, Torsello A (2015) On the \(k\)-anonymization of time-varying and multi-layer social graphs. In: ICWSM, pp 377–386

32.

Rosvall M, Bergstrom CT (2008) Maps of random walks on complex networks reveal community structure. Proc Natl Acad Sci USA 105(4):1118–1123CrossRef

33.

Salas J, Torra V (2016) Improving the characterization of P-stability for applications in network privacy. Discrete Appl Math 206:109–114MathSciNetCrossRef

34.

Salas J (2016) Faster univariate microaggregation for power law distributions: \(k\)-degree-anonymity for big graphs In: ICDM workshop on privacy and discrimination in data mining. IEEE, Barcelona, Spain

35.

Samarati P (2001) Protecting respondents identities in microdata release. IEEE Trans Knowl Data Eng 13(6):1010–1027CrossRef

36.

Sweeney L (2002) \(k\)-anonymity: a model for protecting privacy. Int J Uncertain Fuzziness Knowl Based Syst 10(5):557–570MathSciNetCrossRef

37.

Takac L, Zabovsky M (2012) Data analysis in public social networks in international scientific conference and international workshop present day trends of innovations. Lomza, Poland, pp 1–6

38.

Zhou B, Pei J (2008) Preserving privacy in social networks against neighborhood attacks in ICDE ’08. IEEE, Washington, DC, USA, pp 506–515

39.

Zhou B, Pei J (2011) The \(k\)-anonymity and \(\ell \)-diversity approaches for privacy preservation in social networks against neighborhood attacks. Knowl Inf Syst 28(1):47–77CrossRef

40.

Zou L, Chen L, Özsu MT (2009) \(K\)-Automorphism: a general framework for privacy preserving network publication. In: VLDB ’09, vol 2, no 1, pp 946–957

Title: k-Degree anonymity on directed networks
Authors: Jordi Casas-Roma
Julián Salas
Fragkiskos D. Malliaros
Michalis Vazirgiannis
Publication date: 01-09-2018
Publisher: Springer London
Published in: Knowledge and Information Systems / Issue 3/2019
Print ISSN: 0219-1377
Electronic ISSN: 0219-3116
DOI: https://doi.org/10.1007/s10115-018-1251-5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3/2019

Similarity join on time series by utilizing a dynamic segmentation index

A new rule-based knowledge extraction approach for imbalanced datasets

An adjustable fuzzy classification algorithm using an improved multi-objective genetic strategy based on decomposition for imbalance dataset

Mining frequent and top-K High Utility Time Interval-based Events with Duration patterns

Spatio-temporal neural networks for space-time data modeling and relation discovery

An expected win rate-based real-time bidding strategy for branding campaigns on display advertising

Premium Partner