在現實世界中，許多的網路應用都可以被模組化成圖形，像是社交網絡或是生物網路等。在這些圖形上尋找一些密集的子圖集團是一個有趣的研究。這些密集的子圖集團有一種我們稱為類完全圖，它是一種近似完全圖的圖形。在本篇論文中，我們想要針對圖形上特定的一個目標點v，找出所有包含v點的類完全圖，而且這些類完全圖必須要是最大的。最大的類完全圖代表不會有一個更大的類完全圖可以包含自己。我們準備了一個演算法來解決此問題並且提出了幾種改善的法方能夠增進此演算法的性能。此外我們針對這個問題中的特殊情況又提出了另一個演算法來解決它。我們在實驗部分做了兩組人造資料集以及一組實際資料集。實驗結果顯示我們的方法和過去的方法比較，在大部分的情況下都有較好的效率。

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.

Table of Contents
Acknowledgment
Abstract
摘要
Table of Contents
List of Figures
1 Introduction
2 Related Works
3 Preliminaries
4 Approaches to finding all maximal quasi-cliques for a target vertex
4.1 Quick Algorithm.
4.2 Target-Extending Algorithm
4.3 Special case
4.3.1 Target-Clique Algorithm
5 Performance Evaluations
5.1 Experiment Setup
5.2 Experiment Results
6 Conclusions
7 Future works
7.1 In weighted network graphs
7.2 Multiple target vertices
References

[AL08] N. Agarwal, H. Liu, L. Tang, and P. S. Yu. Identifying the Influential Bloggers in a Community. In WSDM2008.
[AR02]J. Abello, M. G. C. Resende, and S. Sudarsky. Massive quasi-clique detection. In LATIN2002.
[BH07] M. Brunato, H. H. Hoos, and R. Battiti. On Effectively Finding Maximal Quasi-Cliques in Graphs. In LION2007.
[DW06] N. Du, B. Wu, L. Xu, B. Wang, and X. Pei. A Parallel Algorithm for Enumerating All Maximal Cliques in Complex Network. In ICDMW’2006.
[FN06] E. Fratkin, B. T. Naughton, D. L. Brutlag, and S. Batzoglou.MotifCut: regulatory motifs finding with maximum density sub-graphs. In ISMB2006.
[GB08] A. Goyal, F. Bonchi, and L. V. S. Lakshmanan. Discovering Leaders from Community Actions. In CIKM2008.
[GK05] D. Gibson, R. Kumar, and A. Tomkins. Discovering large dense subgraphs in massive graphs. In VLDB2005.
[LL05] M. A. Langston, L. Lin, and X. Peng. A combinatorial approach to theanalysis of differential gene expression data: The use of graph algorithms for disease prediction and screening. Methods of Microarray Data Analysis IV. 2005.
[LW08] G. Liu and L. Wong. Effective Pruning Techniques for Mining Quasi-cliques. In PAKDD 2008.
[SA10]M. Sozio and A. Gionis. The community-search problem and how to plan a successful cocktail party. In KDD2010.
[TB13] C. E. Tsourakakis, F. Bonchi, A. Gionis, F. Gullo, and M. A. Tsiarli. Denser than the Densest Subgraph: Extracting Optimal Quasi-Cliques with Quality Guarantees. In KDD2013.
[TT06] E.Tomita, A. Tanaka, and H. Takahashi. The worst-case time complexity for generating all maximal cliques and computational experiments. In Theoretical Computer Science, TCS2006.
[XG13] J. Xiang, C. Guo, and A. Aboulnaga. Scalable Maximum Clique Computation Using MapReduce. In ICDM2013.
[ZC07] L. Zou, L. Chen, and Y. Lu. Top-K Subgraph Matching Query in a Large Graph. In PIKM 2007.
[ZL10] Z. Zou, J. Li, H. Gao, and S. Zhang. Finding Top-k Maximal Cliques in an Uncertain Graph. In ICDE2010.