论文部分内容阅读
近年来,复杂网络已经成为科学研究中非常重要的研究领域。典型的复杂网络包括社会网络、生物网络、交通网络和信息网络等。这些网络都具有较强的社区结构,因此发现社区结构有助于我们了解网络的其他特性,从而帮助我们开发和利用这些网络。另外,随着复杂网络尤其是英特网的迅速发展,所要处理的信息量不断增加,这使得搜索信息的操作变得尤为复杂,所以如何能够快速搜索到所需信息成为搜索的关键问题,而社区发现技术正是解决这个问题的有效方法。目前,大多数已知的社区发现算法都是串行的,普遍存在速度慢、效率低的缺陷。然而,随着多核技术的发展,以及在面临所处理的信息越来越多的实际情况下,并行社区发现算法会比串行社区发现算法获得更快的效率,可以有效地克服串行算法的局限性。针对上述问题,本文采用并行化策略对经典社区发现算法,即传统的GN (Givern-Newman)算法进行了改进。这两种并行策略分别为粗粒度并行策略和细粒度并行策略,均与计算边介数(full-betweenness,betweenness)相关。第一种方法,即粗粒度并行,分别从不同的源节点出发,并行的计算每条边的边介数(betweenness),然后将每条边的从所有不同的源节点出发计算出的边介数(betweenness)累加起来,得到的这个累加和就是每条边的相对于所有源节点的边介数(full-betweenness)。第二种方法,即细粒度并行,是在计算每条边的相对于一个源节点的边介数(betweenness)的时候,采用并行的搜索方法以及并行的回溯求和方法。从理论上分析,传统的GN算法是一种基于重复移除边的迭代的社区发现算法,我们提出的两种方法都可以减少每次迭代的计算时间。然后,本文选择对粗粒度并行算法加以实现,通过实验对比以粗粒度方式并行的GN算法相对于传统的GN算法的加速效果。实验结果表明粗粒度并行的方法在四核处理器上具有明显的加速效果,并且不会影响算法的准确性。