Cluster structure of optimal solutions in bipartitioning of small worlds

Abstract

Using a simulated annealing, we examine a bipartitioning of small worlds obtained by adding a fraction of randomly chosen links to a one-dimensional chain or a square lattice. Models defined on small worlds typically exhibit a mean-field behaviour, regardless of the underlying lattice. Our work demonstrates that the bipartitioning of small worlds does depend on the underlying lattice. Simulations show that for one-dimensional small worlds, optimal partitions are finite size clusters for any fraction of additional links. In the two-dimensional case, we observe two regimes: when the fraction of additional links is sufficiently small, the optimal partitions have a stripe-like shape, which is lost for larger number of additional links as optimal partitions become disordered. Some arguments, which interpret additional links as thermal excitations and refer to the thermodynamics of Ising models, suggest a qualitatitve explanation of such a behaviour. The histogram of overlaps suggests that a replica symmetry is broken in a one-dimensional small world. In the two-dimensional case, the replica symmetry seems to hold but with some additional degeneracy of stripe-like partitions.

arXiv comment12 pages

References in corpus (10)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Replica Symmetry Breaking in Short-Range Spin Glasses: Theoretical Foundations and Numerical Evidences
• Monte Carlo Simulations of Spin Glasses at Low Temperatures
• Optimisation problems and replica symmetry breaking in finite connectivity spin-glasses
• Extremal Optimization for Graph Partitioning
• Exact Solution of Ising Model on a Small-World Network
• Lying on networks: The role of structure and topology in promoting honesty
• Belief propagation for graph partitioning
• The Peculiar Phase Structure of Random Graph Bisection
• Bipartitioning of directed and mixed random graphs