次聚合體問題是在一張無向圖 G 中給定一正整數 k ，找出一個子集合 S，使得 S 在 G 中的誘導子圖 (induced subgraph)每個點的鄰居個數至少會有 S 的點數減去 k 個，在圖中找出一組點數最多的次聚合體即為最大次聚合體問題。透過這個圖形問題可以幫助我們了解社群網路的架構 。在這篇文章中，我們針對這個問題提出一個基於交換法則的啟發式演算法，從產生一個隨機挑選的初始解開始，我們在不同情況下用使用三種交換算子來增加現有解的大小。我們在許多圖上跑時間我們的演算法，從實驗數據中顯示，基於交換法則的啟發式演算法可以找到很好的解，與前人的方法比較來看，我們的演算法在密度大的圖中勝過他們。

The maximum k-plex problem is intended to relax the clique de nition with maximum cardinality. It helps people understand the structures of networks by considering them a problem of graph clustering; therefore, it is a useful model for social network analysis. In this paper, we propose a swap-based heuristic algorithm for the maximum k-plex problem. Starting with a randomly selected solution, we use three types of swap operators to en-
large our current solution in di erent situations. The results of experiments conducted on various graphs from two benchmarks demonstrated that our proposed algorithm achieved desirable performance on speci c graphs compared with other algorithms.

[1] J. Abello, M. G. Resende, S. Sudarsky, (2002, April). Massive quasi-clique detection.
In Latin American symposium on theoretical informatics (pp. 598-612). Springer,
Berlin, Heidelberg.
[2] R. D. Alba, (1973). A graph-theoretic de nition of a sociometric clique. Journal of
Mathematical Sociology, 3(1), 113-126.
[3] B. Balasundaram, S. Butenko, I. V. Hicks. (2011). Clique relaxations in social network
analysis: The maximum k-plex problem. Operations Research, 59(1), 133-142.
[4] J. M. Bourjolly, G. Laporte, G. Pesant, (2000). Heuristics for nding k-clubs in an
undirected graph. Computers and Operations Research, 27(6), 559-569.
[5] M. Brunato, H. H. Hoos, R. Battiti, (2007, December). On e ectively nding max-
imal quasi-cliques in graphs. In International conference on learning and intelligent
optimization (pp. 41-55). Springer, Berlin, Heidelberg.
[6] M. S. Chang, L. H. Chen, L. J. Hung, Y. Z. Liu, P. Rossmanith, S. Sikdar, (2014).
AnO (1:4658n)-time exact algorithm for the maximum bounded-degree-1 set prob-
lem. In Proceedings of the 31st workshop on combinatorial mathematics and compu-
tation theory (pp. 9-18).
[7] K. R. Gujjula, K. A. Seshadrinathan, A. Meisami. (2014). A Hybrid Metaheuristic
for the Maximum k-Plex Problem.
[8] D. S. Johnson, M. A. Trick, (Eds.). (1996). Cliques, coloring, and satis ability: sec-
ond DIMACS implementation challenge, October 11-13, 1993 (Vol. 26). American
Mathematical Soc..
[9] D. S. Johnson, J. K. Lenstra, A. R. Kan, (1978). The complexity of the network
design problem. Networks, 8(4), 279-285.
[10] R. D. Luce, (1950). Connectivity and generalized cliques in sociometric group struc-
ture. Psychometrika, 15(2), 169-190.
[11] B. McClosky, I. V. Hicks. (2012). Combinatorial algorithms for the maximum k-plex
problem. Journal of combinatorial optimization, 23(1), 29-49.
[12] Z. Miao, B. Balasundaram. (2017). Approaches for nding cohesive subgroups in
large scale social networks via maximum k-plex detection. Networks, 69(4), 388-407.
[13] R. J. Mokken, (1979). Cliques, clubs and clans. Quality and quantity, 13(2), 161-173.
[14] H. Moser, R. Niedermeier, M. Sorge, (2012). Exact combinatorial algorithms and
experiments for nding maximum k-plexes. Journal of combinatorial optimization,
24(3), 347-373.
[15] J. Pattillo, A. Veremyev, S. Butenko, V. Boginski, (2013). On the maximum quasi-
clique problem. Discrete Applied Mathematics, 161(1-2), 244-257.
[16] M. G. Resende, C. C. Ribeiro, (2010). Greedy randomized adaptive search proce-
dures: Advances, hybridizations, and applications. In Handbook of metaheuristics
(pp. 283-319). Springer, Boston, MA.
[17] S. B. Seidman, (1983). Network structure and minimum degree. Social networks,
5(3), 269-287.
[18] S. B. Seidman and B. L. Foster, A graph-theoretic generalization of the clique con-
cept, The Journal of Mathematical Sociology, 1978, p.139{154.
[19] H. Yu, A. Paccanaro, V. Trifonov, M. Gerstein, (2006). Predicting interactions in
protein networks by completing defective cliques. Bioinformatics, 22(7), 823-829.
[20] Y. Zhou, J. K. Hao. (2017). Frequency-driven tabu search for the maximum s-plex
problem. Computers and Operations Research, 86, 65-78.