摘要
We investigate a common used algorithm [Phys. Rev. E 64 （2001） 016132] to calculate the betweenness centrality for all vertices. The inaccurateness of that algorithm is pointed out and a corrected algorithm, also with O（MN） time complexity, is given. In addition, the comparison of calculating results for these two algorithm aiming at the protein interaction network of yeast is shown.
We investigate a common used algorithm [Phys. Rev. E 64 （2001） 016132] to calculate the betweenness centrality for all vertices. The inaccurateness of that algorithm is pointed out and a corrected algorithm, also with O（MN） time complexity, is given. In addition, the comparison of calculating results for these two algorithm aiming at the protein interaction network of yeast is shown.
基金
Supported by the National Natural Science Foundation of China under Grant Nos 10472116, 10532060, 10547004, 70471033 and 70571074, the Special Research Funds for Theoretical Physics Frontier Problems （NSFC No A0524701）, and the President F~nd of Chinese Academy of Science.
