A novel edge rewiring strategy for tuning structural properties in networks

摘要

Synthetic networks can be generated to mimic the dynamics and evolution of complex interconnected systems in real world. Many network models have been established based on various structure and topological characteristics, such as degree distribution, clustering coefficient, mixing parameter, etc. These generated network models can serve as null models in hypothesis testing to assess nontrivial results about real world data in terms of statistical significance and generality. Therefore, researchers have actively pursued the development of network generation models with some given topological characteristics. So far, Standard Monte Carlo method and Simulated Annealing method are popular to adjust the clustering coefficient and average path length of the existing networks. However, these methods require a large number of calculations and are easy to fall into local extremes, which might limit the adjusting range of the algorithm. In order to reduce the amount of calculation and expand the range of adjustment, we propose a local structure based edge rewiring method to adjust the clustering coefficient and average path length of the network. By selecting of an appropriate local neighborhood of the node, we compute the ‘local’ clustering coefficient and ‘local’ average path length on the “local neighborhood”, and then calculating cost in each adjusting iteration is greatly reduced. Focusing on the “local neighborhood” strategy helps the algorithm escape from local extreme. Therefore, our edge rewiring strategy provides a border adjustment range of clustering coefficient and average path length in reasonable computing time. Experiment results show that our edge rewiring strategy can provide a boarder adjusting range for clustering coefficient and average path length than standard Monte Carlo method and the Simulated Annealing method under the same computation condition.