|
|
|
| Node Importance Analysis in Complex Networks Based on Hardware Computing |
| Shi Sheng-qing① Chen Kai② Wang Yu① Luo Rong① |
①(TNList, Dept. of Electronic Engineering, Tsinghua University, Beijing 100084, China)
②(Hainan Communications Administration, Haikou 570206, China) |
|
|
|
|
Abstract 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.
|
|
Received: 14 April 2011
|
|
|
|
Corresponding Authors:
Shi Sheng-qing
E-mail: shisq04@mails.tsinghua.edu.cn
|
|
|
|
|
|
|
2011, Vol. 33 
