Structural attack to anonymous graph of social networks. (English) Zbl 1296.90132
Summary: With the rapid development of social networks and its applications, the demand of publishing and sharing social network data for the purpose of commercial or research is increasing. However, the disclosure risks of sensitive information of social network users are also arising. The paper proposes an effective structural attack to deanonymize social graph data. The attack uses the cumulative degree of \(n\)-hop neighbors of a node as the regional feature and combines it with the simulated annealing-based graph matching method to explore the nodes reidentification in anonymous social graphs. The simulation results on two social network datasets show that the attack is feasible in the nodes reidentification in anonymous graphs including the simply anonymous graph, randomized graph and \(k\)-isomorphism graph.
MSC:
| 90C35 | Programming involving graphs or networks |
| 05C90 | Applications of graph theory |
| 94A60 | Cryptography |
| 91D30 | Social networks; opinion dynamics |
Software:
PrivateLRReferences:
| [1] | J. L. Moreno, Who Shall Survive?Beacon House, Beacon, NY, USA, 1934. |
| [2] | I. Konstas, V. Stathopoulos, and J. M. Jose, “On social networks and collaborative recommendation,” in Proceedings of the 32nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR ’09), pp. 195-202, July 2009. · doi:10.1145/1571941.1571977 |
| [3] | M. Maia, J. Almeida, and V. Almeida, “Identifying user behavior in online social networks,” in Proceedings of the 1st Workshop on Social Network Systems (SocialNets ’08), pp. 1-6, Glasgow, UK, March 2008. |
| [4] | J. Becker and H. Chen, “Measuring privacy risk in online social networks,” in Proceedings of the Web 2.0 Security & Privacy Workshop (W2SP ’09), pp. 1-8, Oakland, Calif, USA, 2009. |
| [5] | I. A. Tsoukalas and P. D. Siozos, “Privacy and anonymity in the information society: challenges for the European Union,” TheScientificWorldJournal, vol. 11, pp. 458-462, 2011. · doi:10.1100/tsw.2011.46 |
| [6] | J. Adibi and J. Shetty, “Discovering important nodes through graph entropy the case of Enron email database,” in Proceedings of the 3rd International Workshop on Link Discovery, pp. 74-81, Chicago, Ill, USA, 2005. |
| [7] | S. Hansell, “AOL removes search data on vast group of web users,” New York Times, 2006. |
| [8] | A. Narayanan and V. Shmatikov, “Robust de-anonymization of large sparse datasets,” in Proceedings of the IEEE Symposium on Security and Privacy (SP ’08), pp. 111-125, May 2008. · doi:10.1109/SP.2008.33 |
| [9] | X. Wu, X. Ying, K. Liu, and L. Chen, “A survey of algorithms for privacy-preservation of graphs and social networks,” in Managing and Mining Graph Data, pp. 421-453, 2009. |
| [10] | B. Zhou, J. Pei, and W. S. Luk, “A brief survey on anonymization techniques for privacy preserving publishing of social network data,” SIGKDD Explorations, vol. 10, no. 2, pp. 12-22, 2009. |
| [11] | B. C. M. Fung, K. Wang, R. Chen, and P. S. Yu, “Privacy-preserving data publishing: a survey of recent developments,” ACM Computing Surveys, vol. 42, no. 4, article 14, 2010. · doi:10.1145/1749603.1749605 |
| [12] | C. Dwork, “Differential Privacy,” in Proceedings of the of the 33rd International Colloquium on Automata, Languages and Programming (ICALP ’06), pp. 1-12, Venice, Italy, 2006. · Zbl 1133.68330 |
| [13] | C. Task and C. Clifton, “A guide to differential privacy theory in social network analysis,” in Proceedings of the International Conference on Advances in Social Networks Analysis and Mining (ASONAM ’12), pp. 411-417, 2012. |
| [14] | http://www-personal.umich.edu/ mejn/netdata/. |
| [15] | http://deim.urv.cat/ aarenas/data/welcome.htm. |
| [16] | L. Backstrom, C. Dwork, and J. Kleinberg, “Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography,” in Proceedings of the 16th International World Wide Web Conference (WWW ’07), pp. 181-190, Banff, Canada, May 2007. · doi:10.1145/1242572.1242598 |
| [17] | K. Liu and E. Terzi, “Towards identity anonymization on graphs,” in Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD ’08), pp. 93-106, Vancouver, Canada, June 2008. · doi:10.1145/1376616.1376629 |
| [18] | N. Medforth and K. Wang, “Privacy risk in graph stream publishing for social network data,” in Proceedings of the 11th IEEE International Conference on Data Mining (ICDM ’11), pp. 437-446, Vancouver, Canada, December 2011. · doi:10.1109/ICDM.2011.120 |
| [19] | B. Zhou and J. Pei, “Preserving privacy in social networks against neighborhood attacks,” in Proceedings of the IEEE 24th International Conference on Data Engineering (ICDE ’08), pp. 506-515, Cancun, Mexico, April 2008. · doi:10.1109/ICDE.2008.4497459 |
| [20] | L. Zou, L. Chen, and M. T. Ä. Ozsu, “K-automorphism: a general framework for privacy preserving network publication,” in Proceedings of the VLDB Endowment, pp. 946-957, 2009. |
| [21] | J. Cheng, A. W.-C. Fu, and J. Liu, “k-isomorphism: privacy preserving network publication against structural attacks,” in Proceedings of the International Conference on Management of Data (SIGMOD ’10), pp. 459-470, Indianapolis, Ind, USA, June 2010. · doi:10.1145/1807167.1807218 |
| [22] | W. Wu, Y. Xiao, W. Wang, Z. He, and Z. Wang, “K-symmetry model for identity anonymization in social networks,” in Proceedings of the 13th International Conference on Extending Database Technology: Advances in Database Technology (EDBT ’10), pp. 111-122, Lausanne, Switzerland, March 2010. · doi:10.1145/1739041.1739058 |
| [23] | A. Narayanan and V. Shmatikov, “De-anonymizing social networks,” in Proceedings of the 30th IEEE Symposium on Security and Privacy, pp. 173-187, Washington, DC, USA, May 2009. · doi:10.1109/SP.2009.22 |
| [24] | M. Rattigan, “Reidentification of artists and genres in KDD Cup 2011,” Technical Report UM-CS-2011-021, University of Massachusetts Amherst, 2011. |
| [25] | A. Narayanan, E. Shi, and B. I. P. Rubinstein, “Link prediction by de-anonymization: how we won the Kaggle Social Network Challenge,” in Proceedings of the International Joint Conference on Neural Network (IJCNN ’11), pp. 1825-1834, San Jose, Calif, USA, August 2011. · doi:10.1109/IJCNN.2011.6033446 |
| [26] | K. Henderson, B. Gallagher, L. Li et al., “It’s who you know: Graph mining using recursive structural features,” in Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’11), pp. 663-671, San Diego, Calif, USA, August 2011. · doi:10.1145/2020408.2020512 |
| [27] | Z. Junping, H. Ping, Y. Minghao, and Z. Chunguang, “Phase transitions of EXPSPACE-complete problems,” International Journal of Foundations of Computer Science, vol. 21, no. 6, pp. 1073-1088, 2010. · Zbl 1215.68162 · doi:10.1142/S012905411000774X |
| [28] | J. Zhou, M. Yin, X. Li, and J. Wang, “Phase transitions of EXPSPACE-complete problems: a further step,” International Journal of Foundations of Computer Science, vol. 23, no. 1, pp. 173-184, 2012. · Zbl 1246.68206 · doi:10.1142/S0129054112500025 |
| [29] | X. Li and M. Yin, “An opposition-based differential evolution algorithm for permutation flow shop scheduling based on diversity measure,” Advances in Engineering Software, vol. 55, pp. 10-31, 2013. · doi:10.1016/j.advengsoft.2012.09.003 |
| [30] | X. Li and M. Yin, “Multi-operator based biogeography based optimization with mutation for global numerical optimization,” Computers & Mathematics with Applications, vol. 64, no. 9, pp. 2833-2844, 2012. · Zbl 1268.90150 · doi:10.1016/j.camwa.2012.04.015 |
| [31] | X. Li, J. Wang, J. Zhou, and M. Yin, “A perturb biogeography based optimization with mutation for global numerical optimization,” Applied Mathematics and Computation, vol. 218, no. 2, pp. 598-609, 2011. · Zbl 1226.65055 · doi:10.1016/j.amc.2011.05.110 |
| [32] | B. Hajek, “A tutorial survey of theory and applications of simulated annealing,” in Proceedings of the 24th IEEE Conference on Decision and Control, pp. 755-760, 1985. |
| [33] | Y. Xiaowei and W. Xintao, “Randomizing social networks: a spectrum preserving approach,” in Proceedings of the 8th SIAM International Conference on Data Mining, Applied Mathematics 130, pp. 739-750, Atlanta, Ga, USA, April 2008. |
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.
