{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:23Z","timestamp":1779174803245,"version":"3.51.4"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,6,24]],"date-time":"2023-06-24T00:00:00Z","timestamp":1687564800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Algorithms and Learning for AI","award":["ALL4AI"],"award-info":[{"award-number":["ALL4AI"]}]},{"name":"Bertinoro International Center for Informatics"},{"name":"European Research Council under the Starting Grant","award":["DMAP 680153"],"award-info":[{"award-number":["DMAP 680153"]}]},{"name":"Department of Computer Science of the Sapienza University of Rome"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,7,31]]},"abstract":"<jats:p>\n            We study the following problem: Given an integer\n            <jats:italic>k<\/jats:italic>\n            \u2265 3 and a simple graph\n            <jats:italic>G<\/jats:italic>\n            , sample a connected induced\n            <jats:italic>k<\/jats:italic>\n            -vertex subgraph of\n            <jats:italic>G<\/jats:italic>\n            uniformly at random. This is a fundamental graph mining primitive with applications in social network analysis, bioinformatics, and more. Surprisingly, no efficient algorithm is known for uniform sampling; the only somewhat efficient algorithms available yield samples that are only approximately uniform, with running times that are unclear or suboptimal. In this work, we provide: (i) a near-optimal mixing time bound for a well-known random walk technique, (ii) the first efficient algorithm for truly uniform graphlet sampling, and (iii) the first sublinear-time algorithm for \u03b5-uniform graphlet sampling.\n          <\/jats:p>","DOI":"10.1145\/3596495","type":"journal-article","created":{"date-parts":[[2023,6,24]],"date-time":"2023-06-24T11:36:16Z","timestamp":1687606576000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5211-2264","authenticated-orcid":false,"given":"Marco","family":"Bressan","sequence":"first","affiliation":[{"name":"Universit\u00e0 degli Studi di Milano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,24]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2019.105851"},{"key":"e_1_3_3_3_2","volume-title":"Reversible Markov Chains and Random Walks on Graphs","author":"Aldous David","year":"1995","unstructured":"David Aldous and James Fill. 1995. Reversible Markov Chains and Random Walks on Graphs. Retrieved from https:\/\/www.stat.berkeley.edu\/aldous\/RWG\/book.pdf."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn163"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2019.6"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3520240"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.87"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2021.55"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0106052"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451042"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00811-0"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018732"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3186586"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342640"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447397"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150418"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021940"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511761942"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1054389"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2021.51"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1176701"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.4230\/OASIcs.SOSA.2018.7"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2016.0029"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741101"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703436424"},{"key":"e_1_3_3_28_2","volume-title":"Markov Chains and Mixing Times","author":"Levin David A.","year":"2009","unstructured":"David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. 2009. Markov Chains and Mixing Times. American Mathematical Society."},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2017.8056956"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976236.64"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330995"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i04.5987"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl301"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-16112-9_2"},{"key":"e_1_3_3_37_2","first-page":"488","volume-title":"Proceedings of the AISTATS","author":"Shervashidze Nino","year":"2009","unstructured":"Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. 2009. Efficient graphlet kernels for large graph comparison. In Proceedings of the AISTATS. 488\u2013495. Retrieved from https:\/\/proceedings.mlr.press\/v5\/shervashidze09a.html."},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052653"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341161.3342908"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488502"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.92917"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629564"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3596495","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3596495","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:48:00Z","timestamp":1750178880000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3596495"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,24]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,7,31]]}},"alternative-id":["10.1145\/3596495"],"URL":"https:\/\/doi.org\/10.1145\/3596495","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,24]]},"assertion":[{"value":"2021-10-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-03","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}