團為一圖中的任兩點皆有連接，亦稱為完全圖，若一團不為其它團的子圖時，則稱為極大團。在社群網路蓬勃發展的時代，群體分析變得越來越重要，透過極大團列舉演算法能快速找出關係密切的群體。Bron-Kerbosch演算法經由Tomita與Eppstein等人改良已提升不少效能，但是碰到類Moon-Moser圖時，會讓計算時間變得冗長。我們將透過切割這種稠密圖，尋找各個群組的區域極大團來降低計算時間，最後僅須組合各個群組的區域極大團，就能得到所有的全域極大團。

In a graph, a clique, also called a complete graph, is a subgraph where every two vertices are adjacent. When there is no vertex which can enlarge a clique, it is a maximal clique. The more popular social communities become, the more important network analysis is. By using algorithms of maximal clique enumeration, we can find large communities quickly. Although the Bron-Kerbosch algorithm has been improved by Tomita, Eppstein and others, it fails to deal with Moon-Moser-like graphs efficiently. By dividing this kind of graphs, we can achieve maximal clique enumeration separately to reduce computation time. In the end, we can combine local maximal cliques to get global ones easily.

[1] R. M. Karp, "Reducibility among combinatorial problems," in Complexity of computer computations: Springer, 1972, pp. 85-103.
[2] J. W. Moon and L. Moser, "On cliques in graphs," Israel journal of Mathematics, vol. 3, no. 1, pp. 23-28, 1965.
[3] E. Montes-Orozco et al., "Mexican university ranking based on maximal clique," in Educational Networking: Springer, 2020, pp. 327-395.
[4] Z. Lu, G. Cao, and T. La Porta, "Teamphone: Networking smartphones for disaster recovery," IEEE Transactions on Mobile Computing, vol. 16, no. 12, pp. 3554-3567, 2017.
[5] D. B. KC, T. Akutsu, E. Tomita, T. Seki, and A. Fujiyama, "Point matching under non-uniform distortions and protein side chain packing based on an efficient maximum clique algorithm," Genome Informatics, vol. 13, pp. 143-152, 2002.
[6] S. Butenko and W. E. Wilhelm, "Clique-detection models in computational biochemistry and genomics," European journal of operational research, vol. 173, no. 1, pp. 1-17, 2006.
[7] C. Bron and J. Kerbosch, "Algorithm 457: finding all cliques of an undirected graph," Communications of the ACM, vol. 16, no. 9, pp. 575-577, 1973.
[8] E. Tomita, A. Tanaka, and H. Takahashi, "The worst-case time complexity for generating all maximal cliques and computational experiments," Theoretical computer science, vol. 363, no. 1, pp. 28-42, 2006.
[9] M. C. Schmidt, N. F. Samatova, K. Thomas, and B.-H. Park, "A scalable, parallel algorithm for maximal clique enumeration," Journal of parallel and distributed computing, vol. 69, no. 4, pp. 417-428, 2009.
[10] D. Eppstein, M. Löffler, and D. Strash, "Listing all maximal cliques in large sparse real-world graphs," Journal of Experimental Algorithmics (JEA), vol. 18, pp. 3.1-3.21, 2013.
[11] S. Tsukiyama, M. Ide, H. Ariyoshi, and I. Shirakawa, "A new algorithm for generating all the maximal independent sets," SIAM Journal on Computing, vol. 6, no. 3, pp. 505-517, 1977.
[12] N. Chiba and T. Nishizeki, "Arboricity and subgraph listing algorithms," SIAM Journal on computing, vol. 14, no. 1, pp. 210-223, 1985.
[13] K. Makino and T. Uno, "New algorithms for enumerating all maximal cliques," in Scandinavian workshop on algorithm theory, 2004: Springer, pp. 260-272.
[14] Y. Xu, J. Cheng, and A. W.-C. Fu, "Distributed maximal clique computation and management," IEEE Transactions on Services Computing, vol. 9, no. 1, pp. 110-122, 2015.
[15] Y.-W. Wei, W.-M. Chen, and H.-H. Tsai, "Accelerating the Bron-Kerbosch algorithm for maximal clique enumeration using GPUs," IEEE Transactions on Parallel and Distributed Systems, vol. 32, no. 9, pp. 2352-2366, 2021.
[16] A. Conte, "Review of the bron-kerbosch algorithm and variations," School of Computing Science, University of Glasgow, pp. 1-9, 2013.
[17] B. Hou et al., "Efficient maximal clique enumeration over graph data," Data Science and Engineering, vol. 1, no. 4, pp. 219-230, 2016.
[18] B. A. Galler and M. J. Fisher, "An improved equivalence algorithm," Communications of the ACM, vol. 7, no. 5, pp. 301-303, 1964.
[19] J. Leskovec and A. Krevl, "SNAP Datasets: Stanford large network dataset collection," ed: Ann Arbor, MI, USA, 2014.
[20] A. Hagberg, D. Schult, and P. Swart, "Exploring network structure, dynamics, and function using Networkx Proceedings of the 7th Python in Science Conference (SciPy2008), eds Varoquaux G, Vaught T, Millman J.(Pasadena, CA) 11–15," ed, 2008.