On computation of the steady-state probability distribution of probabilistic Boolean networks with gene perturbation

Given a Probabilistic Boolean Network (PBN), an important problem is to study its steady-state probability distribution for network analysis. In this paper, we present a new perturbation bound of the steady-state probability distribution of PBNs with gene perturbation. The main contribution of our results is that this new bound is established without additional condition required by the existing method. The other contribution of this paper is to propose a fast algorithm based on the special structure of a transition probability matrix of PBNs with gene perturbation to compute its steady-state probability distribution. Experimental results are given to demonstrate the effectiveness of the new bound, and the efficiency of the proposed method.     

Stability of stationary solutions of piecewise affine differential equations describing gene regulatory networks

We study stability properties of a class of piecewise affine systems of ordinary differential equations arising in the modeling of gene regulatory networks. Our method goes back to the concept of a Filippov stationary solution (in the narrow sense) to a differential inclusion corresponding to the system in question. The main result of the paper justifies a reduction principle in the stability analysis enabling to omit the variables that are not singular, i.e. that stay away from the discontinuity set of the system. We suggest also “the first approximation method” to study asymptotic stability of stationary solutions based on calculating the principal part of the system, which is 0-homogeneous rather than linear. This leads to an efficient algorithm of how to check asymptotic stability without calculating the eigenvalues of the system?s Jacobian. In Appendix A we discuss and compare two other concepts of stationary solutions to the system in question.     

A preferential attachment model with Poisson growth for scale-free networks

We propose a scale-free network model with a tunable power-law exponent. The Poisson growth model, as we call it, is an offshoot of the celebrated model of Barabási and Albert where a network is generated iteratively from a small seed network; at each step a node is added together with a number of incident edges preferentially attached to nodes already in the network. A key feature of our model is that the number of edges added at each step is a random variable with Poisson distribution, and, unlike the Barabási–Albert model where this quantity is fixed, it can generate any network. Our model is motivated by an application in Bayesian inference implemented as Markov chain Monte Carlo to estimate a network; for this purpose, we also give a formula for the probability of a network under our model.     

Graphic requirements for multistability and attractive cycles in a Boolean dynamical framework

To each Boolean function and each x{0,1}ⁿ, we associate a signed directed graph G(x), and we show that the existence of a positive circuit in G(x) for some x is a necessary condition for the existence of several fixed points in the dynamics (the sign of a circuit being defined as the product of the signs of its edges), and that the existence of a negative circuit is a necessary condition for the existence of an attractive cycle. These two results are inspired by rules for discrete models of genetic regulatory networks proposed by the biologist R. Thomas. The proof of the first result is modelled after a recent proof of the discrete Jacobian conjecture.     

Modeling gene regulatory networks with piecewise linear differential equations

Microarray chips generate large amounts of data about a cell’s state. In our work we want to analyze these data in order to describe the regulation processes within a cell. Therefore, we build a model which is capable of capturing the most relevant regulating interactions and present an approach how to calculate the parameters for the model from time-series data. This approach uses the discrete approximation method of least squares to solve a data fitting modeling problem. Furthermore, we analyze the features of our proposed system, i.e., which kinds of dynamical behaviors the system is able to show.     

Control parameters in Boolean networks and cellular automata revisited from a logical and a sociological point of view

The use of “control parameters” as applied to describe the dynamics of complex mathematical systems within models of real social systems is discussed. Whereas single control parameters cannot sufficiently characterize the dynamics of such systems it is suggested that domains of values of certain sets of parameters are appropriately denoting necessary conditions for highly disordered dynamics of social systems. Various of those control parameters permit a straightforward interpretation in terms of properties of social rules and structures. © 1999 John Wiley & Sons, Inc.     

Communicability graph and community structures in complex networks

