A Fast Maximum Clique Algorithm Based on Network Decomposition for Large Sparse Networks
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929320227766272 |
|---|---|
| author | Fan, Tianlong Jiang, Wenjun Zhang, Yi-Cheng Lü, Linyuan |
| author_facet | Fan, Tianlong Jiang, Wenjun Zhang, Yi-Cheng Lü, Linyuan |
| contents | Finding maximum cliques in large networks is a challenging combinatorial problem with many real-world applications. We present a fast algorithm to achieve the exact solution for the maximum clique problem in large sparse networks based on efficient graph decomposition. A bunch of effective techniques is being used to greatly prune the graph and a novel concept called Complete-Upper-Bound-Induced Subgraph (CUBIS) is proposed to ensure that the structures with the potential to form the maximum clique are retained in the process of graph decomposition. Our algorithm first pre-prunes peripheral nodes, subsequently, one or two small-scale CUBISs are constructed guided by the core number and current maximum clique size. Bron-Kerbosch search is performed on each CUBIS to find the maximum clique. Experiments on 50 empirical networks with a scale of up to 20 million show the CUBIS scales are largely independent of the original network scale. This enables an approximately linear runtime, making our algorithm amenable for large networks. Our work provides a new framework for effectively solving maximum clique problems on massive sparse graphs, which not only makes the graph scale no longer the bottleneck but also shows some light on solving other clique-related problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_11862 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Fast Maximum Clique Algorithm Based on Network Decomposition for Large Sparse Networks Fan, Tianlong Jiang, Wenjun Zhang, Yi-Cheng Lü, Linyuan Social and Information Networks Data Structures and Algorithms Information Retrieval Data Analysis, Statistics and Probability 05C82(Primary), 05C80, 91D30, 68P20(Secondary) H.3.3; F.2.2; J.2 Finding maximum cliques in large networks is a challenging combinatorial problem with many real-world applications. We present a fast algorithm to achieve the exact solution for the maximum clique problem in large sparse networks based on efficient graph decomposition. A bunch of effective techniques is being used to greatly prune the graph and a novel concept called Complete-Upper-Bound-Induced Subgraph (CUBIS) is proposed to ensure that the structures with the potential to form the maximum clique are retained in the process of graph decomposition. Our algorithm first pre-prunes peripheral nodes, subsequently, one or two small-scale CUBISs are constructed guided by the core number and current maximum clique size. Bron-Kerbosch search is performed on each CUBIS to find the maximum clique. Experiments on 50 empirical networks with a scale of up to 20 million show the CUBIS scales are largely independent of the original network scale. This enables an approximately linear runtime, making our algorithm amenable for large networks. Our work provides a new framework for effectively solving maximum clique problems on massive sparse graphs, which not only makes the graph scale no longer the bottleneck but also shows some light on solving other clique-related problems. |
| title | A Fast Maximum Clique Algorithm Based on Network Decomposition for Large Sparse Networks |
| topic | Social and Information Networks Data Structures and Algorithms Information Retrieval Data Analysis, Statistics and Probability 05C82(Primary), 05C80, 91D30, 68P20(Secondary) H.3.3; F.2.2; J.2 |
| url | https://arxiv.org/abs/2404.11862 |