{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,13]],"date-time":"2024-07-13T00:07:47Z","timestamp":1720829267274},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2018,11,26]],"date-time":"2018-11-26T00:00:00Z","timestamp":1543190400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soc. Netw. Anal. Min."],"published-print":{"date-parts":[[2018,12]]},"DOI":"10.1007\/s13278-018-0542-x","type":"journal-article","created":{"date-parts":[[2018,11,26]],"date-time":"2018-11-26T12:04:22Z","timestamp":1543233862000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["An efficient heuristic for betweenness estimation and ordering"],"prefix":"10.1007","volume":"8","author":[{"given":"Rishi Ranjan","family":"Singh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. R. S.","family":"Iyengar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shubham","family":"Chaudhary","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manas","family":"Agarwal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,11,26]]},"reference":[{"key":"542_CR1","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/978-3-319-16112-9_11","volume-title":"Complex networks VI","author":"M Agarwal","year":"2015","unstructured":"Agarwal M, Singh RR, Chaudhary S, Iyengar S (2015) An efficient estimation of a node\u2019s betweenness. Complex networks VI. Springer, Berlin, pp 111\u2013121"},{"key":"542_CR2","unstructured":"Anthonisse J.M (1971) The rush in a directed graph. Stichting Mathematisch Centrum. Mathematische Besliskunde (BN 9\/71), 1\u201310"},{"key":"542_CR3","doi-asserted-by":"crossref","unstructured":"Bader DA, Kintali S, Madduri K, Mihail M (2007) Approximating betweenness centrality. In: Proceedings of the 5th International Conference on Algorithms and Models for the Web-graph, WAW\u201907, Springer, Berlin, pp 124\u2013137","DOI":"10.1007\/978-3-540-77004-6_10"},{"issue":"5439","key":"542_CR4","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"AL Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si AL, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509\u2013512","journal-title":"Science"},{"key":"542_CR5","unstructured":"Batagelj V, Mrvar A (2006) Pajek datasets. http:\/\/vlado.fmf.uni-lj.si\/pub\/networks\/data"},{"key":"542_CR6","unstructured":"Bauckhage C, Kersting K, Rastegarpanah B (2013) The Weibull as a model of shortest path distributions in random networks. In: Proc. Int. Workshop on Mining and Learning with Graphs, Chicago, IL, USA"},{"key":"542_CR7","doi-asserted-by":"crossref","unstructured":"Bergamini E, Meyerhenke H (2015) Fully-dynamic approximation of betweenness centrality. arXiv preprint arXiv:1504.07091","DOI":"10.1007\/978-3-662-48350-3_14"},{"key":"542_CR8","unstructured":"Bergamini E, Meyerhenke H, Staudt CL (2014) Approximating betweenness centrality in large evolving networks. arXiv preprint arXiv:1409.6241"},{"issue":"2","key":"542_CR9","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1111\/j.1745-493X.2009.03166.x","volume":"45","author":"SP Borgatti","year":"2009","unstructured":"Borgatti SP, Li X (2009) On social network analysis in a supply chain context*. J Supply Chain Manag 45(2):5\u201322","journal-title":"J Supply Chain Manag"},{"issue":"2","key":"542_CR10","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1080\/0022250X.2001.9990249","volume":"25","author":"U Brandes","year":"2001","unstructured":"Brandes U (2001) A faster algorithm for betweenness centrality. J Math Sociol 25(2):163\u2013177. https:\/\/doi.org\/10.1080\/0022250X.2001.9990249","journal-title":"J Math Sociol"},{"key":"542_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/b106453","volume-title":"Network analysis: methodological foundations","author":"U Brandes","year":"2005","unstructured":"Brandes U, Erlebach T (2005) Network analysis: methodological foundations, vol 3418. Springer, Berlin"},{"issue":"07","key":"542_CR12","doi-asserted-by":"publisher","first-page":"2303","DOI":"10.1142\/S0218127407018403","volume":"17","author":"U Brandes","year":"2007","unstructured":"Brandes U, Pich C (2007) Centrality estimation in large networks. Int J Bifurcation Chaos 17(07):2303\u20132318. https:\/\/doi.org\/10.1142\/S0218127407018403","journal-title":"Int J Bifurcation Chaos"},{"issue":"1","key":"542_CR13","doi-asserted-by":"publisher","first-page":"016,106","DOI":"10.1103\/PhysRevE.80.016106","volume":"80","author":"R Carvalho","year":"2009","unstructured":"Carvalho R, Buzna L, Bono F, Guti\u00e9rrez E, Just W, Arrowsmith D (2009) Robustness of trans-european gas networks. Phys Rev E 80(1):016,106","journal-title":"Phys Rev E"},{"key":"542_CR14","doi-asserted-by":"crossref","unstructured":"Chehreghani MH (2014) An efficient algorithm for approximate betweenness centrality computation. Comput J","DOI":"10.1093\/comjnl\/bxu003"},{"issue":"1","key":"542_CR15","first-page":"1","volume":"38","author":"TA Davis","year":"2011","unstructured":"Davis TA, Hu Y (2011) The university of florida sparse matrix collection. ACM Trans Math Softw (TOMS) 38(1):1","journal-title":"ACM Trans Math Softw (TOMS)"},{"issue":"7","key":"542_CR16","doi-asserted-by":"publisher","first-page":"e40,575","DOI":"10.1371\/journal.pone.0040575","volume":"7","author":"S Derrible","year":"2012","unstructured":"Derrible S (2012) Network centrality of metro systems. PloS One 7(7):e40,575","journal-title":"PloS One"},{"issue":"1","key":"542_CR17","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra EW (1959) A note on two problems in connexion with graphs. Numerische Mathematik 1(1):269\u2013271","journal-title":"Numerische Mathematik"},{"key":"542_CR18","doi-asserted-by":"publisher","first-page":"39","DOI":"10.7155\/jgaa.00081","volume":"8","author":"D Eppstein","year":"2004","unstructured":"Eppstein D, Wang J (2004) Fast approximation of centrality. J Graph Algorithms Appl 8:39\u201345","journal-title":"J Graph Algorithms Appl"},{"issue":"3","key":"542_CR19","doi-asserted-by":"publisher","first-page":"038701","DOI":"10.1103\/PhysRevLett.105.038701","volume":"105","author":"M Ercsey-Ravasz","year":"2010","unstructured":"Ercsey-Ravasz M, Toroczkai Z (2010) Centrality scaling in large networks. Phys Rev Lett 105(3):038701","journal-title":"Phys Rev Lett"},{"issue":"6","key":"542_CR20","doi-asserted-by":"publisher","first-page":"066103","DOI":"10.1103\/PhysRevE.85.066103","volume":"85","author":"M Ercsey-Ravasz","year":"2012","unstructured":"Ercsey-Ravasz M, Lichtenwalter RN, Chawla NV, Toroczkai Z (2012) Range-limited centrality measures in complex networks. Phys Rev E 85(6):066103","journal-title":"Phys Rev E"},{"key":"542_CR21","unstructured":"Erdos D, Ishakian V, Bestavros A, Terzi E (2014) A divide-and-conquer algorithm for betweenness centrality. arXiv preprint arXiv:1406.4173"},{"key":"542_CR22","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P Erdos","year":"1959","unstructured":"Erdos P, Renyi A (1959) On random graphs I. Publ Math Debrecen 6:290\u2013297","journal-title":"Publ Math Debrecen"},{"issue":"6","key":"542_CR23","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"RW Floyd","year":"1962","unstructured":"Floyd RW (1962) Algorithm 97: shortest path. Commun ACM 5(6):345","journal-title":"Commun ACM"},{"issue":"1","key":"542_CR24","doi-asserted-by":"publisher","first-page":"35","DOI":"10.2307\/3033543","volume":"40","author":"LC Freeman","year":"1977","unstructured":"Freeman LC (1977) A set of measures of centrality based on betweenness. Sociometry 40(1):35\u201341","journal-title":"Sociometry"},{"key":"542_CR25","doi-asserted-by":"publisher","unstructured":"Geisberger R, Sanders P, Schultes D (2008) Better approximation of betweenness centrality, chap. 8, pp 90\u2013100. https:\/\/doi.org\/10.1137\/1.9781611972887.9","DOI":"10.1137\/1.9781611972887.9"},{"key":"542_CR26","unstructured":"Gkorou D, Pouwelse J, Epema D, Kielmann T, van Kreveld M, Niessen W (2010) Efficient approximate computation of betweenness centrality. In: 16th annual conf. of the Advanced School for Computing and Imaging (ASCI 2010)"},{"key":"542_CR27","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/978-3-319-03536-9_14","volume-title":"Algorithms and models for the web graph","author":"K Goel","year":"2013","unstructured":"Goel K, Singh RR, Iyengar S (2013) A faster algorithm to update betweenness centrality after node alteration. Algorithms and models for the web graph. Springer, Berlin, pp 170\u2013184"},{"key":"542_CR28","doi-asserted-by":"publisher","unstructured":"Green O, McColl R, Bader D (2012) A fast algorithm for streaming betweenness centrality. In: Privacy, Security, Risk and Trust (PASSAT), 2012 International Conference on and 2012 International Confernece on Social Computing (SocialCom), pp 11\u201320. https:\/\/doi.org\/10.1109\/SocialCom-PASSAT.2012.37","DOI":"10.1109\/SocialCom-PASSAT.2012.37"},{"issue":"1","key":"542_CR29","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0378-8733(94)00248-9","volume":"17","author":"P Hage","year":"1995","unstructured":"Hage P, Harary F (1995) Eccentricity and centrality in networks. Soc Netw 17(1):57\u201363. https:\/\/doi.org\/10.1016\/0378-8733(94)00248-9","journal-title":"Soc Netw"},{"key":"542_CR30","doi-asserted-by":"crossref","DOI":"10.1515\/9781400833993","volume-title":"Social and economic networks","author":"MO Jackson","year":"2008","unstructured":"Jackson MO (2008) Social and economic networks. Princeton University Press, Princeton"},{"issue":"2","key":"542_CR31","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1155\/JBB.2005.96","volume":"2005","author":"MP Joy","year":"2005","unstructured":"Joy MP, Brock A, Ingber DE, Huang S (2005) High-betweenness proteins in the yeast protein interaction network. BioMed Res Int 2005(2):96\u2013103","journal-title":"BioMed Res Int"},{"key":"542_CR32","doi-asserted-by":"publisher","unstructured":"Kas M, Wachs M, Carley KM, Carley LR (2013) Incremental algorithm for updating betweenness centrality in dynamically growing networks. In: Proceedings of the 2013 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM \u201913, ACM, New York, pp 33\u201340. https:\/\/doi.org\/10.1145\/2492517.2492533","DOI":"10.1145\/2492517.2492533"},{"key":"542_CR33","unstructured":"Kintali S (2008) Betweenness centrality: algorithms and lower bounds. arXiv preprint arXiv:0809.1906"},{"key":"542_CR34","volume-title":"The art of computer programming: sorting and searching","author":"DE Knuth","year":"1998","unstructured":"Knuth DE (1998) The art of computer programming: sorting and searching, vol 3. Pearson Education, London"},{"key":"542_CR35","unstructured":"Lee C-Y (2006) Correlations among centrality measures in complex networks. arXiv preprint arXiv:physics\/0605220"},{"issue":"8","key":"542_CR36","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1016\/j.ipl.2014.03.006","volume":"114","author":"E Merrer Le","year":"2014","unstructured":"Le Merrer E, Le Scouarnec N, Tr\u00e9dan G (2014) Heuristical top-k: fast estimation of centralities in complex networks. Inf Process Lett 114(8):432\u2013436","journal-title":"Inf Process Lett"},{"key":"542_CR37","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1016\/j.ins.2015.07.053","volume":"326","author":"MJ Lee","year":"2016","unstructured":"Lee MJ, Choi S, Chung CW (2016) Efficient algorithms for updating betweenness centrality in fully dynamic graphs. Inf Sci 326:278\u2013296","journal-title":"Inf Sci"},{"key":"542_CR38","doi-asserted-by":"publisher","unstructured":"Lee M.J, Lee J, Park JY, Choi RH, Chung CW (2012) Qube: a quick algorithm for updating betweenness centrality. In: Proceedings of the 21st International Conference on World Wide Web, WWW \u201912, ACM, New York, pp 351\u2013360. https:\/\/doi.org\/10.1145\/2187836.2187884","DOI":"10.1145\/2187836.2187884"},{"key":"542_CR39","unstructured":"Leskovec J, Krevl A (2014) SNAP datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data"},{"key":"542_CR40","doi-asserted-by":"crossref","unstructured":"Lim YS, Menasche D.S, Ribeiro B, Towsley D, Basu P (2011) Online estimating the k central nodes of a network. IEEE Network Science Workshop, pp 118\u2013122. http:\/\/doi.ieeecomputersociety.org\/10.1109\/NSW.2011.6004633","DOI":"10.1109\/NSW.2011.6004633"},{"key":"542_CR41","doi-asserted-by":"crossref","unstructured":"Lu TC, Zhang Y, Allen DL, Salman MA (2011) Design for fault analysis using multi-partite, multi-attribute betweenness centrality measures","DOI":"10.36001\/phmconf.2011.v3i1.2036"},{"issue":"5","key":"542_CR42","doi-asserted-by":"publisher","first-page":"1477","DOI":"10.1080\/00207543.2012.695878","volume":"51","author":"KJ Mizgier","year":"2013","unstructured":"Mizgier KJ, J\u00fcttner MP, Wagner SM (2013) Bottleneck identification in supply chain networks. Int J Prod Res 51(5):1477\u20131490","journal-title":"Int J Prod Res"},{"key":"542_CR43","unstructured":"Narayanan S (2005) The betweenness centrality of biological networks. Ph.D. thesis, Virginia Polytechnic Institute and State University"},{"key":"542_CR44","unstructured":"Nasre M, Pontecorvi M, Ramachandran V (2013) Betweenness centality\u2013incremental and faster. arXiv preprint arXiv:1311.2147"},{"key":"542_CR45","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001","volume-title":"Networks: an introduction","author":"M Newman","year":"2010","unstructured":"Newman M (2010) Networks: an introduction. Oxford University Press Inc, New York"},{"key":"542_CR46","doi-asserted-by":"crossref","unstructured":"Riondato M, Kornaropoulos EM (2014) Fast approximation of betweenness centrality through sampling. In: Proceedings of the 7th ACM international conference on Web search and data mining, pp 413\u2013422","DOI":"10.1145\/2556195.2556224"},{"key":"542_CR47","doi-asserted-by":"crossref","unstructured":"Sariy\u00fcce AE, Saule E, Kaya K, \u00c7ataly\u00fcrek \u00dc.V (2013) Shattering and compressing networks for betweenness centrality. In: SIAM Data Mining Conference (SDM)","DOI":"10.1137\/1.9781611972832.76"},{"key":"542_CR48","doi-asserted-by":"crossref","unstructured":"Tang J, Zhang J, Yao L, Li J, Zhang L, Su Z (2008) Arnetminer: extraction and mining of academic social networks. In: Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp 990\u2013998","DOI":"10.1145\/1401890.1402008"},{"issue":"6","key":"542_CR49","first-page":"10","volume":"24","author":"A Tizghadam","year":"2010","unstructured":"Tizghadam A, Leon-Garcia A (2010) Betweenness centrality and resistance distance in communication networks. Network 24(6):10\u201316","journal-title":"Network"},{"issue":"1","key":"542_CR50","first-page":"16","volume":"28","author":"TW Valente","year":"2008","unstructured":"Valente TW, Coronges K, Lakon C, Costenbader E (2008) How correlated are network centrality measures? Connections (Toronto, Ont.) 28(1):16","journal-title":"Connections (Toronto, Ont.)"},{"key":"542_CR51","unstructured":"Van Der Hofstad R (2009) Random graphs and complex networks. http:\/\/www.win.tue.nl\/rhofstad\/NotesRGCN.pdf"},{"key":"542_CR52","doi-asserted-by":"crossref","unstructured":"Wang X (2011) Deciding on the type of the degree distribution of a graph (network) from traceroute-like measurements","DOI":"10.5121\/ijcnc.2012.4311"},{"issue":"1","key":"542_CR53","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/321105.321107","volume":"9","author":"S Warshall","year":"1962","unstructured":"Warshall S (1962) A theorem on boolean matrices. J ACM (JACM) 9(1):11\u201312","journal-title":"J ACM (JACM)"},{"key":"542_CR54","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0038202","volume-title":"Smallest enclosing disks (balls and ellipsoids)","author":"E Welzl","year":"1991","unstructured":"Welzl E (1991) Smallest enclosing disks (balls and ellipsoids). Springer, Berlin"}],"container-title":["Social Network Analysis and Mining"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s13278-018-0542-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-018-0542-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-018-0542-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T19:24:34Z","timestamp":1720812274000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s13278-018-0542-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,26]]},"references-count":54,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["542"],"URL":"https:\/\/doi.org\/10.1007\/s13278-018-0542-x","relation":{},"ISSN":["1869-5450","1869-5469"],"issn-type":[{"value":"1869-5450","type":"print"},{"value":"1869-5469","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,26]]},"assertion":[{"value":"10 January 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 September 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 October 2018","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 November 2018","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"66"}}