View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        Utilising Reinforcement Learning for the Diversified Top-𝑘 Clique Search Problem

        Thumbnail
        View/Open
        Thesis.pdf (2.166Mb)
        Publication date
        2023
        Author
        Remmerden, Jesse van
        Metadata
        Show full item record
        Summary
        The diversified top-𝑘 clique search problem (DTKC) problem is a diversity graph problem in which the goal is to find a clique set of 𝑘 cliques that cover the most nodes in a graph. DTKC is a combinatorial optimisation problem and can be seen as a combination of the maximum clique problem and maximal clique enumeration. In recent years, a new research field arose that research if reinforcement learning can be used for combinatorial optimisation problems. However, no reinforcement learning algorithm exists for DTKC or any other diversity graph problem. Therefore, we propose Deep Clique Comparison Agent (DCCA), which utilises PPO, Graph Isomorphic Networks and the encode-process-decode paradigm to compose an optimal clique set. We tested DCCA for DTKC and the diversified top-𝑘 weighted clique search problem (DTKWC). Our results showed that DCCA could outperform previous methods for DTKC, but only on higher values of 𝑘, such as if 𝑘 = 50. However, we only saw this occur on simpler graphs and DCCA performed significantly worse on the other problem, DTKWC. Due to the novelty of DCCA, we believe that future research can significantly improve our results.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/43388
        Collections
        • Theses
        Utrecht university logo