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.