A multiobjective evolutionary algorithm for optimizing the small-world property

Abstract

Small-world effect plays an important role in the field of network science, and optimizing the small-world property has been a focus, which has many applications in computational social science. In the present study, we model the problem of optimizing small-world property as a multiobjective optimization, where the average clustering coefficient and average path length are optimized separately and simultaneously. A novel method for optimizing small-world property is then proposed based on the multiobjective evolutionary algorithm with decomposition. Experimental results have proved that the presented method is capable of solving this problem efficiently, where a uniform distribution of solutions on the Pareto-optional front can be generated. The optimization results are further discussed to find specific paths for optimizing different objective functions. In general, adding edges within the same community is helpful for promoting ACC, while adding edges between different communities is beneficial for reducing APL. The optimization on networks with the feature of community structure is more remarkable, but community structure has less impact on the optimization when the internal community is triangles-saturated.

1. Introduction

Following the research of small-world and scale-free network models, many studies have been devoted to the analysis of structural properties of complex networks and social networks [1, 2]. In particular, promoting specific network structural indices has been a major focus, which is helpful in improving the efficiency of social system [3]. Among the different indices to be optimized, the small-world property is one of the most popular ones, and the optimization of which is of practical significance in various domains [4].

The term “small world” was first proposed by Milgram [5], who verified the small-world feature of human beings by conducting the famous experiment of six-degree separation. The small-world characteristics of social networks have been proved by a list of subsequent activities [6, 7]. Watts and Strogatz [1] then proposed a dynamic network model (WS model) to explain the small-world effect, which had a profound influence on complexity science and led the success of network science emerging as an interdisciplinary subject. In the rewiring process from the regular structure to the randomized state, they found there exists a critical phase where the network has higher average clustering coefficient (ACC) and lower average path length (APL), which are referred as the typical feature of small-world networks.

Small-world property emerges in various real-world domains, such as power grid [8], transport networks [9], control of epidemics [10], game theory [11] and management science [12, 13]. Improving the small-world property can promote the efficiency of signal transmission and accelerate the computational synchronization [4]. In the neural system, the interconnectedness of small-world network nodes can stimulate a list of biological properties [14–16]. When people fall into the prisoner’s dilemma, the small-world structure helps promote the information transmission of cooperative behaviors and speed up the cooperative convergence [11, 17, 18]. Since lower path length and higher clustering coefficient are helpful for spreading social information, the small-world network is beneficial to knowledge diffusion and knowledge transfer [19, 20]. The inherent strength of small-world topology has prompted research on how to efficiently generate small-world networks.

Since the process of rewiring edges may result in isolated nodes, Watts and Newman [21] proposed a novel model which is to adding shortcut edges. Similarly, Kleinberg [22] established the long-range connections based on the six-degree-separation theory. Subsequently, a list of studies have focused on introducing shortcuts to improve connectivity [23–28]. The optimal methods from these studies have been applied to various real-world situations, such as the set of wireless network [29]. However, most of the existing researches have paid much attention on the reduction of APL, which cannot fully represent the optimization of small-world property. A few studies have included other small-world characteristics, such as ACC [30, 31]. Even though, the main objective function is still the minimum of APL. Therefore, a research that cares about both APL and ACC is required.

Previous studies have found that the small-world structure facilitates the information diffusion and epidemiological transmission [32], and the mainstream reason for the conclusion is attributed to the small value of APL. In fact, reducing APL and increasing ACC have different effects on contributing to the improvement of network properties. Reducing APL lies in establishing relationships between two points over long distances, which highlights the strength of weak ties. Promoting ACC lies in strengthening the unity within the community, i.e., consolidating the effectiveness of strong ties. From a sociological perspective, both strong and weak ties have significant impacts on dynamic human behaviors, such as job seeking. Separately increasing ACC and decreasing APL are of great significance for optimizing different functions of social ties. Moreover, maintaining or adding social ties incurs costs, which requires seeking a balance between strong and weak ties within limited resources. The balance actually depends on the specific scenario in which the values of different objects are situated. For example, job seeking in family businesses relies on the function of strong ties, while it relies more on weak ties in multinational corporations. Simultaneously optimizing ACC and APL separately provides a new perspective for interpreting classic social theories like The Strength of Weak Ties [33], and it is also a new case for applying computational theory to social science.

In a recent study, Du et al. formulated the network property as ACC/APL [4], and proposed an optimization model to maximize the index. However, this model cannot control the ratios of the importance of clustering and distance. A scientific optimization for small-world property should separately consider the calculation of ACC and APL. The method of multiobjective optimization that seeks to optimize multiple objective functions helps us solve this problem. Schleich et al. proposed a multiobjective algorithm for optimizing both ACC and APL on vehicular ad hoc networks to add shortcuts between unconnected networks [34]; this algorithm can be only applied into unconnected wireless networks, but is not suitable for any other kinds of networks.

Given the state-of-the-art methods that optimizing ACC, APL or ACC/APL [3, 4, 23–31], most of them are based on the heuristic tactics, which may inevitably fall into local minimum. Even for the single objective optimization where the complexity is smaller, the effectiveness cannot be guaranteed, especially in large-scale networks. Genetic algorithm and simulated annealing algorithm are difficult to converge [4], and the greedy algorithm can only obtain local optimum [3]. In ref. [34], the multiobjective algorithm for optimizing the small-world property is based on the nondominated sorting genetic algorithm II (NSGA-II), but it is less effective than those single-objective-optimization algorithms, which means the acquired Pareto-optimal front is not the ground truce. In the present study, we retain the advantages of the mentioned algorithms, and form an effective comprehensive algorithm. The new designed algorithm may not only output results with more effectiveness, but also find the Pareto-optimal front more efficiently.

In the present study, we propose a novel algorithm to optimize small-world property based on a multiobjective evolutionary algorithm with decomposition, termed as MOEA/D-SW, which simultaneously optimize the two objectives, ACC and APL. In general, the present study consists of three contributions: (1) We formulize the promotion of small-world property as a mathematical problem, and thus we propose specialized optimization framework that minimizes APL and maximizes ACC separately and simultaneously. The framework is also beneficial for interpreting classic social theories. (2) We propose an algorithm for optimizing small-world property based on MOEA/D-SW, which can be more effective than traditional algorithms despite of single-objective or multi-objective optimization. (3) The optimization results of MOEA/D-SW are further explained to find specific paths for optimizing different objective functions. The present study also explore the optimization mechanisms under different network structures.

In the following, we present a literature review to the generation or transformation of small-world networks, and propose the objective functions to be optimized in Section 2. Section 3 describes the proposed MOEA/D-SW in detail. We conduct experiments with the proposed method on different kinds of networks in Section 4, Conclusion and discussion are presented in Section 5.

2. Related background

2.1 Optimization of small-world property

“Collective dynamics of ‘small-world’ networks” written by Watts and Strogatz was the first study to define the structure of small-world networks [1]. It describes a dynamic model of edge rewiring process (WS model), where a probability p adjusts for the long-distance edges rewired from a regular, locally connected structure, to a completely randomized state. In this progress, there exists an intermediate state with high ACC, like regular networks, and low APL, like random networks. This state is referred as the small-world feature.

One drawback of WS model is that it may lead to isolated nodes in the rewiring process. To solve this problem, Newman and Watts chose to add edges in the dynamics (referred as NW model) [21]. The process of adding edges is based on randomization, which cannot guarantee the effectiveness of the resulting small-world network when the number of edges is limited. This research has prompted a list of studies focusing on adding shortcuts to improve diffusion efficiency [23–28].

