基于智能计算的复杂网络社区发现算法研究

发布时间：2021-05-14 17:38

　　社区发现是复杂网络领域中最具挑战性的问题之一。这个问题引起了许多领域科学家的兴趣,如生物学、社会学和物理学。在过去的几十年里,为了解决这个具有挑战性的问题,提出了许多启发式算法和精确算法。然而,考虑到这些算法需要相当长的计算时间,它们中的大多数并不适合大型网络。与近些年来不断涌现的复杂的自然启发算法不同,本文提出了 一种简单的基于迭代局部搜索（Iterated Local Search,ILS）的元启发式方法,这种元启发式算法在相关问题上已经取得了显著成果。在实验部分,本文提出的算法同其他先进算法通过大量对比实验,进行比较与评估。计算结果表明,ILS稳定性更高,获得的社区质量更高。结构平衡是符号网络最重要的属性之一,它反映了符号网络的潜在的张力与冲突。聚类问题的解是衡量符号网络结构平衡程度的一个重要指标。随着符号网络规模的不断增长,考虑到精确算法需要大量的计算时间,因此精确算法不适用于解决聚类问题。本文提出了一种基于迭代贪心（Iterated Greedy,IG）的元启发式算法,用于对符号网络进行社区划分。通过与其他先进的元启发式算法在许多知名的数据集上进行的对比实验,证明了 IG算法... 

【文章来源】：山东大学山东省 211工程院校 985工程院校 教育部直属院校

【文章页数】：59 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
符号说明
第1章 绪论
    1.1 研究背景与研究意义
    1.2 研究现状
        1.2.1 非符号网络社区发现算法
        1.2.2 符号网络社区发现算法
    1.3 本文主要工作和创新点
    1.4 组织结构
第2章 相关背景知识介绍
    2.1 复杂网络模型
    2.2 社区划分评价标准
        2.2.1 模块度
        2.2.2 不平衡度
        2.2.3 Owsinski-Zadrozny准则
        2.2.4 标准化互信息
    2.3 相关算法介绍
        2.3.1 迭代局部搜索算法
        2.3.2 迭代贪心算法
        2.3.3 标签传播算法
    2.4 本章小结
第3章 基于迭代局部搜索的非符号网络社区发现算法
    3.1 算法描述
        3.1.1 初始化阶段
        3.1.2 局部搜索阶段
        3.1.3 扰动阶段
        3.1.4 接受准则
        3.1.5 终止条件
    3.2 时间复杂度分析
    3.3 实验结果与分析
        3.3.1 参数校准
        3.3.2 收敛性分析
        3.3.3 真实网络数据集实验结果
        3.3.4 人工网络数据集实验结果
    3.4 本章小结
第4章 基于迭代贪心的符号网络社区发现算法
    4.1 算法描述
        4.1.1 初始化阶段
        4.1.2 局部搜索阶段
        4.1.3 解构与重构阶段
        4.1.4 接受准则
        4.1.5 终止条件
    4.2 时间复杂度分析
    4.3 实验结果与分析
        4.3.1 参数校准
        4.3.2 收敛性分析
        4.3.3 社交网络数据集实验结果
    4.4 本章小结
第5章 结论与展望
    5.1 结论
    5.2 展望
参考文献
致谢
攻读学位期间发表的学术成果和参加的科研项目
学位论文评阅及答辩情况表



本文编号：3186055