An Enhanced Clustering-Based (<i>k</i>, <i>t</i>)-Anonymity Algorithm for Graphs

WANG Yuanyuan; ZHANG Xing; CHU Zhiguang; SHI Wei; LI Xiang

doi:10.23919/cje.2023.00.276

Article Contents

Article Navigation > Chinese Journal of Electronics > 2025 > Uncorrected proof

Yuanyuan WANG, Xing ZHANG, Zhiguang CHU, et al., “An Enhanced Clustering-Based (k, t)-Anonymity Algorithm for Graphs,” Chinese Journal of Electronics, vol. 34, no. 1, pp. 1–8, 2025 doi: 10.23919/cje.2023.00.276

Citation:

Yuanyuan WANG, Xing ZHANG, Zhiguang CHU, et al., “An Enhanced Clustering-Based (k, t)-Anonymity Algorithm for Graphs,” Chinese Journal of Electronics, vol. 34, no. 1, pp. 1–8, 2025 doi: 10.23919/cje.2023.00.276

Citation:

PDF( 8988 KB)

An Enhanced Clustering-Based (k, t)-Anonymity Algorithm for Graphs

doi: 10.23919/cje.2023.00.276

WANG Yuanyuan^{1, 2
,},
ZHANG Xing^{1, 2
,
,},
CHU Zhiguang^{1, 2, 3
,},
SHI Wei^{1, 2
,},
LI Xiang^{1, 2
,}

1.
School of Electronics and Information Engineering, Liaoning University of Technology, Jinzhou 121000, China
2.
Key Laboratory of Security for Network and Data in Industrial Internet of Liaoning Province, Jinzhou 121000, China
3.
Faculty of Information Technology, Beijing University of Technology, Beijing 100124, China

More Information

Author Bio:
Yuanyuan WANG was born in Zhoukou, Henan, China. She is currently pursuing her M.S. degree in Computer Science with Liaoning University of Technology, Jinzhou, China. Her research interest focuses on privacy protection of graph data. (Email: wyyuand@163.com)

Xing ZHANG received the Ph.D. degree in Computer Science and Technology from Beijing University of Technology, Beijing, China. Currently, he is a Professor with Liaoning University of Technology, Jinzhou, China. He is also a professional member of CCF (China Computer Federation). His research interests include network architecture and protocols, information security, and related areas. (Email: dr.zhangxing@gmail.com)

Zhiguang CHU was born in Yingkou, Liaoning, China. He is currently pursuing his Ph.D. degree with ??. He is also a Senior Engineer with ???. His research interests include data analysis and privacy protection. (Email: chuzg@lnut.edu.cn)

Wei SHI received her M.S. degree from ??. Currently she is a Laboratory Technician with ???. Her research interests include information security and privacy protection. (Email: shiwei@lnut.edu.cn)

Xiang LI received his Ph.D. degree in Computer and Information Science from Temple University, Philadelphia, USA. He is currently employed as a Lecturer with Liaoning University of Technology, Jinzhou, China. His research interests include general artificial intelligence, cognitive science, and artificial intelli-gence emotions. (Email: xiangliagi@lnut.edu.cn)
Corresponding author: Email: dr.zhangxing@gmail.com
Received Date: 2023-09-28
Accepted Date: 2024-01-12

Available Online: 2024-04-01

Abstract

Abstract

As people become increasingly reliant on the Internet, securely storing and publishing private data has become an important issue. In real life, the release of graph data can lead to privacy breaches, which is a highly challenging problem. Although current research has addressed the issue of identity disclosure, there are still two challenges: First, the privacy protection for large-scale datasets is not yet comprehensive; Second, it is difficult to simultaneously protect the privacy of nodes, edges, and attributes in social networks. To address these issues, this paper proposes a ($k$, $t$)-graph anonymity algorithm based on enhanced clustering. The algorithm uses $k$-means++ clustering for $k$-anonymity and $t$-closeness to improve $k$-anonymity. We evaluated the privacy and efficiency of this method on two datasets and achieved good results. This research is of great significance for addressing the problem of privacy breaches that may arise from the publication of graph data.
- Graph data,
- Enhanced clustering,
- k-anonymity,
- Privacy protection,
- k-means++,
- t-closeness

FullText(HTML)

References(23)

References

