Discovering Cohesive Temporal Subgraphs with Temporal Density Aware Exploration  

作　　者：Chun-Xue Zhu Long-Long Lin Ping-Peng Yuan Hai Jin 朱春雪;林隆龙;袁平鹏;金海(National Engineering Research Center for Big Data Technology and System,Huazhong University of Science and Technology,Wuhan 430074,China;Service Computing Technology and System Laboratory,Huazhong University of Science and Technology,Wuhan 430074,China;Cluster and Grid Computing Laboratory,Huazhong University of Science and Technology,Wuhan 430074,China;School of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan 430074,China)

机构地区：[1]National Engineering Research Center for Big Data Technology and System,Huazhong University of Science and Technology,Wuhan 430074,China [2]Service Computing Technology and System Laboratory,Huazhong University of Science and Technology,Wuhan 430074,China [3]Cluster and Grid Computing Laboratory,Huazhong University of Science and Technology,Wuhan 430074,China [4]School of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan 430074,China

出　　处：《Journal of Computer Science & Technology》2022年第5期1068-1085,共18页计算机科学技术学报（英文版）

基　　金：The work was supported by the National Key Research and Development Program of China under Grant No.2018YFB1402802;the National Natural Science Foundation of China under Grant Nos.61932004 and 62072205.

摘　　要：Real-world networks,such as social networks,cryptocurrency networks,and e-commerce networks,always have occurrence time of interactions between nodes.Such networks are typically modeled as temporal graphs.Mining cohesive subgraphs from temporal graphs is practical and essential in numerous data mining applications,since mining cohesive subgraphs gets insights into the time-varying nature of temporal graphs.However,existing studies on mining cohesive subgraphs,such as Densest-Exact and k-truss,are mainly tailored for static graphs(whose edges have no temporal information).Therefore,those cohesive subgraph models cannot indicate both the temporal and the structural characteristics of subgraphs.To this end,we explore the model of cohesive temporal subgraphs by incorporating both the evolving and the structural characteristics of temporal subgraphs.Unfortunately,the volume of time intervals in a temporal network is quadratic.As a result,the time complexity of mining temporal cohesive subgraphs is high.To efficiently address the problem,we first mine the temporal density distribution of temporal graphs.Guided by the distribution,we can safely prune many unqualified time intervals with the linear time cost.Then,the remaining time intervals where cohesive temporal subgraphs fall in are examined using the greedy search.The results of the experiments on nine real-world temporal graphs indicate that our model outperforms state-of-the-art solutions in efficiency and quality.Specifically,our model only takes less than two minutes on a million-vertex DBLP and has the highest overall average ranking in EDB and TC metrics.

关 键 词：temporal network temporal feature distribution cohesive subgraph convex property 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]