document: QUBE : a quick algorithm for updating betweenness centrality The betweenness centrality of a vertex in a graph is a measure for the participation of the vertex in the shortest paths in the graph . The Betweenness centrality is widely used in network analyses . Especially in a social network , the recursive computation of the betweenness centralities of vertices is performed for the community detection and finding the influential user in the network . Since a social network graph is frequently updated , it is necessary to update the betweenness centrality efficiently . When a graph is changed , the betweenness centralities of all the vertices should be recomputed from scratch using all the vertices in the graph . To the best of our knowledge , this is the first work that proposes an efficient algorithm which handles the update of the betweenness centralities of vertices in a graph . In this paper , we propose a method that efficiently reduces the search space by finding a candidate set of vertices whose betweenness centralities can be updated and computes their betweenness centeralities using candidate vertices only . As the cost of calculating the betweenness centrality mainly depends on the number of vertices to be considered , the proposed algorithm significantly reduces the cost of calculation . The proposed algorithm allows the transformation of an existing algorithm which does not consider the graph update . Experimental results on large real datasets show that the proposed algorithm speeds up the existing algorithm 2 to 2418 times depending on the dataset .
doc_bio_tags: O O O O O O O B I O B I O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O