Abstract
In real world, many applications such as social networks and biological networks can be modeled as graphs. Discovering dense sub-graphs from these graphs is an interesting study. Quasi-cliques are a type of dense graphs, which are close to the complete graphs. In this thesis, we want to find all of the maximal quasi-cliques for a target vertex in a graph. The maximal quasi-clique represents that the vertices in a quasi-clique are not totally contained by another quasi-clique. We propose an algorithm to solve this problem and use several pruning techniques to improve the performance. Moreover, we propose another algorithm to solve a special case of this problem, .i.e. finding the cliques. The experiment results reveal that our method outperforms the previous work both in real and synthetic datasets in most cases.