Phase Transitions in Optimized Networks: Analytic Results and Efficient algorithm

An-Liang Cheng^1*, Pik-Yin Lai^1,2

¹Department of Physics, National Central University, Taoyuan, Taiwan
²Center for complex system, National Central University, Taoyuan, Taiwan

* Presenter:An-Liang Cheng, email:phairst@gmail.com

In this research, we focus on the principle of the formation or growth of the networks. We aim at constructing some basic theory for the optimal growing networks and investigate the drastic structural changes of the networks such as the phase transition. We consider network growing models that aim at minimizing the wiring cost while at the same time maximizing the network connections. By mapping the system to an Ising spin model, we obtain analytic results for two such models, both of them show interesting, but different phase transition behaviors for general wiring cost distributions. The phase diagrams for these transitions are also obtained. These results are also extended for networks optimized with the weighted nodes degree for connections. Furthermore, mean-field theory leads to an effective algorithm for finding the fully optimized network in these models. We compare the minimal cost found by the new algorithm with the results found by solving the coupled mean-field equations. The results clearly verify that the new algorithm finds the minimal cost in all cases, but with a much faster computational time. All these results are also verified by Monte Carlo simulations. Some interesting properties of the fully optimized network are also discussed in the light of small-world-ness, rich-club effects and the 80-20 resource distributions.

Keywords: Optimized networks, Phase transition, Ising model, Mean-field theory, Small-world-ness