基于线图与标签传播的重叠社区发现算法研究

发布时间：2022-07-02 11:06

　　随着社会关系网络等复杂网络的快速发展,复杂网络中的社区发现已经成为了一个研究热点。作为其中的一个分支,重叠社区发现更接近真实的网络结构,因而具有重要的研究和实践意义。目前,基于节点的标签传播算法具有简单和快速发现社区的优点,因而在重叠社区发现研究领域里被广泛应用。但是该类算法的随机性较强,有时甚至会把所有的节点划分到一个社区。因此,为了发现复杂网络中的重叠社区并提高基于标签传播算法的鲁棒性,考虑到以边为研究对象相对于传统的基于节点的划分具有独特的优势,即可以自然地获得重叠社区,本文以边为研究对象,提出了一种基于线图与标签传播的重叠社区发现算法。此外,为了快速发现较大规模网络中的重叠社区,本文在前面提出的算法基础上做了改进,提出一种基于线图的重叠社区的合并与优化算法。本文的主要研究工作如下:（1）由于标签传播算法的随机更新顺序以及更新标签的随机选取,导致其随机性较强,因此,为了提高重叠社区发现中基于标签传播方法的鲁棒性和准确性,本文以边为研究对象,提出了一种定向标签传播算法,即基于线图与标签传播的重叠社区发现算法（LLPA）。LLPA提出种子边的概念,并根据其他边与种子边之间的相似度,来... 

【文章页数】：57 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
第1章 绪论
    1.1 研究背景与意义
    1.2 国内外研究现状
        1.2.1 基于边划分的重叠社区发现算法国内外研究现状
        1.2.2 基于标签传播的重叠社区发现算法国内外研究现状
    1.3 本文的主要工作及内容安排
第2章 复杂网络社区发现的相关基础
    2.1 复杂网络社区结构相关定义
    2.2 社区结构评价标准
        2.2.1 模块度
        2.2.2 归一化互信息
    2.3 复杂网络线图的相关定义及其与原始图的相互转换
        2.3.1 线图定义
        2.3.2 线图与原始图之间的相互转换
    2.4 本章小结
第3章 基于线图与标签传播的重叠社区发现算法
    3.1 基于线图与标签传播的重叠社区发现算法
        3.1.1 算法流程
        3.1.2 种子边
        3.1.3 标签传播
        3.1.4 优化重叠社区
        3.1.5 算法时间复杂度分析
    3.2 实验与分析
        3.2.1 LFR基准网络上的实验
        3.2.2 真实网络上的实验
    3.3 本章小结
第4章 基于线图的重叠社区的合并与优化算法
    4.1 基于线图的重叠社区的合并与优化算法
        4.1.1 算法流程
        4.1.2 高度重叠社区的合并
        4.1.3 过滤操作
        4.1.4 算法时间复杂度分析
    4.2 实验与分析
        4.2.1 LFR基准网络上的实验
        4.2.2 真实网络上的实验
    4.3 本章小结
第5章 结论与展望
    5.1 工作总结
    5.2 未来展望
致谢
参考文献
附录1 攻读硕士学位期间发表的论文
附录2 攻读硕士学位期间参加的科研项目
详细摘要



本文编号：3654255