[1]	L. Sweeney, “k-anonymity: A model for protecting privacy,” International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, vol. 10, no. 5, pp. 557–570, 2002. doi: 10.1142/S0218488502001648
[2]	A. Machanavajjhala, D. Kifer, J. Gehrke, et al., “L-diversity: Privacy beyond k-anonymity,” ACM Transactions on Knowledge Discovery from Data, vol. 1, no. 1, article no. 3, 2007.
[3]	N. H. Li, T. C. Li, and S. Venkatasubramanian, “T-closeness: Privacy beyond k-anonymity and l-diversity,” in Proceedings of the 2007 IEEE 23rd International Conference on Data Engineering, Istanbul, Turkey, pp. 106–115, 2007.
[4]	F. Ahmed, A. X. Liu, and R. Jin, “Social graph publishing with privacy guarantees,” in Proceedings of the 2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS), Nara, Japan, pp. 447–456, 2016.
[5]	C. Borgs, J. Chayes, A. Smith, et al., “Revealing network structure, confidentially: Improved rates for node-private graphon estimation,” in Proceedings of the 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), Paris, France, pp. 533–543, 2018.
[6]	F. Ahmed, A. X. Liu, and R. Jin, “Publishing social network graph eigenspectrum with privacy guarantees,” IEEE Transactions on Network Science and Engineering, vol. 7, no. 2, pp. 892–906, 2020. doi: 10.1109/TNSE.2019.2901716
[7]	C. K. Wei, S. L. Ji, C. C. Liu, et al., “AsgLDP: Collecting and generating decentralized attributed graphs with local differential privacy,” IEEE Transactions on Information Forensics and Security, vol. 15, pp. 3239–3254, 2020. doi: 10.1109/TIFS.2020.2985524
[8]	E. Chicha, B. A. Bouna, M. Nassar, et al., “A user-centric mechanism for sequentially releasing graph datasets under blowfish privacy,” ACM Transactions on Internet Technology, vol. 21, no. 1, article no. 20, 2021. doi: 10.1145/3431501
[9]	Z. J. Zhang, “LDPCD: A novel method for locally differentially private community detection,” Computational Intelligence and Neuroscience, vol. 2022, article no. 4080047, 2022. doi: 10.1155/2022/4080047
[10]	K. Stokes and V. Torra, “Reidentification and k-anonymity: A model for disclosure risk in graphs,” Soft Computing, vol. 16, no. 10, pp. 1657–1670, 2012. doi: 10.1007/s00500-012-0850-4
[11]	R. Assam, M. Hassani, M. Brysch, et al., “(k, d)-core anonymity: Structural anonymization of massive networks,” in Proceedings of the 26th International Conference on Scientific and Statistical Database Management, Aalborg, Denmark, article no. 17, 2014.
[12]	R. Trujillo-Rasua and I. G. Yero, “k-metric antidimension: A privacy measure for social graphs,” Information Sciences, vol. 328, pp. 403–417, 2016. doi: 10.1016/j.ins.2015.08.048
[13]	H. Rong, T. H. Ma, M. L. Tang, et al., “A novel subgraph K⁺- isomorphism method in social network based on graph similarity detection,” Soft Computing, vol. 22, no. 8, pp. 2583–2601, 2018. doi: 10.1007/s00500-017-2513-y
[14]	S. Mauw, Y. Ramírez-Cruz, and R. Trujillo-Rasua, “Conditional adjacency anonymity in social graphs under active attacks,” Knowledge and Information Systems, vol. 61, no. 1, pp. 485–511, 2019. doi: 10.1007/s10115-018-1283-x
[15]	R. Mortazavi and S. H. Erfani, “GRAM: An efficient (k, l) graph anonymization method,” Expert Systems with Applications, vol. 153, article no. 113454, 2020. doi: 10.1016/j.eswa.2020.113454
[16]	W. L. Ren, K. Ghazinour, and X. Lian, “kt-safety: Graph release via k-anonymity and t-closeness,” IEEE Transactions on Knowledge and Data Engineering, vol. 35, no. 9, pp. 9102–9113, 2023. doi: 10.1109/TKDE.2022.3221333
[17]	P. Samarati and L. Sweeney, “Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression,” Available at: https://dataprivacylab.org/dataprivacy/projects/kanonymity/paper3.pdf, 1998.
[18]	M. B. Jamshidi, N. Alibeigi, N. Rabbani, et al., “Artificial neural networks: A powerful tool for cognitive science,” in Proceedings of the 2018 IEEE 9th Annual Information Technology, Electronics and Mobile Communication Conference (IEMCON), Vancouver, Canada, pp. 674–679, 2018.
[19]	“Yelp dataset challenge,” Available at: https://datacollaboratives.org/cases/yelp-dataset-challenge.html.
[20]	“Stanford large network dataset collection,” Available at: http://snap.stanford.edu/data/.
[21]	J. Domingo-Ferrer and J. M. Mateo-Sanz, “Practical data-oriented microaggregation for statistical disclosure control,” IEEE Transactions on Knowledge and data Engineering, vol. 14, no. 1, pp. 189–201, 2002. doi: 10.1109/69.979982
[22]	M. Siddula, Y. S. Li, X. Z. Cheng, et al., “Anonymization in online social networks based on enhanced equi-cardinal clustering,” IEEE Transactions on Computational Social Systems, vol. 6, no. 4, pp. 809–820, 2019. doi: 10.1109/TCSS.2019.2928324
[23]	F. Bonchi, A. Gionis, and T. Tassa, “Identity obfuscation in graphs through the information theoretic lens,” Information Sciences, vol. 275, pp. 232–256, 2014. doi: 10.1016/j.ins.2014.02.035