Among the methods of optimizing the small-world property by adding edges, evolutionary algorithms have gradually become more popular, which are parallel in nature and are effective in solving combinatorial explosion problems. In the research proposed by Du et al. [4], an index of ACC/APL is proposed to quantifying the small-world feature, and a genetic algorithm (GA) and a greedy algorithm (GR) are proposed to optimize the index. Compared with different heuristic operators, GA outputs the best result, and has been also proved to be effective in promoting ACC [4]. GR is the most time-saving, but can only achieve local optimum. Du et al. proposed a memetic algorithm (MA) that can minimize APL making the network a smaller world [3]. The memetic strategy combines the strength of GA and GR, which has proved to be more effective than the classic shortcut-adding algorithms including Average Shortest Path Distance Minimization [35], EdgeEffect Algorithm [36], Fast MinAPL algorithm [37], Path Screening Algorithm [38], although the time complexity of MA is higher. These studies have laid the foundation for optimizing the generating process of small-world networks. The present study may also apply some of these evolutionary techniques in the proposed algorithm, e.g. Genetic Operator, Tournament Selection and Local Search.

2.2 Objective functions

A small-world network can be characterized as low APL and high ACC [1]. APL measures the average shortest distance between all pairs of nodes, and is formulated as , where N is the network size and d(i, j) is the geodesic distance between nodes i and j. ACC is the average value of the local clustering coefficient CC_v (), where CC_v = |E(Γ_v)|/(k_v (k_v − 1)). |E(Γ_v)| is the number of edges among node v’s neighbors, (k_v (k_v − 1)) is the number of pairs of nodes among node v’s neighbors. In the present study, we aim to minimize APL and maximize ACC simultaneously by adding edges. Specifically, given a connected network with the size of N and the number of edges ‖E‖, we aim to add k edges to reduce APL and increase ACC. The corresponding objective functions can be formulated as Eq (1).

(1)

2.3 Multiobjective optimization

The present study aims to simultaneously decrease APL and increase ACC, which is a multiobjective optimization problem (MOP). MOP can be described as Eq (2), where x is the decision vector, m is the number of objective functions, and Ω is the decision space.

(2)

In a minimization problem for each objective, a decision vector x_A dominates another vector x_B (x_A ≻ x_B) if and only if they follow the rule of Eq (3).

(3)

Then a decision vector x* becomes the Pareto-optimal solution if there are no any other vectors that dominate x*. The Pareto-optimal set is formulated as Eq (4).

(4)

The corresponding objective functions of the Pareto-optimal set is the Pareto-optimal front described as Eq (5).

(5)

Multiobjective optimization algorithms aim to find the set of nondominated solutions that approximates the true Pareto-optimal front. Much attention has been paid on the employment of evolutionary knowledge in the design of multiobjective optimization algorithms, such as Pareto archived evolutionary strategy (PAES) [39], strength Pareto evolutionary algorithm II (SPEA-II) [40], or nondominated sorting genetic algorithm II (NSGA-II) [41]. Among these studies, the Multiobjective Evolutionary Algorithm based on Decomposition (MOEA/D) [42] is the state-of-the-art method that decomposes MOP into several scalar optimization subproblems and simultaneously optimizes them. This algorithm has been shown to be effective in solving complex multiobjective optimization problems, especially in the field of network science [43–47]. Because of its high performance, we proposed a novel algorithm to multiply improve the small-world property based on MOEA/D (referred as MOEA/D-SW).

With regard to the optimization of small-world property, NSGA-II has been applied to adding shortcuts between communities, which output the best results compared with different multiobjective optimization strategies [34]. Benefiting from the strength of genetic technique, NSGA-II displays powerful spatial search capabilities. The present algorithm may also employ the genetic operator. The difference is that MOEA/D-SW includes the strength of local search, which significantly improves the capability of short-distance search. Moreover, the mechanism of decomposition is completely different from that of NSGA-II, which is more appropriate for the optimization of small-world property.

3. The algorithm

3.1 Framework of MOEA/D-SW

The idea behind MOEA/D is that the approximation of Pareto-optimal front can be decomposed into a list of scalar optimization subproblems [43]. The algorithm generates a population of solutions for each subproblem, and there exist a list of neighborhood relations among these subproblems, which are calculated by the distances between their aggregation coefficient vectors. With such an operation, two neighboring solutions are similar, while those pairs of long-distance solutions are quite different. At each generation, each subproblem is optimized by using information from its neighboring subproblems.

There are several approaches for constructing aggregation functions, such as Tchebycheff Approach or Weighted Sum Approach [48]. Since we cannot predict whether the Pareto-optimal front is concave, Weighted Sum Approach is not appropriate here, and thus we employ Tchebycheff approach in MOEA/D-SW. Based on the Tchebycheff approach, the scalar optimization problem is described as Eq (6),(6)where submits to for each objective function i. In this approach, there exists a weight λ that can make each Pareto-optimal vector x* to be optimal in Eq (6), and altering the weight vector that adjusts for neighborhood relations can output different Pareto-optimal solutions. Since g^te(x|λ, z*) is continuous of the weight λ, when λ_i is close to λ_j, the solution of g^te(x|λ_i, z*) then should be similar to g^te(x|λ_j, z*). One of the motivations behind MOEA/D is that the information of solutions of g^te with different weight vectors which are close to that of λ_j can be helpful in promoting g^te(x|λ_i, z*). This provides an opportunity for the local search.

Algorithm 1 presents MOEA/D-SW framework. Some necessary parameters and the adjacent matrix are first input. A population consisting of S_pop solutions is initialized by Initial_Population(). Under the maximum iteration G_max, a repeated process is conducted to search for the best solution. In this process, we conduct the genetic operation for each solution. For each solution j, we detect its neighboring solutions by finding its nearest corresponding weight vectors. Then we operate crossover and mutation in the Genetic_Operation() on the detected neighboring solutions to generate an offspring population. Update_Population() employs the Tchebycheff approach and find optimal solutions among the neighboring solutions and offspring solutions. Next, the operator removes the less optimal solutions. In the next step, we use the function Local_Search() to find the local optimized chromosome. Finally, we output the optimal set of solutions.

Algorithm 1. Framework of MOEA/D-SW

1. Input: maximum number of generations G_max; population size S_pop; size of neighboring population S_neighbor; probability of crossover P_c; a pair of weight vectors which follows the uniform spread: λ¹, λ²; the initial network adjacency matrix A;

2. P ← Initial_Population(S_pop);

3. For i = 1: 1: G_max

4.  For j = 1: 1: S_pop

5.   Find P_j’s neighboring population P_neighbor consisting of S_neighbor vectors based on λ¹ and λ²

6.   P_offspring ← Genetic_Operation(P_neighbor, P_c);

7.   P ←Update_Neighbor(P_neighbor, P_offspring, λ¹, λ²);

8.  End For

9.  P ← Local_Search(P);

10. End For

11. Output: an external population

3.2 Representation

Each solution is represented by a chromosome coded by genes. In the present study, we aim to find the pairs of unconnected nodes to be added in order to optimize the small-world property. Therefore, we first find out the positions of those unconnected pairs of nodes, and assign an identity number for each position. The solution can then be written as a series of the corresponding identity numbers. The length of the chromosome is equaling to the number of added edges, and each gene denotes the corresponding unconnected pair of nodes. An illustration of the representation is shown in Fig 1. If we change the 2^nd gene from 2 to 3 and the 3^rd gene from 5 to 4, then the added edges between a and d and between b and f are respectively changed to the positions between b and d and between b and e.

