Indexed by: Essay collection

First Author: Yifei Zhang

Correspondence Author: Pingpeng Yuan

Co-author: Longlong Lin,Hai Jin

Journal: The 27th International Conference on Database Systems for Advanced Applications（DASFAA 2022）

Included Journals: EI

Affiliation of Author(s): 计算机科学与技术学院

Discipline: Engineering

First-Level Discipline: Computer Science and Technology

Funded by: 自然科学基金

Document Type: C

Volume: 13245

Key Words: Temporal networks；Community search；k-core

Date of Publication: 2022-04-08

Abstract: Community search, retrieving the cohesive subgraph which contains the user-specified query vertex, has been widely touched over the past decades. The existing studies on community search mainly focus on static networks. However, real-world networks, such as scientific cooperation networks and communication networks, usually are temporal networks whose each edge is associated with timestamps. Therefore, the previous methods do not work when handling temporal networks. Inspired by this, we study the problem of identifying the significant engagement community to which the user-specified query belongs. Specifically, given an integer k and a query vertex u, then we search for the subgraph H which satisfies (i) u∈H; (ii) the de-temporal graph of H is a connected k-core; (iii) In H that u has the maximum engagement level. To address our problem, we first develop a top-down greedy peeling algorithm named TDGP, which iteratively removes the vertices with the maximum temporal degree. To further boost the efficiency, we then design a bottom-up local search algorithm named BULS with several powerful pruning strategies. Lastly, we empirically show the superiority of our proposed solutions on six real-world temporal graphs.

Links to published journals: https://link.springer.com/chapter/10.1007/978-3-031-00123-9_20