An efficient local search algorithm for solving maximum edge weight clique problem in large graphs

Abstract

Maximum vertex weight clique problem (MVWCP) and maximum edge weight clique problem (MEWCP) are two significant generalizations of maximum clique problem (MCP), and can be widely used in many real-world applications including molecular biology, broadband network design and pattern recognition. Recently, breakthroughs have been made for solving MVWCP in large graphs, resulting in several state-of-the-art algorithms, such as WLMC, FastWClq and LSCC + BMS. However, less attention has been paid to solving MEWCP in large graphs. In this paper, we present an efficient Stochastic Local Search (SLS) algorithm for MEWCP by combining clique construction, local search and graph reduction, resulting in a new algorithm named ReConSLS. We also propose a new upper bound function for edge weighted graphs which is essential for graph reduction. Extensive experiments on a wide range of large graphs demonstrate that ReConSLS surpasses state-of-the-art SLS competitors on the majority of testing graphs.

1 Introduction

Given an undirected graph ${G=(V,E)}$, where V is the set of vertices and E is the set of edges, a clique C is a subset of V, such that all vertices in C are connected. The maximum clique problem (MCP) is to find a clique with the maximum size in G. MCP has two significant generalizations: (1) the maximum vertex weight clique problem (MVWCP), in which each vertex is associated with a positive weight, and the goal is to find a clique with the maximum weight of vertices; (2) the maximum edge weight clique problem (MEWCP), in which each edge is associated with a positive weight, and the goal is to find a clique with the maximum weight of edges.

MCP is a classical combinatorial optimization problem that was among one of the first problems proved to be NP-hard (Karp 1972). The weighted version of MCP (including MVWCP and MEWCP) has many real-world applications, including computer vision, pattern recognition, robotics (Ballard and Brown 1982), broadband network design (Park et al. 1996), wireless telecommunication (Balasundaram and Butenko 2006). Due to the theoretical significance and practical application value, considerable efforts have been made to develop algorithms for MCP, MVWCP and MEWCP. Algorithms for solving these problems are usually categorized into two classes: complete algorithms and incomplete algorithms.

On the one hand, most of the complete algorithms for MCP are based on the general branch and bound (BnB) framework. These algorithms differ from each other mainly by their techniques of determining the upper bound and their branching strategies Carraghan and Pardalos 1990; Tomita and Seki 2003; Tomita and Kameda 2007; San Segundo et al. 2011; Li and Quan 2010; Li et al. 2013; Jiang et al. 2017. On the other hand, incomplete algorithms cannot prove the optimality of the returned solutions, but these algorithms are usually able to find good quality solutions within reasonable time (Battiti and Protasi 2001; Pullan and Hoos 2006; Pullan 2006, 2008; Pullan et al. 2011; Wu et al. 2012; Benlic and Hao 2013; Wang et al. 2016; Fan et al. 2017a). Recently, numerous work focused on solving MVWCP in large-sized real-world graphs, resulting in several start-of-the-art algorithms. LSCC + BMS (Wang et al. 2016) adopts a balanced strategy called ‘Best from Multiple Selections’ (BMS) (Cai 2015) to improve the performance of a state-of-the-art algorithm named LSCC on massive graphs. FastWClq (Cai and Lin 2016) utilizes a new method for MVWCP which interleaves between clique construction and graph reduction, and achieves good performance on solving massive real-world graphs.

There are two classes of methods to obtain the exact solutions of MEWCP: (1) formulating MEWCP into mathematical programming such as integer programming (IP) (Gouveia and Martins 2015) and mixed integer programming (MIP); (2) using branch-and-bound method. The unconstrained quadratic binary program (UQP) model is used to represent the nonlinear formula of MEWCP. A tabu search heuristic designed for UQP produces a new algorithm for MEWCP named TS/UQP (Alidaee et al. 2007). Computational experiments on small instances show that the nonlinear model has computational advantages over the linear model. EWCLIQUE (Shimizu et al. 2018) is a purely combinatorial branch-and-bound algorithm and is faster than the methods based on mathematical programming on random benchmark and DIMACS benchmark. To promote the development of the methods that using branch-and-cut framework for MEWCP, some work is focused on a family of cutting planes and gives the theoretical proof that under certain conditions, one of the inequalities in this family defines a facet for MEWCP (Fomeni 2017).

