{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:57Z","timestamp":1750220697826,"version":"3.41.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,3,13]],"date-time":"2020-03-13T00:00:00Z","timestamp":1584057600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100010193","name":"Korea Electric Power Corporation","doi-asserted-by":"crossref","award":["R18XA05"],"award-info":[{"award-number":["R18XA05"]}],"id":[{"id":"10.13039\/501100010193","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Korea governmen","award":["2016R1A2B4014658"],"award-info":[{"award-number":["2016R1A2B4014658"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2020,6,30]]},"abstract":"<jats:p>\n            A B-hypergraph consisting of nodes and directed hyperedges is a generalization of the directed graph. A directed hyperedge in the B-hypergraph represents a relation from a set of source nodes to a single destination node. We suggest one possible definition of betweenness centrality (BC) in B-hypergraphs, called Participation-based BC (PBC). A PBC score of a node is computed based on the number of the shortest paths in which the node participates. This score can be expressed in terms of dependency on the set of its outgoing hyperedges. In this article, we focus on developing efficient computation algorithms for PBC. We first present an algorithm called ePBC for computing exact PBC scores of nodes, which has a cubic-time complexity. This algorithm, however, can be used for only small-sized B-hypergraphs because of its cubic-time complexity, so we propose linearized PBC (\n            <jats:italic>\u2113<\/jats:italic>\n            PBC) that is an approximation method of ePBC.\n            <jats:italic>\u2113<\/jats:italic>\n            PBC that comes with a guaranteed upper bound on its error, uses a linearization of dependency on a set of hyperedges.\n            <jats:italic>\u2113<\/jats:italic>\n            PBC improves the computing time of ePBC by an order of magnitude (i.e., it requires a quadratic time) while maintaining a high accuracy.\n            <jats:italic>\u2113<\/jats:italic>\n            PBC works well on small to medium-sized B-hypergraphs, but is not scalable enough for a very large B-hypergraph with more than a million hyperedges. To cope with such a very large B-hypergraph, we propose a very fast heuristic sampling-based method called sampling-based\n            <jats:italic>\u2113<\/jats:italic>\n            PBC (s\n            <jats:italic>\u2113<\/jats:italic>\n            PBC). We show through extensive experiments that\n            <jats:italic>\u2113<\/jats:italic>\n            PBC and s\n            <jats:italic>\u2113<\/jats:italic>\n            PBC can efficiently estimate PBC scores in various real-world B-hypergraphs with a reasonably good precision@\n            <jats:italic>k<\/jats:italic>\n            . The experimental results show that s\n            <jats:italic>\u2113<\/jats:italic>\n            PBC works efficiently even for a very large B-hypergraph.\n          <\/jats:p>","DOI":"10.1145\/3375399","type":"journal-article","created":{"date-parts":[[2020,3,13]],"date-time":"2020-03-13T14:48:38Z","timestamp":1584110918000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Linearization of Dependency and Sampling for Participation-based Betweenness Centrality in Very Large B-hypergraphs"],"prefix":"10.1145","volume":"14","author":[{"given":"Kwang Hee","family":"Lee","sequence":"first","affiliation":[{"name":"Korea Advanced Institute of Science and Technology, Daejeon, South Korea"}]},{"given":"Myoung Ho","family":"Kim","sequence":"additional","affiliation":[{"name":"Korea Advanced Institute of Science and Technology, Daejeon, South Korea"}]}],"member":"320","published-online":{"date-parts":[[2020,3,13]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1016\/j.joi.2012.01.002"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/1989656.1989657"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1145\/3085504.3085510"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1038\/nrd1468"},{"key":"e_1_2_1_5_1","volume-title":"PB","author":"Ausiello Giorgio","year":"2017","unstructured":"Giorgio Ausiello and Luigi Laura . 2017. Directed hypergraphs: Introduction and fundamental algorithms - A survey. Theoretical Computer Science 658 , PB ( 2017 ), 293--306. Giorgio Ausiello and Luigi Laura. 2017. Directed hypergraphs: Introduction and fundamental algorithms - A survey. Theoretical Computer Science 658, PB (2017), 293--306."},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.5555\/1777879.1777889"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1214\/009053605000000282"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 11th International Conference on Innovative Internet Community Services. LNI, 159--168","author":"Bothorel C\u00e9cile","year":"2011","unstructured":"C\u00e9cile Bothorel and Mohamed Bouklit . 2011 . An algorithm for detecting communities in folksonomy hypergraphs . In Proceedings of the 11th International Conference on Innovative Internet Community Services. LNI, 159--168 . C\u00e9cile Bothorel and Mohamed Bouklit. 2011. An algorithm for detecting communities in folksonomy hypergraphs. In Proceedings of the 11th International Conference on Innovative Internet Community Services. LNI, 159--168."},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1080\/0022250X.2001.9990249"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1016\/j.socnet.2007.11.001"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1186\/1752-0509-6-10"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.2307\/3033543"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1016\/0166-218X(93)90045-P"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1109\/Allerton.2012.6483306"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.14778\/2850578.2850580"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1103\/PhysRevE.65.056109"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 20--23","author":"Hwang Woochang","year":"2006","unstructured":"Woochang Hwang , Young-rae Cho, Aidong Zhang , and Murali Ramanathan . 2006 . Bridging centrality: Identifying bridging nodes in scale-free networks . In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 20--23 . Woochang Hwang, Young-rae Cho, Aidong Zhang, and Murali Ramanathan. 2006. Bridging centrality: Identifying bridging nodes in scale-free networks. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 20--23."},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1371\/journal.pone.0059613"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1038\/msb.2010.56"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1007\/BF01271266"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1371\/journal.pcbi.1000385"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1093\/bfgp\/els030"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1016\/j.socnet.2009.02.003"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1371\/journal.pone.0086197"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1145\/3132847.3133093"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1145\/2187836.2187884"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1002\/asi.20614"},{"key":"e_1_2_1_28_1","volume-title":"Co-authorship networks in the digital library research community. Information Processing 8 Management 41, 6","author":"Liu Xiaoming","year":"2005","unstructured":"Xiaoming Liu , Johan Bollen , Michael L. Nelson , and Herbert Van de Sompel . 2005. Co-authorship networks in the digital library research community. Information Processing 8 Management 41, 6 ( 2005 ), 1462--1480. Xiaoming Liu, Johan Bollen, Michael L. Nelson, and Herbert Van de Sompel. 2005. Co-authorship networks in the digital library research community. Information Processing 8 Management 41, 6 (2005), 1462--1480."},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1016\/j.socnet.2004.11.009"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1016\/j.cor.2003.11.014"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1093\/nar\/27.1.29"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1103\/PhysRevE.76.056709"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1016\/j.socnet.2013.07.006"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1007\/978-3-319-70278-0_16"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1007\/s10618-015-0423-0"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1145\/2939672.2939770"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1145\/3208351"},{"key":"e_1_2_1_38_1","article-title":"Pathway analysis with signaling hypergraphs","volume":"14","author":"Ritz Anna","year":"2015","unstructured":"Anna Ritz , Brendan Avent , and T. Murali . 2015 . Pathway analysis with signaling hypergraphs . IEEE\/ACM Transactions on Computational Biology and Bioinformatics 14 , 5 (2015). 1042\u20131055. Anna Ritz, Brendan Avent, and T. Murali. 2015. Pathway analysis with signaling hypergraphs. IEEE\/ACM Transactions on Computational Biology and Bioinformatics 14, 5 (2015). 1042\u20131055.","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1093\/nar\/gkn653"},{"doi-asserted-by":"crossref","unstructured":"Shai Shalev-Shwartz and Shai Ben-David. 2014. Understanding Machine Learning: From Theory to Algorithms. CUP.  Shai Shalev-Shwartz and Shai Ben-David. 2014. Understanding Machine Learning: From Theory to Algorithms. CUP.","key":"e_1_2_1_40_1","DOI":"10.1017\/CBO9781107298019"},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.1145\/1401890.1402008"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.1016\/j.ejor.2007.04.023"},{"doi-asserted-by":"publisher","key":"e_1_2_1_43_1","DOI":"10.1145\/2623330.2623626"},{"doi-asserted-by":"publisher","key":"e_1_2_1_44_1","DOI":"10.1038\/s41598-017-07448-6"},{"key":"e_1_2_1_45_1","volume-title":"C","author":"Zhang Wen","year":"2018","unstructured":"Wen Zhang , Xinrui Liu , Yanlin Chen , Wenjian Wu , Wei Wang , and Xiaohong Li. 2018. Feature-derived graph regularized matrix factorization for predicting drug side effects. Neurocomputing 287 , C ( 2018 ), 154--162. Wen Zhang, Xinrui Liu, Yanlin Chen, Wenjian Wu, Wei Wang, and Xiaohong Li. 2018. Feature-derived graph regularized matrix factorization for predicting drug side effects. Neurocomputing 287, C (2018), 154--162."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3375399","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3375399","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:32:49Z","timestamp":1750199569000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3375399"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,13]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,6,30]]}},"alternative-id":["10.1145\/3375399"],"URL":"https:\/\/doi.org\/10.1145\/3375399","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2020,3,13]]},"assertion":[{"value":"2018-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-03-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}