随着互联网的发展,人与人之间的联系越来越密切,所形成的网络也越错综繁杂。直接对其进行分析往往具有一定难度,而社团作为它的一个重要属性,能帮助我们认识网络的拓扑和层次结构,预测网络的变化趋势,找到网络中蕴藏的规律特征。社会网络的社团结构涉及到多个学科,在许多领域都有很好的应用前景,引起了国内外学者的广泛关注,近几年来已出现了许多经典的社团发现算法,但是如何降低算法的时间复杂度、提高算法的准确度和稳定性仍是有待解决的问题。本文以无向无权网络的非重叠社团发现问题作为研究对象,以提高划分结果准确度、降低时间复杂度和增加算法稳定性为目标,重点分析了一些经典的社团发现算法,针对聚类算法和标签传播算法的不足之处,设计了两种改进算法,分别是基于节点相似度的社团发现算法(Community Detection Algorithm Based On Node Similarity,NSCDA)和基于标签权重系数的社团发现算法(Community Detection Algorithm Based On Label Weight Coefficient,LWC)。NSCDA算法在聚类算法K-Means的基础上,改进了k个初始点的选择方式,使这k个节点大于平均节点度并且彼此相似度较小;设计了新的节点相似度计算公式代替欧氏距离;依据节点与社团的平均相似度,将节点依次归入到与其平均相似度最大的社团中,得到最终的划分结果。理论分析和在人工合成网络、真实社会网络数据集上的实验结果表明了NSCDA算法的可行性,而且与其他经典算法相比具有较高的准确度和时间效率。为了解决标签传播算法稳定性差、划分结果准确度低的问题,LWC算法按照节点度由大到小的顺序进行标签更新;引入标签权重系数的概念,使节点能根据节点之间的局部相似度和邻居节点的度有针对性地选择邻居节点的标签;引入标签连接度函数的概念,避免遇到多个候选标签时的随机选择。人工合成网络以及真实社会网络数据集上的实验结果均表明LWC算法得到的结果不仅准确率高,而且稳定性好。综上所述,本文对社会网络的社团划分算法的研究具有一定的理论性和应用价值,所设计的算法不仅提高了准确度和划分效率,而且划分结果稳定,可用于真实社会网络的场景中。
暂无评论