{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:56:20Z","timestamp":1772121380701,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":66,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,8,4]],"date-time":"2023-08-04T00:00:00Z","timestamp":1691107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["CN00000013"],"award-info":[{"award-number":["CN00000013"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,8,6]]},"DOI":"10.1145\/3580305.3599325","type":"proceedings-article","created":{"date-parts":[[2023,8,4]],"date-time":"2023-08-04T18:13:58Z","timestamp":1691172838000},"page":"1872-1884","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Efficient Centrality Maximization with Rademacher Averages"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6601-5526","authenticated-orcid":false,"given":"Leonardo","family":"Pellegrina","sequence":"first","affiliation":[{"name":"University of Padova, Padova, Italy"}]}],"member":"320","published-online":{"date-parts":[[2023,8,4]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989656.1989657"},{"key":"e_1_3_2_2_2_1","volume-title":"Group-Harmonic and Group-Closeness Maximization-Approximation and Engineering. In 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 154--168","author":"Angriman Eugenio","unstructured":"Eugenio Angriman , Ruben Becker , Gianlorenzo d' Angelo , Hugo Gilbert , Alexander van der Grinten, and Henning Meyerhenke. 2021 . Group-Harmonic and Group-Closeness Maximization-Approximation and Engineering. In 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 154--168 . Eugenio Angriman, Ruben Becker, Gianlorenzo d'Angelo, Hugo Gilbert, Alexander van der Grinten, and Henning Meyerhenke. 2021. Group-Harmonic and Group-Closeness Maximization-Approximation and Engineering. In 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 154--168."},{"key":"e_1_3_2_2_3_1","volume-title":"2020 Proceedings of the Twenty-Second Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 56--69","author":"Angriman Eugenio","unstructured":"Eugenio Angriman , Alexander van der Grinten, Aleksandar Bojchevski, Daniel Z\u00fcgner, Stephan G\u00fcnnemann, and Henning Meyerhenke. 2020. Group centrality maximization for large-scale graphs . In 2020 Proceedings of the Twenty-Second Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 56--69 . Eugenio Angriman, Alexander van der Grinten, Aleksandar Bojchevski, Daniel Z\u00fcgner, Stephan G\u00fcnnemann, and Henning Meyerhenke. 2020. Group centrality maximization for large-scale graphs. In 2020 Proceedings of the Twenty-Second Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 56--69."},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"crossref","unstructured":"Martin Anthony Peter L Bartlett Peter L Bartlett etal 1999. Neural network learning: Theoretical foundations. Vol. 9. cambridge university press Cambridge.  Martin Anthony Peter L Bartlett Peter L Bartlett et al. 1999. Neural network learning: Theoretical foundations. Vol. 9. cambridge university press Cambridge.","DOI":"10.1017\/CBO9780511624216"},{"key":"e_1_3_2_2_5_1","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 . Journal of Machine Learning Research , Vol. 3 , Nov (2002), 463 -- 482 . Peter L. Bartlett and Shahar Mendelson. 2002. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, Vol. 3, Nov (2002), 463--482.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_2_6_1","volume-title":"A mathematical model for group structures. Human organization","author":"Bavelas Alex","year":"1948","unstructured":"Alex Bavelas . 1948. A mathematical model for group structures. Human organization , Vol. 7 , 3 ( 1948 ), 16--30. Alex Bavelas. 1948. A mathematical model for group structures. Human organization, Vol. 7, 3 (1948), 16--30."},{"key":"e_1_3_2_2_7_1","volume-title":"Computing top-k closeness centrality faster in unweighted graphs. ACM Transactions on Knowledge Discovery from Data (TKDD)","author":"Bergamini Elisabetta","year":"2019","unstructured":"Elisabetta Bergamini , Michele Borassi , Pierluigi Crescenzi , Andrea Marino , and Henning Meyerhenke . 2019. Computing top-k closeness centrality faster in unweighted graphs. ACM Transactions on Knowledge Discovery from Data (TKDD) , Vol. 13 , 5 ( 2019 ), 1--40. Elisabetta Bergamini, Michele Borassi, Pierluigi Crescenzi, Andrea Marino, and Henning Meyerhenke. 2019. Computing top-k closeness centrality faster in unweighted graphs. ACM Transactions on Knowledge Discovery from Data (TKDD), Vol. 13, 5 (2019), 1--40."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975055.18"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_14"},{"key":"e_1_3_2_2_10_1","volume-title":"2015 Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 133--146","author":"Bergamini Elisabetta","year":"2014","unstructured":"Elisabetta Bergamini , Henning Meyerhenke , and Christian L Staudt . 2014 . Approximating betweenness centrality in large evolving networks . In 2015 Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 133--146 . Elisabetta Bergamini, Henning Meyerhenke, and Christian L Staudt. 2014. Approximating betweenness centrality in large evolving networks. In 2015 Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 133--146."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2013.10"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2013.865686"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2016.03.005"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3284359"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634144"},{"key":"e_1_3_2_2_16_1","volume-title":"Concentration inequalities: A nonasymptotic theory of independence","author":"Boucheron St\u00e9phane","unstructured":"St\u00e9phane Boucheron , G\u00e1bor Lugosi , and Pascal Massart . 2013. Concentration inequalities: A nonasymptotic theory of independence . Oxford university press . St\u00e9phane Boucheron, G\u00e1bor Lugosi, and Pascal Massart. 2013. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1631-073X(02)02292-6"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_3_2_2_19_1","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 APPROX\/RANDOM.  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 APPROX\/RANDOM."},{"key":"e_1_3_2_2_20_1","volume-title":"Support-vector networks. Machine learning","author":"Cortes Corinna","year":"1995","unstructured":"Corinna Cortes and Vladimir Vapnik . 1995. Support-vector networks. Machine learning , Vol. 20 ( 1995 ), 273--297. Corinna Cortes and Vladimir Vapnik. 1995. Support-vector networks. Machine learning, Vol. 20 (1995), 273--297."},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467354"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3534678.3539398"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403235"},{"key":"e_1_3_2_2_24_1","volume-title":"Proceedings of the 2015 SIAM International Conference on Data Mining. SIAM, 433--441","author":"D\u00f3ra","year":"2015","unstructured":"D\u00f3ra ErdHo s, Vatche Ishakian , Azer Bestavros , and Evimaria Terzi . 2015 . A divide-and-conquer algorithm for betweenness centrality . In Proceedings of the 2015 SIAM International Conference on Data Mining. SIAM, 433--441 . D\u00f3ra ErdHo s, Vatche Ishakian, Azer Bestavros, and Evimaria Terzi. 2015. A divide-and-conquer algorithm for betweenness centrality. In Proceedings of the 2015 SIAM International Conference on Data Mining. SIAM, 433--441."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19094-0_4"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403124"},{"key":"e_1_3_2_2_28_1","volume-title":"A set of measures of centrality based on betweenness. Sociometry","author":"Freeman Linton C","year":"1977","unstructured":"Linton C Freeman . 1977. A set of measures of centrality based on betweenness. Sociometry ( 1977 ), 35--41. Linton C Freeman. 1977. A set of measures of centrality based on betweenness. Sociometry (1977), 35--41."},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972887.9"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623738"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-018-0590-x"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116271.3116497"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850578.2850580"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.37"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/3020652.3020697"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0059613"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.930926"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1358-1_29"},{"key":"e_1_3_2_2_41_1","volume-title":"Probability in Banach Spaces: isoperimetry and processes","author":"Ledoux Michel","unstructured":"Michel Ledoux and Michel Talagrand . 1991. Probability in Banach Spaces: isoperimetry and processes . Vol. 23 . Springer Science & Business Media . Michel Ledoux and Michel Talagrand. 1991. Probability in Banach Spaces: isoperimetry and processes. Vol. 23. Springer Science & Business Media."},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1741"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939869"},{"key":"e_1_3_2_2_44_1","first-page":"245","article-title":"Some applications of concentration inequalities to statistics. Annales de la Facult\u00e9 des sciences de Toulouse","volume":"9","author":"Massart Pascal","year":"2000","unstructured":"Pascal Massart . 2000 . Some applications of concentration inequalities to statistics. Annales de la Facult\u00e9 des sciences de Toulouse : Math\u00e9matiques , Vol. 9 , 2 (2000), 245 -- 303 . Pascal Massart. 2000. Some applications of concentration inequalities to statistics. Annales de la Facult\u00e9 des sciences de Toulouse: Math\u00e9matiques, Vol. 9, 2 (2000), 245--303.","journal-title":"Math\u00e9matiques"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975321.14"},{"key":"e_1_3_2_2_46_1","volume-title":"Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher and Eli Upfal . 2017. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis . Cambridge university press . 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_2_2_47_1","volume-title":"Foundations of machine learning","author":"Mohri Mehryar","unstructured":"Mehryar Mohri , Afshin Rostamizadeh , and Ameet Talwalkar . 2018. Foundations of machine learning . MIT press . Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. 2018. Foundations of machine learning. MIT press."},{"key":"e_1_3_2_2_48_1","volume-title":"Networks","author":"Newman Mark","unstructured":"Mark Newman . 2018. Networks . Oxford university press . Mark Newman. 2018. Networks. Oxford university press."},{"key":"e_1_3_2_2_49_1","volume-title":"A measure of betweenness centrality based on random walks. Social networks","author":"Newman Mark EJ","year":"2005","unstructured":"Mark EJ Newman . 2005. A measure of betweenness centrality based on random walks. Social networks , Vol. 27 , 1 ( 2005 ), 39--54. Mark EJ Newman. 2005. A measure of betweenness centrality based on random walks. Social networks, Vol. 27, 1 (2005), 39--54."},{"key":"e_1_3_2_2_51_1","volume-title":"MCRapper: Monte-Carlo Rademacher averages for poset families and approximate pattern mining. ACM Transactions on Knowledge Discovery from Data (TKDD)","author":"Pellegrina Leonardo","year":"2022","unstructured":"Leonardo Pellegrina , Cyrus Cousins , Fabio Vandin , and Matteo Riondato . 2022. MCRapper: Monte-Carlo Rademacher averages for poset families and approximate pattern mining. ACM Transactions on Knowledge Discovery from Data (TKDD) , Vol. 16 , 6 ( 2022 ), 1--29. Leonardo Pellegrina, Cyrus Cousins, Fabio Vandin, and Matteo Riondato. 2022. MCRapper: Monte-Carlo Rademacher averages for poset families and approximate pattern mining. ACM Transactions on Knowledge Discovery from Data (TKDD), Vol. 16, 6 (2022), 1--29."},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3332286"},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330978"},{"key":"e_1_3_2_2_54_1","volume-title":"SILVAN: Estimating Betweenness Centralities with Progressive Sampling and Non-uniform Rademacher Bounds. arXiv preprint arXiv:2106.03462","author":"Pellegrina Leonardo","year":"2021","unstructured":"Leonardo Pellegrina and Fabio Vandin . 2021 . SILVAN: Estimating Betweenness Centralities with Progressive Sampling and Non-uniform Rademacher Bounds. arXiv preprint arXiv:2106.03462 (2021). Leonardo Pellegrina and Fabio Vandin. 2021. SILVAN: Estimating Betweenness Centralities with Progressive Sampling and Non-uniform Rademacher Bounds. arXiv preprint arXiv:2106.03462 (2021)."},{"key":"e_1_3_2_2_55_1","volume-title":"Convergence of stochastic processes","author":"Pollard David","unstructured":"David Pollard . 2012. Convergence of stochastic processes . Springer Science & Business Media . David Pollard. 2012. Convergence of stochastic processes. Springer Science & Business Media."},{"key":"e_1_3_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/312129.312188"},{"key":"e_1_3_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-015-0423-0"},{"key":"e_1_3_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3208351"},{"key":"e_1_3_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385653"},{"key":"e_1_3_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.14778\/3450980.3450988"},{"key":"e_1_3_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3512204"},{"key":"e_1_3_2_2_62_1","unstructured":"Alexander Schrijver et al. 2003. Combinatorial optimization: polyhedra and efficiency. Vol. 24. Springer.  Alexander Schrijver et al. 2003. Combinatorial optimization: polyhedra and efficiency. Vol. 24. Springer."},{"key":"e_1_3_2_2_63_1","volume-title":"Understanding Machine Learning: From Theory to Algorithms","author":"Shalev-Shwartz Shai","unstructured":"Shai Shalev-Shwartz and Shai Ben-David . 2014. Understanding Machine Learning: From Theory to Algorithms . Cambridge University Press . Shai Shalev-Shwartz and Shai Ben-David. 2014. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press."},{"key":"e_1_3_2_2_64_1","volume-title":"Proceedings of Mach. Learn. Knowl. Disc. Databases - European Conf., ECML PKDD","author":"Simionato Dario","year":"2022","unstructured":"Dario Simionato and Fabio Vandin . 2022 . Bounding the Family-Wise Error Rate in Local Causal Discovery using Rademacher Averages . In Proceedings of Mach. Learn. Knowl. Disc. Databases - European Conf., ECML PKDD 2022. Dario Simionato and Fabio Vandin. 2022. Bounding the Family-Wise Error Rate in Local Causal Discovery using Rademacher Averages. In Proceedings of Mach. Learn. Knowl. Disc. Databases - European Conf., ECML PKDD 2022."},{"key":"e_1_3_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_3_2_2_66_1","volume-title":"Collective dynamics of ?small-world'networks. nature","author":"Watts Duncan J","year":"1998","unstructured":"Duncan J Watts and Steven H Strogatz . 1998. Collective dynamics of ?small-world'networks. nature , Vol. 393 , 6684 ( 1998 ), 440--442. Duncan J Watts and Steven H Strogatz. 1998. Collective dynamics of ?small-world'networks. nature, Vol. 393, 6684 (1998), 440--442."},{"key":"e_1_3_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623626"}],"event":{"name":"KDD '23: The 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","location":"Long Beach CA USA","acronym":"KDD '23","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data"]},"container-title":["Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580305.3599325","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3580305.3599325","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:47Z","timestamp":1750178267000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580305.3599325"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,4]]},"references-count":66,"alternative-id":["10.1145\/3580305.3599325","10.1145\/3580305"],"URL":"https:\/\/doi.org\/10.1145\/3580305.3599325","relation":{},"subject":[],"published":{"date-parts":[[2023,8,4]]},"assertion":[{"value":"2023-08-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}