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>

Les codes Low-Density Parity-Check (LDPC) sont au coeur de la recherche des codes correcteurs d'erreurs en raison de leur excellente performance de décodage en utilisant un algorithme de décodage itératif de type propagation de croyances (Belief Propagation - BP). Cet algorithme utilise la représentation graphique d'un code, dit graphe de Tanner, et calcule les fonctions marginales sur le graphe. Même si l'inférence calculée n'est exacte que sur un graphe acyclique (arbre), l'algorithme BP estime de manière très proche les marginales sur les graphes cycliques, et les codes LDPC peuvent asymptotiquement approcher la capacité de Shannon avec cet algorithme. Cependant, sur des codes de longueurs finies dont la représentation graphique contient des cycles, l'algorithme BP est sous-optimal et donne lieu à l'apparition du phénomène dit de plancher d'erreur. Le plancher d'erreur se manifeste par la dégradation soudaine de la pente du taux d'erreur dans la zone de fort rapport signal à bruit où les structures néfastes au décodage sont connues en termes de Trapping Sets présents dans le graphe de Tanner du code, entraînant un échec du décodage. De plus, les effets de la quantification introduite par l'implémentation en hardware de l'algorithme BP peuvent amplifier ce problème de plancher d'erreur. Dans cette thèse nous introduisons un nouveau paradigme pour le décodage itératif à précision finie des codes LDPC sur le canal binaire symétrique. Ces nouveaux décodeurs, appelés décodeurs itératifs à alphabet fini (Finite Alphabet Iterative Decoders - FAID) pour préciser que les messages appartiennent à un alphabet fini, sont capables de surpasser l'algorithme BP dans la région du plancher d'erreur. Les messages échangés par les FAID ne sont pas des probabilités ou vraisemblances quantifiées, et les fonctions de mise à jour des noeuds de variable ne copient en rien le décodage par BP ce qui contraste avec les décodeurs BP quantifiés traditionnels. En effet, les fonctions de mise à jour sont de simples tables de vérité conçues pour assurer une plus grande capacité de correction d'erreur en utilisant la connaissance de topologies potentiellement néfastes au décodage présentes dans un code donné. Nous montrons que sur de multiples codes ayant un poids colonne de trois, il existe des FAID utilisant 3 bits de précision pouvant surpasser l'algorithme BP (implémenté en précision flottante) dans la zone de plancher d'erreur sans aucun compromis dans la latence de décodage. C'est pourquoi les FAID obtiennent des performances supérieures comparées au BP avec seulement une fraction de sa complexité. Par ailleurs, nous proposons dans cette thèse une décimation améliorée des FAID pour les codes LDPC dans le traitement de la mise à jour des noeuds de variable. La décimation implique de fixer certains bits du code à une valeur particulière pendant le décodage et peut réduire de manière significative le nombre d'itérations requises pour corriger un certain nombre d'erreurs fixé tout en maintenant de bonnes performances d'un FAID, le rendant plus à même d'être analysé. Nous illustrons cette technique pour des FAID utilisant 3 bits de précision codes de poids colonne trois. Nous montrons également comment cette décimation peut être utilisée de manière adaptative pour améliorer les capacités de correction d'erreur des FAID. Le nouveau modèle proposé de décimation adaptative a, certes, une complexité un peu plus élevée, mais améliore significativement la pente du plancher d'erreur pour un FAID donné. Sur certains codes à haut rendement, nous montrons que la décimation adaptative des FAID permet d'atteindre des capacités de correction d'erreur proches de la limite théorique du décodage au sens du maximum de vraisemblance.

