论文部分内容阅读
在现实世界中,大量的复杂系统都可以用抽象的社会网络来表示和分析。继发现社会网络的小世界性、无标度性以后,人们发现了它的另一个统计特征——簇结构特性,它具有相同簇结构内部的节点间相互连接紧密、不同簇之间节点间相互连接稀疏的特点,反映社会网络极其普遍和重要的拓扑特性。社会网络的聚类方法以挖掘出社会网络中客观存在的簇结构作为目标,对于分析社会网络的结构、了解网络的潜在功能与特性具有十分重要的理论意义。在近十年来,社会网络簇结构挖掘取得了长足的进展,广泛应用在社会网、生物网和万维网等领域中。本文首先对社会网络聚类的相关背景和理论进行了研究,分析并总结了社会网络聚类方法的研究现状。在此基础上,进一步对基于局部信息的聚类算法进行了深入的探索与研究,重点分析标签传播算法中影响性能和效果的瓶颈因素。为了提高标签传播算法的聚类速度及网络划分的质量,引入节点属性相似度的概念来解决算法的影响因素,提出了一种改进的基于节点属性相似度的标签传播算法。该算法能够在大规模的数据网络中,从网络的局部信息出发,以节点属性信息的相似度为参考,在近乎线性时间内挖掘出网络簇结构。最后,本文采用美国大学足球赛程网络、DBLP中的科学家合著网络数据集进行实验,分别实现原始的标签传播算法与改进的标签传播算法,并对它们的性能进行比较。实验结果表明基于节点属性相似度的标签传播算法,较之原始的标签传播算法,提高了网络聚类的质量,优化了聚类效果,同时降低了算法的时间开销,提高了算法的聚类速度。