A faster algorithm for betweenness centrality Export

@misc{citeulike:297939, abstract = {The betweenness centrality index is essential in the analysis of social networks, but costly to compute. Currently, the fastest known algorithms require \#(n ) time and \#(n ) space, where n is the number of actors in the network.}, author = {Brandes, U.}, citeulike-article-id = {297939}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.2024}, comment = {Betweenness Centralityは社会ネットワーク解析で大事だけど，計算コストがかかる． 現行のアルゴリズムでは，最速でも時間にしてO(n^3)，空間でも(n^2)かかる． 今回の論文で紹介されているアルゴリズムを使えば空間計算量がO(n+m)で，時間計算量にしてO(nm+n^2logn)で計算できる．}, keywords = {networks}, posted-at = {2006-06-29 08:03:33}, priority = {0}, title = {A faster algorithm for betweenness centrality}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.2024}, year = {2001} }

TY - GEN ID - citeulike:297939 L3 - citeulike-article-id:297939 N2 - The betweenness centrality index is essential in the analysis of social networks, but costly to compute. Currently, the fastest known algorithms require #(n ) time and #(n ) space, where n is the number of actors in the network. TI - A faster algorithm for betweenness centrality KW - networks N1 - Betweenness Centralityは社会ネットワーク解析で大事だけど，計算コストがかかる． 現行のアルゴリズムでは，最速でも時間にしてO(n^3)，空間でも(n^2)かかる． 今回の論文で紹介されているアルゴリズムを使えば空間計算量がO(n+m)で，時間計算量にしてO(nm+n^2logn)で計算できる． AU - Brandes, U PY - 2001/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.2024 ER -