This thesis investigates both theoretical and practical aspects of the design and analysis of iterative algorithms for trust and reputation management and recommender systems. It also studies the application of iterative trust and reputation management mechanisms in ad-hoc networks and P2P systems. First, an algebraic and iterative trust and reputation management scheme (ITRM) is proposed. The proposed ITRM can be applied to centralized schemes, in which a central authority collects the reports and forms the reputations of the service providers (sellers) as well as report/rating trustworthiness of the (service) consumers (buyers). It is shown that ITRM is robust in filtering out the peers who provide unreliable ratings. Next, the first application of Belief Propagation algorithm, a fully iterative probabilistic algorithm, on trust and reputation management (BP-ITRM) is proposed. In BP-ITRM, the reputation management problem is formulated as an inference problem, and it is described as computing marginal likelihood distributions from complicated global functions of many variables. However, it is observed that computing the marginal probability functions is computationally prohibitive for large scale reputation systems. Therefore, the belief propagation algorithm is utilized to efficiently (in linear complexity) compute these marginal probability distributions. In BP-ITRM, the reputation system is modeled by using a factor graph and reputation values of the service providers (sellers) are computed by iterative probabilistic message passing between the factor and variable nodes on the graph. It is shown that BP-ITRM is reliable in filtering out malicious/unreliable reports. It is proven that BP-ITRM iteratively reduces the error in the reputation values of service providers due to the malicious raters with a high probability. Further, comparison of BP-ITRM with some well-known and commonly used reputation management techniques (e.g., Averaging Scheme, Bayesian Approach and Cluster Filtering) indicates the superiority of the proposed scheme both in terms of robustness against attacks and efficiency. The introduction of the belief propagation and iterative message passing methods onto trust and reputation management has opened up several research directions. Thus, next, the first application of the belief propagation algorithm in the design of recommender systems (BPRS) is proposed. In BPRS, recommendations (predicted ratings) for each active user are iteratively computed by probabilistic message passing between variable and factor nodes in a factor graph. It is shown that as opposed to the previous recommender algorithms, BPRS does not require solving the recommendation problem for all users if it wishes to update the recommendations for only a single active user using the most recent data (ratings). Further, BPRS computes the recommendations for each user with linear complexity, without requiring a training period while it remains comparable to the state of art methods such as Correlation-based neighborhood model (CorNgbr) and Singular Value Decomposition (SVD) in terms of rating and precision accuracy. This work also explores fundamental research problems related to application of iterative and probabilistic reputation management systems in various fields (such as ad-hoc networks and P2P systems). A distributed malicious node detection mechanism is proposed for delay tolerant networks (DTNs) using ITRM which enables every node to evaluate other nodes based on their past behavior, without requiring a central authority. Further, for the first time. the belief propagation algorithm is utilized in the design and evaluation of distributed trust and reputation management systems for P2P networks. Several schemes are extensively simulated and are compared to demonstrate the effectiveness of the iterative algorithms and belief propagation on these applications.

Survey propagation (SP) has recently been discovered as an efficient algorithm in solving classes of hard constraint-satisfaction problems (CSP). Powerful as it is, SP is still a heuristic algorithm, and further understanding its algorithmic nature, improving its effectiveness and extending its applicability are highly desirable. Prior to the work in this thesis, Maneva et al. introduced a Markov Random Field (MRF) formalism for k-SAT problems, on which SP may be viewed as a special case of the well-known belief propagation (BP) algorithm. This result had sometimes been interpreted to an understanding that “SP is BP” and allows a rigorous extension of SP to a “weighted” version, or a family of algorithms, for k-SAT problems. SP has also been generalized, in a non-weighted fashion, for solving non-binary CSPs. Such generalization is however presented using statistical physics language and somewhat difficult to access by more general audience. This thesis generalizes SP both in terms of its applicability to non-binary problems and in terms of introducing “weights” and extending SP to a family of algorithms. Under a generic formulation of CSPs, we first present an understanding of non-weighted SP for arbitrary CSPs in terms of “probabilistic token passing” (PTP). We then show that this probabilistic interpretation of non-weighted SP makes it naturally generalizable to a weighted version, which we call weighted PTP. Another main contribution of this thesis is a disproof of the folk belief that “SP is BP”. We show that the fact that SP is a special case of BP for k-SAT problems is rather incidental. For more general CSPs, SP and generalized SP do not reduce from BP. We also established the conditions under which generalized SP may reduce as special cases of BP. To explore the benefit of generalizing SP to a wide family and for arbitrary, particularly non-binary, problems, we devised a simple weighted PTP based algorithm for solving 3-COL problems. Experimental results, compared against an existing non-weighted SP based algorithm, reveal the potential performance gain that generalized SP may bring.

Survey propagation (SP) has recently been discovered as an efficient algorithm in solving classes of hard constraint-satisfaction problems (CSP). Powerful as it is, SP is still a heuristic algorithm, and further understanding its algorithmic nature, improving its effectiveness and extending its applicability are highly desirable. Prior to the work in this thesis, Maneva et al. introduced a Markov Random Field (MRF) formalism for k-SAT problems, on which SP may be viewed as a special case of the well-known belief propagation (BP) algorithm. This result had sometimes been interpreted to an understanding that “SP is BP” and allows a rigorous extension of SP to a “weighted” version, or a family of algorithms, for k-SAT problems. SP has also been generalized, in a non-weighted fashion, for solving non-binary CSPs. Such generalization is however presented using statistical physics language and somewhat difficult to access by more general audience. This thesis generalizes SP both in terms of its applicability to non-binary problems and in terms of introducing “weights” and extending SP to a family of algorithms. Under a generic formulation of CSPs, we first present an understanding of non-weighted SP for arbitrary CSPs in terms of “probabilistic token passing” (PTP). We then show that this probabilistic interpretation of non-weighted SP makes it naturally generalizable to a weighted version, which we call weighted PTP. Another main contribution of this thesis is a disproof of the folk belief that “SP is BP”. We show that the fact that SP is a special case of BP for k-SAT problems is rather incidental. For more general CSPs, SP and generalized SP do not reduce from BP. We also established the conditions under which generalized SP may reduce as special cases of BP. To explore the benefit of generalizing SP to a wide family and for arbitrary, particularly non-binary, problems, we devised a simple weighted PTP based algorithm for solving 3-COL problems. Experimental results, compared against an existing non-weighted SP based algorithm, reveal the potential performance gain that generalized SP may bring.

