# The Minimum Spectral Radius of an Edge-Removed Network: A Hypercube Perspective

Authors: Yingbo Wu; Tianrui Zhang; Shan Chen; Tianhui Wang
Journal: Discrete Dynamics in Nature and Society
 (2017)

---

## Abstract

The spectral radius minimization problem (SRMP), which aims to minimize the spectral radius of a network by deleting a given number of edges, turns out to be crucial to containing the prevalence of an undesirable object on the network. As the SRMP is NP-hard, it is very unlikely that there is a polynomial-time algorithm for it. As a result, it is proper to focus on the development of effective and efficient heuristic algorithms for the SRMP. For that purpose, it is appropriate to gain insight into the pattern of an optimal solution to the SRMP by means of checking some regular networks. Hypercubes are a celebrated class of regular networks. This paper empirically studies the SRMP for hypercubes with two/three/four missing edges. First, for each of the three subproblems of the SRMP, a candidate for the optimal solution is presented. Second, it is shown that the candidate is optimal for small-sized hypercubes, and it is shown that the proposed candidate is likely to be optimal for medium-sized hypercubes. The edges in each candidate are evenly distributed over the network, which may be a common feature of all symmetric networks and hence is instructive in designing effective heuristic algorithms for the SRMP.


---

## Body

## 1. Introduction

The epidemic modeling is recognized as an effective approach to the understanding of propagation process of objects over a network [1, 2]. For instance, epidemic models help us understand the key factors that affect the prevalence of malware [3–8]. The speed and extent of spread of an epidemic on a network depend largely on the structure of the network; whether the epidemic goes viral depends on whether the spectral radius of the network exceeds a threshold [9–14]. Therefore, reducing the spectral radius of a network by removing a set of edges is an effective approach to the containment of the prevalence of an undesirable epidemic on the network. The spectral radius minimization problem (SRMP) aims to remove a given number of edges of a network so that the spectral radius of the resulting network attains the minimum. As the SRMP is NP-hard [15], it is much unlikely that there be a polynomial-time algorithm for it. As thus, a number of heuristic algorithms for the SRMP have been proposed [15–19]. In most situations, these heuristics are ineffective, because they produce nonoptimal solutions rather than optimal solutions. For the purpose of developing effective heuristic algorithms for the SRMP, it is appropriate to gain insight into the pattern of an optimal solution to the SRMP by means of checking some regular networks. Recently, Yang et al. [20] studied the SRMP for 2D tori.Hypercubes are a class of regular networks [21]. Due to remarkable advantages in communication [22–25], fault tolerant communication [26–30], fault diagnosis [31–34], and parallel computation [35, 36], hypercubes have been widely adopted as the underlying interconnection network in multicomputer systems [37]. To our knowledge, the SRMP for hypercubes is still unsolved.This paper addresses three subproblems of the SRMP, where two/three/four edges are removed from a hypercube, respectively. First, for each of the three subproblems of the SRMP, a candidate optimal solution is presented. Second, it is shown that the candidate is optimal for small-sized hypercubes, and it is shown that the proposed candidate is likely to be optimal for medium-sized hypercubes. The edges in each candidate are evenly distributed over the network, which may be a common feature of all symmetric networks and hence is instructive in designing effective heuristic algorithms for the SRMP.The remaining materials are organized in this fashion: the preliminary knowledge is given in Section2. Section 3 presents the main results of this work. Finally, Section 4 summarizes this work.


## 2. Preliminaries

For fundamental knowledge on the spectral radius of a network, see [38, 39]. The SRMP is formulated as follows: given a network G=(V,E) and a positive integer k, find a set of k edges of G so that the surviving network obtained by removing the set of edges from the network achieves the minimum spectral radius.Ann-dimensional cube (n-D cube, for short), denoted by Hn, is a network G=(V,E), where there is a one-to-one correspondance ϕ from V to the set of all 0-1 binary strings of length n so that node u is adjacent to node v if and only if ϕ(u) differs from ϕ(v) in exactly one bit position. In what follows, it is always assumed that the nodes of a hypercube have been labelled with 0-1 strings in this way. See Figure 1 for three small-sized hypercubes.Figure 1
Three examples ofHn.Ann-D cube can also be defined in a recursive way as follows. (1) A 0-D cube is a graph on a single node. (2) For n≥1, an n-D cube is built from two copies of an (n-1)-D cube in this way: connect each node in one copy to the same node in the other copy.


## 3. Main Results

This section considers the optimal scheme of deleting two/three/four edges fromHn, respectively.


