基于节点链接关系的复杂网络社区检测算法研究

论文摘要

在现实生活中,存在大量各式各样的复杂系统,对于复杂系统的结构研究是人们关注的热点问题。研究人员为了方便研究,将复杂系统抽象成网络表现形式,网络由许多节点和节点之间的连边组成,其中节点代表复杂系统的个体,连边代表个体之间的关系,例如社交关系网络,交通运输网络,生物蛋白质网络等。通过对复杂网络的大量研究表明,复杂网络有一个显著性的特征-社区结构,即社区成员之间联系紧密,社区和社区之间联系稀疏,社区结构的发现对于个性化服务,推荐系统,链路预测等各项领域都有十分重要的研究意义和价值。本文围绕非重叠社区检测和重叠社区检测展开讨论,旨在解决目前社区发现算法忽视网络节点之间的链接关系导致社区划分质量不高,社区划分结果准确性低和不稳定的问题,并且希望进一步提高算法的时间效率,主要包括以下两方面内容:（1）现有利用边删除方式获取非重叠社区结构的算法,存在时间消耗大,划分结果不准确等缺陷。为此,提出了一种基于约束的边删除非重叠社区发现算法。该方法利用节点之间的链接关系,通过共同邻居数的计算区分网络中的弱链接和强链接,然后不断删除网络中的弱链接,并对删除过程加以约束加速算法迭代过程,保留最优模块度值的社区划分。最后再对划分过程产生的孤立节点进行归并以优化社区结构。在合成网络和真实世界网络上的实验结果说明,相对于其他边删除的方法,该算法在保障社区划分质量的同时,还提高了算法的时间效率。（2）针对当前的局部扩展优化算法忽略网络节点之间的链接有强弱之分,导致实现的社区划分结果不稳定和不准确等问题,提出了一种新的基于点权的局部扩展重叠社区发现算法。该方法也是利用节点和节点之间的链接紧密程度来赋予每个节点权重,根据节点重要性排序选择初始种子。然后设置改进的社区适应度函数,从最重要的种子节点开始进行扩展,直到找到局部最优的社区。迭代前面种子选取和扩展方式直到每个节点都至少被分配到一个社区。最后为了进一步提高社区划分质量,对初始形成社区进行优化处理,合并重叠度分数比较高的局部社区。通过在合成网络和真实世界网络上的实验结果证明,和其他类型的重叠算法以及传统的局部扩展方法相比,提出的算法能进一步提高社区划分的质量和准确性。

论文目录

• 摘要
• Abstract
• 第1章 绪论
•   1.1 课题研究背景与意义
•     1.1.1 研究背景
•     1.1.2 研究意义
•   1.2 研究现状
•   1.3 论文的主要研究内容
•   1.4 本文组织结构
• 第2章 相关理论知识
•   2.1 复杂网络
•     2.1.1 复杂网络的定义与描述
•     2.1.2 复杂网络的特性
•   2.2 社区结构
•   2.3 社区发现算法
•     2.3.1 非重叠社区发现算法
•     2.3.2 重叠社区发现算法
•   2.4 社区划分评价指标
•   2.5 本章小结
• 第3章 基于约束的边删除非重叠社区发现算法
•   3.1 引言
•   3.2 基于约束的边删除非重叠社区发现算法
•     3.2.1 算法思想
•     3.2.2 算法步骤
•     3.2.3 算法时间复杂度分析
•   3.3 实验结果与分析
•     3.3.1 真实网络实验结果与分析
•     3.3.2 合成网络实验结果与分析
•   3.4 本章小结
• 第4章 基于点权的局部扩展重叠社区发现算法
•   4.1 引言
•   4.2 相关定义
•   4.3 基于点权的局部扩展重叠社区发现算法
•   4.4 算法时间复杂度分析
•   4.5 实验结果与分析
•     4.5.1 真实网络实验结果与分析
•     4.5.2 合成网络实验结果与分析
•   4.6 本章小结
• 结论
• 参考文献
• 致谢
• 附录A 研究生阶段论文发表和科研项目参与说明

文章来源

类型: 硕士论文

作者: 李娟

导师: 陈湘涛

关键词: 复杂网络,非重叠社区发现,重叠社区发现,边删除,局部扩展优化

来源: 湖南大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 湖南大学

分类号: O157.5

DOI: 10.27135/d.cnki.ghudu.2019.002033

总页数: 74

文件大小: 4482K

下载量: 17