Journal of Computer Applications ›› 2012, Vol. 32 ›› Issue (09): 2458-2462.DOI: 10.3724/SP.J.1087.2012.02458

• Network and distributed techno • Previous Articles     Next Articles

Parallel algorithms for complex network clustering with GPUs

WANG Hai-feng1,2*   

  1. 1.School of Information,Linyi University,Linyi Shandong 276002,China;
    2.School of Management,University of Shanghai for Science and Technology,Shanghai 200093,China
  • Received:2012-03-26 Revised:2012-05-13 Online:2012-09-01 Published:2012-09-01
  • Contact: Hai-feng WANG

快速复杂网络聚类图形处理器并行算法

王海峰1,2*   

  1. 1.临沂大学 信息学院,山东 临沂 276002;
    2.上海理工大学 管理学院,上海 200093
  • 通讯作者: 王海峰
  • 作者简介:王海峰(1976-),男,山东临沂人,副教授,博士,主要研究方向:复杂网络、并行计算。
  • 基金资助:

    上海市重点学科建设项目(S30501)

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)的并行聚类算法是解决该问题的重要方法。利用原语技术设计并行快速聚类算法,原语法不仅降低并行算法的复杂性而且提高聚类的普适性;再从线程调度策略和缓存管理两个方面提出优化的方法来解决负载均衡和数据重用性问题。通过实验对比并行快速聚类算法与优化算法的性能,结果显示并行快速聚类优化后的算法取得较好加速比。

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

CLC Number: