面向时态图的频繁社区搜索算法研究
The Research of Frequent Community Search Algorithms in Temporal Graphs
社区挖掘是图数据挖掘的一项基本任务.在现有的图数据中,图中的边上通常都包含时间信息,例如科学家合作网络,电信话务网络,微信社交网络等等.绝大多数现有的社区挖掘算法主要针对传统的不包含时态边信息的图数据,因此无法适用于时态图数据的社区挖掘.本文主要研究时态图数据的频繁社区挖掘问题.我们的目标是找出时态图上所有的频繁社区结构.在传统图数据上已有多种社区模型,譬如k-core、clique、k-truss,k-edge connectedcomponent等.但是这些社区模型都是基于传统图数据上的模型,并不能在时态图上有效的搜索出频繁社区,为了能够在时态图上进行频繁社区搜索,我们提出了全新的频繁社区模型k-star.现实世界的时态图数据通常是极为庞大的,直接在原始的时态图上进行社区搜索是十分耗时的,为了能够高效的在时态图上搜索频繁社区,我们提出了时态图削减算法.该削减算法是通过一种弱核子图的概念来进行剪枝的.实验中该算法存在两方面的技术挑战:(1)频繁节点度的计算和(2)邻居节点的动态更新.我们提出度区间分解算法实现了对频繁节点度的快速计算和邻居节点的动态更新操作.在经过削减后的时态图中,为了进一步提升搜索算法的效率,我们又提出了强邻居剪枝算法和虚度剪枝算法.最后,我们在真实世界的时态图数据集上进行了大量的测试和对比实验.通过引入时态图削减技术和两种剪枝算法实现了在大型时态图上的高效频繁社区搜索.通过比较不同模型下的社区搜索结果,我们发现本文所提出的社区模型在搜索连接紧密的频繁社区方面有着非常好的现实效果.此外,实验结果还验证了我们所提出算法的有效性和可扩展性.
- 作者：
- 张培涵
- 学位授予单位：
- 深圳大学
- 专业名称：
- 软件工程
- 授予学位：
- 硕士
- 学位年度：
- 2018年
- 导师姓名：
- 毛睿；李荣华
- 中图分类号：
- TP391.3
- 关键词：
- 时态图；社区搜索；社区模型；频繁社区；时态图削减
- Temporal Graph; Community Discovery; Community Model; Frequent Community; Temporal Graph Reduction;