Optimized quasi two-dimensional Networks: frustrated anti-ferromagnetic spin system

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

We consider quasi two-dimensional networks that aim at minimizing the wiring cost while maximizing the network connections, but at the same time edge crossings are penalized or forbidden. This model is mapped to a dilute anti-ferromagnetic Ising spin system with frustrations. Our motivation is to understand the relation between the energy cost and the connectivity in a network. The optimized network can be obtained from the mean field solution with the minimal cost. We derive analytic results using the mean field theories and verify these results by Monte Carlo simulations. For the case of strictly no bond crossing, finding the optimized network is equivalent to find the minimum length triangulation. Although finding the minimum length triangulation is known as the NP-hard problem, the mean field equations lead to an effective algorithm to find the (near) optimal solution even for this strongly frustrated system.

Keywords: Optimized networks, Mean field theory, Spin glass, Frustration, Triangulation