A faster algorithm for betweenness centrality
A faster algorithm for betweenness centrality
复制标题
DOI：
10.1080/0022250x.2001.9990249
复制
发表时间：
2001-01-01
影响因子：
1
通讯作者：
Brandes, U
中科院分区：
文献类型：
--
作者：
Brandes, U
中间度中心度指数在社交网络分析中是必不可少的，但计算成本很高。目前已知的最快算法需要圆减(n(3))时间和圆减(n(2))空间，其中n是网络中参与者的数量。它们需要O(n+m)空间，在未加权网络和加权网络上的运行时间分别为O(Nm)和O(nm+n(2)logn)，其中m为链数。实验证据表明，这大大增加了中心性分析可行的网络范围。
The betweenness centrality index is essential in the analysis of social networks, but costly to compute. Currently, the fastest known algorithms require circle minus (n(3)) time and circle minus (n(2)) space, where n is the number of actors in the network.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 + n(2) 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.