{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T21:26:28Z","timestamp":1772832388259,"version":"3.50.1"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,16]],"date-time":"2024-05-16T00:00:00Z","timestamp":1715817600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANID\u2014Millennium Science Initiative Program","award":["ICN17_002"],"award-info":[{"award-number":["ICN17_002"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"<jats:p>\n            We present the theoretical foundations and first experimental study of a new approach in centrality measures for graph data. The main principle is straightforward: the more relevant subgraphs around a vertex, the more central it is in the network. We formalize the notion of \u201crelevant subgraphs\u201d by choosing a family of subgraphs that, given a graph\n            <jats:italic>G<\/jats:italic>\n            and a vertex\n            <jats:italic>v<\/jats:italic>\n            , assigns a subset of connected subgraphs of\n            <jats:italic>G<\/jats:italic>\n            that contains\n            <jats:italic>v<\/jats:italic>\n            . Any of such families defines a measure of centrality by counting the number of subgraphs assigned to the vertex, i.e., a vertex will be more important for the network if it belongs to more subgraphs in the family. We show several examples of this approach. In particular, we propose the All-Subgraphs (All-Trees) centrality, a centrality measure that considers every subgraph (tree). We study fundamental properties over families of subgraphs that guarantee desirable properties over the centrality measure. Interestingly, All-Subgraphs and All-Trees satisfy all these properties, showing their robustness as centrality notions. To conclude the theoretical analysis, we study the computational complexity of counting certain families of subgraphs and show a linear time algorithm to compute the All-Subgraphs and All-Trees centrality for graphs with bounded treewidth. Finally, we implemented these algorithms and computed these measures over more than one hundred real-world networks. With this data, we present an empirical comparison between well-known centrality measures and those proposed in this work.\n          <\/jats:p>","DOI":"10.1145\/3649134","type":"journal-article","created":{"date-parts":[[2024,2,23]],"date-time":"2024-02-23T12:03:41Z","timestamp":1708689821000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["A Family of Centrality Measures for Graph Data Based on Subgraphs"],"prefix":"10.1145","volume":"49","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-5951-1069","authenticated-orcid":false,"given":"Sebasti\u00e1n","family":"Bugedo","sequence":"first","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile and Millennium Institute for Foundational Research on Data, Santiago, Chile"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0832-116X","authenticated-orcid":false,"given":"Cristian","family":"Riveros","sequence":"additional","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile and Millennium Institute for Foundational Research on Data, Santiago, Chile"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5535-3055","authenticated-orcid":false,"given":"Jorge","family":"Salas","sequence":"additional","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile and Millennium Institute for Foundational Research on Data, Santiago, Chile"}]}],"member":"320","published-online":{"date-parts":[[2024,5,16]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1177\/2399808317724444"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.5555\/578775"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3104031"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/1540612"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICPR.2018.8546109"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1121\/1.1906679"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0029946"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.03.008"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1017\/nws.2017.21"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2013.865686"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1086\/228631"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2005.11.005"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.5555\/1062400"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_3_3_16_2","unstructured":"Sebasti\u00e1n Bugedo. 2024. Centrality Algorithms. Retrieved February 12 2024 from https:\/\/github.com\/Motif-Based-Centralities\/Centrality-Algorithms"},{"key":"e_1_3_3_17_2","volume-title":"Proceedings of the AMW","author":"Buil-Aranda Carlos","year":"2015","unstructured":"Carlos Buil-Aranda, Mart\u0131n Ugarte, Marcelo Arenas, and Michel Dumontier. 2015. A preliminary investigation into SPARQL query complexity and federation in Bio2RDF. In Proceedings of the AMW."},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129090"},{"issue":"23","key":"e_1_3_3_19_2","article-title":"Kendall tau sequence distance: Extending Kendall tau from ranks to sequences","volume":"7","author":"Vincent Cicirello","year":"2020","unstructured":"Vincent Cicirello. 2020. Kendall tau sequence distance: Extending Kendall tau from ranks to sequences. EAI Endorsed Transactions on Industrial Networks and Intelligent Systems 7, 23.","journal-title":"EAI Endorsed Transactions on Industrial Networks and Intelligent Systems"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511977619"},{"key":"e_1_3_3_21_2","volume-title":"Elements of Information Theory","author":"Cover Thomas M.","year":"2012","unstructured":"Thomas M. Cover and Joy A. Thomas. 2012. Elements of Information Theory. John Wiley and Sons."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jocs.2020.101127"},{"key":"e_1_3_3_23_2","article-title":"Halting viruses in scale-free networks","volume":"65","author":"Dezs\u0151 Zolt\u00e1n","year":"2002","unstructured":"Zolt\u00e1n Dezs\u0151 and Albert-L\u00e1szl\u00f3 Barab\u00e1si. 2002. Halting viruses in scale-free networks. Physical Review E 65, 5 (2002), 055103.","journal-title":"Physical Review E"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.71.056103"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2013.2280884"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.2307\/3033543"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(78)90021-7"},{"key":"e_1_3_3_28_2","article-title":"Axiomatic foundations of centrality in networks","author":"Garg Manuj","year":"2009","unstructured":"Manuj Garg. 2009. Axiomatic foundations of centrality in networks. Available at SSRN 1372441 (2009).","journal-title":"Available at SSRN 1372441"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ecolind.2021.107617"},{"key":"e_1_3_3_31_2","volume-title":"Proceedings of the 7th Python in Science Conference","author":"Hagberg Aric A.","year":"2008","unstructured":"Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. 2008. Exploring network structure, dynamics, and function using networkx. In Proceedings of the 7th Python in Science Conference. Pasadena, CA USA."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.5121\/csit.2016.61301"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2011.06.004"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btq680"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1038\/35075138"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00085-9"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ecolmodel.2007.02.032"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289026"},{"key":"e_1_3_3_39_2","volume-title":"The Stanford GraphBase: A Platform for Combinatorial Computing","author":"Knuth Donald E.","year":"1993","unstructured":"Donald E. Knuth. 1993. The Stanford GraphBase: A Platform for Combinatorial Computing. ACM."},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtbi.2007.05.038"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1037\/h0057189"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2015-50671-y"},{"key":"e_1_3_3_43_2","article-title":"Link prediction model for weighted networks based on evidence theory and the influence of common neighbours","author":"Liu Miaomiao","year":"2022","unstructured":"Miaomiao Liu, Yang Wang, Jing Chen, and Yongsheng Zhang. 2022. Link prediction model for weighted networks based on evidence theory and the influence of common neighbours. Complexity (2022), 9151340.","journal-title":"Complexity"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38288-8_9"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.3233\/SW-180333"},{"key":"e_1_3_3_46_2","volume-title":"Proceedings of the OSDI","author":"Moritz Philipp","year":"2018","unstructured":"Philipp Moritz, Robert Nishihara, Stephanie Wang, Alexey Tumanov, Richard Liaw, Eric Liang, Melih Elibol, Zongheng Yang, William Paul, Michael I. Jordan, et\u00a0al. 2018. Ray: A distributed framework for emerging AI applications. In Proceedings of the OSDI."},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316588284"},{"key":"e_1_3_3_48_2","unstructured":"Neo4j. 2024. Centrality algorithms. Retrieved August 31 2022 from https:\/\/neo4j.com\/docs\/graph-data-science\/current\/algorithms\/centrality\/"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198805090.001.0001"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.74.036104"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0220061"},{"key":"e_1_3_3_52_2","volume-title":"The PageRank Citation Ranking: Bringing Order to the Web.","author":"Page Lawrence","year":"1999","unstructured":"Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. The PageRank Citation Ranking: Bringing Order to the Web.Technical Report. Stanford InfoLab."},{"key":"e_1_3_3_53_2","volume-title":"Proceedings of the ICDT","author":"Riveros Cristian","year":"2020","unstructured":"Cristian Riveros and Jorge Salas. 2020. A family of centrality measures for graph data based on subgraphs. In Proceedings of the ICDT."},{"key":"e_1_3_3_54_2","volume-title":"Closeness Centrality Extended to Unconnected Graphs: The Harmonic Centrality Index","author":"Rochat Yannick","year":"2009","unstructured":"Yannick Rochat. 2009. Closeness Centrality Extended to Unconnected Graphs: The Harmonic Centrality Index. Technical Report."},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289527"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1515\/phys-2018-0122"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2021.09.235"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.11202"},{"key":"e_1_3_3_60_2","volume-title":"Proceedings of the AAMAS","author":"Skibski Oskar","year":"2016","unstructured":"Oskar Skibski, Talal Rahwan, Tomasz P. Michalak, and Makoto Yokoo. 2016. Attachment centrality: An axiomatic approach to connectivity in networks. In Proceedings of the AAMAS."},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.11441"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1089\/brain.2011.0055"},{"key":"e_1_3_3_63_2","article-title":"Centrality algorithms","year":"2024","unstructured":"TigerGraph. 2024. Centrality algorithms. Retrieved August 26 2023 from https:\/\/docs.tigergraph.com\/graph-ml\/current\/centrality-algorithms\/","journal-title":"R"},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1093\/comnet\/cnt004"},{"key":"e_1_3_3_65_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_3_3_66_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.21834"},{"key":"e_1_3_3_67_2","volume-title":"Proceedings of the AAAI","author":"W\u0105s Tomasz","year":"2018","unstructured":"Tomasz W\u0105s and Oskar Skibski. 2018. An axiomatization of the eigenvector and katz centralities. In Proceedings of the AAAI."},{"key":"e_1_3_3_68_2","doi-asserted-by":"publisher","DOI":"10.1002\/asi.21128"},{"key":"e_1_3_3_69_2","doi-asserted-by":"publisher","DOI":"10.1086\/jar.33.4.3629752"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649134","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3649134","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:50:01Z","timestamp":1750287001000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649134"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,16]]},"references-count":68,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1145\/3649134"],"URL":"https:\/\/doi.org\/10.1145\/3649134","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,16]]},"assertion":[{"value":"2023-01-27","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-24","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-05-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}