Research on K-truss Community Search Algorithm for Temporal Networks

doi:10.3778/j.issn.1673-9418.1909050

Abstract

Abstract:

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 K-clique, and it is suitable for the search of slightly closer communities.

Key words: K-truss, temporal networks, community mining

摘要：

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

关键词: K-truss, 时序图, 社区挖掘

XU Lantian, LI Ronghua, WANG Guoren, WANG Biao. Research on K-truss Community Search Algorithm for Temporal Networks[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(9): 1482-1489.

徐兰天，李荣华，王国仁，王彪. 面向时序图的K-truss社区搜索算法研究[J]. 计算机科学与探索, 2020, 14(9): 1482-1489.

References

[1] Hao F, Li S, Min G Y, et al. An efficient approach to generating location-sensitive recommendations in ad-hoc social network environments[J]. IEEE Transactions on Services Computing, 2015, 8(3): 520-533.
[2] Chen J Y, Za?ane O R, Goebel R. A visual data mining approach to find overlapping communities in networks [C]//Proceedings of the 2009 International Conference on Advances in Social Network Analysis and Mining, Athens, Jul 20-22, 2009. Washington: IEEE Computer Society, 2009: 338-343.
[3] Shang H L, Tao Y D, Gao Y, et al. An improved invariant for matching molecular graphs based on VF2 algorithm[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2015, 45(1): 122-128.
[4] Liu J Z, Lee Y T. A graph-based method for face identification from a single 2D line drawing[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(10): 1106-1119.
[5] Kumar A, Kim J, Feng D G, et al. Graph-based retrieval of PET-CT images using vector space embedding[C]//Proceedings of the 26th IEEE International Symposium on Computer-Based Medical Systems, Porto, Jun 20-22, 2013. Washington: IEEE Computer Society, 2013: 413-416.
[6] Wang J, Cheng J. Truss decomposition in massive networks[J]. Proceedings of the VLDB Endowment, 2012, 5(9): 812-823.
[7] Wang Y. Research on K-truss-based graph community discovery algorithm[D]. Qinhuangdao: Yanshan University, 2016.王岩. 基于K-truss的图社区发现算法研究[D]. 秦皇岛: 燕山大学, 2016.
[8] Wang B, Zhou G, Zhang F J. GAS based K-truss decomposition method[J]. Application Research of Computers, 2018, 35(6): 1691-1695.王邠, 周刚, 张凤娟. 基于GAS模型的K-truss分解算法[J]. 计算机应用研究, 2018, 35(6): 1691-1695.
[9] Alemi M, Haghighi H. KTMiner: distributed K-truss detection in big graphs[J]. Information Systems, 2019, 83: 195-216.
[10] Qi B L. Research and implementation of subgraph pattern mining algorithm for uncertain graph data[D]. Shenyang: Northeast University, 2013.齐宝雷. 面向不确定图数据的子图模式挖掘算法的研究与实现[D]. 沈阳: 东北大学, 2013.
[11] Wei T Z. Research on close community query algorithms based on K-truss[D]. Qinhuangdao: Yanshan University, 2018.魏天柱. 基于K-truss的紧密社区查询算法研究[D]. 秦皇岛: 燕山大学, 2018.
[12] Yang L. Identification of the most influential nodes based on diffusion K-truss decomposition algorithm and its application[D]. Nanjing: Nanjing University of Posts and Telecommunications, 2018.杨李. 基于扩散K-truss分解算法识别最有影响力节点及其应用研究[D]. 南京: 南京邮电大学, 2018.
[13] Wang C C. Design and implementation of community search algorithms in social networks[D]. Harbin: Heilongjiang University, 2018.王成成. 社会网络中社区搜索算法设计与实现[D]. 哈尔滨: 黑龙江大学, 2018.
[14] Han W T. Research on data processing technology of sequence diagram[D]. Beijing: Tsinghua University, 2015. 韩文弢. 时序图数据处理技术研究[D]. 北京: 清华大学, 2015.
[15] Paranjape A, Benson A R, Leskovec J. Motifs in temporal networks[C]//Proceedings of the 10th ACM International Conference on Web Search and Data Mining, Cambridge, Feb 6-10, 2017. New York: ACM, 2017: 601-610.
[16] Wu H H, Cheng J, Lu Y, et al. Core decomposition in large temporal graphs[C]//Proceedings of the 2015 IEEE International Conference on Big Data, Santa Clara, Oct 29-Nov 1, 2015. New York: ACM, 2015: 649-658.
[17] Li R H, Su J, Qin L, et al. Persistent community search in temporal networks[C]//Proceedings of the 34th IEEE International Conference on Data Engineering, Paris, Apr 16-19, 2018. Washington: IEEE Computer Society, 2018: 797-808.