Although great efforts have been made to solve MVWCP on large graphs, less attention was paid to MEWCP. Recently, two local search algorithms have been proposed for MEWCP. CERS (Fan et al. 2017b) can be used to solve both MVWCP and MEWCP, which outperforms a number of state-of-the-art algorithms on large graphs. LSMR (Li et al. 2018) is another efficient algorithm for MEWCP on massive graphs. These local search algorithms derived from algorithms for MVWCP, although the frameworks of several algorithms for MVWCP could be adopted to solve MEWCP, many prominent strategies for MVWCP are not suitable for directly solving MEWCP.

1.1 Main contributions

In this paper, we are devoted to improving the performance over the state-of-the-art algorithms for solving MEWCP on large graphs. Our main contributions in this paper are concluded as follows.

Firstly, we construct a novel framework for solving MEWCP, which works in three different phases, i.e., clique construction, local search and graph reduction. Based on this framework, we develop an effective algorithm named ReConSLS for solving MEWCP.

Secondly, we propose an effective upper bound function for edge-weighted graphs which improves the performance of graph reduction.

Thirdly, we incorporate a number of effective techniques into this framework, including BMS strategy (Cai 2015), benefit estimation function of vertices (Cai and Lin 2016), resulting in a considerable performance improvement in the phases of clique construction and local search.

Finally, we conduct extensive experiments to compare ReConSLS against four state-of-the-art SLS algorithms including LSMR, CERS, LSCC and LSCC + BMS on a broad range of practical benchmarks, including 139 graphs from Network Data Repository and 18 graphs from KONECT (the Koblenz Network Collection). Our experimental results indicate that ReConSLS outperforms other competitors in terms of solution quality and running time on the majority of testing graphs.

1.2 Paper structure

We organize the remainder of the paper as follows. Section 2 gives preliminary definitions and notations. In Sect. 3, we present the new algorithm named ReConSLS along with the details of graph reduction, clique construction and local search. Extensive experimental results are shown in Sect. 4 to demonstrate the effectiveness of ReConSLS. Finally, we conclude the paper and point out future work in Sect. 5.

2 Preliminaries

Given an undirected graph ${G = (V, E)}$, where $V = \{v_1, v_2, \cdots , v_n\}$ is the set of vertices and $E = \{e_1, e_2, \cdots , e_m\}$ is the set of edges, a clique C is a subset of V, such that all vertices in C are connected. MCP is to find a clique with the maximum number of vertices in the given graph ${G = (V, E)}$. The MVWCP, in which the graph has a weight function $W_v$ that assigns a positive weight to each vertex, and the weight of a clique C is defined as $W_v(C) = \varSigma _{i \in C}W_i$, is to find a clique with the maximum $W_v(C)$ in the given graph $G = (V, E, W_v )$. The MEWCP, in which the graph has a weight function $W_e$ that assigns a positive weight to each edge, for an edge $e_{ij}$, the weight of e is denoted by $W_{e_{ij}}$, the weight of a clique C is then defined as $W_e(C) = \varSigma _{e_{ij}, i, j \in C}W_{e_{ij}}$, is to find a clique with the maximum $W_e(C)$ in the given graph $G = (V, E, W_e )$. We use $W^*(G)$ to denote the maximum weight of clique in G.

2.1 Basic operations and scoring functions

Given an undirected graph ${G = (V, E)}$, an edge $e \in E$ is expressed as a pair of two vertices in V, i.e., $e_{uv}$, where $u \in V$ and $v \in V$ are two endpoints of e. For a vertex $v \in V$, the set of v’s neighboring vertices is denoted by ${N(v) = \{u\in V \mid e_{uv}\in E\}}$; the degree of v is denoted by $d(v) = |N(v)|$. We also denote $N[v] = N(v) \cup \{v\}$.

