Graphical Explanation in Belief Networks

Abstract

Belief networks provide an important bridge between statistical modeling and expert systems. This article presents methods for visualizing probabilistic “evidence flows” in belief networks, thereby enabling belief networks to explain their behavior. Building on earlier research on explanation in expert systems, we present a hierarchy of explanations, ranging from simple colorings to detailed displays. Our approach complements parallel work on textual explanations in belief networks. Graphical-Belief, Mathsoft Inc.'s belief network software, implements the methods.     

Stability analysis of activation-inhibition Boolean networks with stochastic function structures

This paper analyzes the stability of activation-inhibition Boolean networks with stochastic function structures. First, the activation-inhibition Boolean networks with stochastic function structures are converted to the form of logical networks by the method of semitensor product of matrices. Second, based on the obtained algebraic forms, we use matrices to denote the index set of possible logical operators and transition probabilities for activation-inhibition Boolean networks. Third, equivalence criterions are presented for the stabilities analysis of activation-inhibition Boolean networks with stochastic function structures. Finally, an example is given to verify the validity of the results.     

Petri net modelling of biological regulatory networks

The complexity of biological regulatory networks often defies the intuition of the biologist and calls for the development of proper mathematical methods to model their structures and to delineate their dynamical properties. One qualitative approach consists in modelling regulatory networks in terms of logical equations (using either Boolean or multi-level discretisations). The Petri Net (PN) formalism offers a complementary framework to analyse the dynamical behaviour of large systems, either from a qualitative or from a quantitative point of view.

Our proposal consists in articulating the logical approach with the PN formalism. In a previous work, we have already defined a systematic re-writing of Boolean regulatory models into a standard PN formalism. In this paper, we propose a rigorous and systematic mapping of multi-level logical regulatory models into specific standard Petri nets, called Multi-level Regulatory Petri Nets (MRPNs). We further propose some reduction strategies. Consequently, the resulting models become amenable to the algebraic and computational analyses used by the PN community.

To illustrate our approach, we apply it to a multi-level logical model of the genetic switch controlling the lysis-lysogeny decision in the lambda bacteriophage.     

Polynomial representations of piecewise-linear differential equations arising from gene regulatory networks

We describe generic sliding modes of piecewise-linear systems of differential equations arising in the theory of gene regulatory networks with Boolean interactions. We do not make any a priori assumptions on regulatory functions in the network and try to understand what mathematical consequences this may have in regard to the limit dynamics of the system. Further, we provide a complete classification of such systems in terms of polynomial representations for the cases where the discontinuity set of the right-hand side of the system has a codimension 1 in the phase space. In particular, we prove that the multilinear representation of the underlying Boolean structure of a continuous-time gene regulatory network is only generic in the absence of sliding trajectories. Our results also explain why the Boolean structure of interactions is too coarse and usually gives rise to several non-equivalent models with smooth interactions.     

Factorized time-dependent distributions for certain multiclass queueing networks and an application to?enzymatic processing networks

Motivated by applications in biological systems, we show for certain multiclass queueing networks that time-dependent distributions for the multiclass queue-lengths can have a factorized form which reduces the problem of computing such distributions to a similar problem for related single-class queueing networks. We give an example of the application of this result to an enzymatic processing network.     

On the computation of fixed points in Boolean networks

In this paper we study the problem of finding fixed points of AND-NOT Boolean networks and relate it to the problem of finding maximal independent sets of a graph. Furthermore, we provide a sharp upper bound for the number of fixed points of normal AND-NOT Boolean networks. We also show that any AND-NOT Boolean network can be transformed into a normal AND-NOT Boolean network.     

Limit cycles and update digraphs in Boolean networks

Boolean networks have been used as models of gene regulation and other biological networks, as well as for other kinds of distributed dynamical systems. One key element in these models is the update schedule, which indicates the order in which states have to be updated. In Salinas (2008) [22] and Aracena et al. (2009) [1], equivalence classes of deterministic update schedules according to the labeled digraph associated to a Boolean network (update digraph) were defined and it was proved that two schedules in the same class yield the same dynamical behavior. In this paper, we study the relations between the update digraphs and the preservation of limit cycles of Boolean networks iterated under non-equivalent update schedules. We show that the related problems lie in the class of NP-hard problems and we prove that the information provided by the update digraphs is not sufficient to determine whether two Boolean networks share limit cycles or not. Besides, we exhibit a polynomial algorithm that works as a necessary condition for two Boolean networks to share limit cycles. Finally, we construct some update schedule classes whose elements share a given limit cycle under certain conditions on the frozen nodes of it.     

