基于图谱理论的社团发现问题研究

论文摘要

社团结构是复杂网络重要的拓扑特性,处于同一社团中的节点往往具有相似的特性或功能。社团发现对解决生活中的各种复杂问题发挥着重要的作用,比如商品推荐、网络舆情控制、蛋白质功能探究等。目前大多数社团发现算法都是基于分裂或凝聚的思想,而关于意见动力学模型的社团发现算法较少且效果都不是很好。本文研究基于DeGroot模型的社团发现算法,选取最大团或单个节点作为种子,在初始时刻赋予种子一个较大的状态,而赋予其他节点一个较小的状态。每个节点通过与其邻居交换意见,使得处于同一个社团中的节点状态相对比较一致。本文根据节点状态之间的关系分别设计了将网络分成两个社团和多个社团的算法。为了将网络分成两个社团,我们设计了两个不同的算法。第一个算法是利用网络的最大团来扩展社团,每次将状态不小于均值的节点记录到一个集合中,将其他节点记录到另一个集合中,利用DeGroot模型迭代更新网络节点的状态,当集合达到局部稳定状态时就对应了很好的社团结构。对一个有n个节点m条边的网络,该算法的时间复杂度为O（3n/3+Tn+Tm）,对稀疏网络为O（dn3/3+Tn）,其中T为DeGroot模型的迭代次数,d为解空间树的深度。第二个算法是基于种子节点扩展的方法,设计目的是解决最大团扩展算法对稠密或最大团规模较大网络失效的问题,算法的时间复杂度为O（Tn+Tm）,对稀疏网络为O（Tn）。算法的迭代次数与种子节点的选取有关,通常选取度较大的节点作为种子则迭代次数可能相对较少。通过对基准网络进行测试,这两个算法对社团划分的准确度不低于经典的二分网络社团谱方法,且基于种子节点扩展的算法执行速度略快于谱方法。为了将网络分成多个社团,我们设计了基于DeGroot模型并通过种子节点扩展的算法,每轮迭代完成后将状态较大的节点记录到一个集合里,当集合达到局部稳定状态时该集合就对应了种子节点的社团,然后继续选择种子节点直到所有节点都被扩展到相应的社团中为止。算法的时间复杂度为O（NcT（nlog2 n+m））,对稀疏网络,其时间复杂度为O（NcTnlog2n）,其中Nc为网络的社团数。通过对真实和人工基准网络进行测试,该算法的社团划分准确度要高于CNM、BGLL和MG等算法。

论文目录

• 摘要
• abstract
• 第一章 绪论
•   1.1 研究背景及意义
•   1.2 研究现状
•   1.3 本文研究内容
•   1.4 本文的结构与安排
• 第二章 相关概念与理论
•   2.1 复杂网络概述
•     2.1.1 复杂网络的概念
•     2.1.2 复杂网络的表示
•   2.2 复杂网络的社团
•   2.3 社团的评价指标
•     2.3.1 模块性
•     2.3.2 标准化互信息
•   2.4 最大团问题
•     2.4.1 最大团的基本概念
•     2.4.2 最大团的数学描述
•     2.4.3 求解最大团问题的常用算法
•   2.5 网络数据集
•     2.5.1 真实网络数据
•       2.5.1.1 Zachary空手道俱乐部网络
•       2.5.1.2 海豚社会网络
•       2.5.1.3 美国政治书籍网络
•       2.5.1.4 美国大学足球赛网络
•     2.5.2 人工网络数据
•       2.5.2.1 GN基准网络
•       2.5.2.2 LFR基准网络
•   2.6 本章小结
• 第三章 基于De Groot模型将网络分为两个社团
•   3.1 DeGroot模型
•     3.1.1 模型介绍
•     3.1.2 应用到社团发现
•   3.2 基于最大团扩展的算法
•     3.2.1 算法设计思想
•     3.2.2 算法流程
•     3.2.3 正则网络收敛性分析
•     3.2.4 实验与分析
•       3.2.4.1 真实网络实验结果
•       3.2.4.2 人工网络实验结果
•   3.3 基于种子节点扩展的算法
•     3.3.1 算法设计思想
•     3.3.2 算法流程
•     3.3.3 正则网络收敛性分析
•     3.3.4 实验与分析
•       3.3.4.1 真实网络实验结果
•       3.3.4.2 人工网络实验结果
•   3.4 本章小结
• 第四章 基于De Groot模型将网络分为多个社团
•   4.1 算法设计思想
•   4.2 算法流程
•   4.3 实验与分析
•     4.3.1 真实网络实验结果
•     4.3.2 人工网络实验结果
•   4.4 本章小结
• 第五章 总结与展望
•   5.1 全文总结
•   5.2 研究展望
• 致谢
• 参考文献
• 附录

文章来源

类型: 硕士论文

作者: 张尧毅

导师: 何军华

关键词: 复杂网络,社团发现,模型,最大团,种子扩展

来源: 电子科技大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 电子科技大学

分类号: O157.5

总页数: 66

文件大小: 16461K

下载量: 55