University of Twente Student Theses


Finding maximal cliques in uniform hypergraphs using Baum-Eagon inequality

Melinceanu, Victor (2023) Finding maximal cliques in uniform hypergraphs using Baum-Eagon inequality.

[img] PDF
Abstract:In this paper, we are going to analyze the performance of an algorithm for finding maximal cliques in K-uniform hypergraphs. The algorithm is based on a replicator dynamics method using Baum-Eagon inequality. The following algorithm has been researched in the past on circulant K-hypergraphs, but in this paper, we are going to use a dataset composed of both circulant K-hypergraphs and K-hypertrees. We also present an optimization for the algorithm, that makes each iteration faster by a factor of n (number of nodes) than what the current state of the art presents. We do this through an easy combinatorial optimization. A slight optimization for memory complexity when working with K-hypergraphs is also proposed. We have tested the fast implementation both in Python and in C++, showing that C++ is 15 times faster on average. We also present for the first time an algorithm to generate random K-hypertrees. An interesting observation made during the testing phase is that the size of every converged clique is always exactly k, which is the cardinality of the hyperedge. We provide a new theorem and the proof, stating the maximum clique size in a K-hypertree is always exactly k. The algorithm was tested on a dataset consisting of 500 tests all converging to a correct maximal clique. The results show that the convergence of the algorithm in terms of iterations depends on k and the number of hyperedges, and not on the number of nodes.
Item Type:Essay (Bachelor)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics, 54 computer science
Programme:Computer Science BSc (56964)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page