Efficient Maximal Frequent Group Enumeration in Temporal Bipartite Graphs
Proceedings of the VLDB Endowment · 2024-07 · 17 (11) · 3243-3255
DOI: 10.14778/3681954.3681997 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 30.08.2024. Verfasst von Yanping Wu und 6 weiteren Autor:innen. Die Arbeit wurde bisher 18-mal zitiert (Crossref) und nennt 52 Literaturangaben.
Abstract (Originalsprache)
Cohesive subgraph mining is a fundamental problem in bipartite graph analysis. In reality, relationships between two types of entities often occur at some specific timestamps, which can be modeled as a temporal bipartite graph. However, the temporal information is widely neglected by previous studies. Moreover, directly extending the existing models may fail to find some critical groups in temporal bipartite graphs, which appear in a unilateral (i.e., one-layer) form. To fill the gap, in this paper, we propose a novel model, called maximal λ -frequency group (MFG). Given a temporal bipartite graph 𝒢 = (U, V, ℰ ), a vertex set V S ⊆ V is an MFG if i ) there are no less than λ timestamps, at each of which V S can form a ( τ U , τ V )-biclique with some vertices in U at the corresponding snapshot, and ii ) it is maximal. To solve the problem, a filter-and-verification (FilterV) method is proposed based on the Bron-Kerbosch framework, incorporating novel filtering techniques to reduce the search space and array-based strategy to accelerate the frequency and maximality verification. Nevertheless, the cost of frequency verification in each valid candidate set computation and maximality check could limit the scalability of FilterV to larger graphs. Therefore, we further develop a novel verification-free (VFree) approach by leveraging the advanced dynamic counting structure proposed. Theoretically, we prove that VFree can reduce the cost of each valid candidate set computation in FilterV by a factor of O (| V |). Furthermore, VFree can avoid the explicit maximality verification because of the developed search paradigm. Finally, comprehensive experiments on 15 real-world graphs are conducted to demonstrate the efficiency and effectiveness of the proposed techniques and model.
Zitieren
APA
Wu, Y., Sun, R., Wang, X., Wen, D., Zhang, Y., Qin, L., & Lin, X. (2024). Efficient Maximal Frequent Group Enumeration in Temporal Bipartite Graphs. Proceedings of the VLDB Endowment, 17(11), 3243-3255. https://doi.org/10.14778/3681954.3681997
Vancouver
Wu Y, Sun R, Wang X, Wen D, Zhang Y, Qin L, et al. Efficient Maximal Frequent Group Enumeration in Temporal Bipartite Graphs. Proceedings of the VLDB Endowment. 2024;17(11):3243-3255. doi:10.14778/3681954.3681997
BibTeX
@article{Wu2024,
author = {Wu, Yanping and Sun, Renjie and Wang, Xiaoyang and Wen, Dong and Zhang, Ying and Qin, Lu and Lin, Xuemin},
title = {Efficient Maximal Frequent Group Enumeration in Temporal Bipartite Graphs},
journal = {Proceedings of the VLDB Endowment},
year = {2024},
volume = {17},
number = {11},
pages = {3243--3255},
doi = {10.14778/3681954.3681997}
}
EUVIMED