{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:24:21Z","timestamp":1760239461288,"version":"build-2065373602"},"reference-count":26,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T00:00:00Z","timestamp":1605744000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Using 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 behavior, 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 a 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 qualitative explanation of such a behavior. 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.<\/jats:p>","DOI":"10.3390\/e22111319","type":"journal-article","created":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T06:23:52Z","timestamp":1605767032000},"page":"1319","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Cluster Structure of Optimal Solutions in Bipartitioning of Small Worlds"],"prefix":"10.3390","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4198-6892","authenticated-orcid":false,"given":"Adam","family":"Lipowski","sequence":"first","affiliation":[{"name":"Faculty of Physics, Adam Mickiewicz University in Pozna\u0144, 61-614 Pozna\u0144, Poland"}]},{"given":"Ant\u00f3nio L.","family":"Ferreira","sequence":"additional","affiliation":[{"name":"Departamento de F\u00edsica, I3N, Universidade de Aveiro, 3810-193 Aveiro, Portugal"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6268-7819","authenticated-orcid":false,"given":"Dorota","family":"Lipowska","sequence":"additional","affiliation":[{"name":"Faculty of Modern Languages and Literature, Adam Mickiewicz University in Pozna\u0144, 61-874 Pozna\u0144, Poland"}]}],"member":"1968","published-online":{"date-parts":[[2020,11,19]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Hartmann, A.K., and Weigt, M. (2006). Phase Transitions in Combinatorial Optimization Problems: Basics, Algorithms and Statistical Mechanics, John Wiley & Sons.","DOI":"10.1002\/3527606734"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Krzakala, F., Ricci-Tersenghi, F., Zdeborova, L., Zecchina, R., Tramel, E.W., and Cugli, L.F. (2016). Statistical Physics, Optimization, Inference, and Message-Passing Algorithms, Oxford University Press. Number 2013 in Lecture Notes of the Les Houches.","DOI":"10.1093\/acprof:oso\/9780198743736.001.0001"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1109\/92.748202","article-title":"Multilevel hypergraph partitioning: Applications in VLSI domain","volume":"7","author":"Karypis","year":"1999","journal-title":"IEEE Trans. Very Large Scale Integr. VLSI Syst."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Pothen, A. (1997). Graph partitioning algorithms with applications to scientific computing. Parallel Numerical Algorithms, Springer.","DOI":"10.1007\/978-94-011-5412-3_12"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1109\/TPAMI.2004.1262177","article-title":"What energy functions can be minimized via graph cuts?","volume":"26","author":"Kolmogorov","year":"2004","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"L1","DOI":"10.1088\/0305-4470\/20\/1\/001","article-title":"Graph bipartitioning and statistical mechanics","volume":"20","author":"Banavar","year":"1987","journal-title":"J. Phys. A"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1137\/S1052623497321523","article-title":"Cut size statistics of graph bisection heuristics","volume":"10","author":"Schreiber","year":"1999","journal-title":"SIAM J. Optim."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"026114","DOI":"10.1103\/PhysRevE.64.026114","article-title":"Extremal optimization for graph partitioning","volume":"64","author":"Boettcher","year":"2001","journal-title":"Phys. Rev. E"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1605","DOI":"10.1088\/0305-4470\/19\/9\/033","article-title":"Application of statistical mechanics to NP-complete problems in combinatorial optimisation","volume":"19","author":"Fu","year":"1986","journal-title":"J. Phys. A"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1625","DOI":"10.1103\/PhysRevLett.59.1625","article-title":"Graph bipartitioning problem","volume":"59","author":"Liao","year":"1987","journal-title":"Phys. Rev. Lett."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1067","DOI":"10.1209\/0295-5075\/3\/10\/002","article-title":"Mean-field theory of randomly frustrated systems with finite connectivity","volume":"3","author":"Parisi","year":"1987","journal-title":"EPL"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"125219","DOI":"10.1063\/1.3043666","article-title":"The peculiar phase structure of random graph bisection","volume":"49","author":"Percus","year":"2008","journal-title":"J. Math. Phys."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"285003","DOI":"10.1088\/1751-8113\/43\/28\/285003","article-title":"Belief propagation for graph partitioning","volume":"43","year":"2010","journal-title":"J. Phys. A"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"083301","DOI":"10.1088\/1742-5468\/ab3280","article-title":"Bipartitioning of directed and mixed random graphs","volume":"2019","author":"Lipowski","year":"2019","journal-title":"J. Stat. Mech. Theory Exp."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u2018small world\u2019 networks","volume":"393","author":"Watts","year":"1998","journal-title":"Nature"},{"key":"ref_16","unstructured":"Newman, M.E., Barab\u00e1si, A.L.E., and Watts, D.J. (2006). The Structure and Dynamics of Networks, Princeton University Press."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"026112","DOI":"10.1103\/PhysRevE.70.026112","article-title":"Exact solution of Ising model on a small world network","volume":"70","author":"Lopes","year":"2004","journal-title":"Phys. Rev. E"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"032305","DOI":"10.1103\/PhysRevE.101.032305","article-title":"Lying on networks: The role of structure and topology in promoting honesty","volume":"101","author":"Capraro","year":"2020","journal-title":"Phys. Rev. E"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Liu, M., Li, D., Qin, P., Liu, C., Wang, H., and Wang, F. (2015). Epidemics in interconnected small world networks. PLoS ONE, 10.","DOI":"10.1371\/journal.pone.0120701"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"973","DOI":"10.1023\/A:1018607809852","article-title":"Replica symmetry breaking in short-range spin glasses: Theoretical foundations and numerical evidences","volume":"98","author":"Marinari","year":"2000","journal-title":"J. Stat. Phys."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"184422","DOI":"10.1103\/PhysRevB.63.184422","article-title":"Monte Carlo simulations of spin glasses at low temperatures","volume":"63","author":"Katzgraber","year":"2001","journal-title":"Phys. Rev. B"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"10318","DOI":"10.1073\/pnas.0703685104","article-title":"Gibbs states and the set of solutions of random constraint satisfaction problems","volume":"104","author":"Montanari","year":"2007","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1088\/0305-4470\/31\/2\/012","article-title":"Optimization problems and replica symmetry breaking in finite connectivity spin glasses","volume":"31","author":"Monasson","year":"1998","journal-title":"J. Phys. A"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Stauffer, D., and Aharony, A. (2018). Introduction to Percolation Theory, CRC Press.","DOI":"10.1201\/9781315274386"},{"key":"ref_26","unstructured":"Huang, K. (1987). Statistical Mechanics, John Wiley & Sons."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/22\/11\/1319\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:34:14Z","timestamp":1760178854000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/22\/11\/1319"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,19]]},"references-count":26,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2020,11]]}},"alternative-id":["e22111319"],"URL":"https:\/\/doi.org\/10.3390\/e22111319","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2020,11,19]]}}}