[Figure omitted. See PDF.]

The left part is the topology of the original network and its positions of disconnected edges. The middle part is the identity number corresponding to the disconnected edges, and an illustration of chromosomes. The right part is the topological graph corresponding to the two chromosomes. Solid lines denote the existing edges, and dashed lines denote the edges to be added.

In the initialization, a population consisting of S_pop chromosomes is generated, and we randomly assign a set of identity numbers to each chromosome. We also compute the Euclidean distances between each pair of vectors and output the T closest weight vectors. For each object i = 1 and 2 (1 for ACC, 2 for APL), we generate T pairs of closest weight vectors λ₁ and λ₂. Increasing the number of weight vectors may output a smoother PF, but sacrifices the time complexity. Consistent to ref. [45], the present study sets T = 100, which is capable of finding a satisfactory outcome.

3.3 Genetic operation

Genetic operation is the primary function of Genetic Algorithm, where crossover and mutation operations are employed. In this part, crossover procedure is conducted with the probability of P_c and the mutation procedure runs with 1 − P_c.

In the crossover procedure, we first randomly select two chromosomes from the focal chromosome’s neighboring population detected based on the nearest corresponding weight vectors as parental chromosomes. The shared elements of offspring chromosomes remain unchanged, and the crossover is conducted only for those uncommon elements which differ between the two parental chromosomes. For each pair of unshared elements, a random number a (0 ≤ a ≤ 1) is generated. If a > 0.5, the corresponding pair of unshared genes are exchanged; otherwise, they remain unchanged. In the next step, we add those shared genes on the two new links. Finally, we disrupt the gene order of the two chromosomes and output two offspring solutions. An illustration of the crossover is shown in Fig 2. The identity numbers 3, 5, 31, 7, 13 are shared elements of both selected chromosomes and they remain unchanged. For the other five pairs of unshared elements, the 2^nd, 4^th and 5^th genes are swapped between the two parental chromosomes because a is bigger than 0.5 for them.

[Figure omitted. See PDF.]

We check every pair of uncommon genes of the pair of parental chromosomes, if the generated random number a is smaller than 0.5, the gene remains unchanged; and if a is bigger than 0.5, the corresponding genes are exchanged. Finally, we add the shared elements to new offspring chromosomes and disrupt their gene order.

During mutation, we randomly choose a chromosome from the neighboring population. We randomly generate a number x from 0 to the number of added edges. We then randomly select x genes to be mutated, i.e. a different identity number is randomly selected to replace that gene.

3.4 Local search

In order to improve the algorithm efficiency, we introduce a local search in MOEA/D-SW. The local search operator has been proved to be capable of decreasing useless explorations and accelerating the iteration convergence in the field of network science [49, 50]. Given the updated population derived by previous operations, we check each gene for each solution and find out whether assigning the corresponding edge’s neighbor’s value to it can simultaneously lead to a higher ACC and a lower APL. In this part, an edge’s neighbor is the edge sharing one of the same nodes. If the replacement is able to improve both the two objective functions, then we accept the new assignment. In order to eliminate the endogeneity, we check each gene in a random order.

Algorithm 2. Local Search

1. Input: the updated population P; size of population S_pop; the number of edges to be added k;

2. For i = 1: 1: S_pop

3.  Generate a sequence (Seq) with a disordered list from 1 to k;

4.  For j = 1: 1: k

5.   Find out P(i, Seq(j))’s neighbors y and the number of these neighbors s;

6.   Generate a population C consisting of s chromosomes of P(i) and generate a null set P^new;

7.   For l = 1: 1: s

8.    C(l, Seq(j)) = y(l);

9.    If ACC(C(l)) > ACC(P(i)) & APL(C(l)) < APL(P(i))

10.     Add C(l) to P^new

11.    end If

12.   End For

13.   Randomly select a chromosome from P^new to replace P(i) if P^new is not a null set;

14.  End For

15. End For

16. Output the new population P

3.5 Update

After performing the local-search operator, we update the population based on the updating procedure. We first update z, i.e. for each object j = 1 and 2, we assign z_j = f_j(y′) if z_j = f_j(y′). Then we update the neighboring solutions, i.e. for each object j = 1 and 2, we let x_j = y′ if g^te (x_j|λ_j, z) ≥ g^te (y′|λ_j, z). Further, we remove the vectors dominated by y′, and add those vectors that dominate y′ as well.

When the procedure reaches its maximum iteration, MOEA/D-SW may output a list of optimal solutions, each of which corresponds to a specific tradeoff between ACC and APL. The solution set may diverse the shortcut adding ways, which provides a hierarchical structure of the optimal network.

4. Experiments

In this section, we test the performance of MOEA/D-SW on a regular network and a random network. We also conduct the experiment on various real-world networks and interpret the experimental results in the social context. Table 1 shows the necessary parameters used in the experiments. Specifically, the larger G_max, S_pop, or S_neighbor help increase precision but sacrifice the time complexity. Therefore, we set them to moderate values that can form satisfactory solutions by MOEA/D, consistent to ref. [45]. P_c adjusts for the allocation between the long-distance and short-distance search, and the value of 0.1 for P_c can output the best performance for MOEA/D-SW as shown in the appendix. The procedure is carried out by Matlab on a 32-core workstation with 128 GB memory.

[Figure omitted. See PDF.]

4.1 Results for computer-generated regular and random networks

We first respectively carry out the proposed algorithm on a regular network and a random network generated by computers for 10 times. The two networks consist of 30 nodes with the average degree of 8. Among the state-of-the-art algorithms that aim to optimize the small-world property, 4 single-objective optimization model including the memetic algorithm (MA-SW) proposed by Du et al. [3], the genetic algorithm (GA-SW) and the greedy algorithm (GR-SW) proposed by Du et al. [4], and the typical Newman’s and Watts’s proposed model in 1999 (NW model) [21] are popular ones. The present study aims to compare the effectiveness of MOEA/D-SW with the four algorithms. As mentioned in Section 2, MA is effectively in minimizing APL, GA performs the best on promoting ACC/APL and ACC, GR is the most time-saving, while NW is the most classic. We also compare the result of MOEA/D-SW with NSGA-II, because it has been already applied to adding shortcuts, and it performs the best among different multiobjective optimization strategies [34].

According to Du et al. [4], the small-world property can be generally formulated as ACC/APL, and we thus compare the mean value of the maximum ACC/APL derived by MOEA/D-SW with the results derived by other methods. Fig 3 shows the optimal ACC/APL for each number of added edges k acquired by the 6 algorithms on the regular network and the random network. Generally, ACC/APL has the same tendency among the regular network and the random network, i.e. it increases as k increases. Among the 6 algorithms, MOEA/D-SW always performs the best, from which can be concluded that MOEA/D-SW can effectively solve the problem of optimizing the small-world property. GR-SW performs relatively steady on both the two network structures, while MA-SW is more limited on the random network because of the local optimism. GA-SW performs fare well on the random network but is limited on the optimization process on the regular network. NSGA-II performs less effectively on the single-objective optimization. Since NW model is based on the principle of randomly adding edges, it cannot guarantee the effectiveness of improving the small-world property. Tables 2 and 3 show statistical tests of ACC/APL among different algorithms, and we can find MOEA/D-SW is significantly effective than its peers.

