Bipartitioning of directed and mixed random graphs

Autor:	Lipowski, Adam, Ferreira, Antonio Luis, Lipowska, Dorota, Barroso, Manuel A.
Rok vydání:	2019
Předmět:	Condensed Matter - Statistical Mechanics Condensed Matter - Disordered Systems and Neural Networks Computer Science - Computational Complexity
Zdroj:	J. Stat. Mech. (2019) 083301
Druh dokumentu:	Working Paper
DOI:	10.1088/1742-5468/ab3280
Popis:	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. Comment: 7 pages, J.Stat.Mech. (accepted)
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1901.09298 Zobrazit plný text záznamu View this record from Arxiv