Alternative set-theoretical algorithms for efficient computations of cliques in Vietoris-Rips complexes
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910847327010816 |
|---|---|
| author | de Souza, Danillo Barros Teodomiro, Jonatas Santos, Fernando A. N. Desroches, Mathieu Rodrigues, Serafim |
| author_facet | de Souza, Danillo Barros Teodomiro, Jonatas Santos, Fernando A. N. Desroches, Mathieu Rodrigues, Serafim |
| contents | Identifying cliques in dense networks remains a formidable challenge, even with significant advances in computational power and methodologies. To tackle this, numerous algorithms have been developed to optimize time and memory usage, implemented across diverse programming languages. Yet, the inherent NP-completeness of the problem continues to hinder performance on large-scale networks, often resulting in memory leaks and slow computations. In the present study, we critically evaluate classic algorithms to pinpoint computational bottlenecks and introduce novel set-theoretical approaches tailored for network clique computation. Our proposed algorithms are rigorously implemented and benchmarked against existing Python-based solutions, demonstrating superior performance. These findings underscore the potential of set-theoretical techniques to drive substantial performance gains in network analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_14593 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Alternative set-theoretical algorithms for efficient computations of cliques in Vietoris-Rips complexes de Souza, Danillo Barros Teodomiro, Jonatas Santos, Fernando A. N. Desroches, Mathieu Rodrigues, Serafim Combinatorics Identifying cliques in dense networks remains a formidable challenge, even with significant advances in computational power and methodologies. To tackle this, numerous algorithms have been developed to optimize time and memory usage, implemented across diverse programming languages. Yet, the inherent NP-completeness of the problem continues to hinder performance on large-scale networks, often resulting in memory leaks and slow computations. In the present study, we critically evaluate classic algorithms to pinpoint computational bottlenecks and introduce novel set-theoretical approaches tailored for network clique computation. Our proposed algorithms are rigorously implemented and benchmarked against existing Python-based solutions, demonstrating superior performance. These findings underscore the potential of set-theoretical techniques to drive substantial performance gains in network analysis. |
| title | Alternative set-theoretical algorithms for efficient computations of cliques in Vietoris-Rips complexes |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2502.14593 |