×

KDVEM: a \(k\)-degree anonymity with vertex and edge modification algorithm. (English) Zbl 1329.91116

Summary: Privacy is one of the most important issues in social network data sharing. Structure anonymization is a effective method to protect user from being reidentfied through graph modifications. The data utility of the distorted graph structure after the anonymization is a really severe problem. Reducing the utility loss is a new measurement while \(k\)-anonymity as a criterion to guarantee privacy protection. The existing anonymization algorithms that use vertex’s degree modification usually introduce a large amount of distortion to the original social network graph. In this paper, we present a \(k\)-degree anonymity with vertex and edge modification algorithm which includes two phase: first, finding the optimal target degree of each vertex; second, deciding the candidates to increase the vertex degree and adding the edges between vertices to satisfy the requirement. The community structure factors of the social network and the path length between vertices are used to evaluated the anonymization methods. Experimental results on real world datasets show that the average relative performance between anonymized data and original data is the best with our approach.

MSC:

91D30 Social networks; opinion dynamics
68R10 Graph theory (including graph drawing) in computer science

Software:

igraph
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Kisekka V, Bagchi-Sen S, Raghav Rao H (2013) Extent of private information disclosure on online social networks: an exploration of Facebook mobile phone users. Comput Hum Behav 29(6):2722-2729
[2] Shibchurn J, Yan X (2015) Information disclosure on social networking sites: an intrinsic-extrinsic motivation perspective. Comput Hum Behav 44:103-117
[3] Sweeney L (2002) k-Anonymity: a model for protecting privacy. Int J Uncertain Fuzziness Knowl-Based Syst 10(5):557-570 · Zbl 1085.68589 · doi:10.1142/S0218488502001648
[4] Machanavajjhala A et al (2007) L-diversity: privacy beyond k-anonymity. ACM Trans Knowl Discov Data 1(1):3 · doi:10.1145/1217299.1217302
[5] Li N, Li T, Venkatasubramanian S (2007) t-Closeness: privacy beyond k-anonymity and l-diversity. In: IEEE 23rd international conference on data engineering (ICDE’07), pp 106-115
[6] Zhou B, Pei J (2008) Preserving privacy in social networks against neighborhood attacks. In: IEEE 24th international conference on data engineering (ICDE’08), pp 506-515
[7] Narayanan A, Shmatikov V (2009) De-anonymizing social networks. In: Proceedings of the 30th IEEE symposium on security and privacy. IEEE Computer Society. pp 173-187 · Zbl 1205.91144
[8] Borgatti SP, Mehra A, Brass DJ, Labianca G (2009) Network analysis in the social sciences. Science 323(5916):892-895
[9] Backstrom L, Dwork C, Kleinberg J (2007) Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography. In: Proceedings of the 16th international conference on world wide web. ACM, Banff, pp 181-190
[10] Campan A, Truta T (2009) Data and structural k-anonymity in social networks. In: Bonchi F (eds) Privacy, security, and trust in KDD. Springer, Berlin, pp 33-54
[11] Cheng J, Fu AW, Liu J (2010) K-isomorphism: privacy preserving network publication against structural attacks. In: Proceedings of the 2010 ACM SIGMOD international conference on management of data. ACM, Indianapolis, pp 459-470
[12] Chester S et al (2011) k-Anonymization of social networks by vertex addition. In: Proceedings II of the 15th east-european conference on advances in databases and information systems, CEUR-WS, Germany, pp 107-116
[13] Hay M et al (2008) Resisting structural re-identification in anonymized social networks. Proc VLDB Endow 1(1):102-114 · doi:10.14778/1453856.1453873
[14] Liu K, Terzi E (2008) Towards identity anonymization on graphs. In: Proceedings of the 2008 ACM SIGMOD international conference on management of data. ACM, Vancouver, pp 93-106 · Zbl 1085.68589
[15] Wu W et al (2010) k-Symmetry model for identity anonymization in social networks. In: Proceedings of the 13th international conference on extending database technology. ACM, Lausanne, pp 111-122
[16] Zou L et al (2009) k-Automorphism: a general framework for privacy preserving network publication. Proc VLDB Endow 2(1):946-957 · doi:10.14778/1687627.1687734
[17] Hay M et al (2007) Anonymizing social networks. University of Massachusetts Amherst, Amherst · Zbl 1205.91144
[18] Lu X, Song Y, Bressan S (2012) Fast identity anonymization on graphs. In: Liddle S (eds) Database and expert systems applications. Springer, Berlin, pp 281-295
[19] Blondel VD et al (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exp 2008(10):P10008 · Zbl 1459.91130 · doi:10.1088/1742-5468/2008/10/P10008
[20] Newman ME, Girvan M (2004) Finding and evaluate community structure in networks. Phys Rev E 69(2):026113 · doi:10.1103/PhysRevE.69.026113
[21] Csrdi G, Nepusz T (2006) The igraph software package for complex network research. In: Proceeding of international conference on complex systems 2006 (ICCS2006). http://igraph.sf.net. Accessed April 2015
[22] Chester S et al (2013) Why Waldo befriended the dummy? k-Anonymization of social networks with pseudo-nodes. Soc Netw Anal Min 3(3):381-399 · doi:10.1007/s13278-012-0084-6
[23] Leskovec J, Kleinberg J, Faloutsos C (2007) Graph evolution: densification and shrinking diameters. Trans Knowl Discov Data 1(1):2 · doi:10.1145/1217299.1217301
[24] Leskovec J et al (2009) Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math 6(1):29-123 · Zbl 1205.91144 · doi:10.1080/15427951.2009.10129177
[25] Gu B, Sheng VS (2013) Feasibility and finite convergence analysis for accurate on-line-support vector learning. IEEE Trans Neural Netw Learn Syst 24(8):1304-1315
[26] Ma T et al (2015) Detect structural-connected communities based on BSCHEF in C-DBLP. Concurr Comput Pract Exp. doi:10.1002/cpe.343
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.