The rapid spread of fake news through dense clusters in networks jeopardizes trust and stability. Traditional approaches targeting harmful content often overlook the structural network dynamics that drive disinformation. The Cluster Deletion Problem addresses this by removing edges that bridge communities, disrupting disinformation flow while preserving intra-group communication. Indeed, given a graph representing the considered network, the Cluster Deletion Problem aims to transform it into a cluster graph via minimal edge deletions. In this paper, we address this problem with a tailored Lagrangian heuristic based on a dual descent algorithm, incorporating both a subgradient method and an ad-hoc polynomial-time repair heuristic. The proposed approach is tested on existing instances, in most cases providing better lower bounds with respect to the ones existing in the literature.
clusters indicate genes with correlated expression patterns. Further
In this paper, we tackle the CDP through a Lagrangian relaxation approach, a powerful mathematical
optimization technique, based on the machinery of the nondiferentiable optimization
To model the CDP, we consider the edge-formulation introduced in
max ∑︁ ∈{0,1}|| {,}∈ s.t. + ≤
+ 1 ∀ ∈ , , ∈ : < , {, } ∈ ∀ ∈ , , ∈ : < , {, } ∈/ (1a) (1b) (1c) exist, respectively. with defined as the set of neighbors of node ∈ . The objective function (1a) aims at maximizing the number of edges remaining in the graph. Given a triplet of nodes (, , ) such that both and belong to the neighborhood of , constraints (1b) and (1c) impose that at most one between edges {, } and {, } stays in the graph, if either edge {, } is removed from the graph ( = 0) or does not
Many optimization problems include constraints that make finding an exact solution computationally challenging. Lagrangian relaxation addresses this by relaxing some of these constraints and adding them to the objective as penalties. This simplifies the problem, which can be solved more eficiently while providing insights into the structure of the solution space. Specifically, in Lagrangian relaxation, each relaxed constraint is multiplied by a non-negative parameter, known as Lagrange multiplier, which can be tuned to iteratively approach feasible solutions. We construct the Lagrangian relaxation of the CDP formulation (1) by introducing multipliers , ∀ ∈ , , ∈ : < , {, } ∈ , and , ∀ ∈ , , ∈ : < , {, } ∈/ associated to constraints (1b) and (1c), respectively. We come out with the following problem: ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ (, ) = max
⎨ ∑︁ + ∑︁ ∈{0,1}| ⎪⎪⎪{,}∈ ∈ ,∈ :
<, {,}∈ Let us define, for each edge {, } ∈ , the sets ∑︁ (1 + − − ) + ∑︁ ∑︁ (1 − −
) . ∈ ,∈ :
<, {,}∈/ ⎫ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎭ (2) (3) (5) = ∩ , = ∖ {{} ∪ }, = ∖ {{} ∪ }, which allow us to write the cost coeficient associated to each variable in the objective function of (, ) (see Appendix A) as: = (, ) = 1 + ∑︁ ( − − ) − ∈ ∑︁ − ∈ ∑︁ . ∈ Finally, isolating the constant term independent on , problem (, ) is rewritten as: (, ) = ⎜⎜∑︁ + ∑︁ ∑︁ ⎟⎟ +
max ⎞ ⎠ ⎧ ⎨ ∑︁ ∈{0,1}|| ⎩{,}∈ ⎫ ⎬ ⎭ .
(4) ⎛ ⎝∈ ∑︁ ,∈ : < {,}∈ ∈
,∈ : < {,}∈/ = ︂{ 1 if ≥ 0, 0 otherwise.
Notice that an optimal solution (, ) of (, ) is obtained by simple inspection of the sign of the coeficients
as It is clear that, even relaxing the integrality constraint on (i.e., replacing ∈ {0, 1}|| with ∈ [0, 1]||), the solution of the LR problem obtained as in Eq. (5) is still integer. Hence, the Lagrangian relaxation (,
) of problem (1) has the integrality property, which means that the Lagrangian
relaxation cannot provide a better bound on the original problem than the one given by the Linear
Programming (LP) relaxation of the problem
Furthermore, observe that, once such a solution (, ) of (, ) has been found, a subgradient (, ) of (, ) is immediately available. For any triplet (, , ), it is given by (, ) = ︂{ 1 + − − , ∈ , , ∈ : < , {, } ∈
1 − − , ∈ , , ∈ : < , {, } ∈/ .
Minimizing the Lagrangian function (, ) with respect to the Lagrangian multipliers yields the Lagrangian dual problem. This dual problem provides an upper bound to the original (primal) CDP. The Lagrangian dual associated to our Lagrangian relaxation is = min (, ).
, ≥ 0
This section describes a dual descent procedure to tackle the LD Problem (7). The DD method is an iterative approach to solving the Lagrangian dual problem while achieving the best possible bound on the original problem. As already noticed in Section 3, this bound cannot improve the LP one. However, the DD method can still be useful in exploring the solution space and giving insights into the structure of the problem.
All parameter values at iteration ℎ are associated with the superscript ℎ. In particular, ℎ = ( ℎ, ℎ) and ℎ = ( ℎ, ℎ). The aim of the method, whose pseudo-code is reported in Algorithm 1, is creating a sequence of multipliers ( ℎ, ℎ) such that ( ℎ+1, ℎ+1) ≤ ( ℎ, ℎ). This is pursued by acting on one multiplier at a time. We introduce some possible multiplier updating rules, based on selecting one multiplier and considering the value of the associate constraint in correspondence with the current solution of the relaxation ℎ.
The efect of the increase/decrease of any multiplier or onto the cost coeficients of the variables in problem (, ) is highlighted by recalling that the dualization of the constraints (1b) and (1c) gives rise, respectively, to the terms
(1 + − − ) and (1 − − ).
Given the starting 0, 0 (line 1), the cost coeficients 0 can be immediately found by Eq. (3) (line 2), and consequently an optimal solution of ( ℎ, ℎ) can be obtained by (5), together with its value 0 (line 3). This solution is used as a starting point ℎ within the while loop in lines 5–24 of the algorithm. It may be feasible in problem (1) (lines 11–13), or not (lines 6–10). If it is infeasible, at least one of the constraints of type (1b) or (1c) is violated. In line 7, for each triple (, , ) the diferent options are considered by calling Algorithm 3 described in Appendix B. It returns the updated multipliers together with the corresponding decrease in the cost coeficients Δ. After this multipliers update through Algorithm 3, given the induced graph corresponding to the infeasible solution ℎ, in line 9, we apply a repair heuristic procedure presented in Section 4.1, to reconstruct the feasibility, obtaining solution ˜ℎ. This lets us determine, at each iteration, not only an upper bound ℎ, but also a lower bound to the optimal value of the CDP (line 10).
Stopping upon finding a feasible solution is often suficient, however, one can decide to continue with the descent. In order to proceed, the Lagrangian multipliers must be updated. This is what is done in line 13, where the algorithm calls multiple iterations of a tailored Subgradient Method (Algorithm 4) described in Appendix C. It requires two multiplier pairs and a maximum number of iterations in input. We consider as multiplier pairs: the current pair ( ℎ, ℎ) and the first of the previously generated pairs ( ℎ, ℎ) s.t. its distance (in terms of Euclidean norm) is greater than a given threshold .
Clearly, if, at a given iteration ℎ, the Δ returned by Algorithm 3 is too small (smaller than a threshold > 0), the algorithm cannot generate a diferent solution in the following iterations, remaining blocked at the solution ℎ. For this reason, only if Δ is greater than , we set the new objective function value to ℎ − Δ in line 15. Otherwise, we perform some iterations of the Subgradient Algorithm 4 (line 21) in order to generate diferent multipliers and a corresponding diferent value. We remark that, (6) (7) (8) ∑︀ {,}∈ Algorithm 1: Dual Descent algorithm for the Lagrangian Relaxation of the CDP
Input: Maximum number of DD iterations ℎ, maximum number of subgradient iterations , tolerance parameters , > 0, heuristic parameter 0 < ≤ 1.
Output: Lower bound on the CDP optimal solution. 1 ← 0 and ( 0, 0) ← (0, 0); 2 Compute cost coeficients 0 for each edge {, } ∈ according to Eq. (3); 3 Compute 0 for each edge {, } ∈ according to Eq. (5), and 0 to Eq. (4); 4 ℎ ← 0; 5 while ℎ < ℎ do 6 if ℎ is infeasible then 7 {( ℎ+1, ℎ+1), Δ} ← Algorithm 3 (ℎ, ℎ, ℎ, ℎ); 8 Let ˜ be a graph with node set and edge set ˜ = {{, } ∈ : ℎ = 1}; ˜ℎ ← Algorithm 2 (˜, ℎ, ); if ˜ℎ > then ←
∑︀ ˜ℎ ; {,}∈ else if
∑︀ ℎ > then ← {,}∈
ℎ+1 {( ℎ+1, ℎ+1), } ←
∑︀ ℎ ; {,}∈
Algorithm 4 ( ℎ, ℎ, ); if Δ > then
ℎ+1
Update ← else ← ℎ and ← 0; while > 0 and < do ← − 1; ← ⃦⃦⃦⃦ (︂ ℎℎ)︂ − ︂( )︂ ⃦⃦⃦⃦ ;
ℎ − Δ In this section, we describe a polynomial-time heuristic, which is called within the DD Algorithm whenever an infeasible solution ℎ is found and operates on a graph ˜ = (, ) obtained by considering only the edges associated with positive ℎ . The algorithm starts by receiving a graph, an iteration counter ℎ and a threshold parameter between 0 and 1. Its goal is to transform the infeasible ℎ into a feasible solution ˜ℎ by iteratively processing the connected components of the graph.
While the graph is not empty, in line 2, the algorithm computes the connected components of graph ˜. For each connected component , the nodes are ordered in descending order of their degree, i.e., by the number of neighbors within (line 4). In the case of multiple nodes with the same number of
Algorithm 2: Repair heuristic algorithm.
Input: Graph ˜ = (, ), iteration counter ℎ, parameter 0 < < 1.
Output: Feasible CDP solution ˜ℎ. 1 while Graph ˜ is not empty do
Compute the connected components of ˜; foreach connected component do
Order the nodes in by (descending) value of ; ← ⌈ ||⌉; ← ∅ ; for ∈ 1 . . . do ← []; ← { }; if | | > 0 then foreach ∈ do Compute sets = ∩ and = ∖ { ∪ {}}; Order the set in a non-increasing order of ; in the case of ties, order in a
non-decreasing order of ; while ̸= ∅ do ← [0]; ← ∖ {}; if ⊆ then ← ∪ {} else continue; 17 if || > || then ←
; foreach , ∈ : ∈ and > do
if {, } ∈ and ∈ then Set ˜ℎ ← ← ∖ ; 1 else Set ˜ℎ ← 0; neighbors, they are ordered with respect to their index . In lines 5-6, parameter and set are initialized. They are needed because we consider one by one the first nodes in the ordered set and construct cliques starting from each of these nodes independently. is the largest among the obtained cliques, initialized to the empty set, while is set to a predefined fraction of || (rounded up to the next integer).
After the initialization a for loop starts. At each iteration, the -th node (with from 1 to ) is selected in the ordered set of nodes in as the starting point (line 8), and a clique is initialized with just this node = [] (line 9). If the node is not a singleton (| | > 0), in lines 11–11, for each neighbor of , the sets and are computed as defined in (2). The set is then ordered in a non-increasing order of | |, breaking ties by || in non-decreasing order (line 12). This order will be used to determine how nodes from should be considered for insertion in the clique . First of all, the more neighbors they have in common with (i.e., the greater | |), the greater the potential final dimension of the clique. In the case of ties, we will prefer the nodes that are more isolated (i.e., with smaller ||) because it is less probable that they will be considered for other cliques in the future. The algorithm then enters a while loop (lines 13–16): provided there are still nodes left in , the algorithm iteratively adds nodes from the ordered set to the clique , removing them from . A node is added to if all members of are also neighbors of . If this condition is satisfied ( can belong to the clique ), is updated. In line 17, if clique is larger than the best clique found for so far, is set to . As soon as all the first nodes are considered (the for loop in lines 7–17 ends) the best clique found is considered and the solution ˜ℎ is updated. For each pair of nodes , ∈ , the edge {, } is marked as part of the solution if it exists in the graph. Specifically, if {, } ∈ and both and are in , set ˜ℎ = 1, otherwise set ˜ℎ = 0. After processing a component, the clique is removed from the graph. This process repeats until the graph becomes empty, and the algorithm returns the feasible solution ˜ℎ.
To assess the performance of our proposed approach for the CDP, we conducted experiments using
diferent datasets of instances: one derived from
All the experiments were performed on a 12th Gen Intel(R) Core(TM) i7-12700 2.10 GHz CPU with 16.0 GB RAM. For each run, we set a time limit of one hour, with a maximum of 3000 iterations (ℎ) for the Algorithm 1 and 50 iterations () for the inner Subgradient Algorithm 4. Additionally, we used = 10− 4, = 0.5 and = 0.04.
In Table 1, we report the average results obtained on the first dataset
In Table 2, we present the results obtained for the second dataset
In Table 3 we show the average results obtained for the third dataset coming from the DIMACS graph coloring challenge. The instances are grouped based on the number of nodes (up to 50, up to 100, up to 150, up to 300, over 300), with each group representing the mean performance over the considered instances. The column headings are the same as in Table 1.
The results in the table emphasize the strong performance of the proposed algorithm in producing high-quality lower bounds, which are, in most of the cases, superior to the existing heuristic solution values. As the problem size increases with larger numbers of nodes, the computational time grows significantly, with runtimes reaching the time limit for the instances with ≥ 600 (right part of Table 1). Despite the increased computational efort, for those instances the bound found by the DD method is consistently higher than the one found by the ECH. An important positive indicator of the DD algorithm performance is the number of solutions explored. Higher values of #solDD suggest that the algorithm is efectively exploring a broad solution space, which is beneficial for identifying strong lower bounds. This is particularly notable for mid-sized instances, where the algorithm shows high exploration rates. When considering larger instances, the number of explored solutions decreases as the algorithm does not stop for having performed ℎ iterations, but because the time limit of one hour is reached.
The comparison with the continuous relaxation, which provides the best possible benchmark in terms of upper bounds, further demonstrates the quality of the lower bounds. Even if it does not reach the upper bound found by the LP relaxation, the gap is in most of the cases reduced, underlining the strength of the proposed method. The overall trends across the table indicate consistent and reliable performance, with the algorithm adapting well to varying problem structures and scales. In total the DD algorithm is at least as good as the ECH for 115 on 166 instances. Out of these 115 instances, it is strictly better for 95 of them.
Links between dense clusters in networks are highly critical for disinformation spread. In this work, we study a combinatorial optimization problem, named Cluster Deletion, aimed at partitioning a network into clusters of fully connected nodes, by identifying the minimum number of bridge connections. Monitoring these connections allows for disrupting the disinformation flow while preserving intragroup communication. We introduce a Lagrangian heuristic to solve the problem, consisting of a dual descent algorithm equipped with a subgradient method and an ad-hoc repair heuristic. Computational experiments are conducted on benchmark networks from the literature, providing, in most cases, new best-known solutions.
The research of M. Cerulli was partially supported by the project “SEcurity and RIghts in the CyberSpace” SERICS (PE00000014) under the MUR National Recovery and Resilience Plan funded by the European Union - NextGenerationEU. This support is gratefully acknowledged.
The authors have not employed any Generative AI tools.
A. Linking primal constraints with dual variables
3 ∈ ∈ 4 1 2 ∈ 5
In Fig. 1, a graph with 5 nodes is shown, in order to better explain formula (3). Let be node 1, be node 2, and ∈ {3, 4, 5} (i.e., < < ). Observe that, in problem (1), variable appears in all constraints associated to the nodes , and ∈ ∪ . Consider first the case ∈ , that is {, }, {, }, {, } ∈ (node 3 in Fig. 1). We have the following three constraints of type (1b) associated to the nodes (, , ) and involving the variable : + − ≤ 1 N , + − ≤ 1 N , + − ≤ 1 N ,
M , M , M .
Consequently, the contribution of the above constraints to the cost coeficient (, ) is: − − .
We remark that the indices of the variables are always written in such a way that the first index is smaller than the second one. Therefore, will always appear before , which, in turn, will always appear before . This is why, for example, in the third constraint above, instead of having + − ≤ 1, we have + − ≤ 1. As for the multipliers, the first index is fixed to the node on which the corresponding constraint is defined, while the remaining two are ordered in such a way that the second index is smaller than the third one.
Consider now the case ∈ (node 4 in Fig. 1). The constraint to consider is Instead, for ∈ (node 5 in Fig. 1) the constraint to be taken into account is
The corresponding contributions to (, ) are − and − , respectively.
The pseudo-code of the algorithm which is used to update the Lagrangian multipliers in case an infeasible solution ℎ is found is reported in Algorithm 3. It analyzes diferent constraint violations and updates the multipliers accordingly. Algorithm 3: Multipliers update when an infeasible solution is found.
Input: Iteration counter ℎ, multipliers ℎ, ℎ, and cost coeficients ℎ.
Output: Updated multipliers ( ℎ+1, ℎ+1). 1 foreach triplet (, , ) do 2 if constraint (1b) is violated by (, , ) then 3
Δ ← min{ℎ , − ℎ, ℎ}; else if constraint (1c) is violated by (, , ) then Δ ←
min{ℎ , ℎ}; ¯ℎ¯+¯1 ←
¯ℎ¯+¯1 ← ¯ℎ¯¯ + Δ¯¯¯; 11 else if (¯, ¯, ¯) violates constraint (1c) then 12
¯ℎ¯¯ + Δ¯¯¯; 13 Δ ← Δ¯¯¯; 14 return ( ℎ+1, ℎ+1) and Δ
If, for a certain triplet (^, ^, ^), constraint (1b) is violated, i.e., if ℎ ^^ > ^ℎ^ + 1, it means that ^^ + ℎ ^ℎ^ = ^ℎ^ = 1 and ^ℎ^ = 0. From (5), it holds that ^ℎ^ < 0, ^ℎ^ ≥ 0 and ^ℎ^ ≥ 0. We observe that, taking into account Eq. (8) and the remark in Appendix A, any increase of ^ℎ^^ results in an increase of ℎ ^^ and a decrease of both ^ℎ^ and ^ℎ^.
If instead, for a certain triplet (^, ^, ^) constraint (1c) is violated, that is: ℎ ^^ + ^ℎ^ > 1, it means that ℎ ^^ ≥ 0. We observe that (8) indicates that any increase ^^ = ^ℎ^ = 1, which implies, from (5), that ^ℎ^ , ℎ of ^^^ produces a decrease of both ^ℎ^ and ^ℎ^.
ℎ for each triplet (, , ) violating constraint (1c). Then, we look for the tiplet (¯, ¯, ¯) corresponding to the greatest Δ value in line 8. If it violates constraint (1b), in line 10, we update the corresponding multiplier ¯¯¯ as follows while the remaining multipliers for (, , ) ̸= (¯, ¯, ¯) as well as for all (, , ) do not change (lines 6–7). If, instead, (¯, ¯, ¯) violates constraint (1c), we update the corresponding multiplier ¯¯¯ in line 12 as: ℎ+1 = ¯ℎ¯¯ + Δ¯¯¯, ℎ,+,1 = ¯ℎ¯¯ + Δ¯¯¯, while not changing the remaining multipliers (lines 6–7).
More specifically, in line 3, we define
for each triplet (, , ) violating constraint (1b) and, in line 5, we define
Δ = min {︁ℎ , ℎ, − ℎ}︁ ≥ 0,
Δ = min {︁ℎ , ℎ}︁ ≥ 0,
(9)
(10)
(11)
Within the DD algorithm, we call the subgradient method described in this section, which produces a
diferent multiplier pair which can be used to update the value. Actually, the subgradient methods
itself can be used as an alternative to the DD algorithm to solve the dual problem (7). Indeed, this method,
i
‖ ‖2‖‖ 2( (− 1) − () + ()⊤ ) , where = − − 1. Such a stepsize choice is an extension of the well-known Barzilai and Borwein approach to convex nonsmooth optimization.
When applying the subgradient method to our problem (7), represents the pair of multipliers (, ) and () is the function (, ). The corresponding pseudocode is shown in the Algorithm 4. It starts from two points ( 0, 0) and ( 1, 1), which are needed to determine at the first iteration = 1 the value of the stepsize 1. At the beginning, is assigned the tighter value between the upper bounds associated with the two starting points (line 1). Then, new points ( , ) are found at each iteration > 1, by using the stepsize (lines 4–5) and the subgradient (line 9). The subgradient method stops as soon as a point ( , ) associated with a tighter upper bound than the starting one is found (line 11). If no such a solution is produced during iterations, then the procedure returns the last point, together with the associated upper bound (line 13). Thanks to this algorithm, we can modify the Lagrangian multipliers properly within the DD algorithm, also when a feasible solution is found. 4 5 6 7 8 9 10 11 12
13 return ( , ),
‖ ‖2‖( , )‖ ← +2(( , )− ( − 1, − 1)− ( , )⊤( − − 1, − − 1)) ; ← max {︁min {︁, log101(1+) }︁ , 0}︁; Compute ( +1, +1); Compute +1( +1, +1) according to Eq. (6); if ( +1, +1) < then
return ( +1, +1), ( +1, +1) +1 ← max {︁0, − ‖( , )‖ ( , )}︁ , ∈ , , ∈ : < , {, } ∈ ; +1 ← max {︁0, − ‖( , )‖ ( , )}︁ , ∈ , , ∈ : < , {, } ∈/ ;