[Figure omitted. See PDF.]

(a) and (b) are the results on the regular and the random networks, respectively.

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

We also present the results of the minimum APL among the 6 algorithms in Fig 4, and we can find MOEA/D-SW and GA-SW perform the best. GR-SW and MA-SW are less effective, but they are nearly coincident with MOEA/D-SW and GA-SW. NSGA-II performs better than NW model, but it is still limited to the single-objective optimization. The specific statistical tests can be seen from Tables 4 and 5.

[Figure omitted. See PDF.]

(a) and (b) are the results on the regular and the random networks, respectively.

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

Fig 5 shows the results of the optimal ACC among the 6 algorithms. MOEA/D-SW performs the best on promoting ACC, GR-SW performs the second, GA-SW performs the third, MA-SW performs the forth, NSGA-II performs the fifth, while NW model cannot effectively optimize ACC. Same conclusions can be also found from the statistical tests in Tables 6 and 7.

[Figure omitted. See PDF.]

(a) and (b) are the results on the regular and the random networks, respectively.

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

Fig 6(a) presents the Pareto-optimal fronts derived by MOEA/D-SW and NSGA-II on the regular network with the number of added edges k = 10, from which we can find that the two Pareto-optimal fronts have the hierarchical structure. However, MOEA/D-SW is more optimal than NSGA-II as shown in Fig 4(a). Each point denotes a unique solution of adding shortcuts. Corresponding to the solutions of MOEA/D-SW in Fig 4(a), we present three topologies as described in Fig 6(b)–6(d) that respectively output the minimum APL (APL = 1.823, ACC = 0.551), the maximum ACC (APL = 2.170, ACC = 0.671) and the maximum ACC/APL (APL = 1.991, ACC = 0.660). These results reflect different strategies corresponding to different objectives. As shown in Fig 6(b), we can find the optimal strategy is to connect the distant nodes if the main objective is to minimize APL. This strategy can significantly decrease the distance between each pair of nodes. If the objective is to maximize ACC, the optimal strategy is to add edges in the neighborhood that helps construct more triangles as shown in Fig 6(c), although it may sacrifice the decline of APL. As shown in Fig 6(d), the optimal strategy takes both distance and triangles into account if we aim to maximize ACC/APL. This strategy is to connect to a hub node from both distant nodes and neighboring nodes. According to Du et al. [51], establishing connections between the hub nodes and the rest of nodes is an efficient way to decrease diameter. Therefore, connecting distant nodes to the hub can effectively decrease APL. When the new added edges link to those neighboring nodes, more triangles may then be constructed, and thus ACC increases as a result. These results suggest that MOEA/D-SW can output a series of effective solutions for different goals.

[Figure omitted. See PDF.]

(a) is the results of Pareto-optimal front, where the black line represents the results acquired by MOEA/D-SW, and the blue line represents the results acquired by NSGA-II, (b) is the solution with the minimum APL, (c) is the solution with the maximum ACC, (d) is the solution with the maximum ACC/APL. The solid lines represent edges of the initial network, the dashed lines represent the added edges.

Fig 7 presents the Pareto-optimal fronts derived by MOEA/D-SW and NSGA-II on the random network with k = 10 and its corresponding solutions. The result of MOEA/D-SW is more effective, and it has a hierarchical structure, while NSGA-II has not. Fig 7(b) and 7(c) correspond to the optimal results of minimum APL (APL = 1.703, ACC = 0.376) and the maximum ACC (APL = 1.752, ACC = 0.431, it is also the result of maximum ACC/APL). When the main object is to minimize APL, most added edges are connected to hub nodes (e.g. nodes 14 and 30), which can decrease the network diameter as shown in Fig 7(b). If we aim to maximize ACC, the optimal strategy is to create as many triangles as possible, shown as Fig 7(c). This solution also outputs the maximum of ACC/APL, because it does not sacrifice much of the decline of APL. Results in Figs 6 and 7 have proved that MOEA/D-SW can find an effective Pareto-optimal front on different network structures.

[Figure omitted. See PDF.]

(a) is the results of Pareto-optimal front, where the black line represents the results acquired by MOEA/D-SW, and the blue line represents the results acquired by NSGA-II, (b) is the solution with the minimum APL, (c) is the solution with both the maximum ACC and the maximum ACC/APL. The solid lines represent edges of the initial network, the dashed lines represent the added edges.

Furthermore, we compute the assortative index of those solutions derived by MOEA/D-SW to explore the mixing effect of optimizing small-world property with different goals. The assortative index r is formulated as Eq (7), where M is the edge number, j_i, k_i are the corresponding two nodes’ degree at the ends of the i^th edge [52].

(7)

Fig 8 shows the result of assortative index for the optimized regular network and a random network derived by MOEA/D-SW. All the optimal strategies lead to disassortative structure on both regular and random networks, which suggests that large-degree nodes have a tendency of connecting with small-degree nodes. Among the three strategies, the strategy with the minimum APL is the most disassortative, while the one with the maximum ACC is the least disassortative. This phenomenon suggests that linking nodes with the hub nodes is the common rule for decreasing APL, but may be not for increasing ACC.

[Figure omitted. See PDF.]

(a) and (b) are the results on the regular and the random networks, respectively.

4.2 Results for real-world networks

In this section, we carry out MOEA/D-SW on five real-world networks and interpret the optimal strategies in the social context.

The five networks are Zachary’s Karate Club network (34 members and 78 social connections) [53], Bottlenose Dolphins network (62 dolphins and 159 ties) [54], American College Football network (115 teams and 616 edges) [55] and two networks of the company colleagues C₁ (70 nodes and 272 social ties) and C₂ (193 nodes and 887 social ties) [56].

Table 8 shows the mean results of APL, ACC and ACC/APL of the optimal networks with different goals and number of added edges over 10 runs. We find that MOEA/D-SW is capable of finding different substantial solutions according to the different preference of the optimization. Given the three classic goals of measuring the small-world property, the minimum APL, the maximum ACC, and the maximum ACC/APL, most of the output solutions under these three goals are unique. Several solutions under the goals of maximum ACC and the maximum ACC/APL are similar, which suggests that the index of ACC/APL proposed by Du et al. [4] is more inclined to ACC.

[Figure omitted. See PDF.]

Fig 9(a) and 9(b) respectively present the topologies of edging solution of the minimum APL and maximum ACC or ACC/APL with k = 10 on Zachary’s Karate Club network. When the main goal is to decrease APL, connecting other nodes to the-highest-degree node is the perfect way to improve the small-world property as shown in Fig 7(a). Under this strategy, nearly all the nodes are linked to node 34 (except for nodes 4, 8, 13, 18), which means the network diameter is getting more closed to 2 which is a critical diameter [51], i.e. each node can be contacted within only 2 steps. When we give priority to the optimism of ACC, most of the work is to construct more triangles, e.g. connecting nodes 5 and 6 can build triangles 5-6-7, 5-6-11, 5-6-1. Compared with (a) and (b), some added edges (edges between nodes 1 and 34, 2 and 34, 12 and 34, 25 and 34, 26 and 34) exist in both solutions. These edges are critical in both promoting ACC and declining APL.

[Figure omitted. See PDF.]

(a) is the result with the minimum APL, (b) is the result with both the maximum ACC and the maximum ACC/APL. The solid lines represent edges of the initial network, the dashed lines represent the added edges. The network has a strong characteristic of community structure, and it can be divided into two communities (the left part and the right part).

