Indexed by: Journal paper

First Author: Chunxue Zhu

Correspondence Author: Pingpeng Yuan

Co-author: Longlong Lin,Hai Jin

Journal: Journal of Computer Science and Technology

Affiliation of Author(s): Huazhong University of Science & Technology

Funded by: 自然科学基金

Key Words: Temporal Networks, Temporal Feature Distribution, Cohesive Subgraphs, Convex Property

Abstract: Real-world networks, such as social networks, cryptocurrency networks and e-commerce networks, often have occurrence time of interactions between nodes. Such networks are typically modeled as temporal graphs. Mining cohesive subgraphs from temporal graph is practical and essential in numerous data mining applications since it can get insights into the time-varying nature of temporal graphs. However, existing studies on mining cohesive subgraphs are mainly tailored for static graphs, where there is no temporal information on each edge. So, those cohesive subgraph models cannot indicate both temporal and structural characteristics of subgraphs. Here, we explore the model of cohesive temporal subgraphs by incorporating both evolving and structural characteristics of temporal subgraphs. Unfortunately, the volume of time intervals in a temporal network is quadratic. So, 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 experiments on nine real-world temporal graphs indicate that our proposed solutions are indeed efficient, effective, and scalable