{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,3]],"date-time":"2026-02-03T18:22:12Z","timestamp":1770142932327,"version":"3.49.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,7,11]],"date-time":"2023-07-11T00:00:00Z","timestamp":1689033600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62072138"],"award-info":[{"award-number":["62072138"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Open Research Projects of Zhejiang Lab","award":["2021KC0AB02"],"award-info":[{"award-number":["2021KC0AB02"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Web"],"published-print":{"date-parts":[[2023,11,30]]},"abstract":"<jats:p>\n            Centrality is a family of metrics for characterizing the importance of a vertex in a graph. Although a large number of centrality metrics have been proposed, a majority of them ignores uncertainty in graph data. In this article, we formulate closeness centrality on uncertain graphs and define the batch closeness centrality evaluation problem that computes the closeness centrality of a subset of vertices in an uncertain graph. We develop three algorithms,\n            <jats:sans-serif>MS-BCC<\/jats:sans-serif>\n            ,\n            <jats:sans-serif>MG-BCC,<\/jats:sans-serif>\n            and\n            <jats:sans-serif>MGMS-BCC<\/jats:sans-serif>\n            , based on sampling to approximate the closeness centrality of the specified vertices. All these algorithms require to perform breadth-first searches (BFS) starting from the specified vertices on a large number of sampled possible worlds of the uncertain graph. To improve the efficiency of the algorithms, we exploit operation-level parallelism of the BFS traversals and simultaneously execute the shared sequences of operations in the breadth-first searches. Parallelization is realized at different levels in these algorithms. The experimental results show that the proposed algorithms can efficiently and accurately approximate the closeness centrality of the given vertices.\n            <jats:sans-serif>MGMS-BCC<\/jats:sans-serif>\n            is faster than both\n            <jats:sans-serif>MS-BCC<\/jats:sans-serif>\n            and\n            <jats:sans-serif>MG-BCC<\/jats:sans-serif>\n            because it avoids more repeated executions of the shared operation sequences in the BFS traversals.\n          <\/jats:p>","DOI":"10.1145\/3604912","type":"journal-article","created":{"date-parts":[[2023,6,15]],"date-time":"2023-06-15T12:10:03Z","timestamp":1686831003000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Closeness Centrality on Uncertain Graphs"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-9694-7029","authenticated-orcid":false,"given":"Zhenfang","family":"Liu","sequence":"first","affiliation":[{"name":"Harbin Institute of Technology, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-8004-1313","authenticated-orcid":false,"given":"Jianxiong","family":"Ye","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9475-8944","authenticated-orcid":false,"given":"Zhaonian","family":"Zou","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology, China"}]}],"member":"320","published-online":{"date-parts":[[2023,7,11]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1002\/bs.3830100205"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-8733(98)00010-0"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-8733(01)00038-7"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2953882"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3287921.3287981"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00081"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.2307\/3033543"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData50022.2020.9378076"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384358"},{"key":"e_1_3_3_13_2","article-title":"Scaling up network centrality computations\u2013A brief overview","author":"Grinten Alexander van der","year":"2020","unstructured":"Alexander van der Grinten, Eugenio Angriman, and Henning Meyerhenke. 2020. Scaling up network centrality computations\u2013A brief overview. Inf. Technol. 62, 3\u20134 (2020).","journal-title":"Inf. Technol."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-018-0605-y"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972818.11"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289026"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.2307\/2332226"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3077136.3080794"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dss.2008.06.007"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s12599-010-0127-3"},{"key":"e_1_3_3_21_2","volume-title":"Foundations of Social Research","author":"Lin Nan","year":"1976","unstructured":"Nan Lin. 1976. Foundations of Social Research. McGraw-Hill, New York."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882959"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425883"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9450.1974.tb00598.x"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0053095"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1068\/b34098"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.14778\/3450980.3450988"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.3233\/IDA-205539"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2015.01.003"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019223872X"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3392717.3392743"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735507"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2019.2915974"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.64"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646028"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.80"}],"container-title":["ACM Transactions on the Web"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3604912","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3604912","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:05Z","timestamp":1750178765000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3604912"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,11]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,11,30]]}},"alternative-id":["10.1145\/3604912"],"URL":"https:\/\/doi.org\/10.1145\/3604912","relation":{},"ISSN":["1559-1131","1559-114X"],"issn-type":[{"value":"1559-1131","type":"print"},{"value":"1559-114X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,11]]},"assertion":[{"value":"2022-05-17","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-20","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}