{"id":157,"date":"2022-08-25T14:02:36","date_gmt":"2022-08-25T13:02:36","guid":{"rendered":"https:\/\/blogs.qub.ac.uk\/dipsa\/?p=157"},"modified":"2024-08-12T06:20:30","modified_gmt":"2024-08-12T05:20:30","slug":"approximate-maximum-weighted-clique","status":"publish","type":"post","link":"https:\/\/blogs.qub.ac.uk\/dipsa\/approximate-maximum-weighted-clique\/","title":{"rendered":"Approximate Maximum Weighted Clique"},"content":{"rendered":"\n<p class=\"has-text-align-justify\">This project aims to develop novel algorithms for the maximum weighted clique (MWC) problem, which appears in various data analysis pipelines in precision medicine. The MWC problem is NP-hard in nature, which makes it particularly challenging given the exponentially increasing amount of data it is applied to.<\/p>\n\n\n\n<p class=\"has-text-align-justify\">Although several attempts have been made to solve the maximum weighted clique problem in large graphs, there is still much opportunity for lowering the execution time necessary to find a satisfactory solution. In this project in particular we are investigating approximate algorithms for the MWC problem. We are working towards an algorithm that achieves a very high quality solution (i.e., finding a clique with weight very close to the MWC) in polynomial time.<\/p>\n\n\n\n<p class=\"has-text-align-justify\">IBM will provide industrially relevant context on knowledge extraction from graph-structured data. They have extensive experience in this area by building scalable software systems for the analysis of massive-scale graph data. They will moreover provide access to relevant datasets.<\/p>\n\n\n\n<p class=\"has-medium-font-size\"><strong>Project Members<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><a href=\"https:\/\/pure.qub.ac.uk\/en\/persons\/qasim-abbas\" target=\"_blank\" rel=\"noreferrer noopener\">Qasim Abbas<\/a> (<a href=\"https:\/\/www.qub.ac.uk\/schools\/eeecs\/\" target=\"_blank\" rel=\"noreferrer noopener\">EEECS<\/a>, <a href=\"https:\/\/www.qub.ac.uk\/Study\/PostgraduateStudy\/FundingandScholarships\/Doctoral-Training-Centres\/citigens\/CITI-GENSMeettheFellows\/\" target=\"_blank\" rel=\"noreferrer noopener\">CITI-GENS<\/a>)<\/li>\n\n\n\n<li><a href=\"http:\/\/www.eeecs.qub.ac.uk\/~H.Vandierendonck\/\" target=\"_blank\" rel=\"noreferrer noopener\">Prof. Hans Vandierendonck<\/a> (<a href=\"https:\/\/www.qub.ac.uk\/schools\/eeecs\/\">EEECS<\/a>, <a href=\"https:\/\/www.qub.ac.uk\/ecit\/DSSC\/\">DSSC<\/a>)<\/li>\n\n\n\n<li><a href=\"https:\/\/pure.qub.ac.uk\/en\/persons\/ian-overton\">Dr. Ian Overton<\/a> (<a href=\"https:\/\/www.qub.ac.uk\/schools\/mdbs\/\" target=\"_blank\" rel=\"noreferrer noopener\">MDBS<\/a>)<\/li>\n\n\n\n<li><a href=\"https:\/\/researcher.watson.ibm.com\/researcher\/view.php?person=zurich-TTE\" target=\"_blank\" rel=\"noreferrer noopener\">Dr. Matteo Manica<\/a> (<a href=\"https:\/\/research.ibm.com\/\" target=\"_blank\" rel=\"noreferrer noopener\">IBM Research Europe &#8211; Z\u00fcrich<\/a>)<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading has-medium-font-size\"><strong>Publications<\/strong><\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>QClique: Optimizing Performance and Accuracy in Maximum Weighted Clique, EURO-PAR 2024, <a href=\"https:\/\/blogs.qub.ac.uk\/dipsa\/qclique-optimizing-performance-and-accuracy-in-maximum-weighted-clique-euro-par-2024\/\" data-type=\"post\" data-id=\"3127\">link<\/a>.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading has-medium-font-size\"><strong>Funding<\/strong><\/h2>\n\n\n\n<p>This PhD project is funded by the European Union&#8217;s Horizon 2020 research and innovation program under the Marie Sklodowska-Curie Actions.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.qub.ac.uk\/Study\/PostgraduateStudy\/FundingandScholarships\/Doctoral-Training-Centres\/citigens\/AboutCITI-GENS\/\" target=\"_blank\">CITI-GENS<\/a>&nbsp;MSCA CO-FUND<\/li>\n<\/ul>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>This project aims to develop novel algorithms for the maximum weighted clique (MWC) problem, which appears in various data analysis pipelines in precision medicine. The MWC problem is NP-hard in nature, which makes it particularly challenging given the exponentially increasing amount of data it is applied to. Although several attempts have been made to solve [&hellip;]<\/p>\n","protected":false},"author":1164,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[1],"tags":[34,116,35,38],"class_list":{"0":"post-157","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-uncategorised","7":"tag-algorithm-design-and-engineering","8":"tag-biological-networks","9":"tag-graph-processing","10":"tag-high-performance-computing","11":"czr-hentry"},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/157","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\/1164"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/comments?post=157"}],"version-history":[{"count":6,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/157\/revisions"}],"predecessor-version":[{"id":3254,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/posts\/157\/revisions\/3254"}],"wp:attachment":[{"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/media?parent=157"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/categories?post=157"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.qub.ac.uk\/dipsa\/wp-json\/wp\/v2\/tags?post=157"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}