Implementation of a maximum clique search procedure on CUDA

Paweł Daniluk (), Grzegorz Firlik and Bogdan Lesyng
Additional contact information
Paweł Daniluk: Samsung Research and Development Institute Poland
Grzegorz Firlik: University of Warsaw
Bogdan Lesyng: Mossakowski Medical Research Centre, Polish Academy of Sciences

Journal of Heuristics, 2019, vol. 25, issue 2, No 4, 247-271

Abstract: Abstract We present a novel implementation of a Motzkin–Straus-based iterative clique-finding algorithm for GPUs. The well-known iterative approach is enhanced by an annealing variant, where better convergence is obtained by introducing an additional parameter that eliminates certain local maxima, and by an attenuation variant, where the search is repeated several times and known cliques are attenuated by reducing the edge weights. The proposed solution belongs to a global optimization class of methods. It is particularly well suited to large and/or dense graphs, and outperforms other popular clique-finding methods. Therefore, it could be useful in many practical applications related to graph representations of the structures and/or dynamics of complex systems. The proposed algorithm was chosen on the basis of its portability to GPUs. Our implementation includes optimizations aimed at maximizing utilization of GPU cores by delaying some auxiliary computations and performing them simultaneously with the main matrix-vector multiplication. It achieves an average speedup of up to $$20\,\times $$ 20 × over the CPU version, depending on the graph size and density. CUDA-MS is available under the GPL license.

Keywords: Graphs; Cliques; Motzkin–Straus; Replicator equations; Clique-finding; GPU; Implementation (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-018-9393-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:25:y:2019:i:2:d:10.1007_s10732-018-9393-x

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-018-9393-x

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().