### 3.1. Deleting Two Edges

Firstly, we consider a subproblem of the SRMP, denoted by SRMP-H2, for which two edges will be deleted from a hypercube. Let us present a candidate for the optimal solution to the SRMP-H2 as follows, wheren denotes the dimension of the hypercube:(1)e1=0n,0n-11,e2=1n,1n-10.Figure2 shows the proposed candidate in H2, H3, H4, and H5, respectively.Figure 2
The proposed candidate inHn.For2≤n≤7, it follows by exhaustive search that the proposed candidate is optimal. For instance, assume that the red edge in the upper-left 3D subcube of H5 is the first deleted edge, and each of the remaining edges is a candidate for the second deleted edge. The spectral radius of the surviving network formed by deleting each of the candidate edges from H5 is shown in Figure 3. It can be seen that the larger the distance between the two edges, the smaller the spectral radius of the surviving network. At the extreme, the proposed candidate is optimal.Figure 3
Assume that the red edge in the upper-left 3D subcube ofH5 is the first deleted edge and each of the remaining edges is a candidate for the second deleted edge. The spectral radius of the surviving network formed by deleting each of the candidate edges from H5 is shown.For8≤n≤11, the proposed candidate is compared with 103 random candidates in terms of the spectral radius of the surviving network; see Figure 4. It is concluded that the proposed candidate is optimal among these candidates.Figure 4
The proposed candidate (red) versus103 random candidates (blue).Therefore, we propose the following conjecture.Conjecture 1.
For alln≥2, the proposed candidate is an optimal solution to the SRMP-H2.


### 3.2. Deleting Three Edges

Secondly, we consider a subproblem of the SRMP problem, denoted by SRMP-H3, for which three edges will be removed from a hypercube. Let us present a candidate for the optimal solution to the SRMP-H3 as follows, wheren denotes the dimension of the hypercube, c=⌊(n+1)/3⌋:(2)e1=0n,0n-11,e2=0n-2c12c,0n-2c-112c+1,e3=1n-c-10c+1,1n-c0c.Figure 5 shows the proposed candidate in H3, H4, H5, and H6, respectively.Figure 5
The proposed candidate inHn.For2≤n≤6, it follows by exhaustive search that the proposed candidate is optimal. For 7≤n≤10, the proposed candidate is compared with 103 random candidates; see Figure 6. It is concluded that the proposed candidate is optimal among these candidates. Therefore, we propose the following conjecture.Figure 6
The proposed candidate (red) versus103 random candidates (blue).Conjecture 2.
For alln≥3, the proposed candidate is an optimal solution to the SRMP-H3.


### 3.3. Deleting Four Edges

Finally, consider a subproblem of the SRMP, denoted by SRMP-H4, for which four edges will be deleted from a hypercube. Let us present a candidate to the optimal solution to the SRMP-H4 as follows, wheren denotes the dimension of the hypercube, c=⌊(n-1)/3⌋:Ifn≡0,2 mod 3, then (3)e1=0n,0n-11,e2=0n-2c-212c+2,0n-2c-212c+10,e3=1n-2c-20c1c+10,1n-2c-20c1c02,e4=1n-c-20c+11,1n-c-20c12.Ifn≡1 mod 3, then (4)e1=0n,0n-11,e2=0n-2c-112c+1,0n-2c-112c0,e3=1n-2c-10c1c+1,1n-2c-10c1c0,e4=1n-c-10c+1,1n-c-10c1.Figure7 shows the proposed candidate in H3, H4, H5, and H6, respectively.Figure 7
The proposed candidate inHn.For3≤n≤6, it follows by exhaustive search that the proposed candidate is an optimal solution to the SRMP-H4 problem. For 7≤n≤10, the proposed candidate is compared with 103 random candidates; see Figure 8. It is concluded that the proposed candidate is optimal among these candidates. Therefore, we propose the following conjecture.Figure 8
The proposed candidate (red) versus103 random candidates (blue).Conjecture 3.
For alln≥3, the proposed candidate is an optimal solution to the SRMP-H4.


## 3.1. Deleting Two Edges

