{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T16:21:22Z","timestamp":1780590082663,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":31,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,11,3]],"date-time":"2019-11-03T00:00:00Z","timestamp":1572739200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANR","award":["IDOLE"],"award-info":[{"award-number":["IDOLE"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,11,3]]},"DOI":"10.1145\/3357384.3358064","type":"proceedings-article","created":{"date-parts":[[2019,11,4]],"date-time":"2019-11-04T14:11:35Z","timestamp":1572876695000},"page":"1231-1240","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Adaptive Algorithms for Estimating Betweenness and\n            <i>k<\/i>\n            -path Centralities"],"prefix":"10.1145","author":[{"given":"Mostafa","family":"Haghir Chehreghani","sequence":"first","affiliation":[{"name":"Amirkabir University of Technology (Tehran Polytechnic) &amp; T\u00e9l\u00e9com-Paris, Institut Polytechnique de Paris (IP-Paris), Tehran, Iran"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Albert","family":"Bifet","sequence":"additional","affiliation":[{"name":"T\u00e9l\u00e9com-Paris, IP-Paris, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Talel","family":"Abdessalem","sequence":"additional","affiliation":[{"name":"T\u00e9l\u00e9com-Paris, IP-Paris, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,11,3]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Shubham Chaudhary, and Sudarshan Iyengar.","author":"Agarwal Manas","year":"2014","unstructured":"Manas Agarwal , Rishi Ranjan Singh , Shubham Chaudhary, and Sudarshan Iyengar. 2014 . Betweenness ordering problem: an efficient non-uniform sampling technique for large graphs. CoRR , Vol. abs\/ 1409 .6470 (2014). http:\/\/arxiv.org\/abs\/1409.6470 Manas Agarwal, Rishi Ranjan Singh, Shubham Chaudhary, and Sudarshan Iyengar. 2014. Betweenness ordering problem: an efficient non-uniform sampling technique for large graphs. CoRR , Vol. abs\/1409.6470 (2014). http:\/\/arxiv.org\/abs\/1409.6470"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-16112-9_11"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989656.1989657"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1038\/43601"},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of 5th International Conference on Algorithms and Models for the Web-Graph. 124--137","author":"Bader D. A.","unstructured":"D. A. Bader , S. Kintali , K. Madduri , and M. Mihail . 2007. Approximating betweenness centrality . In Proceedings of 5th International Conference on Algorithms and Models for the Web-Graph. 124--137 . D. A. Bader, S. Kintali, K. Madduri, and M. Mihail. 2007. Approximating betweenness centrality. In Proceedings of 5th International Conference on Algorithms and Models for the Web-Graph. 124--137."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3166071"},{"key":"e_1_3_2_1_7_1","volume-title":"24th Annual European Symposium on Algorithms, ESA 2016","author":"Borassi Michele","year":"2016","unstructured":"Michele Borassi and Emanuele Natale . 2016 . KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation . In 24th Annual European Symposium on Algorithms, ESA 2016 , August 22 --24 , 2016, Aarhus, Denmark . 20:1--20:18. Michele Borassi and Emanuele Natale. 2016. KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation. In 24th Annual European Symposium on Algorithms, ESA 2016, August 22--24, 2016, Aarhus, Denmark . 20:1--20:18."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_3_2_1_9_1","first-page":"303","article-title":"Centrality estimation in large networks","volume":"17","author":"Brandes U.","year":"2007","unstructured":"U. Brandes and C. Pich . 2007 . Centrality estimation in large networks . Intl. Journal of Bifurcation and Chaos , Vol. 17 , 7 (2007), 303 -- 318 . U. Brandes and C. Pich. 2007. Centrality estimation in large networks. Intl. Journal of Bifurcation and Chaos , Vol. 17, 7 (2007), 303--318.","journal-title":"Journal of Bifurcation and Chaos"},{"key":"e_1_3_2_1_10_1","volume-title":"Kamer Kaya, Ahmet Erdem Sariy\u00fc ce, and Erik Saule.","author":"V.","year":"2013","unstructured":"\u00dc mit V. cC ataly\u00fc rek , Kamer Kaya, Ahmet Erdem Sariy\u00fc ce, and Erik Saule. 2013 . Shattering and Compressing Networks for Betweenness Centrality. In Proceedings of the 13th SIAM International Conference on Data Mining. 686--694. \u00dc mit V. cC ataly\u00fc rek, Kamer Kaya, Ahmet Erdem Sariy\u00fc ce, and Erik Saule. 2013. Shattering and Compressing Networks for Betweenness Centrality. In Proceedings of the 13th SIAM International Conference on Data Mining. 686--694."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2556263"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxu003"},{"key":"e_1_3_2_1_13_1","volume-title":"EDBT 2019","author":"Chehreghani Mostafa Haghir","year":"2019","unstructured":"Mostafa Haghir Chehreghani , Talel Abdessalem , and Albert Bifet . 2019 . Metropolis-Hastings Algorithms for Estimating Betweenness Centrality. In Advances in Database Technology - 22nd International Conference on Extending Database Technology , EDBT 2019 , Lisbon, Portugal, March 26--29 , 2019 , , Melanie Herschel, Helena Galhardas, Berthold Reinwald, Irini Fundulaki, Carsten Binnig, and Zoi Kaoudi (Eds.). OpenProceedings.org, 686--689. https:\/\/doi.org\/10.5441\/002\/edbt.2019.87 10.5441\/002 Mostafa Haghir Chehreghani, Talel Abdessalem, and Albert Bifet. 2019. Metropolis-Hastings Algorithms for Estimating Betweenness Centrality. In Advances in Database Technology - 22nd International Conference on Extending Database Technology, EDBT 2019, Lisbon, Portugal, March 26--29, 2019 , , Melanie Herschel, Helena Galhardas, Berthold Reinwald, Irini Fundulaki, Carsten Binnig, and Zoi Kaoudi (Eds.). OpenProceedings.org, 686--689. https:\/\/doi.org\/10.5441\/002\/edbt.2019.87"},{"key":"e_1_3_2_1_14_1","volume-title":"22nd Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD","author":"Chehreghani Mostafa Haghir","unstructured":"Mostafa Haghir Chehreghani , Albert Bifet , and Talel Abdessalem . 2018a. Efficient Exact and Approximate Algorithms for Computing Betweenness Centrality in Directed Graphs . In 22nd Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD . http:\/\/arxiv.org\/abs\/1708.08739 Mostafa Haghir Chehreghani, Albert Bifet, and Talel Abdessalem. 2018a. Efficient Exact and Approximate Algorithms for Computing Betweenness Centrality in Directed Graphs. In 22nd Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD. http:\/\/arxiv.org\/abs\/1708.08739"},{"key":"e_1_3_2_1_15_1","volume-title":"An In-depth Comparison of Group Betweenness Centrality Estimation Algorithms. In IEEE International Conference on Big Data, Big Data 2018","author":"Chehreghani Mostafa Haghir","year":"2018","unstructured":"Mostafa Haghir Chehreghani , Albert Bifet , and Talel Abdessalem . 2018 b. An In-depth Comparison of Group Betweenness Centrality Estimation Algorithms. In IEEE International Conference on Big Data, Big Data 2018 , Seattle, WA, USA, December 10--13 , 2018, Naoki Abe, Huan Liu, Calton Pu, Xiaohua Hu, Nesreen Ahmed, Mu Qiao, Yang Song, Donald Kossmann, Bing Liu, Kisung Lee, Jiliang Tang, Jingrui He, and Jeffrey S. Saltz (Eds.). IEEE, 2104--2113. https:\/\/doi.org\/10.1109\/BigData.2018.8622133 10.1109\/BigData.2018.8622133 Mostafa Haghir Chehreghani, Albert Bifet, and Talel Abdessalem. 2018b. An In-depth Comparison of Group Betweenness Centrality Estimation Algorithms. In IEEE International Conference on Big Data, Big Data 2018, Seattle, WA, USA, December 10--13, 2018, Naoki Abe, Huan Liu, Calton Pu, Xiaohua Hu, Nesreen Ahmed, Mu Qiao, Yang Song, Donald Kossmann, Bing Liu, Kisung Lee, Jiliang Tang, Jingrui He, and Jeffrey S. Saltz (Eds.). IEEE, 2104--2113. https:\/\/doi.org\/10.1109\/BigData.2018.8622133"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2006.10129115"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1999.9990219"},{"key":"e_1_3_2_1_18_1","volume-title":"Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments. 90--100","author":"Geisberger R.","unstructured":"R. Geisberger , P. Sanders , and D. Schultes . 2008. Better approximation of betweenness centrality . In Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments. 90--100 . R. Geisberger, P. Sanders, and D. Schultes. 2008. Better approximation of betweenness centrality. In Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments. 90--100."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_3_2_1_21_1","volume-title":"Phillips","author":"L\u00f6ffler Maarten","year":"2009","unstructured":"Maarten L\u00f6ffler and Jeff M . Phillips . 2009 . Shape Fitting on Point Sets with Probability Distributions . Berlin, Heidelberg , 313--324. Maarten L\u00f6ffler and Jeff M. Phillips. 2009. Shape Fitting on Point Sets with Probability Distributions . Berlin, Heidelberg, 313--324."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939869"},{"key":"e_1_3_2_1_23_1","volume-title":"The Impacts of Airport Centrality in the EU Network and Inter- Airport Competition on Airport Efficiency. MPRA Paper 17673","author":"Malighetti G","unstructured":"G Malighetti , G Martini , S Paleari , and R Redondi . 2009. The Impacts of Airport Centrality in the EU Network and Inter- Airport Competition on Airport Efficiency. MPRA Paper 17673 . University Library of Munich , Germany. https:\/\/ideas.repec.org\/p\/pra\/mprapa\/17673.html G Malighetti, G Martini, S Paleari, and R Redondi. 2009. The Impacts of Airport Centrality in the EU Network and Inter- Airport Competition on Airport Efficiency. MPRA Paper 17673. University Library of Munich, Germany. https:\/\/ideas.repec.org\/p\/pra\/mprapa\/17673.html"},{"key":"e_1_3_2_1_24_1","first-page":"127","article-title":"Bi-directional Search","volume":"6","author":"Pohl Ira","year":"1971","unstructured":"Ira Pohl . 1971 . Bi-directional Search . Machine Intelligence , Vol. 6 (1971), 127 -- 140 . Ira Pohl. 1971. Bi-directional Search. Machine Intelligence , Vol. 6 (1971), 127--140.","journal-title":"Machine Intelligence"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-015-0423-0"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939770"},{"key":"e_1_3_2_1_27_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 , New York, NY, USA . Shai Shalev-Shwartz and Shai Ben-David. 2014. Understanding Machine Learning: From Theory to Algorithms .Cambridge University Press, New York, NY, USA."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijcip.2015.05.003"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0027418"},{"key":"e_1_3_2_1_30_1","volume-title":"Defining and Evaluating Network Communities Based on Ground-Truth. In 12th IEEE International Conference on Data Mining","author":"Yang Jaewon","year":"2012","unstructured":"Jaewon Yang and Jure Leskovec . 2012 . Defining and Evaluating Network Communities Based on Ground-Truth. In 12th IEEE International Conference on Data Mining , Brussels, Belgium, December 10--13 , 2012 . 745--754. Jaewon Yang and Jure Leskovec. 2012. Defining and Evaluating Network Communities Based on Ground-Truth. In 12th IEEE International Conference on Data Mining, Brussels, Belgium, December 10--13, 2012 . 745--754."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623626"}],"event":{"name":"CIKM '19: The 28th ACM International Conference on Information and Knowledge Management","location":"Beijing China","acronym":"CIKM '19","sponsor":["SIGWEB ACM Special Interest Group on Hypertext, Hypermedia, and Web","SIGIR ACM Special Interest Group on Information Retrieval"]},"container-title":["Proceedings of the 28th ACM International Conference on Information and Knowledge Management"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357384.3358064","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357384.3358064","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:18Z","timestamp":1750203858000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357384.3358064"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,3]]},"references-count":31,"alternative-id":["10.1145\/3357384.3358064","10.1145\/3357384"],"URL":"https:\/\/doi.org\/10.1145\/3357384.3358064","relation":{},"subject":[],"published":{"date-parts":[[2019,11,3]]},"assertion":[{"value":"2019-11-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}