{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T12:40:52Z","timestamp":1767962452028,"version":"3.49.0"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,11,25]],"date-time":"2014-11-25T00:00:00Z","timestamp":1416873600000},"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":[[2014,12]]},"DOI":"10.1007\/s13278-014-0235-z","type":"journal-article","created":{"date-parts":[[2014,12,1]],"date-time":"2014-12-01T20:25:00Z","timestamp":1417465500000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["An incremental algorithm for updating betweenness centrality and k-betweenness centrality and its performance on realistic dynamic social network data"],"prefix":"10.1007","volume":"4","author":[{"given":"Miray","family":"Kas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kathleen M.","family":"Carley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L. Richard","family":"Carley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,11,25]]},"reference":[{"key":"235_CR1","doi-asserted-by":"crossref","unstructured":"Bader D, Madduri K (2006) Parallel algorithms for evaluating centrality indices in real-world networks. International conference on parallel processing (ICPP). IEEE, pp 539\u2013550","DOI":"10.1109\/ICPP.2006.57"},{"issue":"5439","key":"235_CR2","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A Barabasi","year":"1999","unstructured":"Barabasi A, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509\u2013512","journal-title":"Science"},{"key":"235_CR3","unstructured":"Batagelj V, Kej\u017ear N, Korenjak-\u010cerne S, Zaver\u0161nik M (2006). Analyzing the structure of US patents network. Springer, Berlin"},{"key":"235_CR4","unstructured":"Berman AM (1992) Lower and upper bounds for incremental algorithms. Ph.D. Dissertation, The State University of New Jersey at Rutgers, Computer Science, New Brunswick"},{"issue":"4","key":"235_CR5","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1016\/j.socnet.2005.11.005","volume":"28","author":"SP Borgatti","year":"2006","unstructured":"Borgatti SP, Everett MG (2006) A graph-theoretic perspective on centrality. Soc Netw 28(4):466\u2013484","journal-title":"Soc Netw"},{"issue":"2","key":"235_CR7","doi-asserted-by":"crossref","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","journal-title":"J Math Sociol"},{"issue":"2","key":"235_CR8","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/j.socnet.2007.11.001","volume":"30","author":"U Brandes","year":"2008","unstructured":"Brandes U (2008) On variants of shortest-path betweenness centrality and their generic computation. Soc Netw 30(2):136\u2013145","journal-title":"Soc Netw"},{"issue":"6","key":"235_CR9","doi-asserted-by":"crossref","first-page":"968","DOI":"10.1145\/1039488.1039492","volume":"51","author":"C Demetrescu","year":"2004","unstructured":"Demetrescu C, Italiano GF (2004) A new approach to dynamic all pairs shortest paths. J ACM (JACM) 51(6):968\u2013992","journal-title":"J ACM (JACM)"},{"issue":"4","key":"235_CR10","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1145\/1198513.1198519","volume":"2","author":"C Demetrescu","year":"2006","unstructured":"Demetrescu C, Italiano GF (2006) Experimental analysis of dynamic all pairs shortest path algorithms. ACM Trans Algorithms (TALG) 2(4):578\u2013601","journal-title":"ACM Trans Algorithms (TALG)"},{"issue":"1","key":"235_CR11","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E Dijkstra","year":"1959","unstructured":"Dijkstra E (1959) A note on two problems in connexion with graphs. Numer Math 1(1):269\u2013271","journal-title":"Numer Math"},{"key":"235_CR12","first-page":"371","volume":"49","author":"S Even","year":"1985","unstructured":"Even S, Gazit H (1985) Updating distances in dynamic graphs. Methods Oper Res 49:371\u2013387","journal-title":"Methods Oper Res"},{"issue":"6","key":"235_CR13","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"R Floyd","year":"1962","unstructured":"Floyd R (1962) Algorithm 97: shortest path. Commun ACM 5(6):345","journal-title":"Commun ACM"},{"key":"235_CR14","unstructured":"Fredman ML, Tarjan RE (1984). Fibonacci heaps and their uses in improved network optimization algorithms. 25th annual symposium on foundations of computer science. IEEE, pp 338\u2013346"},{"issue":"1","key":"235_CR15","doi-asserted-by":"crossref","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":"235_CR16","unstructured":"GraphStream Team (2010) GraphStream. Retrieved 3 February 2012. http:\/\/graphstream-project.org\/"},{"key":"235_CR17","doi-asserted-by":"crossref","unstructured":"Green O, McColl R, Bader DA (2012). A fast algorithm for streaming betweenness centrality. International Conference on Privacy, Security, Risk and Trust (PASSAT) and International Conference on Social Computing (SocialCom). IEEE, Amsterdam, pp 11\u201320","DOI":"10.1109\/SocialCom-PASSAT.2012.37"},{"issue":"5","key":"235_CR18","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/1629607.1629610","volume":"39","author":"FE Gringoli","year":"2009","unstructured":"Gringoli FE (2009) GT: picking up the truth from the ground for internet traffic. Comput Commun Rev 39(5):13\u201318","journal-title":"Comput Commun Rev"},{"key":"235_CR19","unstructured":"Habiba H, Tantipathananandh C, Berger-Wolf T (2007) Betweenness centrality measure in dynamic networks. University of Illinois at Chicago, Department of Computer Science. DIMACS, Chicago"},{"issue":"1","key":"235_CR20","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/j.jtbi.2010.11.033","volume":"271","author":"LE Isella","year":"2011","unstructured":"Isella LE (2011) What\u2019s in a crowd? Analysis of face-to-face behavioral networks. J Theor Biol 271(1):166\u2013180","journal-title":"J Theor Biol"},{"key":"235_CR21","doi-asserted-by":"crossref","unstructured":"Jiang K, Ediger D, Bader DA (2009) Generalizing k-betweenness centrality using short paths and a parallel multithreaded implementation. International conference on parallel processing (ICPP), Vienna, pp 542\u2013549","DOI":"10.1109\/ICPP.2009.76"},{"key":"235_CR22","unstructured":"Kas M (2013b) Incremental centrality algorithms for dynamic network analysis. Ph.D. Dissertation, Carnegie Mellon University, ECE, Pittsburgh"},{"key":"235_CR23","unstructured":"Kas M, Wachs M, Carley L, Carley K (2012a). Incremental centrality computations for dynamic social networks. XXXII international sunbelt social network conference (Sunbelt 2012). INSNA, Redondo Beach"},{"key":"235_CR24","doi-asserted-by":"crossref","unstructured":"Kas M, Carley KM, Carley LR (2012b) Trends in science networks: understanding structures and statistics of scientific networks. Social network analysis and mining (SNAM)","DOI":"10.1007\/s13278-011-0044-6"},{"key":"235_CR25","doi-asserted-by":"crossref","unstructured":"Kas M, Wachs M, Carley K, Carley L (2013) incremental algorithm for updating betweenness centrality in dynamically growing networks. The 2013 IEEE\/ACM international conference on advances in social networks analysis and mining (ASONAM). IEEE, Niagara Falls","DOI":"10.1145\/2492517.2492533"},{"issue":"026107","key":"235_CR26","first-page":"1","volume":"85","author":"H Kim","year":"2012","unstructured":"Kim H, Anderson R (2012) Temporal node centrality in complex networks. Phys Rev E 85(026107):1\u20138","journal-title":"Phys Rev E"},{"key":"235_CR27","doi-asserted-by":"crossref","unstructured":"King, V. (1999). Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. 40th annual symposium on foundations of computer science. IEEE, pp 81\u201389","DOI":"10.1109\/SFFCS.1999.814580"},{"issue":"3","key":"235_CR28","doi-asserted-by":"crossref","first-page":"899","DOI":"10.1007\/s13278-012-0076-6","volume":"4","author":"N Kourtellis","year":"2013","unstructured":"Kourtellis N, Alahakoon T, Simha R, Iamnitchi A, Tripathi R (2013) Identifying high betweenness centrality nodes in large social networks. Soc Netw Anal Min (SNAM) 4(3):899\u2013914","journal-title":"Soc Netw Anal Min (SNAM)"},{"key":"235_CR29","doi-asserted-by":"crossref","unstructured":"Lee MJ, Lee J, Park JY, Choi R, Chung CW (2012a) QUBE: a Quick algorithm for updating BEtweenness centrality. WWW, ACM, pp 351\u2013360","DOI":"10.1145\/2187836.2187884"},{"key":"235_CR30","doi-asserted-by":"crossref","unstructured":"Lee MJ, Lee J, Park JY, Choi R, Chung CW (2012b) QUBE: a quick algorithm for updating BEtweenness centrality. In: Proceedings of the 21st international conference on World Wide Web (WWW). ACM, Lyon, pp 351\u2013360","DOI":"10.1145\/2187836.2187884"},{"key":"235_CR31","doi-asserted-by":"crossref","unstructured":"Lerman K, Ghosh R, Kang JH (2010) Centrality metric for dynamic networks. 8th workshop on mining and learning with graphs (MLG). ACM, pp 70\u201377","DOI":"10.1145\/1830252.1830262"},{"issue":"2","key":"235_CR32","first-page":"1","volume":"1","author":"J Leskovec","year":"2007","unstructured":"Leskovec J, Kleinberg J, Faloutsos C (2007) Graph evolution: densification and shrinking diameters. ACM Trans KDD 1(2):1\u201341","journal-title":"ACM Trans KDD"},{"key":"235_CR33","doi-asserted-by":"crossref","unstructured":"Leskovec J, Huttenlocher DP, Kleinberg JM (2010) Governance in social media: a case study of the Wikipedia promotion process. The international AAAI conference on weblogs and social media (ICWSM)","DOI":"10.1145\/1753326.1753532"},{"issue":"4","key":"235_CR34","doi-asserted-by":"crossref","first-page":"2683","DOI":"10.1016\/j.neuroimage.2010.11.007","volume":"54","author":"W Liao","year":"2011","unstructured":"Liao W, Ding J, Marinazzo D, Xu Q, Wang Z, Yuan C et al (2011) Small-world directed networks in the human brain: multivariate Granger causality analysis of resting-state fMRI. Neuroimage 54(4):2683\u20132694","journal-title":"Neuroimage"},{"key":"235_CR35","unstructured":"Norlen K, Lucas G, Gebbie M, Chuang J (2002) EVA: extraction, visualization and analysis of the telecommunications and media ownership network. International telecommunications society 14th biennial conference"},{"issue":"18","key":"235_CR36","doi-asserted-by":"crossref","first-page":"7332","DOI":"10.1073\/pnas.0610245104","volume":"104","author":"JP Onnela","year":"2007","unstructured":"Onnela JP, Saram\u00e4ki J, Hyv\u00f6nen J, Szab\u00f3 G, Lazer D, Kaski K et al (2007) Structure and tie strengths in mobile communication networks. Proc Natl Acad Sci 104(18):7332\u20137336","journal-title":"Proc Natl Acad Sci"},{"issue":"2","key":"235_CR37","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/j.socnet.2009.02.002","volume":"31","author":"T Opsahl","year":"2009","unstructured":"Opsahl T, Panzarasa P (2009) Clustering in weighted networks. Soc Netw 31(2):155\u2013163","journal-title":"Soc Netw"},{"key":"235_CR38","doi-asserted-by":"crossref","unstructured":"Pfeffer J, Carley KM (2012) k-Centralities: local approximations of global measures based on shortest paths. WWW. ACM, pp 1043\u20131050","DOI":"10.1145\/2187980.2188239"},{"key":"235_CR39","doi-asserted-by":"crossref","unstructured":"Puzis R, Zilberman P, Elovici Y, Dolev S, Brandes U (2012) Heuristics for speeding up betweenness centrality computation. Social computing and on privacy, security, risk and trust. IEEE Computer Society, pp 302\u2013311","DOI":"10.1109\/SocialCom-PASSAT.2012.66"},{"key":"235_CR40","unstructured":"Ramalingam G, Reps T (1991a) On the computational complexity of incremental algorithms. Technical report, University of Wisconsin at Madison"},{"key":"235_CR41","unstructured":"Ramalingam G, Reps T (1991b) On the computational complexity of incremental algorithms. Technical Report, University of Wisconsin at Madison, Computer Science, Madison"},{"key":"235_CR42","unstructured":"Ramezanpour A, Karimipour V (2008) Simple models of small world networks with directed links. Sharif University of Technology, Department of Physics, Tehran"},{"key":"235_CR43","unstructured":"Renyi A, Erdos P (1959). On random graphs. Publicationes Mathematicae, 6"},{"key":"235_CR44","doi-asserted-by":"crossref","unstructured":"Tang J, Musolesi M, Mascolo C, Latora V, Nicosia V (2010) Analysing information flows and key mediators through temporal centrality metrics. 3rd workshop on social network systems (SNS). April","DOI":"10.1145\/1852658.1852661"},{"key":"235_CR45","doi-asserted-by":"crossref","unstructured":"Watts D, Strogatz S (1998) Collective dynamics of \u2018small-world\u2019 networks. Nature 393:440\u2013442","DOI":"10.1038\/30918"},{"key":"235_CR46","first-page":"616","volume":"17","author":"J Xu","year":"2008","unstructured":"Xu J (2008) Markov chain small world model with asymmetric transition probabilities. Electron J Linear Algebra 17:616\u2013636","journal-title":"Electron J Linear Algebra"},{"key":"235_CR47","doi-asserted-by":"crossref","unstructured":"Yang J, Leskovec J (2011). Patterns of temporal variation in online media. International conference on web search and data minig (WSDM). ACM","DOI":"10.1145\/1935826.1935863"},{"key":"235_CR48","doi-asserted-by":"crossref","unstructured":"Zhu C, Xiong S, Tian Y, Li N, Jiang K (2004). Scaling of directed dynamical small-world networks with random responses. Phys Rev Lett 92 218702(24):1\u20134","DOI":"10.1103\/PhysRevLett.92.218702"}],"container-title":["Social Network Analysis and Mining"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-014-0235-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s13278-014-0235-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-014-0235-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,18]],"date-time":"2019-08-18T01:14:11Z","timestamp":1566090851000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s13278-014-0235-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,25]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,12]]}},"alternative-id":["235"],"URL":"https:\/\/doi.org\/10.1007\/s13278-014-0235-z","relation":{},"ISSN":["1869-5450","1869-5469"],"issn-type":[{"value":"1869-5450","type":"print"},{"value":"1869-5469","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11,25]]},"article-number":"235"}}