{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:56:19Z","timestamp":1772121379799,"version":"3.50.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,10]]},"abstract":"<jats:p>\n            Measuring the relative importance of each vertex in a network is one of the most fundamental building blocks in network analysis. Among several importance measures,\n            <jats:italic>betweenness centrality<\/jats:italic>\n            , in particular, plays key roles in many real applications. Considerable effort has been made for developing algorithms for static settings. However, real networks today are highly dynamic and are evolving rapidly, and scalable dynamic methods that can instantly reflect graph changes into centrality values are required.\n          <\/jats:p>\n          <jats:p>\n            In this paper, we present the first fully dynamic method for managing betweenness centrality of all vertices in a large dynamic network. Its main data structure is the weighted hyperedge representation of shortest paths called\n            <jats:italic>hypergraph sketch.<\/jats:italic>\n            We carefully design dynamic update procedure with theoretical accuracy guarantee. To accelerate updates, we further propose two auxiliary data structures called\n            <jats:italic>two-ball index<\/jats:italic>\n            and\n            <jats:italic>special-purpose reachability index.<\/jats:italic>\n            Experimental results using real networks demonstrate its high scalability and efficiency. In particular, it can reflect a graph change in less than a millisecond on average for a large-scale web graph with 106M vertices and 3.7B edges, which is several orders of magnitude larger than the limits of previous dynamic methods.\n          <\/jats:p>","DOI":"10.14778\/2850578.2850580","type":"journal-article","created":{"date-parts":[[2016,2,1]],"date-time":"2016-02-01T14:10:31Z","timestamp":1454335831000},"page":"48-59","source":"Crossref","is-referenced-by-count":52,"title":["Fully dynamic betweenness centrality maintenance on massive networks"],"prefix":"10.14778","volume":"9","author":[{"given":"Takanori","family":"Hayashi","sequence":"first","affiliation":[{"name":"The University of Tokyo, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takuya","family":"Akiba","sequence":"additional","affiliation":[{"name":"National Institute of Informatics, CIT STAIR Lab &amp; JST PRESTO"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuichi","family":"Yoshida","sequence":"additional","affiliation":[{"name":"National Institute of Informatics, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2568007"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1777879.1777889"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2012.79"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03459"},{"key":"e_1_2_1_6_1","volume-title":"The European Physical Journal B - Condensed Matter and Complex Systems, 38(2):163--168","author":"Barth\u00e9lemy M.","year":"2004"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2789813.2789825"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218127407018403"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(00)00083-9"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/971617.971643"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti167"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974010.49"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.2307\/3033543"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1048"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2791204.2791213"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SocialCom-PASSAT.2012.37"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1038\/35075138"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492517.2492533"},{"key":"e_1_2_1_23_1","volume-title":"Transactions on Knowledge and Data Engineering","author":"Kourtellis N.","year":"2014"},{"issue":"3","key":"e_1_2_1_24_1","first-page":"43","article-title":"Mapping networks of terrorist cells","volume":"24","author":"Krebs V. E.","year":"2002","journal-title":"Connections"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187884"},{"key":"e_1_2_1_26_1","unstructured":"J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection.  J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection."},{"issue":"1","key":"e_1_2_1_27_1","first-page":"60","article-title":"The Small World Problem","volume":"2","author":"Milgram S.","year":"1967","journal-title":"Psychology today"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001","volume-title":"Networks: An Introduction","author":"Newman M. E. J.","year":"2010"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.026113"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SocialCom-PASSAT.2012.66"},{"key":"e_1_2_1_31_1","volume-title":"On the Computational Complexity of Incremental Algorithms","author":"Ramalingam G.","year":"1991"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2556224"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063834"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_2_1_35_1","volume-title":"DAGGER: A Scalable Index for Reachability Queries in Large Dynamic Graphs. CoRR, abs\/1301.0:11","author":"Yildirim H.","year":"2013"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623626"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2670030"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612181"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2850578.2850580","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:17:08Z","timestamp":1672222628000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2850578.2850580"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,10]]}},"alternative-id":["10.14778\/2850578.2850580"],"URL":"https:\/\/doi.org\/10.14778\/2850578.2850580","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,10]]}}}