| Notes on the Algorithm for Calculating Betweenness |
| |
| 引用本文： | 周涛 刘建国 汪秉宏. Notes on the Algorithm for Calculating Betweenness[J]. 中国物理快报, 2006, 23(8): 2327-2329 |
| |
| 作者姓名： | 周涛 刘建国 汪秉宏 |
| |
| 作者单位： | [1]Department of Modern Physics and Nonlinear Science Center, University of Science and Technology of China, Hefei 230026 [2]Institute of System Engineering, Dalian University of Technology, Dalian 116023 |
| |
| 基金项目： | 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. |
| |
| 摘 要： | 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.
|
| 关 键 词： | 算法 中间状态 修正 计算结果 |
| 收稿时间： | 2006-05-09 |
| 修稿时间： | 2006-05-09 |
Notes on the Algorithm for Calculating Betweenness |
| |
| ZHOU Tao,LIU Jian-Guo,WANG Bing-Hong. Notes on the Algorithm for Calculating Betweenness[J]. Chinese Physics Letters, 2006, 23(8): 2327-2329 |
| |
| Authors: | ZHOU Tao LIU Jian-Guo WANG Bing-Hong |
| |
| Affiliation: | 1.Department of Modern Physics and Nonlinear Science Center, University of Science and Technology of China, Hefei 230026; 2.Institute 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. |
| |
| Keywords: | 89.75.Hc 89.65.-s 89.70.+c 01.30.-y |
| 本文献已被 维普 等数据库收录！ |
| 点击此处可从《中国物理快报》浏览原始摘要信息 |
|
点击此处可从《中国物理快报》下载免费的PDF全文 |
