We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Continuous community search with attribute constraints in temporal graphs.
- Authors
Du, Ming; Ma, Wanting; Tan, Yuting; Zhou, Junfeng
- Abstract
The problem of continuous community search in temporal graphs aims to identify dense subgraphs that exist continuously over time, which is widely used in sociology, biology, communication, and other fields. Existing methods can find communities that satisfy both temporal and structural constraints, but did not consider constraints on vertex attributes. In this paper, we investigate the continuous community search problem with attribute constraints in temporal graphs. Specifically, we aim to identify graphs that meet temporal, structural, and attribute constraints. To solve the problem efficiently, we first propose a pruning enumeration algorithm (PRUNE_ENUM), which uses the properties of the lower bound of vertices of k-core, the upper bound of attribute intersection, and subgraph continuity to prune useless search space during computation. We then propose an optimized enumeration algorithm (FILTER_ENUM) that first generates much smaller subgraphs using subsets of the given query attributes, then takes these smaller subgraphs as input for enumeration. During the enumeration, we propose two pruning rules to reduce search space based on attribute similarity and subgraph maximization to improve the efficiency. We conduct comparative experiments on four real-world temporal networks, and the experimental results demonstrate the high efficiency of our algorithms.
- Subjects
TIME-varying networks; SOCIAL problems; SUBGRAPHS; PROBLEM solving
- Publication
Journal of Supercomputing, 2023, Vol 79, Issue 18, p21089
- ISSN
0920-8542
- Publication type
Article
- DOI
10.1007/s11227-023-05451-5