| 大规模时序图中持续性稠密子图搜索算法研究 |
| |
| 引用本文： | 李源,刘金生,赵会群,孙晶.大规模时序图中持续性稠密子图搜索算法研究[J].计算机工程与应用,2022,58(3):119-126. |
| |
| 作者姓名： | 李源 刘金生 赵会群 孙晶 |
| |
| 作者单位： | 北方工业大学 信息学院，北京 100144 |
| |
| 基金项目： | 国家自然科学基金青年项目(61902004);国家自然科学基金面上项目(61672041,61977001);北京市教委科技项目(KM202010009009);北方工业大学科研启动经费。 |
| |
| 摘 要： | 时序图是一种边上带有时间戳的图结构，其中边上的时间戳表示该边出现时间，即图随时间变化不断变化。图数据中的稠密子图挖掘问题具有非常强烈的现实意义。目前，时序图中大多数现有的工作都集中在稠密子图检测问题，该问题目标是找到时序图中所有的目标子图。然而，当时序图的规模过大时，这一问题将变得极其复杂且收效甚微。旨在研究在时序图中长期被忽视的稠密子图搜索问题。具体来讲，给定一个图中的查询顶点，目标是找到一个在一段时间内持续存在且包含该查询点的稠密子图，即该子图满足时间持续性。从全局削减和局部扩展两种不同的思路出发，设计两种不同的高效稠密子图搜索算法，用以应对不同的应用场景。在四个真实世界网络中的大量实验，验证了提出算法的高效性。
|
| 关 键 词： | 时序图 持续性稠密子图 高效搜索算法 |
Research on Sustained Cohesive Subgraph Search Algorithm in Large Temporal Graphs |
| |
| 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. |
| |
| Authors: | LI Yuan LIU Jinsheng ZHAO Huiqun SUN Jing |
| |
| Affiliation: | School of Information Science and Technology, North China University of Technology, Beijing 100144, China |
| |
| 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. |
| |
| Keywords: | temporal graph sustained cohesive subgraph efficient searching algorithm |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
|
