Notes on the Algorithm for Calculating Betweenness
ZHOU Tao1, LIU Jian-Guo2, WANG Bing-Hong1
1Department of Modern Physics and Nonlinear Science Center, University of Science and Technology of China, Hefei 230026
2Institute of System Engineering, Dalian University of Technology, Dalian 116023
Notes on the Algorithm for Calculating Betweenness
ZHOU Tao1;LIU Jian-Guo2;WANG Bing-Hong1
1Department of Modern Physics and Nonlinear Science Center, University of Science and Technology of China, Hefei 230026
2Institute of System Engineering, Dalian University of Technology, Dalian 116023
Abstract： We investigate a common used algorithm [Phys. Rev. E64(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.
ZHOU Tao;LIU Jian-Guo;WANG Bing-Hong. Notes on the Algorithm for Calculating Betweenness[J]. 中国物理快报, 2006, 23(8): 2327-2329.
ZHOU Tao, LIU Jian-Guo, WANG Bing-Hong. Notes on the Algorithm for Calculating Betweenness. Chin. Phys. Lett., 2006, 23(8): 2327-2329.
2006, Vol. 23 
