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

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.