{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,31]],"date-time":"2026-07-31T03:11:02Z","timestamp":1785467462576,"version":"3.56.0"},"reference-count":69,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,12,9]],"date-time":"2023-12-09T00:00:00Z","timestamp":1702080000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Italian Ministry of University and Research","award":["2022TS4Y3N"],"award-info":[{"award-number":["2022TS4Y3N"]}]},{"name":"National Center for HPC, Big Data, and Quantum Computing","award":["CN00000013"],"award-info":[{"award-number":["CN00000013"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2024,4,30]]},"abstract":"<jats:p>\n            <jats:italic>\u201cSim Sala Bim!\u201d<\/jats:italic>\n            \u2014Silvan,\n          <\/jats:p>\n          <jats:p>\n            <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"url\" xlink:href=\"https:\/\/en.wikipedia.org\/wiki\/Silvan_(illusionist)\">https:\/\/en.wikipedia.org\/wiki\/Silvan_(illusionist)<\/jats:ext-link>\n          <\/jats:p>\n          <jats:p>\n            Betweenness centrality is a popular centrality measure with applications in several domains and whose exact computation is impractical for modern-sized networks. We present\n            <jats:sc>SILVAN<\/jats:sc>\n            , a novel, efficient algorithm to compute, with high probability, accurate estimates of the betweenness centrality of all nodes of a graph and a high-quality approximation of the top-\n            <jats:italic>k<\/jats:italic>\n            betweenness centralities.\n            <jats:sc>SILVAN<\/jats:sc>\n            follows a progressive sampling approach and builds on novel bounds based on Monte Carlo Empirical Rademacher Averages, a powerful and flexible tool from statistical learning theory.\n            <jats:sc>SILVAN<\/jats:sc>\n            relies on a novel estimation scheme providing\n            <jats:italic>non-uniform<\/jats:italic>\n            bounds on the deviation of the estimates of the betweenness centrality of all the nodes from their true values and a refined characterisation of the number of samples required to obtain a high-quality approximation. Our extensive experimental evaluation shows that\n            <jats:sc>SILVAN<\/jats:sc>\n            extracts high-quality approximations while outperforming, in terms of number of samples and accuracy, the state-of-the-art approximation algorithm with comparable quality guarantees.\n          <\/jats:p>","DOI":"10.1145\/3628601","type":"journal-article","created":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T21:53:37Z","timestamp":1697838817000},"page":"1-55","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["<scp>SILVAN<\/scp>\n            : Estimating Betweenness Centralities with Progressive Sampling and Non-uniform Rademacher Bounds"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6601-5526","authenticated-orcid":false,"given":"Leonardo","family":"Pellegrina","sequence":"first","affiliation":[{"name":"Department of Information Engineering, University of Padova, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2244-2320","authenticated-orcid":false,"given":"Fabio","family":"Vandin","sequence":"additional","affiliation":[{"name":"Department of Information Engineering, University of Padova, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,12,9]]},"reference":[{"issue":"9","key":"e_1_3_3_2_2","article-title":"The rush in a directed graph","author":"Anthonisse Jac M.","year":"1971","unstructured":"Jac M. Anthonisse. 1971. The rush in a directed graph. Stichting Mathematisch Centrum. Mathematische Besliskunde BN 9\/71 (1971).","journal-title":"Stichting Mathematisch Centrum. Mathematische Besliskunde"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1214\/009053605000000282"},{"key":"e_1_3_3_4_2","first-page":"463","article-title":"Rademacher and Gaussian complexities: Risk bounds and structural results","volume":"3","author":"Bartlett Peter L.","year":"2002","unstructured":"Peter L. Bartlett and Shahar Mendelson. 2002. Rademacher and Gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res. 3, Nov (2002), 463\u2013482.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3344719"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3166071"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_14"},{"key":"e_1_3_3_8_2","first-page":"133","volume-title":"Proceedings of the 17th Workshop on Algorithm Engineering and Experiments (ALENEX\u201915)","author":"Bergamini Elisabetta","year":"2014","unstructured":"Elisabetta Bergamini, Henning Meyerhenke, and Christian L. Staudt. 2014. Approximating betweenness centrality in large evolving networks. In Proceedings of the 17th Workshop on Algorithm Engineering and Experiments (ALENEX\u201915). SIAM, 133\u2013146."},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.2000.12005203"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963493"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2013.10"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2016.03.005"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3284359"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1051\/ps:2005018"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/S1631-073X(02)02292-6"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.3390\/a13090216"},{"key":"e_1_3_3_19_2","volume-title":"APPROX\/RANDOM\u201915)","author":"Chechik Shiri","year":"2015","unstructured":"Shiri Chechik, Edith Cohen, and Haim Kaplan. 2015. Average distance queries through weighted samples in graphs and metric spaces: High scalability with tight statistical guarantees. In Proceedings of the International Conference on Randomization and Computation (APPROX\/RANDOM\u201915)."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-018-9613-y"},{"key":"e_1_3_3_21_2","first-page":"15123","article-title":"Sharp uniform convergence bounds through empirical centralization","volume":"33","author":"Cousins Cyrus","year":"2020","unstructured":"Cyrus Cousins and Matteo Riondato. 2020. Sharp uniform convergence bounds through empirical centralization. Adv. Neural Info. Process. Syst. 33 (2020), 15123\u201315132.","journal-title":"Adv. Neural Info. Process. Syst."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3577021"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.09.018"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30850-5_10"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3534678.3539398"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403235"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/DSAA.2019.00021"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974010.49"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.46"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.2307\/3033543"},{"key":"e_1_3_3_31_2","volume-title":"Empirical Processes in M-estimation","author":"Geer Sara A.","year":"2000","unstructured":"Sara A. Geer and Sara van de Geer. 2000. Empirical Processes in M-estimation, Vol. 6. Cambridge University Press."},{"key":"e_1_3_3_32_2","article-title":"A tutorial on statistically sound pattern discovery","author":"H\u00e4m\u00e4l\u00e4inen Wilhelmiina","year":"2018","unstructured":"Wilhelmiina H\u00e4m\u00e4l\u00e4inen and Geoffrey I. Webb. 2018. A tutorial on statistically sound pattern discovery. Data Min Knowl Disc. 33 (2019), 325\u2013377.","journal-title":"Data Min Knowl Disc."},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.5555\/3116271.3116497"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.14778\/2850578.2850580"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.37"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1358-1_29"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1741"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_29"},{"key":"e_1_3_3_39_2","first-page":"1","article-title":"Fast computation of empirically tight bounds for the diameter of massive graphs","volume":"13","author":"Magnien Cl\u00e9mence","year":"2009","unstructured":"Cl\u00e9mence Magnien, Matthieu Latapy, and Michel Habib. 2009. Fast computation of empirically tight bounds for the diameter of massive graphs. J. Exper. Algor. 13 (2009), 1\u201310.","journal-title":"J. Exper. Algor."},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939869"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.5555\/98124"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.5802\/afst.961"},{"key":"e_1_3_3_43_2","volume-title":"Proceedings of the 22nd Conference on Learning Theory (COLT\u201909)","author":"Maurer Andreas","year":"2009","unstructured":"Andreas Maurer and Massimiliano Pontil. 2009. Empirical bernstein bounds and sample-variance penalization. In Proceedings of the 22nd Conference on Learning Theory (COLT\u201909)."},{"key":"e_1_3_3_44_2","volume-title":"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis","author":"Mitzenmacher Michael","year":"2017","unstructured":"Michael Mitzenmacher and Eli Upfal. 2017. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press."},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198805090.001.0001"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.neunet.2013.03.017"},{"key":"e_1_3_3_47_2","unstructured":"Leonardo Pellegrina. 2020. Sharper convergence bounds of Monte Carlo Rademacher Averages through Self-Bounding functions. Retrieved from https:\/\/arXiv:2010.12103"},{"key":"e_1_3_3_48_2","volume-title":"Rigorous and Efficient Algorithms for Significant and Approximate Pattern Mining","author":"Pellegrina Leonardo","year":"2021","unstructured":"Leonardo Pellegrina. 2021. Rigorous and Efficient Algorithms for Significant and Approximate Pattern Mining. Ph.D. Thesis. Retrieved from https:\/\/hdl.handle.net\/11577\/3471458"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3580305.3599325"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3532187"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3332286"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330978"},{"key":"e_1_3_3_53_2","volume-title":"Convergence of Stochastic Processes","author":"Pollard David","year":"2012","unstructured":"David Pollard. 2012. Convergence of Stochastic Processes. Springer Science & Business Media."},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/312129.312188"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-015-0423-0"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629586"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783265"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/3208351"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/3385653"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.14778\/3450980.3450988"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3512204"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.3390\/a13050123"},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972832.76"},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/3459637.3482459"},{"key":"e_1_3_3_65_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107298019"},{"key":"e_1_3_3_66_2","doi-asserted-by":"publisher","DOI":"10.1017\/nws.2016.20"},{"key":"e_1_3_3_67_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2545-2"},{"key":"e_1_3_3_68_2","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_3_3_69_2","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_3_3_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623626"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3628601","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3628601","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:44Z","timestamp":1750291424000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3628601"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,9]]},"references-count":69,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,4,30]]}},"alternative-id":["10.1145\/3628601"],"URL":"https:\/\/doi.org\/10.1145\/3628601","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,9]]},"assertion":[{"value":"2022-06-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-26","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}