According to Du et al. [4], if the network has a strong characteristic of community structure, connecting nodes within the same community is an effective way to promote the small-world property. However, the edging method is not appropriate in Zachary’s Karate Club network which is also a typical network with the feature of community structure [55]. This can be attributed to the number of added edges and the density. Actually, adding edges within the same community is more likely to create more triangles, and thus helps increase ACC. However, if the local density of the community is large enough, adding the interior edges may not effectively create more triangles, and then the strategy may become useless. Compared with the optimized network in [4], the interior community is already saturated in Zachary’s Karate Club network that there is no need to add more edges within the community. In summary, the impact of community structure on optimizing small-world property mainly lies in the way of creating more triangles. If the internal community is saturated, the optimization process is less impacted by community structure.

In order to explore the effect of community structure, we ran MOEA/D-SW on the benchmark networks proposed by Lancichinetti et al. [57]. The network consists of 128 nodes with the average degree of 16. All the nodes are evenly assigned to a specific clustering attribute 1, 2, 3 or 4. A mixing parameter δ is then introduced to denote the fraction of edges that link nodes between different clusters. A higher δ represents a more apparent feature of community structure. Table 9 shows the mean results of APL, ACC and ACC/APL of the optimal networks with different δ over 10 runs. We find that there exists a sudden reduction of ACC/APL between δ = 0 and δ = 1/8 when k is not large enough. This is because APL significantly increases as δ increases from 0 to 1/8. As δ increases to a higher level, the optimal APL gradually decreases, and the gradients of the three indices decreases as well. On the other hand, as the number of added edges increases, the difference between different δ gets smaller, which suggests community structure has less impact on the optimization of small-world property with increase of the network density.

[Figure omitted. See PDF.]

Table 10 presents the mean percentage of edges added within the same community for different values of δ and different goals. When δ is small, more edges should be added between different communities in order to minimize APL; but if the goal is to maximize ACC, adding edges within the same community is the best choice; if we aim to maximize ACC/APL, the optimal solution depends on the balance between ACC and APL, and the percentage of edges added within the same community experiences an inverted U change as δ increases. When δ is large enough, the difference between adding edges within the same community and between different communities decreases, and the result does not show a clear pattern. On the other hand, if k is small, adding edges within the same community is an effective way to enhance the small-world property; but if k is large, there is no need to add more edges within the community because the internal community is saturated.

[Figure omitted. See PDF.]

5. Conclusion

In the present study, we present a multi-objective optimization model to maximize ACC and minimize APL simultaneously. A novel multiobjective evolutionary algorithm is designed, and has been proved to solve the optimization problem efficiently. The experiment shows that the present method can generate a uniform distribution of solutions with distinct hierarchical levels. Simulations on real-world networks also proves the effectiveness of the presented algorithm, and we find the optimization on networks with the feature of community structure is more remarkable, but community structure has less impact on the optimization when the internal community is triangles-saturated. Adding edges within the same community is helpful for promoting ACC, while adding edges between different communities is beneficial for reducing APL. When the feature of community structure weakens, the difference between adding edges between communities and adding edges within communities decreases. Moreover, an increase of network density may also weaken the impact of community structure on small-world optimization.

In many natural settings, researchers have different requirements on the small-world property, e.g. the set of power grid aims to promote ACC to guard against the risk of power failure, while the main object of transport network is to reduce APL to improve transmission efficiency. The present method can help researchers quickly find the edging solutions according to different goals.

Future research may apply the proposed algorithm to networks that contain both node and edge attributes. On the one hand, node attributes may impact on the formation of networks, and thus we can propose a framework of small-world optimization under the tag-mediated system. On the other hand, the present work is only conducted on nonnegative networks, while the edge attribute, especially the negative edge, has been ignored. Therefore, the optimizations of APL and ACC need to be conducted in signed networks. Further, the optimization on dynamic adaptive networks needs to be focused, where nodes and edges are dynamically updated.

Supporting information

S1 Fig. The mean value of the maximum ACC/APL for each number of added edges k and different crossover probability P_c for 10 runs acquired by MOEA/D-SW on the regular network.

The different curves represent results derived from different P_c. We can find the algorithm performs best when P_c = 0.1.

https://doi.org/10.1371/journal.pone.0313757.s001

(TIF)

S1 Dataset.

https://doi.org/10.1371/journal.pone.0313757.s002

(RAR)

References

1. 1. Watts D. and Strogatz S. H., “Collective dynamics of small-world networks,” Nature, vol. 393, pp. 440–442, 1998. pmid:9623998

* View Article

* PubMed/NCBI

* Google Scholar

2. 2. Barabási A. L., and Albert R., “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999. pmid:10521342

* View Article

* PubMed/NCBI

* Google Scholar

3. 3. Du W., Li G., and He X., “Network structure optimization for social networks by minimizing the average path length,” Computing, vol. 104, no. 6, pp. 1461–1480, 2022.

* View Article

* Google Scholar

4. 4. Du H., Fan J., He X., and Feldman M. W., “A genetic simulated annealing algorithm to optimize the small-world network generating process,” Complexity, vol. 2018, pp. 1–12, 2018.

* View Article

* Google Scholar

5. 5. Milgram S., “The Small World Problem,” Psychol Today, vol. 1, no. 1, pp. 60–67, 1967.

* View Article

* Google Scholar

6. 6. Collins J. J. and Chow C. C., “It’s a small world,” Nature, vol. 393, no. 6684, pp. 409–410, 1998. pmid:9623993

* View Article

* PubMed/NCBI

* Google Scholar

7. 7. T. Remes, Six Degrees of Rogers Hornsby, New York Times, 1997.

8. 8. Liu F., Gu B., Qin S, Zhang K., Cui L., and Xie G., “Power grid partition with improved biogeography-based optimization algorithm,” Sustain. Energy Technol. Assess., vol. 46, Article ID 101267, 2021.

* View Article

* Google Scholar

9. 9. De Bona A. A., de Oliveira Rosa M., Fonseca K. V. O., and Lüders R., “A reduced model for complex network analysis of public transportation systems,” Phys. A: Stat. Mech., vol. 567, Article ID 125715, 2021.

* View Article

* Google Scholar

10. 10. R. F. Rodrigues, A. R. da Silva, V. da Fonseca Vieira, and C. R. Xavier, “Optimization of the choice of individuals to be immunized through the genetic algorithm in the SIR model,” in Computational Science and Its Applications–ICCSA 2018. Springer, Cham, vol. 10961, 2018.

11. 11. Yang H. and Sun L., “Heterogeneous donation game in geographical small-world networks,” Phys. A: Stat. Mech., vol. 540, Article ID 123255, 2020.

* View Article

* Google Scholar

12. 12. Y. Liao, M. Maama, and M. A. Aziz-Alaoui, “Consensus dynamics and coherence in hierarchical small-world networks,” arXiv preprint, arXiv:2302.02590, 2023.

13. 13. İkizler H., “Contagion of network products in small-world networks,” J. Econ. Interact. Coord., vol. 14, no. 4, pp. 789–809, 2019.

* View Article

* Google Scholar

14. 14. C. Aguirre, R. Huerta, F. Corbacho, and P. Pascual, “Analysis of biologically inspired small-world networks,” in Artificial Neural Networks—ICANN 2002: International Conference, Madrid, Spain, Springer Science & Business Media. vol. 2415, pp. 27–32, 2002.

