局部拓展类重叠社区发现算法研究

发布时间：2023-03-28 19:02

　　随着互联网在现代生活中的普及,现实世界中的许多事物都以网络的形态存在,重叠社区发现算法可以帮助我们更好地理解网络的结构特征。目前重叠社区发现算法总体可以分为全局划分和局部扩展两大类。本文主要对局部扩展类的重叠社区发现算法进行研究,针对现有算法在划分结果的准确性、稳定性和算法运行时间等方面存在的一些不足进行研究,提出多种改进算法。本文的主要研究工作及贡献如下:(1)针对现有算法划分结果在准确性和稳定性方面的不足,提出了一种基于K-核迭代因子和社区隶属度的重叠社区发现算法(KIMDOC)。首先,该算法引入一种节点重要性评估方法K-核迭代因子,同时引入节点密度的概念得到节点局部影响力的计算公式,利用这两种方法来计算节点影响力,并依据节点影响力选择种子节点,作为初始社区。其次,基于节点影响力提出一种新的社区隶属度函数,利用该社区隶属度函数基础上,以初始社区为核心,逐步进行局部扩展,因不同的社区间会有交集,故KIMDOC算法可以发现重叠社区。最后,对重叠度高的社区和孤立节点进行处理,得到最终的划分结果。(2)为了提高KIMDOC算法的运行效率,提出了一种基于完全图和社区隶属度的重叠社区发现算法(...

【文章页数】：64 页

【学位级别】：硕士

【文章目录】：
摘要
英文摘要
1 绪论
    1.1 研究背景和研究意义
    1.2 国内外研究现状
    1.3 本文主要研究内容和创新点
    1.4 文章组织架构
2 相关理论
    2.1 复杂网络概述
    2.2 复杂网络结构特征
        2.2.1 规则网络结构
        2.2.2 小世界特性
        2.2.3 聚类系数
    2.3 社区的概念及评价指标
        2.3.1 社区的相关定义
        2.3.2 社区的评价标准
    2.4 局部扩展类算法
        2.4.1 算法基本过程
        2.4.2 时间复杂度分析
    2.5 K-核分解算法
    2.6 本章小结
3 基于K-核迭代因子和社区隶属度的重叠社区发现算法
    3.1 种子节点选择的改进
        3.1.1 节点影响力计算
        3.1.2 种子节点选择
    3.2 社区隶属度
        3.2.1 邻接节点集的影响力
        3.2.2 节点在社区中的影响力
    3.3 算法局部扩展过程
    3.4 算法描述
    3.5 算法分析
    3.6 实验分析
        3.6.1 实验数据
        3.6.2 实验参数选择
        3.6.3 真实网络结果对比
        3.6.4 人工基准网络结果对比
    3.7 本章小结
4 基于完全图和社区隶属度的重叠社区发现算法
    4.1 种子节点选择
    4.2 形成初始社区
    4.3 算法局部扩展
    4.4 算法描述
    4.5 算法分析
    4.6 实验分析
        4.6.1 实验数据
        4.6.2 实验参数选择
        4.6.3 真实网络结果对比
        4.6.4 人工基准网络结果对比
    4.7 本章小结
5 基于K-核迭代因子和完全图的重叠社区发现算法
    5.1 种子节点选择
    5.2 算法局部扩展过程
    5.3 算法描述
    5.4 算法分析
    5.5 实验分析
        5.5.1 实验数据
        5.5.2 真实网络结果对比
        5.5.3 人工基准网络结果对比
    5.6 本章小结
6 总结和展望
    6.1 总结
    6.2 展望
参考文献
附录
    A.作者在攻读学位期间发表的论文目录
    B.学位论文数据集
致谢



本文编号：3773101