×

zbMATH — the first resource for mathematics

Local search for diversified top-\(k\) clique search problem. (English) Zbl 1458.68146
Summary: The objective of the diversified top-\(k\) clique (DTKC) search problem is to find \(k\) maximal cliques that cover the maximum number of vertices in a given graph. This problem is equivalent to the well-known maximum clique problem (MaxClique) when \(k = 1\). This paper proves the NP-hardness of the DTKC search problem and presents a local search algorithm, named TOPKLS, based on two novel strategies for the DTKC search problem. The first strategy is called enhanced configuration checking (ECC), which is a new variant of a recent effective strategy called configuration checking (CC), for reducing cycling in the local search and improving the diversity of the DTKC search problem. The second strategy is a heuristic to estimate the quality of each maximal clique. Experiments demonstrate that TOPKLS outperforms the existing algorithms on large sparse graphs from real-world applications.
MSC:
68R10 Graph theory (including graph drawing) in computer science
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] AbramĂ©, A.; Habet, D.; Toumi, D., Improving configuration checking for satisfiable random k-sat instances, Ann. Math. Artif. Intell., 79, 1-3, 5-24 (2017) · Zbl 1404.68136
[2] Akkoyunlu, E. A., The enumeration of maximal cliques of large graphs, SIAM J. Comput., 2, 1, 1-6 (1973) · Zbl 0239.05125
[3] Bron, C.; Kerbosch, J., Algorithm 457: finding all cliques of an undirected graph, Commun. ACM, 16, 9, 575-577 (1973) · Zbl 0261.68018
[4] Cai, S., Balance between complexity and quality: Local search for minimum vertex cover in massive graphs, (Yang, Q.; Wooldridge, M. J., Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015 (2015), AAAI Press), 747-753
[5] Cai, S.; Jie, Z.; Su, K., An effective variable selection heuristic in sls for weighted max-2-sat, J. Heuristics, 21, 3, 433-456 (2015)
[6] Cai, S.; Lin, J., Fast solving maximum weight clique problem in massive graphs, (Kambhampati, S., Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016 (2016), IJCAI/AAAI Press), 568-574
[7] Cai, S.; Su, K., Local search for boolean satisfiability with configuration checking and subscore, Artif. Intell., 204, 75-98 (2013) · Zbl 1334.68200
[8] Cai, S.; Su, K.; Sattar, A., Local search with edge weighting and configuration checking heuristics for minimum vertex cover, Artif. Intell., 175, 9-10, 1672-1696 (2011) · Zbl 1225.68242
[9] Chang, L.; Yu, J. X.; Qin, L., Fast maximal cliques enumeration in sparse graphs, Algorithmica, 66, 1, 173-186 (2013) · Zbl 1263.05045
[10] Cheng, J.; Ke, Y.; Fu, A. W.-C.; Yu, J. X.; Zhu, L., Finding maximal cliques in massive networks, ACM Trans. Database Syst. (TODS), 36, 4, 21 (2011)
[11] Cheng, J.; Zhu, L.; Ke, Y.; Chu, S., Fast algorithms for maximal clique enumeration with limited memory, Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1240-1248 (2012), ACM
[12] Lee, C.; McDaid, A.; Reid, F.; Hurley, N. J., Detecting highly overlapping community structure by greedy clique expansion, Workshop on Social Network Mining and Analysis (2010)
[13] Li, R.; Hu, S.; Zhang, H.; Yin, M., An efficient local search framework for the minimum weighted vertex cover problem, Inf. Sci., 372, 428-445 (2016) · Zbl 1428.90183
[14] Luo, C.; Cai, S.; Su, K.; Wu, W., Clause states based configuration checking in local search for satisfiability, IEEE Trans. Cybern., 45, 5, 1028-1041 (2015)
[15] Luo, C.; Cai, S.; Wu, W.; Jie, Z.; Su, K., Ccls: an efficient local search algorithm for weighted maximum satisfiability, IEEE Trans. Comput., 64, 7, 1830-1843 (2015) · Zbl 1360.68786
[16] Rossi, R.; Ahmed, N., The network data repository with interactive graph analytics and visualization., AAAI, 15, 4292-4293 (2015)
[17] Wang, Y.; Cai, S.; Yin, M., Two efficient local search algorithms for maximum weight clique problem., AAAI, 805-811 (2016)
[18] Wang, Y.; Yin, M.; Ouyang, D.; Zhang, L., A novel local search algorithm with configuration checking and scoring mechanism for the set k-covering problem, Int. Trans. Oper. Res., 24, 6, 1463-1485 (2017) · Zbl 1386.90130
[19] Yuan, L.; Qin, L.; Lin, X.; Chang, L.; Zhang, W., Diversified top-k clique search, VLDB J., 25, 2, 171-196 (2016)
[20] Zheng, X.; Liu, T.; Yang, Z.; Wang, J., Large cliques in arabidopsis gene coexpression network and motif discovery, J. Plant Physiol., 168, 6, 611-618 (2011)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.