紀要論文

Accelerating GN Algorithm on Many-core Processors to Find Community Structure in Complex Networks

eng

18810667

https://doi.org/10.15002/00009516

法政大学大学院情報科学研究科

8

19

22

2013-03

Version of Record

Complex network has become an important field in science research recently and it is proved that many networks possess strong community structure. In order to exploit and utilize networks, we need to detect community structure. Here we introduce a kind of classical community detecting algorithm, Givern-Newman (GN) algorithm and propose two methods to parallel GN algorithm. These two proposed methods are based on calculating edge betweenness in parallel. The first method, calculating full betweenness of each edge for different source vertices in parallel, was implemented on the many-core processor. GN algorithm is an iterative community detection algorithm based on removing edge repeatedly. Our two methods can reduce the running time of per iteration. As a result, the method using coarse-grained parallelism for 4-core processor is 3 times faster than the sequential program of GN algorithm.

Article

AA12222297