Faster Evaluation of Shortest-Path Based Centrality Indices

@misc{citeulike:969598, abstract = {Centrality indices are an important tool in network analysis, and many of them are derived from the set of all shortest paths of the underlying graph. The so-called betweenness centrality index is essential for the analysis of social networks, but most costly to compute. Currently, the fastest known algorithms require Theta(n\³) time and Theta(n\²) space, where n is the number of vertices. Motivated by the fast-growing need to compute centrality indices on large, yet very sparse,...}, author = {Brandes, Ulrik }, citeulike-article-id = {969598}, keywords = {path, shortest}, posted-at = {2006-12-01 04:31:46}, priority = {3}, title = {Faster Evaluation of Shortest-Path Based Centrality Indices}, url = {http://citeseer.ist.psu.edu/brandes00faster.html} }

TY - GEN ID - citeulike:969598 L3 - citeulike-article-id:969598 TI - Faster Evaluation of Shortest-Path Based Centrality Indices N2 - Centrality indices are an important tool in network analysis, and many of them are derived from the set of all shortest paths of the underlying graph. The so-called betweenness centrality index is essential for the analysis of social networks, but most costly to compute. Currently, the fastest known algorithms require Theta(n³) time and Theta(n²) space, where n is the number of vertices. Motivated by the fast-growing need to compute centrality indices on large, yet very sparse,... KW - path KW - shortest AU - Brandes, Ulrik UR - http://citeseer.ist.psu.edu/brandes00faster.html ER -