Robustness in biological regulatory networks II: Application to genetic threshold Boolean random regulatory networks (getBren)

An important example of biological regulatory networks is constituted by the genetic threshold Boolean random regulatory networks (getBren), which are very useful for explaining the precise mechanisms of the genetic control. This article shows the mathematical relationships between parameter sensitivity of the evolutionary entropy and network frustration in the particular context of the getBrens.     

Dynamic information handling in continuous time Boolean Network model of gene interactions

Growing information and knowledge on gene regulatory networks, which are typical hybrid systems, has led a significant interest in modeling those networks. An important direction of gene network modeling is studying the abstract network models to understand the behavior of a class of systems. Boolean Networks has emerged as an important model class on this direction. Limitations of traditional Boolean Networks led the researchers to propose several generalizations. In this work, one such class, the Continuous Time Boolean Networks (CTBN’s), is studied. CTBN’s are constructed by allowing the Boolean variables evolve in continuous time and involve a biologically-motivated refractory period. In particular, we analyze the basic circuits and subsystems of the class of CTBN’s. We demonstrate the existence of various qualitative dynamic behavior including stable, multistable, neutrally stable, quasiperiodic and chaotic behaviors. We show that those models are capable of demonstrating highly adjustable features like maintenance of continuous protein concentrations. Finally, we discuss the relation between qualitative dynamic features and information handling.     

Identification of predictors of Boolean networks from observed attractor states

Predictors of Boolean networks are of significance for biologists to target their research on gene regulation and control. This paper aims to investigate how to determine predictors of Boolean networks from observed attractor states by solving logical equations. The proposed method consists of four steps. First, all possible cycles formed by known attractor states are constructed. Then, for each possible cycle, all data‐permitted predictors of each node are identified according to the known attractor states. Subsequently, the data‐permitted predictors are incorporated with some common biological constraints to generate logical equations that describe whether such possible predictors can ultimately be chosen as valid ones by the biological constraints. Finally, solve the logical equations; the solutions determine a family of predictors satisfying the known attractor states. The approach is quite different from others such as computer algorithm‐based and provides a new angle and means to understand and analyze the structures of Boolean networks.     

Detecting evolving patterns of self‐organizing networks by flow hierarchy measurement

Hierarchies occur widely in evolving self‐organizing ecological, biological, technological, and social networks, but detecting and comparing hierarchies is difficult. Here we present a metric and technique to quantitatively assess the extent to which self‐organizing directed networks exhibit a flow hierarchy. Flow hierarchy is a commonly observed but theoretically overlooked form of hierarchy in networks. We show that the ecological, neurobiological, economic, and information processing networks are generally more hierarchical than their comparable random networks. We further discovered that hierarchy degree has increased over the course of the evolution of Linux kernels. Taken together, our results suggest that hierarchy is a central organizing feature of real‐world evolving networks, and the measurement of hierarchy opens the way to understand the structural regimes and evolutionary patterns of self‐organizing networks. Our measurement technique makes it possible to objectively compare hierarchies of different networks and of different evolutionary stages of a single network, and compare evolving patterns of different networks. It can be applied to various complex systems, which can be represented as directed networks. © 2011 Wiley Periodicals, Inc. Complexity, 2011     

Classes of network connectivity and dynamics

Many kinds of complex systems exhibit characteristic patterns of temporal correlations that emerge as the result of functional interactions within a structured network. One such complex system is the brain, composed of numerous neuronal units linked by synaptic connections. The activity of these neuronal units gives rise to dynamic states that are characterized by specific patterns of neuronal activation and co‐activation. These patterns, called functional connectivity, are possible neural correlates of perceptual and cognitive processes. Which functional connectivity patterns arise depends on the anatomical structure of the underlying network, which in turn is modified by a broad range of activity‐dependent processes. Given this intricate relationship between structure and function, the question of how patterns of anatomical connectivity constrain or determine dynamical patterns is of considerable theoretical importance. The present study develops computational tools to analyze networks in terms of their structure and dynamics. We identify different classes of network, including networks that are characterized by high complexity. These highly complex networks have distinct structural characteristics such as clustered connectivity and short wiring length similar to those of large‐scale networks of the cerebral cortex. © 2002 Wiley Periodicals, Inc.     

Evolution in random environment and structural instability

