×

Finding a maximum \(k\)-club using the \(k\)-clique formulation and canonical hypercube cuts. (English) Zbl 1414.90349

Optim. Lett. 12, No. 8, 1947-1957 (2018); correction ibid. 12, No. 8, 1959-1969 (2018).
Summary: Detecting low-diameter clusters is an important graph-based data mining technique used in social network analysis, bioinformatics and text-mining. Low pairwise distances within a cluster can facilitate fast communication or good reachability between vertices in the cluster. Formally, a subset of vertices that induce a subgraph of diameter at most \(k\) is called a \(k\)-club. For low values of the parameter \(k\), this model offers a graph-theoretic relaxation of the clique model that formalizes the notion of a low-diameter cluster. Using a combination of graph decomposition and model decomposition techniques, we demonstrate how the fundamental optimization problem of finding a maximum size \(k\)-club can be solved optimally on large-scale benchmark instances that are available in the public domain. Our approach circumvents the use of complicated formulations of the maximum \(k\)-club problem in favor of a simple relaxation based on necessary conditions, combined with canonical hypercube cuts introduced by Balas and Jeroslow.

MSC:

90C35 Programming involving graphs or networks

Software:

Gurobi; DIMACS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alba, RD, A graph-theoretic definition of a sociometric clique, J. Math. Sociol., 3, 113-126, (1973) · Zbl 0297.92019 · doi:10.1080/0022250X.1973.9989826
[2] Almeida, MT; Carvalho, FD, Integer models and upper bounds for the 3-club problem, Networks, 60, 155-166, (2012) · Zbl 1269.90120 · doi:10.1002/net.21455
[3] Almeida, MT; Carvalho, FD, An analytical comparison of the LP relaxations of integer models for the \(k\)-club problem, Eur. J. Oper. Res., 232, 489-498, (2014) · Zbl 1305.90303 · doi:10.1016/j.ejor.2013.08.004
[4] Balas, E.; Jeroslow, R., Canonical cuts on the unit hypercube, SIAM J. Appl. Math., 23, 61-69, (1972) · Zbl 0237.52004 · doi:10.1137/0123007
[5] Balasundaram, B.: Graph theoretic generalizations of clique: optimization and extensions. PhD thesis, Texas A&M University, College Station, Texas, USA (2007)
[6] Balasundaram, Balabhaskar; Pajouh, Foad Mahdavi, Graph Theoretic Clique Relaxations and Applications, 1559-1598, (2013), New York, NY · doi:10.1007/978-1-4419-7997-1_9
[7] Balasundaram, B.; Butenko, S.; Trukhanov, S., Novel approaches for analyzing biological networks, J. Comb. Optim., 10, 23-39, (2005) · Zbl 1080.90010 · doi:10.1007/s10878-005-1857-x
[8] Bourjolly, JM; Laporte, G.; Pesant, G., Heuristics for finding \(k\)-clubs in an undirected graph, Comput. Oper. Res., 27, 559-569, (2000) · Zbl 0955.91051 · doi:10.1016/S0305-0548(99)00047-7
[9] Bourjolly, JM; Laporte, G.; Pesant, G., An exact algorithm for the maximum \(k\)-club problem in an undirected graph, Eur. J. Oper. Res., 138, 21-28, (2002) · Zbl 1008.90048 · doi:10.1016/S0377-2217(01)00133-3
[10] Carvalho, FD; Almeida, MT, Upper bounds and heuristics for the 2-club problem, Eur. J. Oper. Res., 210, 489-494, (2011) · Zbl 1213.90250 · doi:10.1016/j.ejor.2010.11.023
[11] Cook, DJ; Holder, LB, Graph-based data mining, IEEE Intell. Syst., 15, 32-41, (2000) · doi:10.1109/5254.850825
[12] Dimacs (2012) Graph partitioning and graph clustering: tenth Dimacs implementation challenge. http://www.cc.gatech.edu/dimacs10/index.shtml. Accessed Feb 2015
[13] Gurobi Optimization, Inc (2014) Gurobi optimizer reference manual,version 6.0, copyright \(\copyright \) 2014. http://www.gurobi.com/documentation/6.0/refman/
[14] Kahruman-Anderoglu, Sera; Buchanan, Austin; Butenko, Sergiy; Prokopyev, Oleg A., On provably best construction heuristics for hard combinatorial optimization problems, Networks, 67, 238-245, (2015) · Zbl 1390.90467 · doi:10.1002/net.21620
[15] Miao, J., Berleant, D.: From paragraph networks to document networks. In: Proceedings of the International Conference on Information Technology: Coding and Computing, 2004 (ITCC 2004), vol. 1, pp 295-302 (2004). doi:10.1109/ITCC.2004.1286469
[16] Mirghorbani, M., Krokhmal, P.: On finding \(k\)-cliques in \(k\)-partite graphs. Optimization Letters. 7(6), 1155-1165 (2013) · Zbl 1276.90061
[17] Mokken, RJ, Cliques, clubs and clans, Qual. Quant., 13, 161-173, (1979) · doi:10.1007/BF00139635
[18] Pajouh, F.M., Balasundaram, B.: On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs. Discret. Optim. 9(2), 84-97 (2012) · Zbl 1246.90130
[19] Pajouh, F.M., Balasundaram, B., Hicks, I.V.: On the 2-club polytope of graphs (2015, under review) · Zbl 1354.05035
[20] Pattillo, Jeffrey; Youssef, Nataly; Butenko, Sergiy, Clique Relaxation Models in Social Network Analysis, 143-162, (2011), New York, NY · Zbl 1247.91162
[21] Schäfer, A.; Komusiewicz, C.; Moser, H.; Niedermeier, R., Parameterized computational complexity of finding small-diameter subgraphs, Optim. Lett., 6, 883-891, (2012) · Zbl 1254.90279 · doi:10.1007/s11590-011-0311-5
[22] Shahinpour, S., Butenko, S.: Algorithms for the maximum \(k\)-club problem in graphs. J. Comb. Optim. 26(3), 520-554 (2013a) · Zbl 1282.90220
[23] Shahinpour, S., Butenko, S.: Distance-based clique relaxations in networks: \(s\)-clique and \(s\)-club. In: Goldengorin, B.I., Kalyagin, V.A., Pardalos, P.M. (eds.) Models, Algorithms, and Technologies for Network Analysis, vol. 59, pp 149-174. Springer New York (2013b) · Zbl 1344.90064
[24] Spirin, V.; Mirny, L. A., Protein complexes and functional modules in molecular networks, Proceedings of the National Academy of Sciences, 100, 12123-12128, (2003) · doi:10.1073/pnas.2032324100
[25] Terveen, L.; Hill, W.; Amento, B., Constructing, organizing, and visualizing collections of topically related, web resources, ACM Trans. Comput. Hum. Interact., 6, 67-94, (1999) · doi:10.1145/310641.310644
[26] Veremyev, A.; Boginski, V., Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems, Eur. J. Oper. Res., 218, 316-326, (2012) · Zbl 1244.90201 · doi:10.1016/j.ejor.2011.10.027
[27] Veremyev, Alexander; Prokopyev, Oleg A.; Pasiliao, Eduardo L., Critical nodes for distance-based connectivity and related problems in graphs, Networks, 66, 170-195, (2015) · doi:10.1002/net.21622
[28] Wasserman, S., Faust, K.: Social Network Analysis. Cambridge University Press, New York (1994) · doi:10.1017/CBO9780511815478
[29] Yannakakis, M.: Node-and edge-deletion NP-complete problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, STOC ’78, pp. 253-264. ACM Press, New York (1978) · Zbl 1282.68131
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.