15. 15. Gray R. T., Fung C. K. C., and Robinson P. A., “Stability of small-world networks of neural populations,” Neurocomputing, vol. 72, no.7-9, pp. 1565–1574, 2009.

* View Article

* Google Scholar

16. 16. Wang S., Zhao X., Wang H., and Li M., “Small-world neural network and its performance for wind power forecasting,” CSEE Journal of Power and Energy Systems, vol. 6, no. 2, pp. 362–373, 2019.

* View Article

* Google Scholar

17. 17. Liu X., Wu Z., and Guan Y., “Influence of small-world topology and time-scale in evolutionary Kuramoto dilemma,” Europhysics Letters, vol. 122, no. 2, Article ID 20001, 2018.

* View Article

* Google Scholar

18. 18. Neumann M., “Indirect reciprocity with contagious reputation in large-scale small-world networks,” Journal of Artificial Societies and Social Simulation, vol. 23, no. 4, 2020.

* View Article

* Google Scholar

19. 19. Qiao T., Shan W., Zhang M., and Liu C., “How to facilitate knowledge diffusion in complex networks: The roles of network structure, knowledge role distribution and selection rule,” International Journal of Information Management, vol. 47, pp. 152–167, 2019.

* View Article

* Google Scholar

20. 20. Zhang L., Wei Q., Yuan Y., and Li Y., “Knowledge diffusion simulation of knowledge networks: based on complex network evolutionary algorithms,” Cluster Computing, vol. 22, pp. 15255–15265, 2019.

* View Article

* Google Scholar

21. 21. Newman M. E. J. and Watts D. J., “Renormalization group analysis of the small-world network model,” Physics Letters A, vol. 263, no. 4–6, pp. 341–346, 1999.

* View Article

* Google Scholar

22. 22. Kleinberg J. M., “Navigation in a small world,” Nature, vol. 406, no. 6798, pp. 845–845, 2000. pmid:10972276

* View Article

* PubMed/NCBI

* Google Scholar

23. 23. D. Cavalcanti, D. Agrawal, J. Kelner, and D. Sadok, “Exploiting the small-world effect to increase connectivity in wireless ad hoc networks,” Telecommunications and Networking-ICT 2004: 11th International Conference on Telecommunications, Springer Berlin Heidelberg, pp. 388–393, 2004.

24. 24. Xuan Q., Li Y., and Wu T. J., “Optimal symmetric networks in terms of minimizing average shortest path length and their sub-optimal growth model,” Physica A: Statistical Mechanics and its Applications, vol. 388, no. 7, pp. 1257–1267, 2009.

* View Article

* Google Scholar

25. 25. M. Papagelis, F. Bonchi, and A. Gionis, “Suggesting ghost edges for a smaller world,” in Proceedings of the 20th ACM international conference on Information and knowledge management, pp. 2305–2308, 2011.

26. 26. N. Parotsidis, E. Pitoura, and P. Tsaparas, “Selecting shortcuts for a smaller world,” in Proceedings of the 2015 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics, pp. 28–36, 2015.

27. 27. Gozzard A., Ward M., and Datta A., “Converting a network into a small-world network: Fast algorithms for minimizing average path length through link addition,” Information Sciences, vol. 422, pp. 282–289, 2018.

* View Article

* Google Scholar

28. 28. Garijo D., Márquez A., Rodríguez N., and Silveira R. I., “Computing optimal shortcuts for networks,” European Journal of Operational Research, vol. 279, no. 1, pp. 26–37, 2019.

* View Article

* Google Scholar

29. 29. Qiu T., Li B., Zhou X., Song H., Lee I., and Lloret J. “A novel shortcut addition algorithm with particle swarm for multisink Internet of Things,” IEEE Transactions on Industrial Informatics, vol. 16, no. 5, pp. 3566–3577, 2019.

* View Article

* Google Scholar

30. 30. Gaur N., Chakraborty A., and Manoj B. S. “Delay optimized small-world networks,” IEEE Communications Letters, vol. 18, no.11, pp. 1939–1942, 2014.

* View Article

* Google Scholar

31. 31. Soriano-Sánchez A. G. and Posadas-Castillo C., “Smart pattern to generate small–world networks,” Chaos, Solitons & Fractals, vol. 114, pp. 415–422, 2018.

* View Article

* Google Scholar

32. 32. Monasson R., “Localization and dispersion relations on “small-world” lattices,” The European Physical Journal B-Condensed Matter and Complex Systems, vol. 12, pp. 555–567, 1999.

* View Article

* Google Scholar

33. 33. Granovetter M. S., “The strength of weak ties,” American Journal of Sociology, vol. 78, no.6, pp. 1360–1380, 1973.

* View Article

* Google Scholar

34. 34. Schleich J., Danoy G., Dorronsoro B., and Bouvry P., “Optimising small-world properties in VANETs: centralised and distributed overlay approaches,” Applied Soft Computing, vol. 21, pp. 637–646, 2014.

* View Article

* Google Scholar

35. 35. Meyerson A., Tagiku B., “Minimizing average shortest path distances via shortcut edge addition,” in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2009, Springer, Berlin, Heidelberg, vol. 5687, pp. 272–285, 2009.

36. 36. N. Parotsidis, E. Pitoura, and P. Tsaparas, “Selecting shortcuts for a smaller world,” SIAM International Conference on Data Mining 2015, SDM 2015, Society for Industrial and Applied Mathematics, Philadelphia, PA, pp. 28–36, 2015.

37. 37. Gozzard A., Ward M., Datta A., “Converting a network into a small-world network: Fast algorithms for minimizing average path length through link addition,” Information Sciences, vol. 422, pp. 282–289, 2018.

* View Article

* Google Scholar

38. 38. Papagelis M., “Refining social graph connectivity via shortcut edge addition,” ACM Transactions on Knowledge Discovery from Data, vol. 10, no. 2, pp. 1556–4681, 2015.

* View Article

* Google Scholar

39. 39. J. Knowles and D. Corne, “The pareto archived evolution strategy: A new baseline algorithm for pareto multiobjective optimization,” in Proceedings of the 1999 congress on evolutionary computation-CEC99 (Cat. No. 99TH8406). IEEE, vol. 1, pp. 98–105, 1999.

40. 40. E. Zitzler, M. Laumanns, and L. Thiele, “SPEA2: Improving the strength Pareto evolutionary algorithm,” TIK-report, vol. 103, 2001.

41. 41. Deb K., Pratap A., Agarwal S., and Meyarivan T., “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182–197, 2002.

* View Article

* Google Scholar

42. 42. Zhang Q. and Li H., “MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition,” IEEE Transactions on Evolutionary Computation, vol. 11, no. 6, pp. 712–731, 2007.

* View Article

* Google Scholar

43. 43. Li H. and Zhang Q., “Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II,” IEEE transactions on evolutionary computation, vol. 13, no. 2, pp. 284–302, 2008.

* View Article

* Google Scholar

44. 44. Zhang Q., Liu W., Tsang E. P., and Virginas B., “Expensive multiobjective optimization by MOEA/D with Gaussian process model,” IEEE Transactions on Evolutionary Computation, vol. 14, no. 3, pp. 456–474, 2009.

* View Article

* Google Scholar

45. 45. Gong M., Ma L., Zhang Q., and Jiao L., “Community detection in networks by using multiobjective evolutionary algorithm with decomposition,” Physica A: Statistical Mechanics and its Applications, vol. 391, no. 15, pp. 4050–4060, 2012.

