Bipartitioning of directed and mixed random graphs
arXiv:1901.09298 · doi:10.1088/1742-5468/ab3280
Abstract
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.
arXiv comment7 pages, J.Stat.Mech. (accepted)
References in corpus (15)
- Random graphs with arbitrary degree distributions and their applications
- Clustering and Community Detection in Directed Networks: A Survey
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- Giant strongly connected component of directed networks
- 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
- Nonequilibrium Phase Transitions in Directed Small-World Networks
- Extremal Optimization for Graph Partitioning
- Mapping the Structure of Directed Networks: Beyond the "Bow-tie" Diagram
- Nonequilibrium Stationary States and Phase Transitions in Directed Ising Models
- Belief propagation for graph partitioning
- Percolation on Isotropically Directed Lattice
- Phase transitions in Ising models on directed networks
- The Peculiar Phase Structure of Random Graph Bisection