{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T16:12:41Z","timestamp":1780416761060,"version":"3.54.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T00:00:00Z","timestamp":1691712000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>\n            This article proposes methods for efficiently computing the anonymity of entities in networks. We do so by partitioning nodes into equivalence classes where a node is\n            <jats:italic>k<\/jats:italic>\n            -anonymous if it is equivalent to\n            <jats:italic>k<\/jats:italic>\n            -1 other nodes. This assessment of anonymity is crucial when one wants to share data and must ensure the anonymity of entities represented is compliant with privacy laws. Additionally, in such an assessment, it is necessary to account for a realistic amount of information in the hands of a possible attacker that attempts to de-anonymize entities in the network. However, measures introduced in earlier work often assume a fixed amount of attacker knowledge. Therefore, in this work, we use a new parameterized measure for anonymity called\n            <jats:italic>d<\/jats:italic>\n            -\n            <jats:italic>k<\/jats:italic>\n            -anonymity. This measure can be used to model the scenario where an attacker has perfect knowledge of a node\u2019s surroundings up to a given distance\n            <jats:italic>d<\/jats:italic>\n            . This poses nontrivial computational challenges, as naive approaches would employ large numbers of possibly computationally expensive graph isomorphism checks. This article proposes novel algorithms that severely reduce this computational burden. In particular, we present an iterative approach, assisted by techniques for preprocessing nodes that are trivially automorphic and heuristics that exploit graph invariants. We evaluate our algorithms on three well-known graph models and a wide range of empirical network datasets. Results show that our approaches significantly speed up the computation by multiple orders of magnitude, which allows one to compute\n            <jats:italic>d<\/jats:italic>\n            -\n            <jats:italic>k<\/jats:italic>\n            -anonymity for a range of meaningful values of\n            <jats:italic>d<\/jats:italic>\n            on large empirical networks with tens of thousands of nodes and over a million edges.\n          <\/jats:p>","DOI":"10.1145\/3604908","type":"journal-article","created":{"date-parts":[[2023,6,17]],"date-time":"2023-06-17T09:13:50Z","timestamp":1686993230000},"page":"1-22","source":"Crossref","is-referenced-by-count":3,"title":["Algorithms for Efficiently Computing Structural Anonymity in Complex Networks"],"prefix":"10.1145","volume":"28","author":[{"given":"Rachel G.","family":"de Jong","sequence":"first","affiliation":[{"name":"Leiden University, Statistics Netherlands, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark P. J.","family":"van der Loo","sequence":"additional","affiliation":[{"name":"Leiden University, Statistics Netherlands, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Frank W.","family":"Takes","sequence":"additional","affiliation":[{"name":"Leiden University, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,8,11]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.idm.2019.11.002"},{"key":"e_1_3_3_3_2","volume-title":"Network Science","author":"Barab\u00e1si Albert L\u00e1szl\u00f3","year":"2016","unstructured":"Albert L\u00e1szl\u00f3 Barab\u00e1si. 2016. Network Science. Cambridge University Press."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2014.04.001"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807218"},{"issue":"1","key":"e_1_3_3_7_2","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u0151s Paul","year":"1960","unstructured":"Paul Erd\u0151s and Alfr\u00e9d R\u00e9nyi. 1960. On the evolution of random graphs. Publication of the Mathematical Institute of the Hungarian Academy of Sciences 5, 1 (1960), 17\u201360.","journal-title":"Publication of the Mathematical Institute of the Hungarian Academy of Sciences"},{"key":"e_1_3_3_8_2","unstructured":"Michael Fire. 2020. Data 4 Good Lab. Retrieved May 2022 from https:\/\/data4goodlab.github.io\/MichaelFire\/#section3."},{"key":"e_1_3_3_9_2","volume-title":"Exploring Network Structure, Dynamics, and Function using NetworkX","author":"Hagberg Aric","year":"2008","unstructured":"Aric Hagberg, Pieter Swart, and Daniel Schult. 2008. Exploring Network Structure, Dynamics, and Function using NetworkX. Technical Report. Los Alamos National Lab (LANL), Los Alamos, NM (United States)."},{"key":"e_1_3_3_10_2","first-page":"180","article-title":"Anonymizing social networks","author":"Hay Michael","year":"2007","unstructured":"Michael Hay, Gerome Miklau, David Jensen, Philipp Weis, and Siddharth Srivastava. 2007. Anonymizing social networks. Computer Science Department Faculty Publication Series (2007), 180. https:\/\/scholarworks.umass.edu\/cs_faculty_pubs\/180\/.","journal-title":"Computer Science Department Faculty Publication Series"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1002\/9781118348239"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2016.2633620"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_3_3_14_2","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved May 2022 from http:\/\/snap.stanford.edu\/data."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376629"},{"key":"e_1_3_3_16_2","volume-title":"Topological Anonymity in Networks","author":"Loo Mark van der","year":"2022","unstructured":"Mark van der Loo. 2022. Topological Anonymity in Networks. Discussion Paper. Statistics Netherlands, The Hague. Retrieved from https:\/\/www.cbs.nl\/en-gb\/background\/2022\/17\/topological-anonymity-in-networks."},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1151659.1159930"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.09.003"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055591"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247490"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-021-94283-5"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2068816.2068825"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/69.971193"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.6084\/m9.figshare.7267433.v1"},{"key":"e_1_3_3_26_2","unstructured":"Sociopatterns. 2021. Sociopatterns: Datasets. Retrieved May 2022 from http:\/\/www.sociopatterns.org\/datasets\/."},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1142\/S021848850200165X"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0121-9"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150499"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739058"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497459"},{"key":"e_1_3_3_33_2","unstructured":"Marinka Zitnik Rok Sosi\u010d Sagar Maheshwari and Jure Leskovec. 2018. BioSNAP Datasets: Stanford. Biomedical Network Dataset Collection. Retrieved May 2022 from http:\/\/snap.stanford.edu\/biodata."},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687734"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3604908","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3604908","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:05Z","timestamp":1750178765000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3604908"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,11]]},"references-count":33,"alternative-id":["10.1145\/3604908"],"URL":"https:\/\/doi.org\/10.1145\/3604908","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,11]]}}}