基于图分解的社区发现算法研究

发布时间：2023-03-05 18:57

　　随着近年来信息技术的飞速发展,大数据时代的来临使得各个领域的重要数据资源在数据量上快速增长,研究如何对这些数据资源进行合理有效的分析、处理和应用无疑充满了机遇与挑战。图结构具有丰富的表现能力,适用于大数据中实体间复杂关系的分析和处理。而大规模图数据中通常包含一些能够揭示数据重要特征的社区结构,因此对社区发现问题的研究是图数据分析与处理领域的重要研究方向。另一方面,稠密子图指图中相互联系较为紧密,呈现较高内聚性的局部子图。由于各类稠密子图定义具有高内聚低耦合的特点,稠密局部在拓扑结构上呈现为联系较为紧密的社区结构,可见稠密子图天然适用于社区发现任务。因此,在社区发现研究领域中,基于稠密子图的方法是最为热门的方向之一。本文研究基于稠密子图分解的社区发现算法。通过对现有基于稠密子图的社区发现方法进行分析,发现大多或者在模型定义上对子图结构的稠密度约束不合理,或者在算法效率上难以应用于大规模图数据,存在诸多不足。此外,由于增加了对社区的持续度的要求,在时序图上的持续社区发现研究成果也不尽人意。本文针对静态图提出了基于三角形这一高阶连通结构的k-TriPeak社区模型,并为之设计了采取自顶向下分...

【文章页数】：78 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 绪论
    1.1 研究背景及意义
    1.2 研究现状
    1.3 本文主要内容
    1.4 本文组织结构
第二章 背景知识和相关工作
    2.1 图的基本概念
    2.2 基于稠密子图的社区发现
    2.3 基于稠密子图的持续社区发现
    2.4 本章小结
第三章 k-TriPeak社区发现算法
    3.1 问题定义
    3.2 基础算法
    3.3 优化算法
    3.4 实验结果及分析
    3.5 本章小结
第四章 (k,l,τ)-TriPeak持续社区发现算法
    4.1 问题定义
    4.2 基础算法
    4.3 优化算法
    4.4 实验结果及分析
    4.5 本章小结
第五章 总结与展望
    5.1 本文工作总结
    5.2 未来工作展望
参考文献
攻读硕士学位期间发表论文和科研情况
致谢



本文编号：3756746