Abstract: The complex network clustering algorithm to research the topology properties of complex network needs to deal with large-scale nodes and links. Therefore, it requires higher computation performance to the large-scale complex networks that represent the complex system in reality. Hence, a parallel complex network clustering algorithm on Graphic Processing Units (GPU) based on fast Newman clustering algorithm was designed through the primitive technology that not only reduced the complexity of the parallel algorithm design but also improved the universality in various applications. Then from the thread scheduling strategies and the cache management perspectives, the optimal parallel complex network clustering algorithms were presented to deal with the load balance and the data reuse problem in computing process. The experiments results of the parallel complex network clustering algorithm and the optimal algorithms show that the optimal algorithms have better performance than the former.

Key words: cluster structure, complex network, clustering discovery, Graphic Processing Unit (GPU), parallel algorithm

摘要： 研究复杂网络拓扑属性的聚类算法需要处理大量节点和连接边,因此对计算性能要求高,否则无法处理现实中的表示为复杂网络的系统。利用图形处理器(GPU)的并行聚类算法是解决该问题的重要方法。利用原语技术设计并行快速聚类算法,原语法不仅降低并行算法的复杂性而且提高聚类的普适性;再从线程调度策略和缓存管理两个方面提出优化的方法来解决负载均衡和数据重用性问题。通过实验对比并行快速聚类算法与优化算法的性能,结果显示并行快速聚类优化后的算法取得较好加速比。

关键词: 簇结构, 复杂网络, 聚类发现, 图形处理器, 并行算法