Research on Sustained Cohesive Subgraph Search Algorithm in Large Temporal Graphs

doi:10.3778/j.issn.1002-8331.2012-0563

Abstract

Abstract: Temporal graph is a kind of graph structure with timestamps on its edges, where the timestamps indicate the time when the edges appear, that is, the graph evolves constantly by time. The problem of cohesive subgraph mining for graph data has very strong practical significance. Recently, most of the existing work in temporal graphs focus on the problem of cohesive subgraph detection, which aims to find all the target subgraphs in the temporal graph. However, when the size of the temporal graph becoming too large, the problem of cohesive subgraph detection will go extremely impractical and ineffective. The purpose of this paper is to study the problem of cohesive subgraph search, which has been overlooked for long. Specifically, given a query vertex in the temporal graph, the goal is to find a cohesive subgraph that sustaining over a period and include the query vertex. That is the subgraph satisfies the time sustainability. To this end, two efficient searching algorithms are designed based on global reduction and local expansion to cope with different application scenarios. A large number of experiments on four real networks verify the efficiency of the proposed algorithms.

Key words: temporal graph, sustained cohesive subgraph, efficient searching algorithm

摘要： 时序图是一种边上带有时间戳的图结构，其中边上的时间戳表示该边出现时间，即图随时间变化不断变化。图数据中的稠密子图挖掘问题具有非常强烈的现实意义。目前，时序图中大多数现有的工作都集中在稠密子图检测问题，该问题目标是找到时序图中所有的目标子图。然而，当时序图的规模过大时，这一问题将变得极其复杂且收效甚微。旨在研究在时序图中长期被忽视的稠密子图搜索问题。具体来讲，给定一个图中的查询顶点，目标是找到一个在一段时间内持续存在且包含该查询点的稠密子图，即该子图满足时间持续性。从全局削减和局部扩展两种不同的思路出发，设计两种不同的高效稠密子图搜索算法，用以应对不同的应用场景。在四个真实世界网络中的大量实验，验证了提出算法的高效性。

关键词: 时序图, 持续性稠密子图, 高效搜索算法

LI Yuan, LIU Jinsheng, ZHAO Huiqun, SUN Jing. Research on Sustained Cohesive Subgraph Search Algorithm in Large Temporal Graphs[J]. Computer Engineering and Applications, 2022, 58(3): 119-126.

李源, 刘金生, 赵会群, 孙晶. 大规模时序图中持续性稠密子图搜索算法研究[J]. 计算机工程与应用, 2022, 58(3): 119-126.

References

[1] LATHIA N，HAILES S，CAPRA L.kNN CF：a temporal social network[C]//Proceedings of the 2008 ACM Conference on Recommender Systems，2008：227-234.
[2] YU C，ZHANG Z，LIN C，et al.Can data-driven precision marketing promote user AD clicks? Evidence from advertising in WeChat moments[J].Industrial Marketing Management，2020，90：481-492.
[3] LAPPAS T，LIU K，TERZI E.Finding a team of experts in social networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2009：467-476.
[4] SHEN X，YI L，JIANG X，et al.Neighbor affinity based algorithm for discovering temporal protein complex from dynamic PPI network[J].Methods，2016，110：90-96.
[5] LI R H，SU J，QIN L，et al.Persistent community search in temporal networks[C]//2018 IEEE 34th International Conference on Data Engineering（ICDE），2018：797-808.
[6] WU H，CHENG J，LU Y，et al.Core decomposition in large temporal graphs[C]//2015 IEEE International Conference on Big Data，2015：649-658.
[7] MA S，HU R，WANG L，et al.Fast computation of dense temporal subgraphs[C]//2017 IEEE 33rd International Conference on Data Engineering（ICDE），2017：361-372.
[8] SEMERTZIDIS K，PITOURA E，TERZI E，et al.Finding lasting dense subgraphs[J].Data Mining and Knowledge Discovery，2019，33（5）：1417-1445.
[9] HUANG X，CHENG H，QIN L，et al.Querying k-truss community in large and dynamic graphs[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data，2014：1311-1322.
[10] FANG Y，CHENG R，CHEN Y，et al.Effective and efficient attributed community search[J].The VLDB Journal，2017，26（6）：803-828.
[11] BI F，CHANG L，LIN X，et al.An optimal and progressive approach to online search of top-k influential communities[J].arXiv：1711.05857，2017.
[12] CHEN L，LIU C，ZHOU R，et al.Maximum co-located community search in large scale social networks[J].Proceedings of the VLDB Endowment，2018，11（10）：1233-1246.
[13] DOROGOVTSEV S N，GOLTSEV A V，MENDES J F F.K-core organization of complex networks[J].Physical Review Letters，2006，96（4）：040601.
[14] JANSON S，LUCZAK M J.A simple solution to the k-core problem[J].Random Structures & Algorithms，2007，30（1/2）：50-62.
[15] ALVAREZ-HAMELIN J I，DALL’ASTA L，BARRAT A，et al.Large scale networks fingerprinting and visualization using the k-core decomposition[C]//Advances in Neural Information Processing Systems，2006：41-50.