蒋莉芳，苏一丹，覃　华

(广西大学计算机与电子信息学院，广西 南宁 530004)



基于CUDA的并行谱聚类社区挖掘算法*

蒋莉芳，苏一丹，覃华

(广西大学计算机与电子信息学院，广西 南宁 530004)

摘要：社会网络和社交媒体数据具有大规模、高维度的特性，社区挖掘算法的计算效率是一个值得研究的问题。针对此问题，本文利用CUDA并行计算架构，提出一种并行的谱聚类社区挖掘算法，首先对高维的社会网络数据集进行降维，再用CUDA的并行计算能力提高谱聚类算法的计算效率。实验表明，本文所提算法能有效地提高社区挖掘算法的计算速度，并行计算效率较常规算法有5～8倍的提高，为社区挖掘计算提出一种新的思路。

关键词：社区挖掘；CUDA；并行计算；谱聚类；大规模网络

1概述

快速增长的社交媒体，形成了很多规模巨大和维数众多的网络，社区发现成为了理解网络拓扑结构的重要技术[1，2]。

目前的社区发现算法中，大多数算法的性能其实都很优越，如Luxburg提出的谱聚类算法(Spectral Clustering，SC)[3]，通过求解图分割问题获得网络划分。Newman提出了Modularity算法[4]，考虑节点度的分布情况，用两点间的实际作用和期望值之差，定义社区效应强度，通过最大化效应强度，获得最佳的社区划分。再比如郭进时等[5]提出的联合拓扑与属性的社区模糊划分算法，用完全相异距离指数将拓扑结构与属性相结合，以此作为隶属关系建立模糊等价关系矩阵，再选择合适的聚类对网络进行社区划分。这些算法都能在一定程度上达到社区发现的效果，但这些算法的计算量都很大。……