تقرير
Efficient Enumeration of Large Maximal k-Plexes
| العنوان: | Efficient Enumeration of Large Maximal k-Plexes |
|---|---|
| المؤلفون: | Cheng, Qihao, Yan, Da, Wu, Tianhao, Yuan, Lyuheng, Cheng, Ji, Huang, Zhongyi, Zhou, Yang |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms, Computer Science - Distributed, Parallel, and Cluster Computing |
| الوصف: | Finding cohesive subgraphs in a large graph has many important applications, such as community detection and biological network analysis. Clique is often a too strict cohesive structure since communities or biological modules rarely form as cliques for various reasons such as data noise. Therefore, $k$-plex is introduced as a popular clique relaxation, which is a graph where every vertex is adjacent to all but at most $k$ vertices. In this paper, we propose a fast branch-and-bound algorithm as well as its task-based parallel version to enumerate all maximal $k$-plexes with at least $q$ vertices. Our algorithm adopts an effective search space partitioning approach that provides a lower time complexity, a new pivot vertex selection method that reduces candidate vertex size, an effective upper-bounding technique to prune useless branches, and three novel pruning techniques by vertex pairs. Our parallel algorithm uses a timeout mechanism to eliminate straggler tasks, and maximizes cache locality while ensuring load balancing. Extensive experiments show that compared with the state-of-the-art algorithms, our sequential and parallel algorithms enumerate large maximal $k$-plexes with up to $5 \times$ and $18.9 \times$ speedup, respectively. Ablation results also demonstrate that our pruning techniques bring up to $7 \times$ speedup compared with our basic algorithm. Comment: Accepted by EDBT2025. Camera-ready version |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2402.13008 |
| رقم الأكسشن: | edsarx.2402.13008 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |