{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:29:17Z","timestamp":1755998957009,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":61,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,18]],"date-time":"2023-06-18T00:00:00Z","timestamp":1687046400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CNS-2120667 and CCF-1763786"],"award-info":[{"award-number":["CNS-2120667 and CCF-1763786"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,18]]},"DOI":"10.1145\/3584372.3588671","type":"proceedings-article","created":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T22:21:22Z","timestamp":1685744482000},"page":"183-194","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Node-Differentially Private Estimation of the Number of Connected Components"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0995-6346","authenticated-orcid":false,"given":"Iden","family":"Kalemaj","sequence":"first","affiliation":[{"name":"Boston University, Boston, MA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4902-050X","authenticated-orcid":false,"given":"Sofya","family":"Raskhodnikova","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9393-1127","authenticated-orcid":false,"given":"Adam","family":"Smith","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5591-3585","authenticated-orcid":false,"given":"Charalampos E.","family":"Tsourakakis","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,18]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2019.2901716"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-014-0365-y"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1214\/10-AAP718"},{"volume-title":"Geometric nonlinear functional analysis","author":"Benyamini Yoav","key":"e_1_3_2_1_4_1","unstructured":"Yoav Benyamini and Joram Lindenstrauss. 1998. Geometric nonlinear functional analysis. American Mathematical Society."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.05.008"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.67"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422449"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.26"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--319--17142--5_14"},{"key":"e_1_3_2_1_10_1","volume-title":"Smith","author":"Borgs Christian","year":"2015","unstructured":"Christian Borgs, Jennifer T. Chayes, and Adam D. Smith. 2015. Private Graphon Estimation for Sparse Graphs. In Advances in Neural Information Processing Systems (NeurIPS). 1369--1377."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00057"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403244"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1214\/18-AOAS1163"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465304"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-031--26390--3_1"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.32"},{"key":"e_1_3_2_1_17_1","volume-title":"Gaurav Aggarwal, and Prateek Jain.","author":"Daigavane Ameya","year":"2021","unstructured":"Ameya Daigavane, Gagan Madan, Aditya Sinha, Abhradeep Guha Thakurta, Gaurav Aggarwal, and Prateek Jain. 2021. Node-Level Differentially Private Graph Neural Networks. arxiv: 2111.15521"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2926745"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00077"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3269206.3271736"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11761679_29"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.29012\/jpc.v7i3.405"},{"key":"e_1_3_2_1_23_1","volume-title":"On the evolution of random graphs","author":"ErdHos Paul","year":"1960","unstructured":"Paul ErdHos and Alfr\u00e9d R\u00e9yni. 1960. On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences (1960), 17--61."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2006.10129124"},{"key":"e_1_3_2_1_25_1","first-page":"177","article-title":"Estimation of the number of connected components in a graph by using a sampled subgraph","volume":"5","author":"Frank Ove","year":"1978","unstructured":"Ove Frank. 1978. Estimation of the number of connected components in a graph by using a sampled subgraph. Scandinavian Journal of Statistics , Vol. 5, 4 (1978), 177--188.","journal-title":"Scandinavian Journal of Statistics"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_19"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.11"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.121"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611523"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642--33627-0_21"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642--36594--2_26"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2670979.2670997"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.3150\/19-BEJ1147"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.3040077"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623683"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002--9904--1934-05978-0"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.41"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_3_2_1_40_1","unstructured":"Tamara T. Mueller Dmitrii Usynin Johannes C. Paetzold Daniel Ruecker and Georgios Kaissis. 2022. SoK: Differential privacy on graph-structured data. arxiv: 2203.09205"},{"key":"e_1_3_2_1_41_1","volume-title":"Proceedings of the Workshops of the EDBT\/ICDT 2015 Joint Conference","volume":"1330","author":"Yvonne M\u00fc","year":"2015","unstructured":"Yvonne M\u00fc lle, Chris Clifton, and Klemens B\u00f6 hm. 2015. Privacy-integrated graph clustering through differential privacy. In Proceedings of the Workshops of the EDBT\/ICDT 2015 Joint Conference, Vol. 1330. 247--254."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2994620.2994624"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250803"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73429--7"},{"volume-title":"Random Geometric Graphs","author":"Penrose Mathew D.","key":"e_1_3_2_1_45_1","unstructured":"Mathew D. Penrose. 2003. Random Geometric Graphs. Vol. 5. Oxford University Press."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-012-0428--1"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732296.2732300"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--1--4939--2864--4_549"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.60"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2019.8737405"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.29012\/jpc.745"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642--42033--7_15"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642--37456--2_28"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-013-0127--7"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01788671"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452756"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00701--5"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737785"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2019.2927365"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM50108.2020.00184"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2022.37"}],"event":{"name":"SIGMOD\/PODS '23: International Conference on Management of Data","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"],"location":"Seattle WA USA","acronym":"SIGMOD\/PODS '23"},"container-title":["Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584372.3588671","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/abs\/10.1145\/3584372.3588671","content-type":"text\/html","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3584372.3588671","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3584372.3588671","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:28Z","timestamp":1750178788000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584372.3588671"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,18]]},"references-count":61,"alternative-id":["10.1145\/3584372.3588671","10.1145\/3584372"],"URL":"https:\/\/doi.org\/10.1145\/3584372.3588671","relation":{},"subject":[],"published":{"date-parts":[[2023,6,18]]},"assertion":[{"value":"2023-06-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}