基于k团核的稠密子图发现算法研究

发布时间：2023-02-15 14:08

　　随着大规模网络的不断发展,涌现了许多相关的新兴应用,同时图规模快速增长,图数据也频繁更新,对大规模网络的处理提出了更高的要求。稠密子图发现是一个基本的图挖掘问题,已经成为广泛的数据分析任务中的原语,稠密子图发现作为网络处理中的热点问题,其质量和效率直接影响到复杂的网络分析。本文对稠密子图发现和k核的相关理论进行了研究,根据静态图及动态图上稠密子图的特点提出了基于k团核的稠密子图发现方法,主要研究内容包括:1.提出一种新的稠密子图模型。k团核模型既可以捕获顶点的团核数又能保证子图一定的紧密性,k团核心分解算法获得的团核数能够有效地得到密度假想值的紧密上下限,从而减少二进制搜索的次数。2.提出基于k团核的静态稠密子图发现的一种精确算法和一种近似算法,实现大规模图上的快速稠密子图发现。精确算法利用k团核,提出三个优化规则提高效率,并且利用核心分解算法,在特定的核上构建流网络,通过使用二分查找法解决最大流问题找到稠密子图。近似算法为了进一步提高效率,不利用核心分解算法,而是提出一种新的方法,直接计算最大的k团核,并证明最大k团核是稠密子图发现问题的近似解。3.提出动态图上的稠密子图发现算法。在...

【文章页数】：76 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
1 绪论
    1.1 研究背景与意义
    1.2 国内外研究现状
        1.2.1 稠密子图发现研究现状
        1.2.2 基于k核的稠密子图发现研究现状
    1.3 研究内容
    1.4 论文结构
2 相关理论基础概述
    2.1 稠密子图模型
        2.1.1 基于平均度的稠密子图模型
        2.1.2 基于k核的稠密子图模型
        2.1.3 基于团的稠密子图模型
    2.2 稠密子图发现算法
        2.2.1 稠密子图发现的精确算法
        2.2.2 稠密子图发现的近似算法
        2.2.3 稠密子图发现的分段算法
        2.2.4 稠密子图发现的边权更新算法
    2.3 k核心分解方法
    2.4 h团(h-clique)
    2.5 本章小结
3 基于k团核的稠密子图发现算法
    3.1 问题定义
        3.1.1 k团核定义
        3.1.2 静态稠密子图发现定义
        3.1.3 在k团核上构建流网络的过程
    3.2 基于k团核的精确算法
        3.2.1 k团核的密度上限和下限
        3.2.2 k团核心分解
        3.2.3 基于k团核的精确算法设计
    3.3 基于k团核的近似算法
    3.4 本章小结
4 动态的稠密子图发现算法
    4.1 问题定义
        4.1.1 动态稠密子图定义
        4.1.2 滑动时间窗口模型
        4.1.3 存储高团度顶点的数据结构
    4.2 动态稠密子图发现算法
        4.2.1 添加顶点和添加边算法
        4.2.2 删除顶点和删除边算法
        4.2.3 完整的动态稠密子图发现算法
    4.3 本章小结
5 实验验证与结果分析
    5.1 实验概述
        5.1.1 实验环境及评估指标
        5.1.2 实验数据集
    5.2 实验分析
        5.2.1 稠密子图发现的精确算法结果分析
        5.2.2 稠密子图发现的近似算法结果分析
        5.2.3 稠密子图发现的精确与近似算法比较
        5.2.4 稠密子图发现的动态算法结果分析
    5.3 案例研究
    5.4 本章小结
结论
参考文献
致谢
作者简历及攻读硕士学位期间的科研成果



本文编号：3743345