论文部分内容阅读
现实世界中的很多网络系统都可以抽象成社会网络,在这些网络中,节点表示个体,节点之间的边表示个体之间的相互联系。随着对社会网络研究的不断深入,人们发现网络具有社团结构的特性,在社团结构内部,节点之间的连接比较紧密,而社团与社团之间的节点连接较为稀疏。社团结构往往代表了网络中具有某一相同属性特征的节点集合,挖掘网络中这种社团结构对研究社会网络的演化过程、分析网络的拓扑结构以及了解网络潜在的功能都具有非常重要的意义。本文围绕着如何快速且有效地对网络中的社团结构进行聚类这一问题进行了相关研究。本文首先分析总结了社团聚类的相关背景与研究现状,研究了有关社会网络的重要理论,为后续研究奠定了理论基础。对基于局部信息的标签传播算法(LPA算法)进行了深入研究与分析,发现LPA算法在算法迭代过程中会出现“标签逆流”现象,同时初始化标签数目过多,标签更新条件单一、不全面,标签更新策略具有随机性等问题,针对这些问题给出了总体的解决方案。在具体实现这个解决方案的基础上,本文提出了一种带有适合度的标签传播算法,记为LPA-FA算法。LPA-FA算法首先将网络中所有的节点按照其度的大小进行排序,组成了一个有序的节点序列,在每次算法迭代过程中,都按照这个节点序列依次进行节点标签更新,避免了LPA算法由于采用随机节点序列而造成的“标签逆流”现象,提高了算法效率。在节点标签初始化过程中,在LPA-FA算法中设计了一种简单线性初始化方法,减少了网络中初始标签的个数,从而降低算法的运行时间。然后在节点标签传播过程中,当节点的更新标签出现不唯一时,LPA-FA算法引入了邻接子系统聚集系数、邻接边权重、节点属性相似度三个参数,进而通过Topsis方法得到三者的综合评价值标签适合度,最终选择使标签适合度最大的邻接子系统内的标签作为更新标签,不仅解决了LPA算法节点标签更新条件单一、不全面的缺陷,也克服了LPA算法的随机性,从而降低算法的时间开销,提高了聚类社团的质量。最后,将LPA-FA算法与LPA算法分别在Zachary空手道俱乐部网络和科学家合著网络两个数据集上进行了实验,并对实验结果与实验数据进行比对分析。最终,实验表明本文提出的LPA-FA算法无论在运行时间,还是聚类社团的质量上都要优于LPA算法,从而验证了LPA-FA算法的有效性。