面向时序图的K-truss社区搜索算法研究

摘要

在诸如通信网络、协作网络和社交网络的分析等应用中,边缘上通常包含时间戳.然而以前大多数的研究主要集中在识别没有时间信息的网络中的社区.大规模时序图数据管理与挖掘已经成为数据挖掘领域的一个热点问题,其应用领域十分广泛.团模型是图社区发现问题中的一个重要模型,K-truss结构是团模型的一种重要的松弛模型.对时序图中的社区挖掘问题进行研究,目标是搜索能持续存在的社区结构.由于K-团结构的搜索是一个NP难问题,采用经典的K-truss模型对社区进行建模,进而提出了一种新的适合于时序图数据的持续社区模型(k,Δ,θ)-truss.还提出了一种近似线性时间的时序图社区搜索算法,然后基于真实数据集分析算法的性能和社区挖掘的结果.实验结果表明,K-truss挖掘的效率和社区规模介于K-core与K-团之间,适合比较紧密的社区的搜索.