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

Research on K-truss Community Search Algorithm for Temporal Networks

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

In applications such as communication network,collaboration network and social network analysis,time stamps are usually included on the edge.However,most previous studies focus on identifying communities in networks without time information.Large-scale temporal networks management and mining has become a hot issue in the field of data mining,and its application is very extensive.Clique model is an important model in graph community discovery,and K-truss structure is an important relaxation model of clique model.In this paper,the problem of community mining in temporal networks is studied,and the goal is to search for community structure that can persist.Since the search of K-clique structure is a NP-hard problem,this paper uses the classical K-truss model to model the community,and then proposes a new continuous community model(k,Δ,θ)-truss suitable for time series graph data.This paper also proposes a temporal community search algorithm with approximate linear time,and then analyzes the performance of the algorithm and the results of community mining based on real datasets.The experimental results show that the efficiency and community size of K-truss mining are between K-core and Kclique,and it is suitable for the search of slightly closer communities.