{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T23:08:41Z","timestamp":1767049721251,"version":"3.48.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T00:00:00Z","timestamp":1763942400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T00:00:00Z","timestamp":1766966400000},"content-version":"vor","delay-in-days":35,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["EURASIP J. on Info. Security"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Anonymization of graph data is fundamental to preserving users\u2019 privacy while publishing social network datasets. The strongest privacy guarantees against any structural attacks provide three well-known methods:\n                    <jats:italic>k<\/jats:italic>\n                    -automorphism,\n                    <jats:italic>k<\/jats:italic>\n                    -isomorphism and\n                    <jats:italic>k<\/jats:italic>\n                    -symmetry. These methods have been proposed independently and are often considered distinct, although certain relationships between them have been noted. This paper presents a comprehensive theoretical analysis of the relationships between these methods. A refined definition of\n                    <jats:italic>k<\/jats:italic>\n                    -automorphism is introduced, formalizing conditions implicitly assumed in practical algorithms. Using this enhanced definition, it is formally proved that\n                    <jats:italic>k<\/jats:italic>\n                    -symmetry and\n                    <jats:italic>k<\/jats:italic>\n                    -automorphism are equivalent. Additionally, the relationship between these two methods and\n                    <jats:italic>k<\/jats:italic>\n                    -isomorphism is analyzed. A novel proof demonstrates that a\n                    <jats:italic>k<\/jats:italic>\n                    -automorphic graph necessarily contains\n                    <jats:italic>k<\/jats:italic>\n                    isomorphic subgraphs. The practical relevance of the provided theoretical results is shown by comparing existing anonymization algorithms. This work contributes to a deeper mathematical understanding of privacy guarantees in graph-structured data, supporting the design of anonymization methods in network security.\n                  <\/jats:p>","DOI":"10.1186\/s13635-025-00220-8","type":"journal-article","created":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T03:15:49Z","timestamp":1763954149000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Bridging privacy-preserving approaches: a formal comparison of k-automorphism, k-isomorphism, and k-symmetry"],"prefix":"10.1186","volume":"2025","author":[{"given":"Jana","family":"Medkov\u00e1","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,11,24]]},"reference":[{"unstructured":"P. Samarati, L. Sweeney, Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression. Technical Report SRI-CSL-98-04 (1998)","key":"220_CR1"},{"doi-asserted-by":"publisher","unstructured":"K. Liu, E. Terzi, in Proceedings of the ACM SIGMOD International Conference on Management of Data. Towards identity anonymization on graphs (ACM Press, Vancouver, 2008), pp. 93\u2013106. https:\/\/doi.org\/10.1145\/1376616.1376629","key":"220_CR2","DOI":"10.1145\/1376616.1376629"},{"doi-asserted-by":"publisher","unstructured":"B. Zhou, J. Pei, in 2008 IEEE 24th International Conference on Data Engineering. Preserving privacy in social networks against neighborhood attacks (IEEE, Cancun, 2008), pp. 506\u2013515. https:\/\/doi.org\/10.1109\/icde.2008.4497459","key":"220_CR3","DOI":"10.1109\/icde.2008.4497459"},{"doi-asserted-by":"publisher","unstructured":"A. Alavi, R. Gupta, Z. Qian, in Information Security. When the attacker knows a lot: The GAGA graph anonymizer (Springer International Publishing, Cham, 2019), pp. 211\u2013230. https:\/\/doi.org\/10.1007\/978-3-030-30215-3_11","key":"220_CR4","DOI":"10.1007\/978-3-030-30215-3_11"},{"issue":"1","key":"220_CR5","doi-asserted-by":"publisher","first-page":"946","DOI":"10.14778\/1687627.1687734","volume":"2","author":"L Zou","year":"2009","unstructured":"L. Zou, L. Chen, M.T. \u00d6zsu, K-automorphism: a general framework for privacy preserving network publication. Proc. VLDB Endow. 2(1), 946\u2013957 (2009). https:\/\/doi.org\/10.14778\/1687627.1687734","journal-title":"Proc. VLDB Endow."},{"doi-asserted-by":"publisher","unstructured":"J. Cheng, A.W.C. Fu, J. Liu, in Proceedings of the ACM SIGMOD International Conference on Management of Data. K-isomorphism: privacy preserving network publication against structural attacks (ACM Press, New York, 2010), pp. 459\u2013470. https:\/\/doi.org\/10.1145\/1807167.1807218","key":"220_CR6","DOI":"10.1145\/1807167.1807218"},{"doi-asserted-by":"publisher","unstructured":"W. Wu, Y. Xiao, W. Wang, Z. He, Z. Wang, in Proceedings of the 13th International Conference on Extending Database Technology. K-symmetry model for identity anonymization in social networks (ACM Press, Lausanne, 2010), pp. 111\u2013122. https:\/\/doi.org\/10.1145\/1739041.1739058","key":"220_CR7","DOI":"10.1145\/1739041.1739058"},{"doi-asserted-by":"publisher","unstructured":"X. Lu, Y. Song, S. Bressan, Fast identity anonymization on graphs. Lect. Notes Comput. Sci. (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7446 LNCS(PART 1), 281\u2013295 (2012). https:\/\/doi.org\/10.1007\/978-3-642-32600-4_21","key":"220_CR8","DOI":"10.1007\/978-3-642-32600-4_21"},{"key":"220_CR9","doi-asserted-by":"publisher","DOI":"10.1145\/2700836","author":"H Fu","year":"2015","unstructured":"H. Fu, A. Zhang, X. Xie, Effective social graph deanonymization based on graph structure and descriptive information. ACM Trans. Intell. Syst. Technol. (2015). https:\/\/doi.org\/10.1145\/2700836","journal-title":"ACM Trans. Intell. Syst. Technol."},{"issue":"2","key":"220_CR10","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1109\/COMST.2016.2633620","volume":"19","author":"S Ji","year":"2017","unstructured":"S. Ji, P. Mittal, R. Beyah, Graph data anonymization, de-anonymization attacks, and de-anonymizability quantification: a survey. IEEE Commun. Surv. Tutor. 19(2), 1305\u20131326 (2017). https:\/\/doi.org\/10.1109\/COMST.2016.2633620","journal-title":"IEEE Commun. Surv. Tutor."},{"doi-asserted-by":"publisher","unstructured":"C. Li, T. Amagasa, H. Kitagawa, G. Srivastava, in ACM International Conference Proceeding Series. Label-bag based graph anonymization via edge addition (Association for Computing Machinery, Montreal, 2014), pp. 1\u20139. https:\/\/doi.org\/10.1145\/2641483.2641516","key":"220_CR11","DOI":"10.1145\/2641483.2641516"},{"doi-asserted-by":"publisher","unstructured":"S. Nobari, P. Karras, H. Pang, S. Bressan, in Advances in Database Technology - EDBT 2014: 17th International Conference on Extending Database Technology, Proceedings. L-opacity: Linkage-aware graph anonymization (OpenProceedings.org, University of Konstanz, University Library, Athens, 2014), pp. 583\u2013594. https:\/\/doi.org\/10.5441\/002\/edbt.2014.52","key":"220_CR12","DOI":"10.5441\/002\/edbt.2014.52"},{"doi-asserted-by":"publisher","unstructured":"K. Sharad, in AISec 2016 - Proceedings of the 2016 ACM Workshop on Artificial Intelligence and Security, co-located with CCS 2016. True friends let you down: Benchmarking social graph anonymization schemes (ACM Press, Vienna, 2016), pp. 93\u2013104. https:\/\/doi.org\/10.1145\/2996758.2996765","key":"220_CR13","DOI":"10.1145\/2996758.2996765"},{"key":"220_CR14","doi-asserted-by":"publisher","first-page":"143950","DOI":"10.1109\/ACCESS.2021.3066176","volume":"9","author":"K Chong","year":"2021","unstructured":"K. Chong, A. Malip, Trace me if you can: an unlinkability approach for privacy-preserving in social networks. IEEE Access 9, 143950\u2013143968 (2021). https:\/\/doi.org\/10.1109\/ACCESS.2021.3066176","journal-title":"IEEE Access"},{"doi-asserted-by":"publisher","unstructured":"A. Zhang, C. Gunter, X. Xie, J. Han, K.C. Chang, X. Wang, in Advances in Database Technology - EDBT 2014: 17th International Conference on Extending Database Technology, Proceedings. Privacy risk in anonymized heterogeneous information networks (OpenProceedings.org, University of Konstanz, University Library, Athens, 2014), pp. 595\u2013606. https:\/\/doi.org\/10.5441\/002\/edbt.2014.53","key":"220_CR15","DOI":"10.5441\/002\/edbt.2014.53"},{"doi-asserted-by":"publisher","unstructured":"M. Rajaei, M. Haghjoo, E. Miyaneh, Ambiguity in social network data for presence, sensitive-attribute, degree and relationship privacy protection. PLoS ONE 10(6) (2015). https:\/\/doi.org\/10.1371\/journal.pone.0130693","key":"220_CR16","DOI":"10.1371\/journal.pone.0130693"},{"key":"220_CR17","doi-asserted-by":"publisher","first-page":"108201","DOI":"10.1109\/ACCESS.2020.3001308","volume":"8","author":"H Parastvand","year":"2020","unstructured":"H. Parastvand, O. Bass, M. Masoum, A. Chapman, S. Lachowicz, Cyber-security constrained placement of FACTS devices in power networks from a novel topological perspective. IEEE Access 8, 108201\u2013108215 (2020). https:\/\/doi.org\/10.1109\/ACCESS.2020.3001308","journal-title":"IEEE Access"},{"doi-asserted-by":"publisher","unstructured":"Z. Lin, M. Tripunitara, in CODASPY 2017 - Proceedings of the 7th ACM Conference on Data and Application Security and Privacy. Graph automorphism-based, semantics-preserving security for the resource description framework (RDF) (2017), pp. 337\u2013348. https:\/\/doi.org\/10.1145\/3029806.3029827","key":"220_CR18","DOI":"10.1145\/3029806.3029827"},{"issue":"4","key":"220_CR19","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1007\/s10115-022-01662-z","volume":"64","author":"S Mauw","year":"2022","unstructured":"S. Mauw, Y. Ram\u00edrez-Cruz, R. Trujillo-Rasua, Preventing active re-identification attacks on social graphs via sybil subgraph obfuscation. Knowl. Inf. Syst. 64(4), 1077\u20131100 (2022). https:\/\/doi.org\/10.1007\/s10115-022-01662-z","journal-title":"Knowl. Inf. Syst."},{"key":"220_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-023-01064-1","author":"J Medkov\u00e1","year":"2023","unstructured":"J. Medkov\u00e1, J. Hynek, Hakau: hybrid algorithm for effective k-automorphism anonymization of social networks. Soc. Netw. Anal. Min. (2023). https:\/\/doi.org\/10.1007\/s13278-023-01064-1","journal-title":"Soc. Netw. Anal. Min."},{"doi-asserted-by":"publisher","unstructured":"J. Gao, J. Xu, G. Liu, W. Chen, H. Yin, L. Zhao, A privacy-preserving framework for subgraph pattern matching in cloud. Lect. Notes Comput. Sci. (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10827 LNCS, 307\u2013322 (2018). https:\/\/doi.org\/10.1007\/978-3-319-91452-7_20","key":"220_CR21","DOI":"10.1007\/978-3-319-91452-7_20"},{"doi-asserted-by":"publisher","unstructured":"Z. Chang, L. Zou, F. Li, in Proceedings of the ACM SIGMOD International Conference on Management of Data. Privacy preserving subgraph matching on large graphs in cloud (ACM Press, San Francisco, 2016), pp. 199\u2013213. https:\/\/doi.org\/10.1145\/2882903.2882956","key":"220_CR22","DOI":"10.1145\/2882903.2882956"},{"issue":"5","key":"220_CR23","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1007\/s11390-014-1466-1","volume":"29","author":"M Yuan","year":"2014","unstructured":"M. Yuan, L. Chen, P. Yu, H. Mei, Protect you more than blank: anti-learning sensitive user information in the social networks. J. Comput. Sci. Technol. 29(5), 762\u2013776 (2014). https:\/\/doi.org\/10.1007\/s11390-014-1466-1","journal-title":"J. Comput. Sci. Technol."},{"doi-asserted-by":"publisher","unstructured":"H. Nguyen, A. Imine, M. Rusinowitch, in ASIACCS 2015 - Proceedings of the 10th ACM Symposium on Information. Computer and Communications Security. Anonymizing social graphs via uncertainty semantics (2015), pp. 495\u2013506. https:\/\/doi.org\/10.1145\/2714576.2714584","key":"220_CR24","DOI":"10.1145\/2714576.2714584"},{"key":"220_CR25","doi-asserted-by":"publisher","DOI":"10.1145\/3604908","volume":"28","author":"R De Jong","year":"2023","unstructured":"R. De Jong, M. Van Der Loo, F. Takes, Algorithms for efficiently computing structural anonymity in complex networks. ACM J. Exp. Algorithmics 28, 5439 (2023). https:\/\/doi.org\/10.1145\/3604908","journal-title":"ACM J. Exp. Algorithmics"},{"key":"220_CR26","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/s10115-015-0855-2","volume":"47","author":"Y Sun","year":"2016","unstructured":"Y. Sun, Y. Yuan, G. Wang, Y. Cheng, Splitting anonymization: a novel privacy-preserving approach of social network. Knowl. Inf. Syst. 47, 595\u2013623 (2016). https:\/\/doi.org\/10.1007\/s10115-015-0855-2","journal-title":"Knowl. Inf. Syst."},{"key":"220_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-970-5","volume-title":"Graph theory","author":"JA Bondy","year":"2008","unstructured":"J.A. Bondy, U.S.R. Murty, Graph theory (Springer-Verlag, London, 2008)"},{"key":"220_CR28","volume-title":"R\u00e9cr\u00e9ations math\u00e9matiques","author":"\u00c9 Lucas","year":"1882","unstructured":"\u00c9. Lucas, R\u00e9cr\u00e9ations math\u00e9matiques, vol. 1 (Gauthier-Villars, Paris, 1882)"},{"key":"220_CR29","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/j.jcta.2014.04.010","volume":"126","author":"D K\u00fchn","year":"2014","unstructured":"D. K\u00fchn, D. Osthus, Decompositions of complete uniform hypergraphs into hamilton berge cycles. J. Comb. Theory Ser. A 126, 128\u2013135 (2014). https:\/\/doi.org\/10.1016\/j.jcta.2014.04.010","journal-title":"J. Comb. Theory Ser. A"},{"issue":"1","key":"220_CR30","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s11856-017-1583-y","volume":"222","author":"R Glebov","year":"2017","unstructured":"R. Glebov, Z. Luria, B. Sudakov, The number of hamiltonian decompositions of regular graphs. Isr. J. Math. 222(1), 91\u2013108 (2017)","journal-title":"Isr. J. Math."},{"doi-asserted-by":"crossref","unstructured":"B. Csaba, Proof of the 1-factorization and Hamilton decomposition conjectures\/ B\u00e9la Csaba [and four others], vol. 244, issue 1154 (American Mathematical Society, Providence, Rhode Island, 2016).\u00a0http:\/\/dx.doi.org\/10.1090\/memo\/1154","key":"220_CR31","DOI":"10.1090\/memo\/1154"},{"key":"220_CR32","volume-title":"Abstract algebra","author":"DS Dummit","year":"2004","unstructured":"D.S. Dummit, R.M. Foote, Abstract algebra, vol. 3 (Wiley, Hoboken, 2004)"}],"container-title":["EURASIP Journal on Information Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13635-025-00220-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13635-025-00220-8","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13635-025-00220-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T23:05:25Z","timestamp":1767049525000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1186\/s13635-025-00220-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,24]]},"references-count":32,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["220"],"URL":"https:\/\/doi.org\/10.1186\/s13635-025-00220-8","relation":{},"ISSN":["2510-523X"],"issn-type":[{"type":"electronic","value":"2510-523X"}],"subject":[],"published":{"date-parts":[[2025,11,24]]},"assertion":[{"value":"5 May 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 October 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 November 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author declares no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"36"}}