Complex networks are an important class of models used to describe the behaviour of a very broad category of systems which appear in different fields of science ranging from physics, biology and statistics to computer science and other disciplines. This set of models includes spin systems on a graph, neural networks, decision networks, spreading disease, financial trade, social networks and all systems which can be represented as interacting agents on some sort of graph architecture. In this thesis, by using the theoretical framework of statistical mechanics, the equilibrium and the dynamical behaviour of such systems is studied. For the equilibrium case, after presenting the region graph free energy approximation, the Survey Propagation method, previously used to investi- gate the low temperature phase of complex systems on tree-like topologies, is extended to the case of loopy graph architectures. For time-dependent behaviour, both discrete-time and continuous-time dynamics are considered. It is shown how to extend the cavity method ap- proach from a tool used to study equilibrium properties of complex systems to the discrete-time dynamical scenario. A closure scheme of the dynamic message-passing equation based on a Markovian approximations is presented. This allows to estimate non-equilibrium marginals of spin models on a graph with reversible dynamics. As an alternative to this approach, an extension of region graph variational free energy approximations to the non-equilibrium case is also presented. Non-equilibrium functionals that, when minimized with constraints, lead to approximate equations for out-of-equilibrium marginals of general spin models are introduced and discussed. For the continuous-time dynamics a novel approach that extends the cav- ity method also to this case is discussed. The main result of this part is a Cavity Master Equation which, together with an approximate version of the Master Equation, constitutes a closure scheme to estimate non-equilibrium marginals of continuous-time spin models. The investigation of dynamics of spin systems is concluded by applying a quasi-equilibrium approach to a sim- ple case. A way to test self-consistently the assumptions of the method as well as its limits is discussed. In the final part of the thesis, analogies and differences between the graph- ical model approaches discussed in the manuscript and causal analysis in statistics are presented. / <p>QC 20160904</p>

Magnetic recording systems have reached a point where the grain size can no longer be reduced due to energy stability constraints. As a new magnetic recording paradigm, two-dimensional magnetic recording (TDMR) relies on sophisticated signal processing and coding algorithms, a much less expensive alternative to radically altering the media or the read/write head as required for the other technologies. Due to 1) the significant reduction of grains per bit, and 2) the aggressive shingled writing, TDMR faces several formidable challenges. Firstly, severe interference is introduced in both down-track and cross-track directions due to the read/write head dimensions. Secondly, reduction in the number of grains per bit results in variations of bit boundaries which consequently lead to data-dependent jitter noise. Moreover, the bit to grain ratio reduction will cause some bits not to be properly magnetized or to be overwritten which introduces write errors to the system. The nature of write and read processes in TDMR necessitates that the information storage be viewed as a two-dimensional (2D) system. The challenges in TDMR signal processing are 1) an accurate read channel model, 2) mitigating the effect of inter-track interference (ITI) and inter-symbol interference (ISI) by using an equalizer, 3) developing 2D modulation/error correcting codes matching the TDMR channel model, 4) design of truly 2D detectors, and 5) computing the lower bounds on capacity of TDMR channel. The work is concerned with several objectives in regard to the challenges in TDMR systems. 1. TDMR Channel Modeling: As one of the challenges of the project, the 2D Microcell model is introduced as a read channel model for TDMR. This model captures the data-dependent properties of the media noise and it is well suited in regard to detector design. In line with what has been already done in TDMR channel models, improvements can be made to tune the 2D Microcell model for different bit to grain densities. Furthermore, the 2D Microcell model can be modified to take into account dependency between adjacent microtrack borders positions. This assumption will lead to more accurate model in term of closeness to the Voronoi model. 2. Detector Design: The need for 2D detection is not unique to TDMR systems. However, it is still largely an open problem to develop detectors that are close to optimal maximum likelihood (ML) detection for the 2D case. As one of the important blocks of the TDMR system, the generalized belief propagation (GBP) detector is developed and introduced as a near ML detector. Furthermore, this detector is tuned to improve the performance for the TDMR channel model. 3. Channel Capacity Estimation: Two dimensional magnetic recording (TDMR) is a new paradigm in data storage which envisions densities up to 10 Tb/in² as a result of drastically reducing bit to grain ratio. In order to reach this goal aggressive write (shingled writing) and read process are used in TDMR. Kavcic et al. proposed a simple magnetic grain model called the granular tiling model which captures the essence of read/write process in TDMR. Capacity bounds for this model indicate that 0.6 user bit per grain densities are possible, however, previous attempt to reach capacities are not close to the channel capacity. We provide a truly two-dimensional detection scheme for the granular tiling model based on generalized belief propagation (GBP). Factor graph interpretation of the detection problem is provided and formulated in this section. Then, GBP is employed to compute marginal a posteriori probabilities for the constructed factor graph. Simulation results show huge improvements in detection. A lower bound on the mutual information rate (MIR) is also derived for this model based on GBP detector. Moreover, for the Voronoi channel model, the MIR is estimated for the case of constrained and unconstrained input. 4. Modulation Codes: Constrained codes also known as modulation codes are a key component in the digital magnetic recording systems. The constrained code forbids particular input data patterns which lead to some of the dominant error events or higher media noise. The goal of the dissertation in regard to modulation codes is to construct a 2D modulation code for the TDMR channel which improves the overall performance of the TDMR system. Furthermore, we implement an algorithm to estimate the capacity of the 2D modulation codes based on generalized belief propagation (GBP) algorithm. The capacity is also calculated in presence of white and colored noise which is the case for TDMR channel. 5. Joint Detection and Decoding Schemes: In data recording systems, a concatenated approach toward the constrained code and error-correcting code (ECC) is typically used and the decoding is done independently. We show the improvement in combining the decoding of the constrained code and the ECC using GBP algorithm. We consider the performance of a combined modulation constraints and the ECC on a binary-input additive white Gaussian noise (AWGN) channel (BIAWGNC) and also over one-dimensional (1D) and 2D ISI channels. We will show that combining the detection, demodulation and decoding results in a superior performance compared to concatenated schemes.

Two dimensional magnetic recording (TDMR) achieves high areal densities by reducing the size of a bit comparable to the size of the magnetic grains resulting in two dimensional (2D) inter symbol interference (ISI) and very high media noise. Therefore, it is critical to handle the media noise along with the 2D ISI detection. In this paper, we tune the generalized belief propagation (GBP) algorithm to handle the media noise seen in TDMR. We also provide an intuition into the nature of hard decisions provided by the GBP algorithm. The performance of the GBP algorithm is evaluated over a Voronoi based TDMR channel model where the soft outputs from the GBP algorithm are used by a belief propagation (BP) algorithm to decode low-density parity check (LDPC) codes.