* View Article

* Google Scholar

46. 46. Zhang W., Shang R., and Jiao L., “Complex network graph embedding method based on shortest path and MOEA/D for community detection,” Applied Soft Computing, vol. 97, no.1, Article ID 106764, 2020.

* View Article

* Google Scholar

47. 47. Fan C., Ding C., Xiao L., Cheng F., and Ai Z., “Deep belief ensemble network based on MOEA/D for short-term load forecasting,” Nonlinear Dynamics, vol. 105, pp. 2405–2430, 2021.

* View Article

* Google Scholar

48. 48. Miettinen K., Nonlinear Multiobjective Optimization, Norwell, MA: Kluwer, 1999.

49. 49. He X., Zhang R., and Zhu B., “A Generalized Modularity for Computing Community Structure in Fully Signed Networks,” Complexity, vol. 2023, Article ID 8767131, 2023.

* View Article

* Google Scholar

50. 50. He X., Du H., Xu X., and Du W., “An energy function for computing structural balance in fully signed network,” IEEE Transactions on Computational Social Systems, vol. 7, no. 3, pp. 696–708, 2020.

* View Article

* Google Scholar

51. 51. Du H., He X., Du W., and Feldman M. W., “Optimization of the critical diameter and average path length of social networks,” Complexity, vol. 2017, pp. 1–11, 2017.

* View Article

* Google Scholar

52. 52. Newman M. E. J., “Assortative mixing in networks,” Physical Review Letters, vol. 89, no. 20, Article ID 208701, 2002.

* View Article

* Google Scholar

53. 53. Zachary W. W., “An information flow model for conflict and fission in small groups,” Journal of anthropological research, vol. 33, no. 4, pp. 452–473, 1977.

* View Article

* Google Scholar

54. 54. Lusseau D., “The emergent properties of a dolphin social network,” Proceedings of the Royal Society of London. Series B: Biological Sciences, vol. 270, pp. S186–S188, 2003. pmid:14667378

* View Article

* PubMed/NCBI

* Google Scholar

55. 55. Girvan M. and Newman M. E., “Community structure in social and biological networks.,” Proceedings of the national academy of sciences, vol. 99, no.12, pp. 7821–7826, 2002. pmid:12060727

* View Article

* PubMed/NCBI

* Google Scholar

56. 56. He X., Wang Y., Du H., and Feldman M. W., “A method for finding multiple subgraphs that optimally cover an input network,” Plos one. vol. 18, no. 1, Article ID e0280506, 2023.

* View Article

* Google Scholar

57. 57. Lancichinetti A., Fortunato S., and Radicchi F., “Benchmark graphs for testing community detection algorithms,” Physical. Review E. vol. 78, no. 4, pp. 046110, 2008. pmid:18999496

* View Article

* PubMed/NCBI

* Google Scholar

Citation: Zhang R, Zhu B (2024) A multiobjective evolutionary algorithm for optimizing the small-world property. PLoS ONE 19(12): e0313757. https://doi.org/10.1371/journal.pone.0313757

About the Authors:

Ruochen Zhang

Roles: Conceptualization, Writing – original draft, Writing – review & editing

Affiliation: School of Economics and Management, Xi’an Shiyou University, Xi’an, Shaanxi, China

ORICD: https://orcid.org/0000-0002-4173-0937

Bin Zhu

Roles: Methodology, Software

E-mail: [email protected]

Affiliation: School of Public Health and Emergency Management, Southern University of Science and Technology, Shenzhen, Guangdong, China

ORICD: https://orcid.org/0000-0002-0091-6356

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

[/RAW_REF_TEXT]

References

1. Watts D. and Strogatz S. H., “Collective dynamics of small-world networks,” Nature, vol. 393, pp. 440–442, 1998. pmid:9623998

2. Barabási A. L., and Albert R., “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999. pmid:10521342

3. Du W., Li G., and He X., “Network structure optimization for social networks by minimizing the average path length,” Computing, vol. 104, no. 6, pp. 1461–1480, 2022.

4. Du H., Fan J., He X., and Feldman M. W., “A genetic simulated annealing algorithm to optimize the small-world network generating process,” Complexity, vol. 2018, pp. 1–12, 2018.

5. Milgram S., “The Small World Problem,” Psychol Today, vol. 1, no. 1, pp. 60–67, 1967.

6. Collins J. J. and Chow C. C., “It’s a small world,” Nature, vol. 393, no. 6684, pp. 409–410, 1998. pmid:9623993

7. T. Remes, Six Degrees of Rogers Hornsby, New York Times, 1997.

8. Liu F., Gu B., Qin S, Zhang K., Cui L., and Xie G., “Power grid partition with improved biogeography-based optimization algorithm,” Sustain. Energy Technol. Assess., vol. 46, Article ID 101267, 2021.

9. De Bona A. A., de Oliveira Rosa M., Fonseca K. V. O., and Lüders R., “A reduced model for complex network analysis of public transportation systems,” Phys. A: Stat. Mech., vol. 567, Article ID 125715, 2021.

10. R. F. Rodrigues, A. R. da Silva, V. da Fonseca Vieira, and C. R. Xavier, “Optimization of the choice of individuals to be immunized through the genetic algorithm in the SIR model,” in Computational Science and Its Applications–ICCSA 2018. Springer, Cham, vol. 10961, 2018.

11. Yang H. and Sun L., “Heterogeneous donation game in geographical small-world networks,” Phys. A: Stat. Mech., vol. 540, Article ID 123255, 2020.

12. Y. Liao, M. Maama, and M. A. Aziz-Alaoui, “Consensus dynamics and coherence in hierarchical small-world networks,” arXiv preprint, arXiv:2302.02590, 2023.

13. İkizler H., “Contagion of network products in small-world networks,” J. Econ. Interact. Coord., vol. 14, no. 4, pp. 789–809, 2019.

14. C. Aguirre, R. Huerta, F. Corbacho, and P. Pascual, “Analysis of biologically inspired small-world networks,” in Artificial Neural Networks—ICANN 2002: International Conference, Madrid, Spain, Springer Science & Business Media. vol. 2415, pp. 27–32, 2002.

15. Gray R. T., Fung C. K. C., and Robinson P. A., “Stability of small-world networks of neural populations,” Neurocomputing, vol. 72, no.7-9, pp. 1565–1574, 2009.

16. Wang S., Zhao X., Wang H., and Li M., “Small-world neural network and its performance for wind power forecasting,” CSEE Journal of Power and Energy Systems, vol. 6, no. 2, pp. 362–373, 2019.

17. Liu X., Wu Z., and Guan Y., “Influence of small-world topology and time-scale in evolutionary Kuramoto dilemma,” Europhysics Letters, vol. 122, no. 2, Article ID 20001, 2018.

18. Neumann M., “Indirect reciprocity with contagious reputation in large-scale small-world networks,” Journal of Artificial Societies and Social Simulation, vol. 23, no. 4, 2020.

19. Qiao T., Shan W., Zhang M., and Liu C., “How to facilitate knowledge diffusion in complex networks: The roles of network structure, knowledge role distribution and selection rule,” International Journal of Information Management, vol. 47, pp. 152–167, 2019.

20. Zhang L., Wei Q., Yuan Y., and Li Y., “Knowledge diffusion simulation of knowledge networks: based on complex network evolutionary algorithms,” Cluster Computing, vol. 22, pp. 15255–15265, 2019.

