Incremental Maximal Clique Enumeration for Hybrid Edge Changes in Large Dynamic Graphs
Article
Yu, Ting, Jiang, Ting, Bah, Mohamed Jaward, Zhao, Chen, Huang, Hao, Liu, Mengchi, Zhou, Shuigeng, Li, Zhao and Zhang, Ji. 2024. "Incremental Maximal Clique Enumeration for Hybrid Edge Changes in Large Dynamic Graphs." IEEE Transactions on Knowledge and Data Engineering. 36 (4), pp. 1650-1666. https://doi.org/10.1109/TKDE.2023.3311398
Article Title | Incremental Maximal Clique Enumeration for Hybrid Edge Changes in Large Dynamic Graphs |
---|---|
ERA Journal ID | 17876 |
Article Category | Article |
Authors | Yu, Ting, Jiang, Ting, Bah, Mohamed Jaward, Zhao, Chen, Huang, Hao, Liu, Mengchi, Zhou, Shuigeng, Li, Zhao and Zhang, Ji |
Journal Title | IEEE Transactions on Knowledge and Data Engineering |
Journal Citation | 36 (4), pp. 1650-1666 |
Number of Pages | 16 |
Year | 2024 |
Publisher | IEEE (Institute of Electrical and Electronics Engineers) |
Place of Publication | United States |
ISSN | 1041-4347 |
1558-2191 | |
Digital Object Identifier (DOI) | https://doi.org/10.1109/TKDE.2023.3311398 |
Web Address (URL) | https://ieeexplore.ieee.org/abstract/document/10238766 |
Abstract | Incremental maximal clique enumeration (IMCE), which maintains maximal cliques in dynamic graphs, is a fundamental problem in graph analysis. A maximal clique has a solid descriptive power of dense structures in graphs. Real-world graph data is often large and dynamic. Studies on IMCE face significant challenges in the efficiency of incremental batch computation and hybrid edge changes. Moreover, with growing graph sizes, new requirements occur on indexing global maximal cliques and obtaining maximal cliques under specific vertex scope constraints. This work presents a new data structure SOMEi to maintain intermediate maximal cliques during construction. SOMEi serves as a space-efficient index to retrieve scope-constrained maximal cliques on the fly. Based on SOMEi, we design a procedure-oriented IMCE algorithm to deal with hybrid edge changes within a unified algorithm framework. In particular, the algorithm is able to process a large batch of edge changes and significantly improve the average processing time of a single edge change through an efficient pruning strategy. Experimental results on real and synthetic graph data demonstrate that the proposed algorithm outperforms all the baselines and achieves good efficiency through pruning. IEEE |
Keywords | Batch production systems; maximal clique enumeration; incremental algorithm; dense subgraph; dynamic graph; vertex scope constraint |
Contains Sensitive Content | Does not contain sensitive content |
ANZSRC Field of Research 2020 | 461299. Software engineering not elsewhere classified |
Public Notes | Files associated with this item cannot be displayed due to copyright restrictions. |
Byline Affiliations | Zhejiang Lab, China |
Wuhan University, China | |
South China Normal University, China | |
Fudan University, China | |
Hangzhou Yugu Technology, China | |
University of Southern Queensland |
Permalink -
https://research.usq.edu.au/item/z273v/incremental-maximal-clique-enumeration-for-hybrid-edge-changes-in-large-dynamic-graphs
36
total views0
total downloads1
views this month0
downloads this month