面向时态图的频繁社区搜索算法研究

发布时间：2023-04-01 13:19

　　社区挖掘是图数据挖掘的一项基本任务。在现有的图数据中,图中的边上通常都包含时间信息,例如科学家合作网络,电信话务网络,微信社交网络等等。绝大多数现有的社区挖掘算法主要针对传统的不包含时态边信息的图数据,因此无法适用于时态图数据的社区挖掘。本文主要研究时态图数据的频繁社区挖掘问题。我们的目标是找出时态图上所有的频繁社区结构。在传统图数据上已有多种社区模型,譬如k-core、clique、k-truss,k-edge connectedcomponent等。但是这些社区模型都是基于传统图数据上的模型,并不能在时态图上有效的搜索出频繁社区,为了能够在时态图上进行频繁社区搜索,我们提出了全新的频繁社区模型k-star。现实世界的时态图数据通常是极为庞大的,直接在原始的时态图上进行社区搜索是十分耗时的,为了能够高效的在时态图上搜索频繁社区,我们提出了时态图削减算法。该削减算法是通过一种弱核子图的概念来进行剪枝的。实验中该算法存在两方面的技术挑战:(1)频繁节点度的计算和(2)邻居节点的动态更新。我们提出度区间分解算法实现了对频繁节点度的快速计算和邻居节点的动态更新操作。在经过削减后的时态图中,为...

【文章页数】：50 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 研究背景与意义
    1.2 本文的主要工作
    1.3 本文的组织结构
第2章 社区模型
    2.1 传统社区模型
        2.1.1 k-core模型
        2.1.2 clique模型
        2.1.3 k-truss模型
        2.1.4 k边连通子图模型
    2.2 社区分解算法
        2.2.1 k-core分解算法
        2.2.2 clique分解算法
        2.2.3 k-truss分解算法
        2.2.4 k边连通子图分解算法
    2.3 频繁社区模型
        2.3.1 时态图
        2.3.2 k-star模型
    2.4 本章小结
第3章 面向时态图的社区搜索算法
    3.1 时态图削减
        3.1.1 度区间分解
        3.1.2 邻居节点的动态更新
        3.1.3 时态图削减算法
    3.2 两个关键算法
    3.3 剪枝算法
        3.3.1 强邻居剪枝
        3.3.2 虚度剪枝
    3.4 社区搜索算法
    3.5 本章小结
第4章 实验结果与分析
    4.1 效率测试
    4.2 有效性测试
    4.3 本章小结
第5章 总结与展望
    5.1 论文工作总结
    5.2 研究工作展望
参考文献
致谢
攻读硕士学位期间的研究成果



本文编号：3777212