{"id":3127,"date":"2024-05-15T13:30:00","date_gmt":"2024-05-15T12:30:00","guid":{"rendered":"https:\/\/blogs.qub.ac.uk\/dipsa\/?p=3127"},"modified":"2024-08-29T07:01:55","modified_gmt":"2024-08-29T06:01:55","slug":"qclique-optimizing-performance-and-accuracy-in-maximum-weighted-clique-euro-par-2024","status":"publish","type":"post","link":"https:\/\/blogs.qub.ac.uk\/dipsa\/qclique-optimizing-performance-and-accuracy-in-maximum-weighted-clique-euro-par-2024\/","title":{"rendered":"QClique: Optimizing Performance and Accuracy in Maximum Weighted Clique &#8211; Euro-Par 2024"},"content":{"rendered":"\n<p><strong>30th International European Conference on Parallel and Distributed Computing (Euro-Par 2024)<\/strong><\/p>\n\n\n\n<p><strong>DOI:<\/strong> <span style=\"text-decoration: underline\"><a href=\"https:\/\/doi.org\/10.1007\/978-3-031-69583-4_7\" target=\"_blank\" rel=\"noreferrer noopener\">10.1007\/978-3-031-69583-4_7<\/a><\/span><br><a href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2024\/06\/QClique.pdf\" target=\"_blank\" rel=\"noreferrer noopener\"><strong>PDF Version <\/strong><\/a><\/p>\n\n\n\n<p><\/p>\n\n\n\n<p class=\"has-medium-font-size\"><strong>Abstract<\/strong><\/p>\n\n\n\n<p class=\"has-text-align-justify\">The Maximum Weighted Clique(MWC) problem remains challenging due to its unfavourable time complexity.In this paper, we analyze the execution of exact search-based MWC algorithms and show that high-accuracy weighted cliques can be discovered in the early stages of the execution if searching the combinatorial space is performed systematically.<\/p>\n\n\n\n<p class=\"has-text-align-justify\">Based on this observation, we introduce QClique as an approximate MWC algorithm that processes the search space as long as better cliques are expected. QClique uses a tunable parameter to trade-off between accuracy vs. execution time and delivers 4.7-$82.3 time speedup in comparison to previous state-of-the-art MWC algorithms while providing 91.4% accuracy and achieves a parallel speedup of up to 56x on 128 threads.<\/p>\n\n\n\n<p class=\"has-text-align-justify\">Additionally, QClique accelerates the exact MWC computation by replacing the initial clique of the exact algorithm. For WLMC, an exact state-of-the-art MWC algorithm, this results in 3.3x on average.<\/p>\n\n\n\n<p class=\"has-medium-font-size\"><strong>Code<\/strong><\/p>\n\n\n\n<p><a href=\"https:\/\/github.com\/DIPSA-QUB\/QClique\" target=\"_blank\" rel=\"noreferrer noopener\">https:\/\/github.com\/DIPSA-QUB\/QClique<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>30th International European Conference on Parallel and Distributed Computing (Euro-Par 2024) DOI: 10.1007\/978-3-031-69583-4_7PDF Version Abstract The Maximum Weighted Clique(MWC) problem remains challenging due to its unfavourable time complexity.In this paper, we analyze the execution of exact search-based MWC algorithms and &hellip; <a href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/qclique-optimizing-performance-and-accuracy-in-maximum-weighted-clique-euro-par-2024\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1315,"featured_media":3137,"comment_status":"closed","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[1],"tags":[116,125,35,38,126,66,19],"class_list":["post-3127","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-uncategorised","tag-biological-networks","tag-clique-counting","tag-graph-processing","tag-high-performance-computing","tag-max-weight-cliques","tag-real-world-graphs","tag-source-code"],"jetpack_featured_media_url":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-content\/uploads\/sites\/14\/2024\/06\/Jun-17-1.jpg","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/3127","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/users\/1315"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/comments?post=3127"}],"version-history":[{"count":3,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/3127\/revisions"}],"predecessor-version":[{"id":3293,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/3127\/revisions\/3293"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/media\/3137"}],"wp:attachment":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/media?parent=3127"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/categories?post=3127"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/tags?post=3127"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}