A Lookahead algorithm to compute Betweenness Centrality

Details A Lookahead algorithm to compute Betweenness Centrality A Lookahead algorithm to compute Betweenness Centrality

2011-08-16

arxiv.org/abs/1108.3286v1

Computer Science

Social and Information Networks

12 pages, 5 figures

Scientific paper

The Betweenness Centrality index is a very important centrality measure in the analysis of a large number of networks. Despite its significance in a lot of interdisciplinary applications, its computation is very expensive. The fastest known algorithm presently is by Brandes which takes O(|V || E|) time for computation. In real life scenarios, it happens very frequently that a single vertex or a set of vertices is sequentially removed from a network. The recomputation of Betweenness Centrality on removing a single vertex becomes expensive when the Brandes algorithm is repeated. It is to be understood that as the size of the network increases, Betweenness Centrality calculation becomes more and more expensive and even a decrease in running time by a small fraction results in a phenomenal decrease in the actual running time. The algorithm introduced in this paper achieves the same in a significantly lesser time than repetition of the Brandes algorithm. The algorithm can also be extended to a general case.

Affiliated with

Also associated with

No associations

Rating

A Lookahead algorithm to compute Betweenness Centrality does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Lookahead algorithm to compute Betweenness Centrality, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Lookahead algorithm to compute Betweenness Centrality will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-196344