{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T15:59:07Z","timestamp":1773503947467,"version":"3.50.1"},"reference-count":32,"publisher":"IOP Publishing","issue":"8","license":[{"start":{"date-parts":[[2019,8,21]],"date-time":"2019-08-21T00:00:00Z","timestamp":1566345600000},"content-version":"vor","delay-in-days":20,"URL":"https:\/\/publishingsupport.iopscience.iop.org\/iop-standard\/v1"},{"start":{"date-parts":[[2019,8,21]],"date-time":"2019-08-21T00:00:00Z","timestamp":1566345600000},"content-version":"tdm","delay-in-days":20,"URL":"https:\/\/iopscience.iop.org\/info\/page\/text-and-data-mining"}],"content-domain":{"domain":["iopscience.iop.org"],"crossmark-restriction":false},"short-container-title":["J. Stat. Mech."],"published-print":{"date-parts":[[2019,8,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We show that an intricate relation of cluster properties and optimal bipartitions, which takes place in undirected random graphs, extends to directed and mixed random graphs. In particular, the satisfability threshold coincides with the relative size of the giant OUT component reaching 1\/2. Moreover, when counting undirected links as two directed ones, the partition cost, and cluster properties, as well as location of the replica symmetry breaking transition for these random graphs depend primarily on the total number of directed links and not on their specific distribution.<\/jats:p>","DOI":"10.1088\/1742-5468\/ab3280","type":"journal-article","created":{"date-parts":[[2019,8,21]],"date-time":"2019-08-21T09:14:12Z","timestamp":1566378852000},"page":"083301","update-policy":"https:\/\/doi.org\/10.1088\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Bipartitioning of directed and mixed random graphs"],"prefix":"10.1088","volume":"2019","author":[{"given":"Adam","family":"Lipowski","sequence":"first","affiliation":[]},{"given":"Ant\u00f3nio Luis","family":"Ferreira","sequence":"additional","affiliation":[]},{"given":"Dorota","family":"Lipowska","sequence":"additional","affiliation":[]},{"given":"Manuel A","family":"Barroso","sequence":"additional","affiliation":[]}],"member":"266","published-online":{"date-parts":[[2019,8,21]]},"reference":[{"key":"jstatab3280bib001","author":"Hartmann","year":"2006","type":"book"},{"key":"jstatab3280bib002","author":"Krzakala","year":"2016","type":"book"},{"key":"jstatab3280bib003","doi-asserted-by":"publisher","first-page":"6979","DOI":"10.1109\/92.748202","type":"journal-article","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":"jstatab3280bib004","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-011-5412-3_12","type":"book","article-title":"Graph partitioning algorithms with applications to scientific computing","author":"Pothen","year":"1997"},{"key":"jstatab3280bib005","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1109\/TPAMI.2004.1262177","type":"journal-article","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":"jstatab3280bib006","doi-asserted-by":"publisher","first-page":"L1","DOI":"10.1088\/0305-4470\/20\/1\/001","type":"journal-article","article-title":"Graph bipartitioning and statistical mechanics","volume":"20","author":"Banavar","year":"1987","journal-title":"J. Phys. A: Math. Gen."},{"key":"jstatab3280bib007","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1137\/S1052623497321523","type":"journal-article","article-title":"Cut size statistics of graph bisection heuristics","volume":"10","author":"Schreiber","year":"1999","journal-title":"SIAM J. Optim."},{"key":"jstatab3280bib008","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.64.026114","type":"journal-article","article-title":"Extremal optimization for graph partitioning","volume":"64","author":"Boettcher","year":"2001","journal-title":"Phys. Rev. E"},{"key":"jstatab3280bib009","doi-asserted-by":"publisher","first-page":"1605","DOI":"10.1088\/0305-4470\/19\/9\/033","type":"journal-article","article-title":"Application of statistical mechanics to NP-complete problems in combinatorial optimisation","volume":"19","author":"Fu","year":"1986","journal-title":"J. Phys. A: Math. Gen."},{"key":"jstatab3280bib010","doi-asserted-by":"publisher","first-page":"1625","DOI":"10.1103\/PhysRevLett.59.1625","type":"journal-article","article-title":"Graph bipartitioning problem","volume":"59","author":"Liao","year":"1987","journal-title":"Phys. Rev. Lett."},{"key":"jstatab3280bib011","doi-asserted-by":"publisher","first-page":"1067","DOI":"10.1209\/0295-5075\/3\/10\/002","type":"journal-article","article-title":"Mean-field theory of randomly frustrated systems with finite connectivity","volume":"3","author":"M\u00e9zard","year":"1987","journal-title":"Europhys. Lett."},{"key":"jstatab3280bib012","doi-asserted-by":"publisher","DOI":"10.1063\/1.3043666","type":"journal-article","article-title":"The peculiar phase structure of random graph bisection","volume":"49.12","author":"Percus","year":"2008","journal-title":"J. Math. Phys."},{"key":"jstatab3280bib013","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8113\/43\/28\/285003","type":"journal-article","article-title":"Belief propagation for graph partitioning","volume":"43","author":"\u0160ulc","year":"2010","journal-title":"J. Phys. A: Math. Theor."},{"key":"jstatab3280bib014","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00026-005-0237-z","type":"journal-article","article-title":"Laplacians and the Cheeger inequality for directed graphs","volume":"9","author":"Chung","year":"2005","journal-title":"Ann. Comb."},{"key":"jstatab3280bib015","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.physrep.2013.08.002","type":"journal-article","article-title":"Clustering and community detection in directed networks: a survey","volume":"533","author":"Malliaros","year":"2013","journal-title":"Phys. Rep."},{"key":"jstatab3280bib016","first-page":"290","type":"journal-article","article-title":"On random graphs","volume":"6","author":"Erd\u00f6s","year":"1959","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"key":"jstatab3280bib017","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2009\/12\/P12016","type":"journal-article","article-title":"Nonequilibrium stationary states and phase transitions in directed Ising models","author":"Godr\u00e8che","year":"2009","journal-title":"J. Stat. Mech."},{"key":"jstatab3280bib018","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.88.048701","type":"journal-article","article-title":"Nonequilibrium phase transitions in directed small-world networks","volume":"88","author":"S\u00e1nchez","year":"2002","journal-title":"Phys. Rev. Lett."},{"key":"jstatab3280bib019","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109564","type":"conference-proceedings","article-title":"Directed metrics and directed graph partitioning problems","author":"Charikar","year":"2006"},{"key":"jstatab3280bib020","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0020-0190(03)00251-5","type":"journal-article","article-title":"On the complexity of finding balanced oneway cuts","volume":"87","author":"Feige","year":"2003","journal-title":"Inf. Proc. Lett."},{"key":"jstatab3280bib021","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1002\/1098-2418(200101)18:1<31::AID-RSA3>3.0.CO;2-1","type":"journal-article","article-title":"Bisecting sparse random graphs","volume":"18","author":"Luczak","year":"2001","journal-title":"Random Struct. Algorithms"},{"key":"jstatab3280bib022","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1002\/rsa.20539","type":"journal-article","article-title":"The mixing time of the giant component of a random graph","volume":"45","author":"Benjamini","year":"2014","journal-title":"Random Struct. Algorithms"},{"key":"jstatab3280bib023","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/S1389-1286(00)00083-9","type":"journal-article","article-title":"Graph structure in the web","volume":"33","author":"Broder","year":"2000","journal-title":"Comput. Netw."},{"key":"jstatab3280bib024","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.118.078301","type":"journal-article","article-title":"Mapping the structure of directed networks: beyond the bow-tie diagram","volume":"118","author":"Tim\u00e1r","year":"2017","journal-title":"Phys. Rev. Lett."},{"key":"jstatab3280bib025a","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.64.025101","type":"journal-article","article-title":"Giant strongly connected component of directed networks","volume":"64","author":"Dorogovtsev","year":"2001","journal-title":"Phys. Rev. E"},{"key":"jstatab3280bib025b","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.64.026118","type":"journal-article","article-title":"Random graphs with arbitrary degree distributions and their applications","volume":"64","author":"Newman","year":"2001","journal-title":"Phys. Rev. E"},{"key":"jstatab3280bib026","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.92.052811","type":"journal-article","article-title":"Phase transitions in Ising models on directed networks","volume":"92","author":"Lipowski","year":"2015","journal-title":"Phys. Rev. E"},{"key":"jstatab3280bib027","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.98.062116","type":"journal-article","article-title":"Percolation on an isotropically directed lattice","volume":"98","author":"De Noronha","year":"2018","journal-title":"Phys. Rev. E"},{"key":"jstatab3280bib028","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1023\/A:1018607809852","type":"journal-article","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":"jstatab3280bib029","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.63.184422","type":"journal-article","article-title":"Monte Carlo simulations of spin glasses at low temperatures","volume":"63","author":"Katzgraber","year":"2001","journal-title":"Phys. Rev. B"},{"key":"jstatab3280bib030","doi-asserted-by":"publisher","first-page":"10318","DOI":"10.1073\/pnas.0703685104","type":"journal-article","article-title":"Gibbs states and the set of solutions of random constraint satisfaction problems","volume":"104","author":"Krzakala","year":"2007","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"jstatab3280bib031","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1088\/0305-4470\/31\/2\/012","type":"journal-article","article-title":"Optimization problems and replica symmetry breaking in finite connectivity spin glasses","volume":"31","author":"Monasson","year":"1998","journal-title":"J. Phys. A: Math. Gen."}],"container-title":["Journal of Statistical Mechanics: Theory and Experiment"],"original-title":[],"link":[{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/1742-5468\/ab3280\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/1742-5468\/ab3280","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/1742-5468\/ab3280","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/1742-5468\/ab3280\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/1742-5468\/ab3280\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/1742-5468\/ab3280\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/1742-5468\/ab3280","content-type":"text\/html","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/1742-5468\/ab3280\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T12:45:18Z","timestamp":1773492318000},"score":1,"resource":{"primary":{"URL":"https:\/\/iopscience.iop.org\/article\/10.1088\/1742-5468\/ab3280"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,1]]},"references-count":32,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2019,8,21]]},"published-print":{"date-parts":[[2019,8,1]]}},"URL":"https:\/\/doi.org\/10.1088\/1742-5468\/ab3280","relation":{},"ISSN":["1742-5468"],"issn-type":[{"value":"1742-5468","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,1]]},"assertion":[{"value":"Bipartitioning of directed and mixed random graphs","name":"article_title","label":"Article Title"},{"value":"Journal of Statistical Mechanics: Theory and Experiment","name":"journal_title","label":"Journal Title"},{"value":"paper","name":"article_type","label":"Article Type"},{"value":"\u00a9 2019 IOP Publishing Ltd and SISSA Medialab srl. All rights, including for text and data mining, AI training, and similar technologies, are reserved.","name":"copyright_information","label":"Copyright Information"},{"value":"2019-02-08","name":"date_received","label":"Date Received","group":{"name":"publication_dates","label":"Publication dates"}},{"value":"2019-06-06","name":"date_accepted","label":"Date Accepted","group":{"name":"publication_dates","label":"Publication dates"}},{"value":"2019-08-21","name":"date_epub","label":"Online publication date","group":{"name":"publication_dates","label":"Publication dates"}}]}}