Search

Investigating the performance of different methods is a fundamental problem in graph partitioning. In this paper, we estimate the so-called detectability threshold for the spectral method with both un-normalized and normalized Laplacians in sparse graphs. The detectability threshold is the critical point at which the result of the spectral method is completely uncorrelated to the planted partition. We also analyze whether the localization of eigenvectors affects the partitioning performance in the detectable region. We use the replica method, which is often used in the field of spin-glass theory, and focus on the case of bisection. We show that the gap between the estimated threshold for the spectral method and the threshold obtained from Bayesian inference is considerable in sparse graphs, even without eigenvector localization. This gap closes in a dense limit.

Through supervised learning in a binary perceptron one is able to classify an extensive number of random patterns by a proper assignment of binary synaptic weights. However, to find such assignments in practice is quite a nontrivial task. The relation between the weight space structure and the algorithmic hardness has not yet been fully understood. To this end, we analytically derive the Franz-Parisi potential for the binary perceptron problem by starting from an equilibrium solution of weights and exploring the weight space structure around it. Our result reveals the geometrical organization of the weight space; the weight space is composed of isolated solutions, rather than clusters of exponentially many close-by solutions. The pointlike clusters far apart from each other in the weight space explain the previously observed glassy behavior of stochastic local search heuristics.

We develop a methodology for analyzing the percolation phenomena of two mutually coupled (interdependent) networks based on the cavity method of statistical mechanics. In particular, we take into account the influence of degree-degree correlations inside and between the networks on the network robustness against targeted (random degree-dependent) attacks and random failures. We show that the developed methodology is reduced to the well-known generating function formalism in the absence of degree-degree correlations. The validity of the developed methodology is confirmed by a comparison with the results of numerical experiments. Our analytical results indicate that the robustness of the interdependent networks depends on both the intranetwork and internetwork degree-degree correlations in a nontrivial way for both cases of random failures and targeted attacks.

The adaptive Thouless-Anderson-Palmer equation is derived for inverse Ising problems in the presence of quenched random fields. We test the proposed scheme on Sherrington-Kirkpatrick, Hopfield, and random orthogonal models and find that the adaptive Thouless-Anderson-Palmer approach allows accurate inference of quenched random fields whose distribution can be either Gaussian or bimodal. In particular, another competitive method for inferring external fields, namely, the naive mean field method with diagonal weights, is compared and discussed.

The emerging popular scheme of fourth generation wireless communication, orthogonal frequency-division multiplexing, is mapped onto a variant of a random field Ising Hamiltonian and results in an efficient physical intercarrier interference (ICI) cancellation decoding scheme. This scheme is based on Monte Carlo (MC) dynamics at zero temperature as well as at the Nishimori temperature and demonstrates improved bit error rate (BER) and robust convergence time compared to the state of the art ICI cancellation decoding scheme. An optimal BER performance is achieved with MC dynamics at the Nishimori temperature but with a substantial computational cost overhead. The suggested ICI cancellation scheme also supports the transmission of biased signals.

We developed a scheme for evaluating the size of the largest connected subnetwork (giant component) in random networks and the percolation threshold when sites (nodes) and/or bonds (edges) are removed from the networks based on the cavity method of statistical mechanics of disordered systems. We apply our scheme particularly to random networks of bimodal degree distribution (two-peak networks), which have been proposed in earlier studies as robust networks against random failures of site and/or targeted (random degree-dependent) attacks on sites. Our analysis indicates that the correlations among degrees affect a network's robustness against targeted attacks on sites or bonds nontrivially depending on details of network configurations.

The Kronecker channel model of wireless communication is analyzed using statistical mechanics methods. In the model, spatial proximities among transmission/reception antennas are taken into account as certain correlation matrices, which generally yield nontrivial dependence among symbols to be estimated. This prevents accurate assessment of the communication performance by naively using a previously developed analytical scheme based on a matrix integration formula. In order to resolve this difficulty, we develop a formalism that can formally handle the correlations in Kronecker models based on the known scheme. Unfortunately, direct application of the developed scheme is, in general, practically difficult. However, the formalism is still useful, indicating that the effect of the correlations generally increase after the fourth order with respect to correlation strength. Therefore, the known analytical scheme offers a good approximation in performance evaluation when the correlation strength is sufficiently small. For a class of specific correlation, we show that the performance analysis can be mapped to the problem of one-dimensional spin systems in random fields, which can be investigated without approximation by the belief propagation algorithm.

We investigate the use of Gallager's low-density parity-check (LDPC) codes in a degraded broadcast channel, one of the fundamental models in network information theory. Combining linear codes is a standard technique in practical network communication schemes and is known to provide better performance than simple time sharing methods when algebraic codes are used. The statistical physics based analysis shows that the practical performance of the suggested method, achieved by employing the belief propagation algorithm, is superior to that of LDPC based time sharing codes while the best performance, when received transmissions are optimally decoded, is bounded by the time sharing limit.

The performance of a lossy data compression scheme for uniformly biased Boolean messages is investigated via methods of statistical mechanics. Inspired by a formal similarity to the storage capacity problem in neural network research, we utilize a perceptron of which the transfer function is appropriately designed in order to compress and decode the messages. Employing the replica method, we analytically show that our scheme can achieve the optimal performance known in the framework of lossy compression in most cases when the code length becomes infinite. The validity of the obtained results is numerically confirmed.

The performance of "typical set (pairs) decoding" for ensembles of Gallager's linear code is investigated using statistical physics. In this decoding method, errors occur, either when the information transmission is corrupted by atypical noise, or when multiple typical sequences satisfy the parity check equation as provided by the received corrupted codeword. We show that the average error rate for the second type of error over a given code ensemble can be accurately evaluated using the replica method, including the sensitivity to message length. Our approach generally improves the existing analysis known in the information theory community, which was recently reintroduced in IEEE Trans. Inf. Theory 45, 399 (1999), and is believed to be the most accurate to date.