Shi Sheng-Qing, Chen Kai, Wang Yu, Luo Rong. Node Importance Analysis in Complex Networks Based on Hardware Computing[J]. Journal of Electronics & Information Technology, 2011, 33(10): 2536-2540. doi: 10.3724/SP.J.1146.2011.00363
Citation:
Shi Sheng-Qing, Chen Kai, Wang Yu, Luo Rong. Node Importance Analysis in Complex Networks Based on Hardware Computing[J]. Journal of Electronics & Information Technology, 2011, 33(10): 2536-2540. doi: 10.3724/SP.J.1146.2011.00363
Shi Sheng-Qing, Chen Kai, Wang Yu, Luo Rong. Node Importance Analysis in Complex Networks Based on Hardware Computing[J]. Journal of Electronics & Information Technology, 2011, 33(10): 2536-2540. doi: 10.3724/SP.J.1146.2011.00363
Citation:
Shi Sheng-Qing, Chen Kai, Wang Yu, Luo Rong. Node Importance Analysis in Complex Networks Based on Hardware Computing[J]. Journal of Electronics & Information Technology, 2011, 33(10): 2536-2540. doi: 10.3724/SP.J.1146.2011.00363
Betweenness centrality is a widely used indicator to measure the node importance in complex network s, but it is computationally-expensive to calculate betweenness centrality. In this paper, analysis on the traditional betweenness centrality algorithms is completed and a novel algorithm is proposed to meet the hardware design features. Based on this algorithm, parallel computing system is implemented on FPGA with task level coarse grained parallelism and pipeline based fine grained parallelism. The experimental results show that the FPGA based implementation achieves up to 4.31 times speedup compared with an 8-core CPU implementation.