We use the concept of the network communicability [E. Estrada, N. Hatano, Communicability in complex networks, Phys. Rev. E 77 (2008) 036111] to define communities in a complex network. The communities are defined as the cliques of a “communicability graph”, which has the same set of nodes as the complex network and links determined by the communicability function. Then, the problem of finding the network communities is transformed to an all-clique problem of the communicability graph. We discuss the efficiency of this algorithm of community detection. In addition, we extend here the concept of the communicability to account for the strength of the interactions between the nodes by using the concept of inverse temperature of the network. Finally, we develop an algorithm to manage the different degrees of overlapping between the communities in a complex network. We then analyze the USA airport network, for which we successfully detect two big communities of the eastern airports and of the western/central airports as well as two bridging central communities. In striking contrast, a well-known algorithm groups all but two of the continental airports into one community.     

A fast and efficient algorithm to identify clusters in networks

A characteristic feature of many relevant real life networks, like the WWW, Internet, transportation and communication networks, or even biological and social networks, is their clustering structure. We discuss in this paper a novel algorithm to identify cluster sets of densely interconnected nodes in a network. The algorithm is based on local information and therefore it is very fast with respect other proposed methods, while it keeps a similar performance in detecting the clusters.     

A cooperative differential game model based on transmission rate in wireless networks

Network throughput and energy efficiency are paramount for network performance in an energy-constrained wireless network. However, it is difficult to achieve optimal objectives simultaneously. Therefore, it is necessary to find a rate control solution based on tradeoff between network throughput and energy efficiency. In this paper, we propose a cooperative differential game model and find an optimal rate control of each player to get the total minimal cost with tradeoff between network throughput and energy efficiency of the networks.     

Estimating the sojourn time sensitivity in queueing networks using perturbation analysis

The sample path perturbation analysis technique developed earlier for the analysis of throughput sensitivities (Refs. 1–3) is extended to the performance measures involving mean sojourn times of customers. The major features of the sojourn time sensitivity problem are twofold. Firstly, it is a performance associated with servers, and not with customers. Secondly, the average sojourn time in any finite observation period can be a discontinuous function of mean service times when blocking is involved in a system. This discontinuity causes errors which must be accounted for in the estimation of sensitivities. Numerical experiments and analysis validate this method of computation of the sensitivities.This work was supported by the US Office of Naval Research, Contracts N00014-84-K-0465 and N00014-79-C-0776, and by the National Science Foundation, Grant No. ENG-78-15231.     

Existence of solution to a model for gas transportation networks on non-flat topography

In this paper we prove the existence of solution to a mathematical model for gas transportation networks on non-flat topography. Firstly, the network topology is represented by a directed graph and then a nonlinear system of numerical equations is introduced whose unknowns are the pressures at the nodes and the mass flow rates at the edges of the graph. This system is written in a compact vector form in terms of the vector of the square pressures at the nodes and then an existence result is proved under some simplifying assumptions. The proof is done in two steps: the first one uses convex analysis tools and the second one the Brouwer fixed-point theorem.     

A model to simplify 2D triangle meshes with irregular shapes

We present a 2D triangle mesh simplification model which is able to produce high quality approximations of any original planar mesh, regardless of the shape of the original mesh. This method consists of two phases: a self-organizing algorithm and a triangulation algorithm. The self-organizing algorithm is an unsupervised incremental clustering algorithm which provides us a set of nodes representing the best approximation of the original mesh. The triangulation algorithm reconstructs the simplified mesh from the planar points obtained by the self-organizing training process. Some examples are detailed with the purpose of demonstrating the ability of the model to perform the task of simplifying an original mesh with irregular shape.     

The differential perturbative method applied to the sensitivity analysis for waterhammer problems in hydraulic networks