Firstly, we consider a subproblem of the SRMP, denoted by SRMP-H2, for which two edges will be deleted from a hypercube. Let us present a candidate for the optimal solution to the SRMP-H2 as follows, wheren denotes the dimension of the hypercube:(1)e1=0n,0n-11,e2=1n,1n-10.Figure2 shows the proposed candidate in H2, H3, H4, and H5, respectively.Figure 2
The proposed candidate inHn.For2≤n≤7, it follows by exhaustive search that the proposed candidate is optimal. For instance, assume that the red edge in the upper-left 3D subcube of H5 is the first deleted edge, and each of the remaining edges is a candidate for the second deleted edge. The spectral radius of the surviving network formed by deleting each of the candidate edges from H5 is shown in Figure 3. It can be seen that the larger the distance between the two edges, the smaller the spectral radius of the surviving network. At the extreme, the proposed candidate is optimal.Figure 3
Assume that the red edge in the upper-left 3D subcube ofH5 is the first deleted edge and each of the remaining edges is a candidate for the second deleted edge. The spectral radius of the surviving network formed by deleting each of the candidate edges from H5 is shown.For8≤n≤11, the proposed candidate is compared with 103 random candidates in terms of the spectral radius of the surviving network; see Figure 4. It is concluded that the proposed candidate is optimal among these candidates.Figure 4
The proposed candidate (red) versus103 random candidates (blue).Therefore, we propose the following conjecture.Conjecture 1.
For alln≥2, the proposed candidate is an optimal solution to the SRMP-H2.


## 3.2. Deleting Three Edges

Secondly, we consider a subproblem of the SRMP problem, denoted by SRMP-H3, for which three edges will be removed from a hypercube. Let us present a candidate for the optimal solution to the SRMP-H3 as follows, wheren denotes the dimension of the hypercube, c=⌊(n+1)/3⌋:(2)e1=0n,0n-11,e2=0n-2c12c,0n-2c-112c+1,e3=1n-c-10c+1,1n-c0c.Figure 5 shows the proposed candidate in H3, H4, H5, and H6, respectively.Figure 5
The proposed candidate inHn.For2≤n≤6, it follows by exhaustive search that the proposed candidate is optimal. For 7≤n≤10, the proposed candidate is compared with 103 random candidates; see Figure 6. It is concluded that the proposed candidate is optimal among these candidates. Therefore, we propose the following conjecture.Figure 6
The proposed candidate (red) versus103 random candidates (blue).Conjecture 2.
For alln≥3, the proposed candidate is an optimal solution to the SRMP-H3.


## 3.3. Deleting Four Edges

Finally, consider a subproblem of the SRMP, denoted by SRMP-H4, for which four edges will be deleted from a hypercube. Let us present a candidate to the optimal solution to the SRMP-H4 as follows, wheren denotes the dimension of the hypercube, c=⌊(n-1)/3⌋:Ifn≡0,2 mod 3, then (3)e1=0n,0n-11,e2=0n-2c-212c+2,0n-2c-212c+10,e3=1n-2c-20c1c+10,1n-2c-20c1c02,e4=1n-c-20c+11,1n-c-20c12.Ifn≡1 mod 3, then (4)e1=0n,0n-11,e2=0n-2c-112c+1,0n-2c-112c0,e3=1n-2c-10c1c+1,1n-2c-10c1c0,e4=1n-c-10c+1,1n-c-10c1.Figure7 shows the proposed candidate in H3, H4, H5, and H6, respectively.Figure 7
The proposed candidate inHn.For3≤n≤6, it follows by exhaustive search that the proposed candidate is an optimal solution to the SRMP-H4 problem. For 7≤n≤10, the proposed candidate is compared with 103 random candidates; see Figure 8. It is concluded that the proposed candidate is optimal among these candidates. Therefore, we propose the following conjecture.Figure 8
The proposed candidate (red) versus103 random candidates (blue).Conjecture 3.
For alln≥3, the proposed candidate is an optimal solution to the SRMP-H4.


## 4. Summary

This paper has addressed the spectral radius minimization problem for hypercubes. Given the number of edges to be deleted, a candidate for the optimal solution has been presented. For small-sized hypercubes, the proposed candidate has been shown to be optimal. For medium-sized hypercubes, it has been shown that the proposed candidate is likely to be optimal. Due to the symmetry of hypercubes, there are multiple optimal solutions for each of the subproblems. The experimental results show that, up to isomorphism, all of the optimal solutions are identical. By observing the pattern of the proposed candidate, it has been speculated that, for any symmetric network, the edges in an optimal solution are always evenly distributed.Towards this direction, some researches are yet to be done. First, the proposed conjectures need a proof. Second, this work should be extended to asymmetric networks such as the hypercube-like networks [40, 41], the small-world networks [42], the scale-free networks [43, 44], and the general networks [45, 46]. Last, the effectiveness of heuristics for the spectral radius minimization problem must be improved.



---

*Source: 1382980-2017-04-19.xml*