21. Newman M. E. J. and Watts D. J., “Renormalization group analysis of the small-world network model,” Physics Letters A, vol. 263, no. 4–6, pp. 341–346, 1999.

22. Kleinberg J. M., “Navigation in a small world,” Nature, vol. 406, no. 6798, pp. 845–845, 2000. pmid:10972276

23. D. Cavalcanti, D. Agrawal, J. Kelner, and D. Sadok, “Exploiting the small-world effect to increase connectivity in wireless ad hoc networks,” Telecommunications and Networking-ICT 2004: 11th International Conference on Telecommunications, Springer Berlin Heidelberg, pp. 388–393, 2004.

24. Xuan Q., Li Y., and Wu T. J., “Optimal symmetric networks in terms of minimizing average shortest path length and their sub-optimal growth model,” Physica A: Statistical Mechanics and its Applications, vol. 388, no. 7, pp. 1257–1267, 2009.

25. M. Papagelis, F. Bonchi, and A. Gionis, “Suggesting ghost edges for a smaller world,” in Proceedings of the 20th ACM international conference on Information and knowledge management, pp. 2305–2308, 2011.

26. N. Parotsidis, E. Pitoura, and P. Tsaparas, “Selecting shortcuts for a smaller world,” in Proceedings of the 2015 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics, pp. 28–36, 2015.

27. Gozzard A., Ward M., and Datta A., “Converting a network into a small-world network: Fast algorithms for minimizing average path length through link addition,” Information Sciences, vol. 422, pp. 282–289, 2018.

28. Garijo D., Márquez A., Rodríguez N., and Silveira R. I., “Computing optimal shortcuts for networks,” European Journal of Operational Research, vol. 279, no. 1, pp. 26–37, 2019.

29. Qiu T., Li B., Zhou X., Song H., Lee I., and Lloret J. “A novel shortcut addition algorithm with particle swarm for multisink Internet of Things,” IEEE Transactions on Industrial Informatics, vol. 16, no. 5, pp. 3566–3577, 2019.

30. Gaur N., Chakraborty A., and Manoj B. S. “Delay optimized small-world networks,” IEEE Communications Letters, vol. 18, no.11, pp. 1939–1942, 2014.

31. Soriano-Sánchez A. G. and Posadas-Castillo C., “Smart pattern to generate small–world networks,” Chaos, Solitons & Fractals, vol. 114, pp. 415–422, 2018.

32. Monasson R., “Localization and dispersion relations on “small-world” lattices,” The European Physical Journal B-Condensed Matter and Complex Systems, vol. 12, pp. 555–567, 1999.

33. Granovetter M. S., “The strength of weak ties,” American Journal of Sociology, vol. 78, no.6, pp. 1360–1380, 1973.

34. Schleich J., Danoy G., Dorronsoro B., and Bouvry P., “Optimising small-world properties in VANETs: centralised and distributed overlay approaches,” Applied Soft Computing, vol. 21, pp. 637–646, 2014.

35. Meyerson A., Tagiku B., “Minimizing average shortest path distances via shortcut edge addition,” in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2009, Springer, Berlin, Heidelberg, vol. 5687, pp. 272–285, 2009.

36. N. Parotsidis, E. Pitoura, and P. Tsaparas, “Selecting shortcuts for a smaller world,” SIAM International Conference on Data Mining 2015, SDM 2015, Society for Industrial and Applied Mathematics, Philadelphia, PA, pp. 28–36, 2015.

37. Gozzard A., Ward M., Datta A., “Converting a network into a small-world network: Fast algorithms for minimizing average path length through link addition,” Information Sciences, vol. 422, pp. 282–289, 2018.

38. Papagelis M., “Refining social graph connectivity via shortcut edge addition,” ACM Transactions on Knowledge Discovery from Data, vol. 10, no. 2, pp. 1556–4681, 2015.

39. J. Knowles and D. Corne, “The pareto archived evolution strategy: A new baseline algorithm for pareto multiobjective optimization,” in Proceedings of the 1999 congress on evolutionary computation-CEC99 (Cat. No. 99TH8406). IEEE, vol. 1, pp. 98–105, 1999.

40. E. Zitzler, M. Laumanns, and L. Thiele, “SPEA2: Improving the strength Pareto evolutionary algorithm,” TIK-report, vol. 103, 2001.

41. Deb K., Pratap A., Agarwal S., and Meyarivan T., “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182–197, 2002.

42. Zhang Q. and Li H., “MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition,” IEEE Transactions on Evolutionary Computation, vol. 11, no. 6, pp. 712–731, 2007.

43. Li H. and Zhang Q., “Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II,” IEEE transactions on evolutionary computation, vol. 13, no. 2, pp. 284–302, 2008.

44. Zhang Q., Liu W., Tsang E. P., and Virginas B., “Expensive multiobjective optimization by MOEA/D with Gaussian process model,” IEEE Transactions on Evolutionary Computation, vol. 14, no. 3, pp. 456–474, 2009.

45. Gong M., Ma L., Zhang Q., and Jiao L., “Community detection in networks by using multiobjective evolutionary algorithm with decomposition,” Physica A: Statistical Mechanics and its Applications, vol. 391, no. 15, pp. 4050–4060, 2012.

46. Zhang W., Shang R., and Jiao L., “Complex network graph embedding method based on shortest path and MOEA/D for community detection,” Applied Soft Computing, vol. 97, no.1, Article ID 106764, 2020.

47. Fan C., Ding C., Xiao L., Cheng F., and Ai Z., “Deep belief ensemble network based on MOEA/D for short-term load forecasting,” Nonlinear Dynamics, vol. 105, pp. 2405–2430, 2021.

48. Miettinen K., Nonlinear Multiobjective Optimization, Norwell, MA: Kluwer, 1999.

49. He X., Zhang R., and Zhu B., “A Generalized Modularity for Computing Community Structure in Fully Signed Networks,” Complexity, vol. 2023, Article ID 8767131, 2023.

50. He X., Du H., Xu X., and Du W., “An energy function for computing structural balance in fully signed network,” IEEE Transactions on Computational Social Systems, vol. 7, no. 3, pp. 696–708, 2020.

51. Du H., He X., Du W., and Feldman M. W., “Optimization of the critical diameter and average path length of social networks,” Complexity, vol. 2017, pp. 1–11, 2017.

52. Newman M. E. J., “Assortative mixing in networks,” Physical Review Letters, vol. 89, no. 20, Article ID 208701, 2002.

53. Zachary W. W., “An information flow model for conflict and fission in small groups,” Journal of anthropological research, vol. 33, no. 4, pp. 452–473, 1977.

54. Lusseau D., “The emergent properties of a dolphin social network,” Proceedings of the Royal Society of London. Series B: Biological Sciences, vol. 270, pp. S186–S188, 2003. pmid:14667378

55. Girvan M. and Newman M. E., “Community structure in social and biological networks.,” Proceedings of the national academy of sciences, vol. 99, no.12, pp. 7821–7826, 2002. pmid:12060727

56. He X., Wang Y., Du H., and Feldman M. W., “A method for finding multiple subgraphs that optimally cover an input network,” Plos one. vol. 18, no. 1, Article ID e0280506, 2023.

57. Lancichinetti A., Fortunato S., and Radicchi F., “Benchmark graphs for testing community detection algorithms,” Physical. Review E. vol. 78, no. 4, pp. 046110, 2008. pmid:18999496