Maximum cut‐clique problem: ILS heuristics and a data analysis application
- 5 September 2014
- journal article
- Published by Wiley in International Transactions in Operational Research
- Vol. 22 (5) , 775-809
Abstract
This paper focuses on iterated local search heuristics for the maximum cut‐clique (MCC, or clique neighborhood) problem. Given an undirected graph G = (V,E) and a clique C of G, the cut‐clique is the set of edges running between C and V\C, establishing the cut (C,V\C). The MCC in G is to find a clique with the largest number of edges in the neighborhood of the clique, also known as the maximum edge‐neighborhood clique. This problem has been recently introduced in the literature together with a number of applications, namely, in cell biology instances. However, it has only been addressed so far by exact methods. In this paper, we introduce the first approximate algorithms for tackling the MCC problem, compare the results with the exact methodologies, and explore a new application within marketing analysis, which provide a new alternative perspective for mining market basket problems.Keywords
This publication has 34 references indexed in Scilit:
- Maximising the Size of Non-Redundant Protein Datasets Using Graph TheoryPLOS ONE, 2013
- Cliques with maximum/minimum edge neighborhood and neighborhood densityComputers & Operations Research, 2012
- Extended and discretized formulations for the maximum clique problemComputers & Operations Research, 2010
- A sequential elimination algorithm for computing bounds on the clique number of a graphDiscrete Optimization, 2008
- Protein complexes and functional modules in molecular networksProceedings of the National Academy of Sciences, 2003
- A fast algorithm for the maximum clique problemDiscrete Applied Mathematics, 2002
- Reactive Local Search for the Maximum Clique Problem1Algorithmica, 2001
- Algorithms for association rule mining — a general survey and comparisonACM SIGKDD Explorations Newsletter, 2000
- Parallel and distributed association mining: a surveyIEEE Concurrency, 1999
- A multi-KP modeling for the maximum-clique problemEuropean Journal of Operational Research, 1994