Betweenness versus Linerank

In our paper we compare two centrality measures of networks, namely betweenness and Linerank. Betweenness is a popular, widely used measure, however, its computation is prohibitively expensive for large networks, which strongly limits its applicability in practice. On the other hand, the calculation of Linerank remains manageable even for graphs of billion nodes, therefore it was offered as a substitute of betweenness in [4]. Nevertheless, to the best of our knowledge the relationship between the two measures has never been seriously examined. As a first step of our experiments we calculate the Pearson’s and Spearman’s correlation coefficients for both the node and edge variants of these measures. In the case of the edges the correlation is varying but tends to be rather low. Our tests with the Girvan-Newman algorithm for detecting clusters in networks [7] also underlie that edge betweenness cannot be substituted with edge Linerank in practice. The results for the node variants are more promising. The correlation coefficients are close to 1 almost in all cases. Notwithstanding, in the practical application in which the robustness of social and web graphs to node removal is examined node betweenness still outperforms node Linerank, which shows that even in this case the substitution still remains a problematic issue. Beside these investigations we also clarify how Linerank should be computed on undirected graphs.