In many modern wireless and wireline communication networks, the interference power from other communication and non-communication devices is increasingly dominating the background noise power, leading to interference limited communication systems. Conventional communication systems have been designed under the assumption that noise in the system can be modeled as additive white Gaussian noise (AWGN). While appropriate for thermal noise, the AWGN model does not always capture the interference statistics in modern communication systems. Interference from uncoordinated users and sources is particularly harmful to communication performance because it cannot be mitigated by current interference management techniques. Based on previous statistical-physical models for uncoordinated wireless interference, this dissertation derives similar models for uncoordinated interference in PLC networks. The dissertation then extends these models for wireless and powerline interference to include temporal dependence among amplitude samples. The extensions are validated with measured data. The rest of this dissertation utilizes the proposed models to design receivers in interference limited environments. Prior designs generally adopt suboptimal approaches and often ignore the problem of channel estimation which limits their applicability in practical systems. This dissertation uses the graphical model representation of the OFDM system to propose low-complexity message passing OFDM receivers that leverage recent results in soft-input soft-output decoding, approximate message passing, and sparse signal recovery for joint channel/interference estimation and data decoding. The resulting receivers provide huge improvements in communication performance (more than 10dB) over the conventional receivers at a comparable computational complexity. Finally, this dissertation addresses the design of robust receivers that can be deployed in rapidly varying environments where the interference statistics are constantly changing. / text

Distributed iterative algorithms are of great importance, as they are known to provide low-complexity and approximate solutions to what are otherwise high-dimensional intractable optimization problems. The theory of message-passing based algorithms is fairly well developed in the coding, machine learning and statistical physics literatures. Even though several applications of message-passing algorithms have already been identified, this work aims at establishing that a plethora of other applications exist where it can be of great importance. In particular, the goal of this work is to develop and demonstrate applications of this class of algorithms in network communications and computational biology. In the domain of communications, message-passing based algorithms provide distributed ways of inferring the optimal solution without the aid of a central agent for various optimization problems that happen in the resource allocation of communication networks. Our main framework is Affinity Propagation (AP), originally developed for clustering problems. We reinterpret this framework to unify the development of distributed algorithms for discrete resource allocation problems. Also, we consider a network-coded communication network, where continuous rate allocation is studied. We formulate an optimization problem with a linear cost function, and then utilize a Belief Propagation (BP) approach to determine a decentralized rate allocation strategy. Next, we move to the domain of computational biology, where graphical representations and computational biology play a major role. First, we consider the motif finding problem with several DNA sequences. In effect, this is a sequence matching problem, which can be modeled using various graphical representations and also solved using low-complexity algorithms based on message-passing techniques. In addition, we address the application of message-passing algorithms for a DNA sequencing problem where the one dimensional structure of a single DNA sequence is identified. We reinterpret the problem as being equivalent to the decoding of a nonlinear code. Based on the iterative decoding framework, we develop an appropriate graphical model which enables us to derive a message-passing algorithm to improve the performance of the DNA sequencing problem. Although this work consists of disparate application domains of communications, networks and computational biology, graphical models and distributed message-passing algorithms form a common underlying theme. / text