We consider stability and evolution of complex biological systems, in particular, genetic networks. We focus our attention on the problem of homeostasis in these systems with respect to fluctuations of an external medium (the problem is posed by Gromov and Carbone). Using a certain measure of stochastic stability, we show that a generic system with fixed parameters is unstable, i.e., the probability to support homeostasis converges to zero as the time T goes to infinity. However, if we consider a population of unstable systems that are capable to evolve (change their parameters), then such a population can be stable as T → ∞. This means that the probability to survive may be nonzero as T → ∞. Evolution algorithms that provide stability of populations are not trivial. We show that the mathematical results on evolution algorithms are consistent with experimental data on genetic evolution. Bibliography: 45 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 325, 2005, pp. 28–60.     

Cooperative Boolean systems with generically long attractors I

We study the class of cooperative Boolean networks whose only regulatory functions are COPY, binary AND and binary OR. We prove that for all sufficiently large N and c < 2 there exist Boolean networks in this class that have an attractor of length >c ^N whose basin of attraction comprises an arbitrarily large fraction of the state space. The existence of such networks sharply contrasts with results on continuous dynamical systems that imply non-genericity of non-steady-state attractors under the assumption of cooperativity.     

Complete Fault Detection Tests of Length 2 for Logic Networks under Stuck-at Faults of Gates

We consider the problem of the synthesis of the logic networks implementing Boolean functions of n variables and allowing short complete fault detection tests regarding arbitrary stuck-at faults at the outputs of gates. We prove that there exists a basis consisting of two Boolean functions of at most four variables in which we can implement each Boolean function by a network allowing such a test with length at most 2.     

Mean-field modeling approach for understanding epidemic dynamics in interconnected networks

Modern systems (e.g., social, communicant, biological networks) are increasingly interconnected each other formed as ‘networks of networks’. Such complex systems usually possess inconsistent topologies and permit agents distributed in different subnetworks to interact directly/indirectly. Corresponding dynamics phenomena, such as the transmission of information, power, computer virus and disease, would exhibit complicated and heterogeneous tempo-spatial patterns. In this paper, we focus on the scenario of epidemic spreading in interconnected networks. We intend to provide a typical mean-field modeling framework to describe the time-evolution dynamics, and offer some mathematical skills to study the spreading threshold and the global stability of the model. Integrating the research with numerical analysis, we are able to quantify the effects of networks structure and epidemiology parameters on the transmission dynamics. Interestingly, we find that the diffusion transition in the whole network is governed by a unique threshold, which mainly depends on the most heterogenous connection patterns of network substructures. Further, the dynamics is highly sensitive to the critical values of cross infectivity with switchable phases.     

Fourth-generation warfare: Jihadist networks and percolation

This paper studies the approach to the fourth-generation warfare (4GW) paradigm from the perspective of physical and mathematical disciplines, through the interdisciplinary bridge offered by the analysis of complex networks. The study is within an emerging multidisciplinary field, Sociophysics, which attempts to apply statistical mechanics and the science of complex systems to predict human social behavior. The fourth-generation warfare concept is reviewed, and the war of the Jihadist Islam against the West will be contextualized as 4GW. The paradigm of complex systems has in diverse branches of science changed how collective phenomena are processed. The jihadist networks phenomenon in particular is appropriate for study from the standpoint of complex networks. We present an empirical study of the 9/11 and 11M networks, implemented from public information, and we give a comparison of both networks from the standpoint of complex networks. Several authors have made use of the phenomenon of percolation in complex physical systems to analyse complex networks, particularly jihadist actions like 9/11. The relationship between jihadist networks and percolation is considered. The percolation concept is reviewed and related to 4GW, and the definition of memetic dimension is introduced.     

Deriving Behavior of Boolean Bioregulatory Networks from Subnetwork Dynamics

In the well-known discrete modeling framework developed by R. Thomas, the structure of a biological regulatory network is captured in an interaction graph, which, together with a set of Boolean parameters, gives rise to a state transition graph describing all possible dynamical behaviors. For complex networks the analysis of the dynamics becomes more and more difficult, and efficient methods to carry out the analysis are needed. In this paper, we focus on identifying subnetworks of the system that govern the behavior of the system as a whole. We present methods to derive trajectories and attractors of the network from the dynamics suitable subnetworks display in isolation. In addition, we use these ideas to link the existence of certain structural motifs, namely circuits, in the interaction graph to the character and number of attractors in the state transition graph, generalizing and refining results presented in [10]. Lastly, we show for a specific class of networks that all possible asymptotic behaviors of networks in that class can be derived from the dynamics of easily identifiable subnetworks.