基于节点相似性的复杂网络社区发现算法研究

发布时间：2020-04-12 09:09

【摘要】：复杂网络是众多现实复杂系统的抽象表现形式,其节点代表复杂系统中的个体,网络连边蕴含着系统个体间的某种内在联系。随着复杂网络的物理意义和数学特性的深入研究,实际网络中的一个共同性质,即社区结构,引起学者们的广泛关注。研究发现:整个网络是由若干个“社区”构成的,并且每个社区内部节点之间的连接相对紧密,但各个社区之间的连接却比较稀疏。复杂网络社区发现研究对分析复杂网络的拓扑和层次结构、理解社区的形成过程、预测复杂网络的演化趋势、发现复杂网络的独有特征等具有十分重要的理论意义与应用价值。成功挖掘复杂网络社区的关键在于根据网络节点或边的特性设计合适且高效的社区发现算法。本文选择网络节点之间的余弦相似性和朴素相异性等指标作为划分社区节点的标准,分别设计出网络社区发现新算法,并基于其他几种重要的相似性指标获得多种相似性指标的最优组合,进一步获得Zachary空手道网络、海豚关系网络、美国足球网络和电力网络等真实网络的社区发现结果。本文首先简要介绍复杂网络及其社区发现的概念、基本方法与研究意义。在此基础上,重点介绍了几类重要的社区发现算法及其划分思想,如K-L算法、谱二分法、GN算法、Newman快速算法等。然后,选择节点间的余弦相似性作为划分社区节点的标准,利用社区间的全局相似信息,通过迭代凝聚具有最大相似性的两个社区,得到网络社区发现结果;而最优社区数量由迭代过程中的模块度的最大值自动获得。利用新算法,获得Zachary空手道网络、海豚关系网络、美国足球网络和电力网络等真实网络的社区数量和最大模块度值,并通过实证分析获得多种相似性指标的最优组合结果。进一步,基于节点属于不同社区的相异特征,定义节点间的相异性度量,结合分裂算法思想进而设计出基于节点间相异性度量的新社区发现算法。实证发现,此算法的时间复杂度和社区发现结果的准确性等稍微优于GN算法。最后,总结了本文的研究工作,并对进一步的研究工作进行了展望。
【图文】：

杭州电子科技大学硕士学位论文网络社区结构的定义和评价指标结构的定义究的深入阶段，相关学者注意到复杂网络的又一个非常普遍的特点，就是是由一些相对较小的“区”或者“群”组成[23]。所有的这些群满足群里群彼此的连接十分松散。例如，就像图 2.1 表示的那样，，该网络具有三个解，在图内已经把它们用虚线圈起来了。在复杂网络中，根据各个节点不分类从而得到各个社区[34-36]。

杭州电子科技大学硕士学位论文元素ijS 是第i个社区和第 j 个社区之间的相似度，矩阵维相似性矩阵中除了 1 以外（因为社区和自身合并没有意义为maxS 相应的两个社区归为一个新的社区。社区结构的模块度值。（2）（3）（4）到网络中社区个数变为 1。最高的社区划分结果就认为是网络的最优社区结构。介绍算法的步骤，如图 3.1：
【学位授予单位】：杭州电子科技大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【参考文献】

相关期刊论文 前2条

1 黄承慧;印鉴;侯f ;;一种结合词项语义信息和TF-IDF方法的文本相似度量方法[J];计算机学报;2011年05期

2 王小黎;;一种改进的图聚类的相异度度量方法[J];计算机应用与软件;2011年05期

本文编号：2624539