This thesis deals with the problem of three dimensional scene reconstruction from multiple camera images. This is a well established problem in computer vision and has been significantly researched. In recent years some excellent results have been achieved, however existing algorithms often fall short of many biological systems in terms of robustness and generality. The aim of this research was to develop improved algorithms for reconstructing 3D scenes, with a focus on accurate system modelling and correctly dealing with occlusions. With scene reconstruction the objective is to infer scene parameters describing the 3D structure of the scene from the data given by camera images. This is an illposed inverse problem, where an exact solution cannot be guaranteed. The use of a statistical approach to deal with the scene reconstruction problem is introduced and the differences between maximum a priori (MAP) and minimum mean square estimate (MMSE) considered. It is discussed how traditional stereo matching can be performed using a volumetric scene model. An improved model describing the relationship between the camera data and a discrete model of the scene is presented. This highlights some of the common causes of modelling errors, enabling them to be dealt with objectively. The problems posed by occlusions are considered. Using a greedy algorithm the scene is progressively reconstructed to account for visibility interactions between regions and the idea of a complete scene estimate is established. Some simple and improved techniques for reliably assigning opaque voxels are developed, making use of prior information. Problems with variations in the imaging convolution kernel between images motivate the development of a pixel dissimilarity measure. Belief propagation is then applied to better utilise prior information and obtain an improved global optimum. A new volumetric factor graph model is presented which represents the joint probability distribution of the scene and imaging system. By utilising the structure of the local compatibility functions, an efficient procedure for updating the messages is detailed. To help convergence, a novel approach of accentuating beliefs is shown. Results demonstrate the validity of this approach, however the reconstruction error is similar or slightly higher than from the Greedy algorithm. To simplify the volumetric model, a new approach to belief propagation is demonstrated by applying it to a dynamic model. This approach is developed as an alternative to the full volumetric model because it is less memory and computationally intensive. Using a factor graph, a volumetric known visibility model is presented which ensures the scene is complete with respect to all the camera images. Dynamic updating is also applied to a simpler single depth-map model. Results show this approach is unsuitable for the volumetric known visibility model, however, improved results are obtained with the simple depth-map model.

Survey propagation (SP) has recently been discovered as an efficient algorithm in solving classes of hard constraint-satisfaction problems (CSP). Powerful as it is, SP is still a heuristic algorithm, and further understanding its algorithmic nature, improving its effectiveness and extending its applicability are highly desirable. Prior to the work in this thesis, Maneva et al. introduced a Markov Random Field (MRF) formalism for k-SAT problems, on which SP may be viewed as a special case of the well-known belief propagation (BP) algorithm. This result had sometimes been interpreted to an understanding that “SP is BP” and allows a rigorous extension of SP to a “weighted” version, or a family of algorithms, for k-SAT problems. SP has also been generalized, in a non-weighted fashion, for solving non-binary CSPs. Such generalization is however presented using statistical physics language and somewhat difficult to access by more general audience. This thesis generalizes SP both in terms of its applicability to non-binary problems and in terms of introducing “weights” and extending SP to a family of algorithms. Under a generic formulation of CSPs, we first present an understanding of non-weighted SP for arbitrary CSPs in terms of “probabilistic token passing” (PTP). We then show that this probabilistic interpretation of non-weighted SP makes it naturally generalizable to a weighted version, which we call weighted PTP. Another main contribution of this thesis is a disproof of the folk belief that “SP is BP”. We show that the fact that SP is a special case of BP for k-SAT problems is rather incidental. For more general CSPs, SP and generalized SP do not reduce from BP. We also established the conditions under which generalized SP may reduce as special cases of BP. To explore the benefit of generalizing SP to a wide family and for arbitrary, particularly non-binary, problems, we devised a simple weighted PTP based algorithm for solving 3-COL problems. Experimental results, compared against an existing non-weighted SP based algorithm, reveal the potential performance gain that generalized SP may bring.

Survey propagation (SP) has recently been discovered as an efficient algorithm in solving classes of hard constraint-satisfaction problems (CSP). Powerful as it is, SP is still a heuristic algorithm, and further understanding its algorithmic nature, improving its effectiveness and extending its applicability are highly desirable. Prior to the work in this thesis, Maneva et al. introduced a Markov Random Field (MRF) formalism for k-SAT problems, on which SP may be viewed as a special case of the well-known belief propagation (BP) algorithm. This result had sometimes been interpreted to an understanding that “SP is BP” and allows a rigorous extension of SP to a “weighted” version, or a family of algorithms, for k-SAT problems. SP has also been generalized, in a non-weighted fashion, for solving non-binary CSPs. Such generalization is however presented using statistical physics language and somewhat difficult to access by more general audience. This thesis generalizes SP both in terms of its applicability to non-binary problems and in terms of introducing “weights” and extending SP to a family of algorithms. Under a generic formulation of CSPs, we first present an understanding of non-weighted SP for arbitrary CSPs in terms of “probabilistic token passing” (PTP). We then show that this probabilistic interpretation of non-weighted SP makes it naturally generalizable to a weighted version, which we call weighted PTP. Another main contribution of this thesis is a disproof of the folk belief that “SP is BP”. We show that the fact that SP is a special case of BP for k-SAT problems is rather incidental. For more general CSPs, SP and generalized SP do not reduce from BP. We also established the conditions under which generalized SP may reduce as special cases of BP. To explore the benefit of generalizing SP to a wide family and for arbitrary, particularly non-binary, problems, we devised a simple weighted PTP based algorithm for solving 3-COL problems. Experimental results, compared against an existing non-weighted SP based algorithm, reveal the potential performance gain that generalized SP may bring.