To find a clique with good solution-quality, the local search based method usually moves from one clique to another until the time limit is reached, it then returns the clique with the best solution-quality found so far. Our algorithm framework contains three types of search steps: add, swap, and drop. Assume that C is a clique. In order to preserve the property of a clique, we define three sets as follows:

• $S_{add} = \{u | u \not \in C, u \in N(v)\ \text {for\ all}\ v \in C\}$, where C is still a clique after adding u into C if $u \in S_{add}$.

• ${S_{swap} = \{ e_{uv} | u \not \in C, v \in C, e_{uv}\not \in E, u \in N(w)\ \text {for\ all}\ w \in C\backslash \{v\}\}}$, where C is still a clique after both adding u into C and dropping v from C if $(u, v) \in S_{swap}$.

• $S_{drop} = \{v | v \in C\}$.

Let C be a clique, W(C) denotes the weight of clique C. Ascore(v, C) represents the increment of W(C) after adding v into C, i.e., $Ascore(v,C) = W(C\cup \{v\})-W(C)$. Sscore(u, v, C) corresponds the increment of W(C) after both adding u into C and dropping v from C, i.e., $Sscore(u,v,C)=W(C\backslash \{v\} \cup \{u\})-W(C)$. Dscore(v, C) is the increment of W(C) after dropping v from C, i.e., $Dscore(v,C)=W(C\backslash \{v\})-W(C)$.

Besides, given an undirected graph $G=(V,E)$ as well as a clique C in G, a vertex $v \in V$ has two possible states: inside C or outside C. We define the number of steps that has occurred since v last changed its states, as the age of v, denoted as age(v). The cardinality of C is |C|.

2.2 Strong configuration checking

For local search algorithms, it is well acknowledged that a severe issue is the so-called cycling problem, i.e., frequently revisiting candidate solutions which have been explored lately. Cai et al. (2011) proposed an efficient strategy called configuration checking (CC) to handle the cycling problem. The CC strategy is usually implemented with a Boolean array named confChange, in which $confChange(v) = 1$ means that v’s circumstance information (also known as configuration) has changed since the most recent change of v’s state. Till now, the CC strategy has been successfully applied to a number of well-known NP-hard problems, including Boolean satisfiability (Cai and Su 2012; Luo et al. 2012, 2015a; Cai and Su 2013; Abramé et al. 2017), maximum satisfiability (Luo et al. 2015b, 2017), minimum vertex cover (Cai et al. 2011, 2013). Based on the CC strategy, literature Wang et al. (2016) proposed a strategy called strong configuration checking (SCC) in the context of MCP solving. The SCC strategy works according to the following rules:

• (1) initially, for each vertex v, confChange(v) is set to 1;

• (2) when v is added into the current clique, confChange(u) is set to 1 for all $u\in N(v)$;

• (3) when v is removed from the current clique, confChange(v) is set to 0;

• (4) when v is removed from the current clique and u is added into the clique, confChange(v) is set to 0.

A vertex v is allowed to be added into the clique if $confChange(v) = 1$.

3 The ReConSLS algorithm

In this section, we propose a new algorithm for MEWCP, which works in three phases, i.e., clique construction, local search and graph reduction. We first describe the algorithm, and then present details about the three phases of the algorithm.

3.1 The framework of ReConSLS

The pseudo-code of ReConSLS is outlined in Algorithm 1. The framework of the algorithm is described as follows. After initialization, ReConSLS executes a WHILE loop until the time limit is reached or the simplified graph of G is a clique. In each WHILE loop: firstly, a clique is constructed by iteratively adding vertices into a set that is initialized to be empty (line 3), the variable ContinuousNoImprovedNum is a consecutive loop counter which increases by 1 after each construction (line 4) and sets to 0 if a better solution is found (line 6, 9). Then the local search phase is executed (line 7). Finally, if ContinuousNoImprovedNum is greater than a positive integer threshold (In this paper, the threshold is set to 10) and the weight of the current best clique is larger than that of the clique that has been used in the most recent graph reduction phase, the graph reduction phase is executed (line 11).

3.2 Graph reduction

