复杂网络社群发现算法的研究对于分析复杂网络的拓扑结构、理解复杂网络的功能、发现复杂网络中的隐藏规律和预测复杂网络的行为不仅有十分重要的理论意义,而且有广阔的应用前景。目前已经广泛应用于恐怖组织识别与组织结构管理等社会网络分析中。近年来,复杂网络的社群发现问题受到了广泛的关注,涌现出很多新颖的算法。但是,目前的社群发现算法存在划分效果较好的算法时间复杂度过高、划分速度快的算法划分质量不佳等问题。本文针对K-Means算法的一些缺点,结合其它算法的特点,加入增益函数的使用,在事先不确定k值的情况下,以最远距离为原则选择簇类中心,以最近距离为原则选择簇中元素,以此提高算法的划分精度,然后结合GPU并行化技术,将串行结构的K-Means算法改造成基于GPU并行的K-Means算法,提高算法的效率,最后使用NIVIDA的CUDA作为运算平台进行并行算法的实现。当应用到实际的复杂网络社群发现中时,则利用关联度原则对该算法进行相应的改进,并使用相关网络数据集对串行结构和并行结构的算法进行测试与结果的比较。实验表明,两个算法的划分结果相同,但是并行结构的算法相比较于串行算法有明显的速度提升。结合并行化技术的K-Means社群发现算法能够快速准确的定位网络中的社群结构,为研究人员分析社群结构提供有效的帮助,而且可以采用类似的并行化处理手段对其它社群发现算法进行并行优化。