๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A faster algorithm for betweenness centrality*

โœ Scribed by Brandes, Ulrik

Book ID
111905191
Publisher
Taylor and Francis Group
Year
2001
Tongue
English
Weight
621 KB
Volume
25
Category
Article
ISSN
0022-250X

No coin nor oath required. For personal study only.

โœฆ Synopsis

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.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 0(nm) and 0(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.

๐Ÿ“œ SIMILAR VOLUMES

A measure of betweenness centrality base
A measure of betweenness centrality based on random walks
โœ M.E. J. Newman ๐Ÿ“‚ Article ๐Ÿ“… 2005 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 399 KB

Betweenness is a measure of the centrality of a node in a network, and is normally calculated as the fraction of shortest paths between node pairs that pass through the node of interest. Betweenness is, in some sense, a measure of the influence a node has over the spread of information through the n

A practical algorithm for faster matrix
A practical algorithm for faster matrix multiplication
โœ Igor Kaporin ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 69 KB

The purpose of this paper is to present an algorithm for matrix multiplication based on a formula discovered by Pan [7]. For matrices of order up to 10 000, the nearly optimum tuning of the algorithm results in a rather clear non-recursive one-or two-level structure with the operation count comparab