A graph can be reduced to a simplified graph with the identical maximum weight clique by applying proper graph reduction rules. Intuitively, it is easier for a local search algorithm for finding a larger clique weight in the simplified graph due to a smaller search space. As computing the upper bound for a vertex in MEWCP is more complicated than that in MVWCP, it is not easy to directly adapt the bound-computing strategies in Cai and Lin (2016), Fang et al. (2014) and Jiang et al. (2017) for solving MEWCP. In this subsection, we propose an upper bound function for edge-weighted graphs and describe the graph reduction algorithm.

As in literature Cai and Lin (2016), we give the definition of upper bound of a vertex.

Definition 1

Given an edge-weighted graph ${G = (V, E, W_e)}$, for a vertex $v\in V$, an upper bound of v is a positive integer, denoted by $UB_{func}(v)$, such that for ${\forall C}$ in G that $v\in C$, $UB_{func}(v)\ge W(C)$.

Based on the Definition 1, we consider the following reduction rule:

Reduction Rule: Given an edge-weighted graph ${G = (V, E, W_e)}$ and a clique $C_0$ in G, for ${\forall v \in V}$, if ${UB_{func}(v) <W(C_0)}$, delete v and its incident edges from G.

We denote this rule by ${Rule(UB_{func}, C_0)}$, where $UB_{func}$ is the upper bound function and $C_0$ is the input clique. We can apply this rule in the algorithm of solving MEWCP for graph reduction, which depends on the following proposition being true.

Proposition 1

Given an edge-weighted graph ${G = (V, E, W_e)}$, $G'$ is a simplified graph by applying ${Rule(UB_{func}, C_0)}$ on G. Then $W(G) = max\{W(C_0), W(G')\}$. The proof of Proposition 1 has been given in the literature Cai and Lin (2016).

The upper bound function is fundamental in the reduction rule. We provide some notations before proposing the upper bound function. The sum of the weight of the edges adjacent to v is denoted by $WN(v) = \varSigma _{u \in N(v)}W_{e_{uv}}$. For a vertex v, the maximum weight of the edges adjacent to v is denoted by $Emax(v)=max\{W_{e_{uv}}|u \in N(v)\}$, the minimum weight of the edges adjacent to v is denoted by $Emin(v)=min\{W_{e_{uv}}|u \in N(v)\}$. For a clique C, we say that an edge $e_{uv}$ is in C iff $i \in C$ and $j \in C$.

In order to describe the upper bound function, we propose a concept called the contribution from vertex u to vertex v. The contribution from u to v is defined as the sum of the weights of edges that connected with vertex u and may be in cliques containing vertex v, and is denoted by CB(u, v). From this definition, we learn that u makes contribution to v iff u and v are neighbors. It is clear that the value of cardinality of cliques containing v will not be greater than $d(v)+1$. The number of edges that u can contribute to v will not be greater than d(v). In order to define the upper bound of vertex v, we first define the upper limit of CB(u, v), denoted by $UL_{CB}(u,v)$. Suppose that vertices u and v are neighbors, then the maximum number of edges adjacent to u within any clique C containing u and v is not greater than $min\{d(u), d(v)\}$. Assume that $d(v)<d(u)$, C is any clique containing u and v, let $EMAX=d(v)*Emax(u)$, $EMIN=WN(u)-(d(u)-d(v))*Emin(u)$, the sum of weight of any d(v) edges within C that are adjacent to u is not greater than $min\{EMAX, EMIN\}$. Thus, we give the definition of $UL_{CB}(u,v)$ as follows.