The differential perturbative method was applied to the sensitivity analysis for waterhammer problems in hydraulic networks. Starting from the classical waterhammer equations in a single-phase liquid with friction (the direct problem) the state vector comprising the piezometric head and the velocity was defined. Applying the differential method the adjoint operator, the adjoint equations with the general form of their boundary conditions, and the general form of the bilinear concomitant were calculated for a single pipe. Considering that any hydraulic network can be built by connecting different components (reservoirs, valves, pumps, tees, etc.) through pipes, the adjoint relationships for any component, as well as the final contribution to the bilinear concomitant, were calculated. Moreover, an analogy was established in which transmission and reflection coefficients can be derived for any adjoint component. The importance or adjoint function was analyzed when the piezometric head or velocity at a given position and time is chosen as the response functional. In this case, it is shown that the importance function is represented by delta-functions travelling along the hydraulic network with the propagation speed. The calculation of the sensitivity coefficients takes into account the cases in which the parameters under consideration influence the initial condition. For these cases, the calculation can be performed by solving sequentially two perturbative problems: the first one is non-steady, while the second one is steady, with an appropriate selection of a weight function coming from the unsteady perturbative problem. The discretized adjoint equations and the corresponding boundary conditions were programmed and solved by using the method of characteristics. As an example, a constant-level tank connected through a pipe to a valve discharging to atmosphere was considered. The corresponding sensitivity coefficients due to the variation of different parameters by using both the differential method and the response surface generated by the computer code WHAT, solver of the direct problem, were also calculated. The results obtained with these methods show excellent agreement.     

An analytical method for cost analysis in multi-stage supply chains: A stochastic network model approach

This paper studies the cost distribution characteristics in multi-stage supply chain networks. Based on the graphical evaluation and review technique, we propose a novel stochastic network mathematical model for cost distribution analysis in multi-stage supply chain networks. Further, to investigate the effects of cost components, including the procurement costs, inventory costs, shortage costs, production costs and transportation costs of supply chain members, on the total supply chain operation cost, we propose the concept of cost sensitivity and provide corresponding algorithms based on the proposed stochastic network model. Then the model is extended to analyze the cost performance of supply chain robustness under different order compensation ability scenarios and the corresponding algorithms are developed. Simulation experiment shows the effectiveness and flexibility of the proposed model, and also promotes a better understanding of the model approach and its managerial implications in cost management of supply chains.     

A fluid system with coupled input and output,and its application to bottlenecks in ad hoc networks

This paper studies a fluid queue with coupled input and output. Flows arrive according to a Poisson process, and when n flows are present, each of them transmits traffic into the queue at a rate c/(n+1), where the remaining c/(n+1) is used to serve the queue. We assume exponentially distributed flow sizes, so that the queue under consideration can be regarded as a system with Markov fluid input. The rationale behind studying this queue lies in ad hoc networks: bottleneck links have roughly this type of sharing policy. We consider four performance metrics: (i) the stationary workload of the queue, (ii) the queueing delay, i.e., the delay of a ‘packet’ (a fluid particle) that arrives at the queue at an arbitrary point in time, (iii) the flow transfer delay, i.e., the time elapsed between arrival of a flow and the epoch that all its traffic has been put into the queue, and (iv) the sojourn time, i.e., the flow transfer time increased by the time it takes before the last fluid particle of the flow is served. For each of these random variables we compute the Laplace transform. The corresponding tail probabilities decay exponentially, as is shown by a large-deviations analysis. F. Roijers’ work has been carried out partly in the SENTER-NOVEM funded project Easy Wireless.     

Parameter uncertainty, sensitivity analysis and prediction error in a water-balance hydrological model

Analysis of uncertainty is often neglected in the evaluation of complex systems models, such as computational models used in hydrology or ecology. Prediction uncertainty arises from a variety of sources, such as input error, calibration accuracy, parameter sensitivity and parameter uncertainty. In this study, various computational approaches were investigated for analysing the impact of parameter uncertainty on predictions of streamflow for a water-balance hydrological model used in eastern Australia. The parameters and associated equations which had greatest impact on model output were determined by combining differential error analysis and Monte Carlo simulation with stochastic and deterministic sensitivity analysis. This integrated approach aids in the identification of insignificant or redundant parameters and provides support for further simplifications in the mathematical structure underlying the model. Parameter uncertainty was represented by a probability distribution and simulation experiments revealed that the shape (skewness) of the distribution had a significant effect on model output uncertainty. More specifically, increasing negative skewness of the parameter distribution correlated with decreasing width of the model output confidence interval (i.e. resulting in less uncertainty). For skewed distributions, characterisation of uncertainty is more accurate using the confidence interval from the cumulative distribution rather than using variance. The analytic approach also identified the key parameters and the non-linear flux equation most influential in affecting model output uncertainty.