中间性中心性
中心性
计算机科学
算法
空格(标点符号)
航程(航空)
理论计算机科学
数学
组合数学
操作系统
复合材料
材料科学
标识
DOI:10.1080/0022250x.2001.9990249
摘要
Motivated by the fast‐growing need to compute centrality indices on large, yet very sparse, networks, new algorithms for betweenness are introduced in this paper. They require O(n + m) space and run in O(nm) and O(nm + n2 log n) time on unweighted and weighted networks, respectively, where m is the number of links. Experimental evidence is provided that this substantially increases the range of networks for which centrality analysis is feasible. The betweenness centrality index is essential in the analysis of social networks, but costly to compute. Currently, the fastest known algorithms require ?(n 3) time and ?(n 2) space, where n is the number of actors in the network.
科研通智能强力驱动
Strongly Powered by AbleSci AI