1
|
Takabe S, Hukushima K. Minimum vertex cover problems on random hypergraphs: replica symmetric solution and a leaf removal algorithm. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2014; 89:062139. [PMID: 25019756 DOI: 10.1103/physreve.89.062139] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 02/03/2013] [Indexed: 06/03/2023]
Abstract
The minimum vertex-cover problems on random α-uniform hypergraphs are studied using two different approaches, a replica method in statistical mechanics of random systems and a leaf removal algorithm. It is found that there exists a phase transition at the critical average degree e/(α-1), below which a replica symmetric ansatz in the replica method holds and the algorithm estimates exactly the same solution of the problem as that by the replica method. In contrast, above the critical degree, the replica symmetric solution becomes unstable and the leaf-removal algorithm fails to estimate the optimal solution because of the emergence of a large size core. These results strongly suggest a close relation between the replica symmetry and the performance of an approximation algorithm. Critical properties of the core percolation are also examined numerically by a finite-size scaling.
Collapse
Affiliation(s)
- Satoshi Takabe
- Graduate School of Arts and Sciences, The University of Tokyo, 3-8-1 Komaba, Meguro-ku, Tokyo 153-8902, Japan
| | - Koji Hukushima
- Graduate School of Arts and Sciences, The University of Tokyo, 3-8-1 Komaba, Meguro-ku, Tokyo 153-8902, Japan
| |
Collapse
|
2
|
Alamino RC, Neirotti JP, Saad D. Replication-based inference algorithms for hard computational problems. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2013; 88:013313. [PMID: 23944589 DOI: 10.1103/physreve.88.013313] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 05/13/2013] [Indexed: 06/02/2023]
Abstract
Inference algorithms based on evolving interactions between replicated solutions are introduced and analyzed on a prototypical NP-hard problem: the capacity of the binary Ising perceptron. The efficiency of the algorithm is examined numerically against that of the parallel tempering algorithm, showing improved performance in terms of the results obtained, computing requirements and simplicity of implementation.
Collapse
Affiliation(s)
- Roberto C Alamino
- Non-linearity and Complexity Research Group, Aston University, Birmingham B4 7ET, United Kingdom
| | | | | |
Collapse
|
3
|
Alamino RC, Saad D. Typical kernel size and number of sparse random matrices over Galois fields: a statistical physics approach. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2008; 77:061123. [PMID: 18643233 DOI: 10.1103/physreve.77.061123] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/14/2008] [Indexed: 05/26/2023]
Abstract
Using methods of statistical physics, we study the average number and kernel size of general sparse random matrices over Galois fields GF(q) , with a given connectivity profile, in the thermodynamical limit of large matrices. We introduce a mapping of GF(q) matrices onto spin systems using the representation of the cyclic group of order q as the q th complex roots of unity. This representation facilitates the derivation of the average kernel size of random matrices using the replica approach, under the replica-symmetric ansatz, resulting in saddle point equations for general connectivity distributions. Numerical solutions are then obtained for particular cases by population dynamics. Similar techniques also allow us to obtain an expression for the exact and average numbers of random matrices for any general connectivity profile. We present numerical results for particular distributions.
Collapse
Affiliation(s)
- R C Alamino
- Neural Computing Research Group, Aston University, Birmingham, United Kingdom
| | | |
Collapse
|
4
|
Krząkała F, Zdeborová L. Phase transitions and computational difficulty in random constraint satisfaction problems. ACTA ACUST UNITED AC 2008. [DOI: 10.1088/1742-6596/95/1/012012] [Citation(s) in RCA: 10] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/11/2022]
|
5
|
Zdeborová L, Krzakała F. Phase transitions in the coloring of random graphs. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2007; 76:031131. [PMID: 17930223 DOI: 10.1103/physreve.76.031131] [Citation(s) in RCA: 41] [Impact Index Per Article: 2.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/11/2007] [Indexed: 05/25/2023]
Abstract
We consider the problem of coloring the vertices of a large sparse random graph with a given number of colors so that no adjacent vertices have the same color. Using the cavity method, we present a detailed and systematic analytical study of the space of proper colorings (solutions). We show that for a fixed number of colors and as the average vertex degree (number of constraints) increases, the set of solutions undergoes several phase transitions similar to those observed in the mean field theory of glasses. First, at the clustering transition, the entropically dominant part of the phase space decomposes into an exponential number of pure states so that beyond this transition a uniform sampling of solutions becomes hard. Afterward, the space of solutions condenses over a finite number of the largest states and consequently the total entropy of solutions becomes smaller than the annealed one. Another transition takes place when in all the entropically dominant states a finite fraction of nodes freezes so that each of these nodes is allowed a single color in all the solutions inside the state. Eventually, above the coloring threshold, no more solutions are available. We compute all the critical connectivities for Erdos-Rényi and regular random graphs and determine their asymptotic values for a large number of colors. Finally, we discuss the algorithmic consequences of our findings. We argue that the onset of computational hardness is not associated with the clustering transition and we suggest instead that the freezing transition might be the relevant phenomenon. We also discuss the performance of a simple local Walk-COL algorithm and of the belief propagation algorithm in the light of our results.
Collapse
Affiliation(s)
- Lenka Zdeborová
- LPTMS, UMR 8626 CNRS et Université Paris-Sud, 91405 Orsay CEDEX, France
| | | |
Collapse
|
6
|
Krzakala F, Kurchan J. Landscape analysis of constraint satisfaction problems. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2007; 76:021122. [PMID: 17930021 DOI: 10.1103/physreve.76.021122] [Citation(s) in RCA: 19] [Impact Index Per Article: 1.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/03/2007] [Indexed: 05/25/2023]
Abstract
We discuss an analysis of constraint satisfaction problems, such as sphere packing, K-SAT, and graph coloring, in terms of an effective energy landscape. Several intriguing geometrical properties of the solution space become in this light familiar in terms of the well-studied ones of rugged (glassy) energy landscapes. A benchmark algorithm naturally suggested by this construction finds solutions in polynomial time up to a point beyond the clustering and in some cases even the thermodynamic transitions. This point has a simple geometric meaning and can be in principle determined with standard statistical mechanical methods, thus pushing the analytic bound up to which problems are guaranteed to be easy. We illustrate this for the graph 3- and 4-coloring problem. For packing problems the present discussion allows to better characterize the J-point, proposed as a systematic definition of random close packing, and to place it in the context of other theories of glasses.
Collapse
Affiliation(s)
- Florent Krzakala
- PCT, CNRS UMR Gulliver 7083, ESPCI, 10 rue Vauquelin, 75005 Paris, France
| | | |
Collapse
|
7
|
Bounkong S, van Mourik J, Saad D. Coloring random graphs and maximizing local diversity. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2006; 74:057101. [PMID: 17280022 DOI: 10.1103/physreve.74.057101] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 11/27/2005] [Indexed: 05/13/2023]
Abstract
We study a variation of the graph coloring problem on random graphs of finite average connectivity. Given the number of colors, we aim to maximize the number of different colors at neighboring vertices (i.e., one edge distance) of any vertex. Two efficient algorithms, belief propagation and Walksat, are adapted to carry out this task. We present experimental results based on two types of random graphs for different system sizes and identify the critical value of the connectivity for the algorithms to find a perfect solution. The problem and the suggested algorithms have practical relevance since various applications, such as distributed storage, can be mapped onto this problem.
Collapse
Affiliation(s)
- S Bounkong
- Neural Computing Research Group, Aston University, Birmingham B4 7ET, United Kingdom
| | | | | |
Collapse
|
8
|
Guimerà R, Sales-Pardo M, Amaral LAN. Modularity from fluctuations in random graphs and complex networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2004; 70:025101. [PMID: 15447530 PMCID: PMC2441765 DOI: 10.1103/physreve.70.025101] [Citation(s) in RCA: 227] [Impact Index Per Article: 11.4] [Reference Citation Analysis] [Abstract] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/15/2004] [Indexed: 05/07/2023]
Abstract
The mechanisms by which modularity emerges in complex networks are not well understood but recent reports have suggested that modularity may arise from evolutionary selection. We show that finding the modularity of a network is analogous to finding the ground-state energy of a spin system. Moreover, we demonstrate that, due to fluctuations, stochastic network models give rise to modular networks. Specifically, we show both numerically and analytically that random graphs and scale-free networks have modularity. We argue that this fact must be taken into consideration to define statistically significant modularity in complex networks.
Collapse
Affiliation(s)
- Roger Guimerà
- Department of Chemical and Biological Engineering, Northwestern University, Evanston, Illinois 60208, USA
| | | | | |
Collapse
|
9
|
Castellani T, Napolano V, Ricci-Tersenghi F, Zecchina R. Bicolouring random hypergraphs. ACTA ACUST UNITED AC 2003. [DOI: 10.1088/0305-4470/36/43/026] [Citation(s) in RCA: 10] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/11/2022]
|
10
|
Braunstein A, Mulet R, Pagnani A, Weigt M, Zecchina R. Polynomial iterative algorithms for coloring and analyzing random graphs. ACTA ACUST UNITED AC 2003; 68:036702. [PMID: 14524921 DOI: 10.1103/physreve.68.036702] [Citation(s) in RCA: 88] [Impact Index Per Article: 4.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/24/2003] [Indexed: 11/07/2022]
Abstract
We study the graph coloring problem over random graphs of finite average connectivity c. Given a number q of available colors, we find that graphs with low connectivity admit almost always a proper coloring whereas graphs with high connectivity are uncolorable. Depending on q, we find with a one-step replica-symmetry breaking approximation the precise value of the critical average connectivity c(q). Moreover, we show that below c(q) there exists a clustering phase c in [c(d),c(q)] in which ground states spontaneously divide into an exponential number of clusters. Furthermore, we extended our considerations to the case of single instances showing consistent results. This leads us to propose a different algorithm that is able to color in polynomial time random graphs in the hard but colorable region, i.e., when c in [c(d),c(q)].
Collapse
Affiliation(s)
- A Braunstein
- International Center for Theoretical Physics, Strada Costiera 11, P.O. Box 586, I-34100 Trieste, Italy
| | | | | | | | | |
Collapse
|