$$\begin{aligned} UL_{CB}(u,v) = \left\{ \begin{array}{ll} WN(u), &{}d(v) \ge d(u); \\ min\{EMAX,EMIN\}, &{}d(v) < d(u). \end{array}\right. \end{aligned}$$

Based on the concept of contribution, we propose an efficient upper bound function. The definition is described as follows.

$$\begin{aligned} UB(v) = \left\{ \begin{array}{ll} 0, &{} d(v)=0; \\ WN(v), &{} d(v)=1; \\ \frac{WN(v)+\Sigma _{u\in N(v)}UL_{CB}(u,v)}{2}, &{} d(v) > 1. \end{array}\right. \end{aligned}$$

Our graph reduction algorithm is based on our upper bound function and the reduction rule. The pseudo-code is outlined in Algorithm 2.

3.3 Clique construction

In this subsection, we present a clique construction algorithm. This algorithm contains two components: first, selecting a starting vertex, and add it into an empty set C; second, iteratively adding a vertex to expand the clique C.

We use CandSet to denote the set containing candidate vertices. After initialization, each candidate vertex in CandSet could be utilized as a starting vertex to construct a clique. During the adding vertex selection phase, given a current clique C, the property of CanSet is identical with $S_{add}$ which was proposed in Sect. 2.1, i.e., C is still a clique after adding u into C if $u\in CandSet$.

To select a starting vertex, we utilize our upper bound function $UB_{func}(v)$ as the selection criterion and utilize the BMS strategy to select a vertex in CandSet. The BMS strategy has been proposed for efficiently selecting a good-quality element from a large-sized candidate element set which uses a parameter $k_s$ to control the sampling size. For instance, $k_s$ sets to 1, referring to randomly select a vertex from CandSet; $k_s$ sets to 100, indicating randomly selecting 100 vertices from CandSet and then selecting v with the largest value of $UB_{func}(v)$ from the vertices previously selected. In our algorithm, $k_s$ is set to 1 and 100 alternatively, which means randomly and greedily selecting alternatively.

To select adding vertices, inspired by the benefit estimation function of vertex addition in literature Cai and Lin (2016), we use CandNeighborWeight(v) to denote the possible benefit after adding v into C, i.e, $CandNeighborWeight(v)=\Sigma _{u\in (N(v)\cap S_{add})}W_{e_{uv}}$. Based on CandNeighborWeight(v), we propose a new function B(v) to estimate the benefit of adding vertex v, i.e., $B(v) = Ascore(v,C)+CandNeighborWeight(v)/2$. We select the adding vertex based on B(v), and adopt the dynamic BMS heuristic proposed in literature Cai and Lin (2016). For the parameter k of the dynamic BMS, it starts with a small value (${k_0}$). The dynamic BMS utilized in our algorithm is similar with that in FastWClq (Cai and Lin 2016), but with two differences. (1) The dynamic BMS utilized in our algorithm adjusts k more frequently than that utilized in FastWClq. After each starting vertex selection phase, the value of k is increased via $k:=2k$; (2) whenever k exceeds the maximum value ${k_m}$, it resets to ${k=k_0}$ (In FastWclq, resets to $k:=++k_0$).

3.4 Stochastic local search

Based on the SCC strategy, in this phase, we utilize the BMS heuristic to strike a good balance between the quality of the selected neighboring clique and the time complexity. We also adopt a random walk strategy to choose the dropping vertex from the current clique.

The pseudo-code of the local search procedure is outlined in Algorithm 3. In each search step, according to the SCC strategy, Algorithm 3 randomly selects k vertices from $S_{add}$ and then selects v with the maximum Ascore from the vertices previously selected (line 3). It also randomly selects k vertex pairs from $S_{swap}$ and then selects $(u,u')$ with the maximum Sscore from the vertex pairs previously selected (line 4). If $null = v$, then Algorithm 3 selects $v'$ with the maximum Dscore from $S_{drop}$ (line 11), if $(null, null) = (u, u{'})$ or $Dscore(v{'})>Sscore(u, u{'})$, then Algorithm 3 determines to select a vertex to drop from the current clique; with probability p, it randomly selects a vertex from $S_{drop}$ to be dropped (line 13-14), otherwise it drops vertex $v'$ from the current clique (line 15).

4 Experimental evaluations

In this section, we conduct experiments to compare ReConSLS against existing state-of-the-art competitors on a broad range of real-world large graphs, in order to evaluate the efficiency of ReConSLS for solving MEWCP.

4.1 The benchmarks

To comprehensively evaluate the effectiveness of our ReConSLS algorithm, we conducted experiments on two benchmarks:

(i) We downloaded all 139 graphs online,¹ which were originally taken from the Network Data Repository.² These graphs have been recently used for evaluating the performance of algorithms for solving MVWCP (Cai and Lin 2016; Wang et al. 2016; Fan et al. 2017a; Jiang et al. 2017), MEWCP (Fan et al. 2017b), Coloring (Rossi and Ahmed 2014) and MVC (Cai 2015).

(ii) In addition, we downloaded 18 unweighted undirected graphs from KONECT (The Koblenz Network Collection) (Kunegis 2013).³ (We chose those graphs with more than 300K edges and not included in the Network Data Repository. The graphs we used are available online⁴)

Many of these real-world graphs have millions of vertices and dozens of millions of edges. Since the original graphs are unweighted, we transformed them into an edge weighted version using the same weighting method as in Pullan (2008) – for an edge $e_{ij}$, the weight of edge $e_{ij}$ is set to $W_{e_{ij}} = ((i + j)\ mod\ 200) + 1$.

4.2 Experimental setup

We include four state-of-the-art SLS solvers as the competitors. CERS (Fan et al. 2017b) and LSMR (Li et al. 2018) are two efficient solvers for MEWCP in large graphs. Recently, breakthroughs have been made in MVWCP solving, resulting in several state-of-the-art solvers, such as LSCC, LSCC + BMS (Wang et al. 2016), FastWClq (Cai and Lin 2016) and WLMC (Jiang et al. 2017). Considering that it is not easy to adapt FastWClq and WLMC to solve MEWCP, we utilized LSCC and LSCC + BMS as two competitors by adapting such two solvers to solve MEWCP. We implemented ReConSLS, LSCC and LSCC + BMS in C++. The source code of ReConSLS is available online (see footnote 4). CERS was also implemented in C++ by its author and could be downloaded online⁵. LSMR was kindly provided by its author. All solvers were compiled by g++ (version 4.8.5) with the option ‘-O3’. All the experiments in this paper were carried out on a workstation under the operating system CentOS (version: 7.6.1810), with Intel(R) Xeon(R) CPU E5-2620 2.10GHz CPU, 20MB L3 cache and 128GB RAM.

In our experiments, all solvers are randomized ones. As a result, to make our evaluations statistically significant, each algorithm was performed 10 runs on each graph with seeds from 1 to 10. The cutoff time for each solver run was set to 1000 CPU seconds. For each run, we recorded the final solution and the time for seeking out the final solution. For each solver on each graph, we report the best clique weight, denoted by ‘Wmax’, the averaged clique weight over all runs, denoted by ‘Wavg’ (we do not report ‘Wavg’ if ‘Wavg’ = ‘Wmax’), and the averaged time of finding the final solution in each run, denoted by ‘time’ (the unit is CPU second). We use ‘N/A’ to denote that a solver failed to run on that graph. In Tables 2 and 4 , in each category, we report the number of graphs where the solver finds the best clique weight among all competing solvers, denoted by ‘#max’, the number of graphs where the solver finds the best averaged clique weight weight among all competing solvers, denoted by ‘#avg’. The number of graphs in each category is indicated by ‘#graph’. The number of vertices and edges in each graph is indicated by ‘|V|’ and ‘|E|’, respectively. The results in boldface show the best performance for the related graph or category in the same table. In this experiments, unspecified time units are CPU seconds.

In ReConSLS, parameters $k_0$ and $k_m$ for dynamic BMS heuristic were set to 8 and 128, respectively. In the local search phase, the search depth L was set to 100, $k_{add}$ and $k_{swap}$ were set to 128, p for randomly choose the vertex to drop was set to 50%. In LSCC and LSCC + BMS, the search depth L was set to 4000, the BMS parameter k for LSCC + BMS was set to 100 as suggested in literature Wang et al. (2016).

4.3 Experimental results

4.3.1 Experimental results on graphs from network repository

Table 1 presents the comparative results of ReConSLS, CERS, LSMR, LSCC and LSCC + BMS on graphs from Network Repository. For the sake of space, we report 35 graphs and do not report the graphs that all the solvers find the same best clique weight within 25 s. The complete results are available online (see footnote 4). From Table 1, we can see that ReConSLS stands out as the best solver on this benchmark. On all 35 graphs reported in Table 1, ReConSLS finds the best clique weight on all of them. ReConSLS also finds the best averaged clique weight on all the 35 graphs, while the figure for CERS, LSMR, LSCC and LSCC + BMS is 33, 20, 27 and 32, respectively. In terms of running time, ReConSLS finds the best averaged clique weight with the shortest averaged time on 31 of the 35 graphs. Furthermore, on 16 of the 35 graphs, ReConSLS’s speed of finding the best averaged clique weight is more than 3 times as fast as the second fastest competitor’s. The comparative results on all the 139 graphs from Network Repository was presented in Table 2. The 139 graphs are divided into 12 categories according to the filename of these graphs. On all 12 categories, ReConSLS gives the best clique weight and best averaged clique weight with the shortest averaged time on all of them.

Table 1 Experimental results on graphs from network repository (For the sake of space, we do not report on graphs that all the solvers find the same best clique weight within 25 s, we do not report ‘Wavg’ which is equal to ‘Wmax’)

Table 2 Experimental results on 139 graphs from network repository

4.3.2 Experimental results on graphs from KONECT

Table 3 presents the comparative results of ReConSLS, CERS, LSMR, LSCC and LSCC + BMS on 18 graphs from KONECT. From Table 3, ReConSLS provides a performance advantage in terms of both clique weight and runtime. On all 18 instances, all the solvers find the best clique weight for all of them except LSMR. ReConSLS also finds the best clique weight on all 10 runs for all 18 graphs, while this figure for CERS, LSMR, LSCC and LSCC + BMS is only 13, 13, 14 and 13, respectively. In terms of running time, ReConSLS finds the best averaged clique weight with the shortest averaged time on 14 of the 18 instances. Furthermore, on 8 of the 18 graphs, ReConSLS’s speed of finding the best averaged clique weight is more than 3 times as fast as the second fastest competitor’s.

Table 3 Comparative results of ReConSLS, CERS, LSMR, LSCC and LSCC + BMS on real world graphs from KONECT

Table 4 Experimental results of ReConSLS, ConSLS, CERS, LSMR, LSCC and LSCC + BMS on all the graphs

4.3.3 The effectiveness of the graph reduction algorithm and the ConSLS algorithm

To evaluate the effectiveness of the graph reduction algorithm proposed in Sect. 3.2, as well as the techniques utilized in the clique construction phase and the stochastic local search phase, we disable the graph reduction algorithm in ReConSLS, resulting in another solver named ConSLS.

We compare ReConSLS with ConSLS, CERS, LSMR, LSCC and LSCC + BMS on all the 157 graphs. The related results are listed in Table 4. According to Table 4, we can see that ReConSLS gives the best performance on all the graphs and ConSLS is the second best solver. In terms of solution quality, ReConSLS gives the best clique weight and best averaged clique weight on all of them. In terms of running time, the averaged running time for ReConSLS of finding the largest clique weight is 9.61, and the figure for ConSLS, CERS, LSMR, LSCC and LSCC + BMS is 13.04, 32.88, 76.19, 43.80 and 42.82, respectively. The comparison between ReConSLS and ConSLS indicates the effectiveness of the graph reduction algorithm. The comparison between ConSLS and other competitors shows that the techniques utilized in clique construction phase and stochastic local search phase are efficient.

5 Conclusions and future work

In this paper, we present an effective local search algorithm named ReConSLS, which works in three phases, i.e. clique construction, stochastic local search and graph reduction. We also proposed a new upper bound function for edge-weighted graphs to improve the performance of graph reduction. Experiments on real-world large graphs demonstrate that ReConSLS outperforms other competitors in terms of solution quality and running time on majority of testing graphs. Furthermore, we remove the graph reduction algorithm from ReConSLS, resulting in an alternative algorithm named ConSLS. We conducted experiments to compare ConSLS against ReConSLS, CERS, LSMR, LSCC and LSCC + BMS, and the related results show that ConSLS is the second best solver following ReConSLS, indicating the effectiveness of our upper bound function and the techniques utilized in the clique construction phase and the stochastic local search phase.

For future work, we would like to design more efficient graph reduction algorithm, as well as heuristics applied to MEWCP.