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.

Fig 1. Illustration of the representation.

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.

Fig 2. Illustration of crossover.

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.

Fig 3. The mean value of the maximum ACC/APL for each number of added edges k for 10 runs acquired by MOEA/D-SW, MA-SW, GA-SW, GR-SW, NW model, and NSGA-II.

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

Fig 4. The mean value of the minimum APL for each number of added edges k for 10 runs acquired by MOEA/D-SW, MA-SW, GA-SW, GR-SW, NW model, and NSGA-II.

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

Fig 5. The mean value of the maximum ACC for each number of added edges k for 10 runs acquired by MOEA/D-SW, MA-SW, GA-SW, GR-SW, NW model, and NSGA-II.

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

Fig 6. The Pareto-optimal fronts on the regular network with 10 added edges and its corresponding solutions.

(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. The Pareto-optimal fronts on the random network with 10 added edges and its corresponding solutions.

(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.

Fig 8. Assortative index r for each number of added edges k with the solutions of minimum APL, the maximum ACC, and the maximum ACC/APL acquired by MOEA/D-SW.

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

Fig 9. The topologies of edging solution with k = 10 on Zachary’s Karate Club network.

(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).