论文部分内容阅读
社区发现,是指在社会网络中发现有用社区结构的过程。随着科技的发展,社会网络以多种形式影响着现实世界中各个领域的方方面面,如朋友关系网络、科学家文献引用网络以及信息通讯网络等等。作为社会网络的一个重要属性,社区结构的相关研究吸引了越来越多的来自社会学、生物信息学、计算机学等领域专家和学者的密切关注。到目前为止已经涌现出了GN、K-L、谱平分法等为代表的多种在社区发现的算法,其中的一些算法甚至已经在现实中得到了应用。 本文对社区发现算法,特别是在大数据集下社会网络中的社区发现方面做了许多改进。主要体现在如下三个方面: 第一,提出了一种使用PageRank值和结点度评估关键点的算法。首先提出在社会网络中,使用PageRank算法评估结点本身的重要性,然后结合Map-Reduce和空间压缩思想对PageRank改进,使其能够适应处理大数据集的情况。这样做即保证了算法的有效性,又可在较低的时间复杂度下完成任务。 第二,提出了一种改进的层次聚类算法,对社区网络关键点进行聚类。首先利用结点的连接作为其属性,将网络映射到n维空间中,并将结点间的相似性度量转换成经典的距离定义来计算。然后对模块度的计算进行改进,计算两个相近过程之间的模块度增益更能适应拥有小社区和离群点特征的关键点聚类。最后,利用改进的凝聚策略进行聚类,在实验中获得了较高准确性。 第三,在上述两个算法的基础之上,提出了一种改进的基于k-均值的社区发现算法。对于使用上述两种算法获得的初始簇,使用压缩技术和类B+树格式存储社区信息,有效降低结点匹配的时间复杂度和存储临时数据的空间复杂度。其中利用“维数灾难”特征估算社区信息,在处理大数据集时有较高准确性。该算法能够对社区进行微调,保证在小概率事件发生时,也能得到准确的社区划分结果。