基于边重整化的网络社团检测方法研究

论文摘要

近年来,随着机器学习、人工智能、大数据技术的快速发展,人们能更迅速、准确地了解与掌握现实复杂世界。现实世界中大多数复杂系统被抽象成复杂网络,作为复杂网络研究的一个重要分支,网络社团检测对理解网络的形成过程、发现复杂网络的内在演化规律等具有十分重要的意义。本文首先介绍复杂网络和社团结构的有关概念、定义及研究意义;同时,比较复杂网络中几种常用的社团检测方法和相关的评价指标。然后,基于节点邻居的差异性定义3种相异性指标:即单层邻居相异性、2-邻居相异性和全局2-邻居相异性。根据两个节点之间的相异性越大,它们出现在同一社团的概率越小的原理,采用分裂思想基于上述节点相异性指标,设计一种有效的社团检测算法―NDA算法。该算法不断移除网络中相异性最高的两节点之间的边,直到网络中所有的节点都变为孤立节点,在移除边的过程中会记录当前网络模块度,算法实现过程中最大的模块度对应于网络的最佳社团结构。通过与GN算法、Newman-Fast算法对比,说明NDA算法具有较高的准确度。进一步,受分级聚类思想和小世界网络模型中边重连接方式的启发,在NDA算法的基础上,基于边重整化方法提出新的社团检测算法。该算法的核心是保持网络的总边数不变,在移除节点间相异性最大连边的同时在相似性最大的节点间建立新边。将边重整化方法与GN算法和NDA算法进行对比,发现采用大度节点相似性指标的边重整化方法在类似于无标度模型网络中效果最好。最后,总结本文的研究内容并对今后的工作进行展望。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
•   1.1 社团检测的研究背景与意义
•   1.2 国内外研究现状
•   1.3 本文的内容和结构
• 2 复杂网络与社团检测的基本理论
•   2.1 复杂网络的发展及表示
•   2.2 社团结构的定义
•   2.3 常用社团检测算法
•   2.4 社团划分结果的评价指标
•   2.5 本章小结
• 3 基于节点相异性指标的网络社团检测算法
•   3.1 三种相异性指标的定义
•   3.2 NDA算法描述与示例
•   3.3 三种相异性指标的对比与分析
•   3.4 实验结果分析
•   3.5 本章小结
• 4 基于边重整化的社团检测方法
•   4.1 边重整化原理
•   4.2 相似性指标介绍
•   4.3 边重整化方法描述与示例
•   4.4 实验结果与分析
•   4.5 本章小结
• 5 总结与展望
•   5.1 总结
•   5.2 工作的展望
• 致谢
• 参考文献
• 附录

文章来源

类型: 硕士论文

作者: 刘亚东

导师: 覃森

关键词: 复杂网络,社团检测,边重整化,相异性,相似性

来源: 杭州电子科技大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 杭州电子科技大学

分类号: O157.5;TP301.6

DOI: 10.27075/d.cnki.ghzdc.2019.000102

总页数: 41

文件大小: 2193k