论文部分内容阅读
现实生活中很多系统结构都能抽象成网络,比如关系网络、新陈代谢网络、电子邮件通信网络、移动电话网络等。这些网络能够根据内部的相互作用表现出某些结构特征,其中社区结构(Community Structure)是这类网络中一个重要的特征,对网络中的社区结构的进行检测的方法叫做社区检测(Community Detection)。社区检测作为网络分析的基本任务有助于其它网络计算任务的完成,近年来有很多针对社区检测的研究并取得了不少研究成果。科学技术的不断进步使得网络的规模不断增大,现有的部分社区检测算法已经不能胜任大规模网络的社区检测任务。另外,社区检测问题能够转化为聚类问题,所以本文主要从相似性算法、聚类算法和分布式并行化计算三个方面入手对社区检测问题进行研究,本文的主要内容如下:1.在现有的一些针对网络中顶点之间相似性进行计算的算法研究中,大多数算法要么时间复杂度过高,要么没有充分的考虑整个网络的拓扑结构。基于以上问题,本文以随机游走模型为基础并基于个性化排名算法APR(Approximate Page Rank)算法,提出了一种快速的相似性计算算法,使得该算法在充分考虑网络的拓扑情况下提高网络中顶点之间相似性计算的效率。2.在社区检测的聚类阶段,现有的一些聚类算法不能够充分的利用网络中所蕴含的信息使得检测出来的社区质量不高。基于以上问题,本文提出了一种适用于针对网络进行社区检测的半监督聚类算法SSAP(Similarity Set based Affinity Propagation),该算法是基于AP(Affinity Propagation)算法的一种改进,提高了聚类算法在迭代时的运行效率以及整个算法的收敛速度。并结合提出的相似性计算方法,把社区检测问题转化成为了聚类问题。3.随着分布式计算的技术越来越成熟,比如基于Hadoop平台的Map Reduce并行化计算框架、基于内存模型的并行化计算框架Spark等。这些分布式计算技术的出现使得先前不能在单机环境下完成的计算任务得以实现。同时,在社区检测任务中,由于面临的网络规模越来越庞大,至此,本文在Spark框架下对所提出的社区检测算法进行了并行化实现,利用分布式并行化的优势使得该算法能够对大规模的网络进行社区检测。