Rare event probabilities in stochastic networks

The paper is dealing with estimation of rare event probabilities in stochastic networks. The well known variance reduction technique, called Importance Sampling (IS) is an effective tool for doing this. The main idea of IS is to simulate the random system under a modified set of parameters, so as to make the occurrence of the rare event more likely. The major problem of the IS technique is that the optimal modified parameters, called reference parameters to be used in IS are usually very difficult to obtain. Rubinstein (Eur J Oper Res 99:89–112, 1997) developed the Cross Entropy (CE) method for the solution of this problem of IS technique and then he and his collaborators applied this for estimation of rare event probabilities in stochastic networks with exponential distribution [see De Boer et al. (Ann Oper Res 134:19–67, 2005)]. In this paper, we test this simulation technique also for medium sized stochastic networks and compare its effectiveness to the simple crude Monte Carlo (CMC) simulation. The effectiveness of a variance reduction simulation algorithm is measured in the following way. We calculate the product of the necessary CPU time and the estimated variance of the estimation. This product is compared to the same for the simple Crude Monte Carlo simulation. This was originally used for comparison of different variance reduction techniques by Hammersley and Handscomb (Monte Carlo Methods. Methuen & Co Ltd, London, 1967). The main result of the paper is the extension of CE method for estimation of rare event probabilities in stochastic networks with beta distributions. In this case the calculation of reference parameters of the importance sampling distribution requires numerical solution of a nonlinear equation system. This is done by applying a Newton–Raphson iteration scheme. In this case the CPU time spent for calculation of the reference parameter values cannot be neglected. Numerical results will also be presented. This work was supported by grant from the Hungarian National Scientific Research Grant OTKA T047340.     

Linear time-periodic dynamical systems: an H2 analysis and a model reduction framework

Linear time-periodic (LTP) dynamical systems frequently appear in the modelling of phenomena related to fluid dynamics, electronic circuits and structural mechanics via linearization centred around known periodic orbits of nonlinear models. Such LTP systems can reach orders that make repeated simulation or other necessary analysis prohibitive, motivating the need for model reduction. We develop here an algorithmic framework for constructing reduced models that retains the LTP structure of the original LTP system. Our approach generalizes optimal approaches that have been established previously for linear time-invariant (LTI) model reduction problems. We employ an extension of the usual H₂ Hardy space defined for the LTI setting to time-periodic systems and within this broader framework develop an a posteriori error bound expressible in terms of related LTI systems. Optimization of this bound motivates our algorithm. We illustrate the success of our method on three numerical examples.     

Dominating sets in social network graphs

This paper presents an approach to the study of the structure of social networks using dominating sets of graphs. A method is presented for partitioning the vertices of a graph using dominating vertices. For certain classes of graphs this is helpful in determining the underlying structure of the corresponding social network. An extension of this technique provides a method of studying the structure of directed graphs and directed social networks. Minimum dominating sets are related to statuses and structurally equivalent sets.     

Approximating Networks and Extended Ritz Method for the Solution of Functional Optimization Problems

Functional optimization problems can be solved analytically only if special assumptions are verified; otherwise, approximations are needed. The approximate method that we propose is based on two steps. First, the decision functions are constrained to take on the structure of linear combinations of basis functions containing free parameters to be optimized (hence, this step can be considered as an extension to the Ritz method, for which fixed basis functions are used). Then, the functional optimization problem can be approximated by nonlinear programming problems. Linear combinations of basis functions are called approximating networks when they benefit from suitable density properties. We term such networks nonlinear (linear) approximating networks if their basis functions contain (do not contain) free parameters. For certain classes of d-variable functions to be approximated, nonlinear approximating networks may require a number of parameters increasing moderately with d, whereas linear approximating networks may be ruled out by the curse of dimensionality. Since the cost functions of the resulting nonlinear programming problems include complex averaging operations, we minimize such functions by stochastic approximation algorithms. As important special cases, we consider stochastic optimal control and estimation problems. Numerical examples show the effectiveness of the method in solving optimization problems stated in high-dimensional settings, involving for instance several tens of state variables.     

Ein Verfahren zur Optimierung von Nachrichtenübertragungsnetzen mit Mehrwegeführung

Within the framework of long-term planning of telecommunication transmission networks, an economic solution has to be calculated for the future network structure. In this structure, the cost of routing the circuits required between the exchanges must be optimized. For reliability reasons, it is necessary to route over several edge-disjoint paths. The paper describes the importance of long-term planning of telecommunication transmission networks. It is shown that this problem can be formulated by a model with a concave objective function and linear constraints. For this model, an algorithm is developed whose numeric behaviour is described. Practical applications of the procedure are indicated.     

Inducing Measures by Cyclic Networks

Abstract

Measures on cyclic networks are defined in good agreement with basic homologic and measure-theoretic principles. A method to induce measures when the original network is reduced to smaller collections of circuits, is given as well.     

Approximate analysis of load-dependent generally distributed queuing networks with low service time variability

In this paper, we present an approximate method for solution of load-dependent, closed queuing networks having general service time distributions with low variability. The proposed technique is an extension of Marie’s (1980) method. In the methodology, conditional throughputs are obtained by an iterative procedure. The iterations are repeated until an invalid result is detected or no improvements are found. We demonstrate the performance of the technique with 10 different examples. On average, the solutions have 5% or lower deviations when compared to simulation results.     

Ranking hubs and authorities using matrix functions

The notions of subgraph centrality and communicability, based on the exponential of the adjacency matrix of the underlying graph, have been effectively used in the analysis of undirected networks. In this paper we propose an extension of these measures to directed networks, and we apply them to the problem of ranking hubs and authorities. The extension is achieved by bipartization, i.e., the directed network is mapped onto a bipartite undirected network with twice as many nodes in order to obtain a network with a symmetric adjacency matrix. We explicitly determine the exponential of this adjacency matrix in terms of the adjacency matrix of the original, directed network, and we give an interpretation of centrality and communicability in this new context, leading to a technique for ranking hubs and authorities. The matrix exponential method for computing hubs and authorities is compared to the well known HITS algorithm, both on small artificial examples and on more realistic real-world networks. A few other ranking algorithms are also discussed and compared with our technique. The use of Gaussian quadrature rules for calculating hub and authority scores is discussed.     

Impact of Correlated Activity and STDP on Network Structure

Synaptic strengths between neurons are plastic and modified by spontaneous activity and information from the outside. There is increasing interest in the impact of correlated neuron activity and learning rules on global network structure. Here the networks of exponential integrate-and-fire neurons with spike timing-dependent plasticity (STDP) learning rules are considered, by providing the theoretical approximation of spiking cross-covariance between connected neurons and the theory for the evolution of synaptic weights. Background input mean and variance highly affect the spiking covariance, even for the fixed baseline firing rate and connection. Through analyzing the effects of covariance and STDP on vector fields for pairwise correlated neurons under fixed baseline firing rate, we show that the connections from a neuron with lower input mean to that with higher one will strengthen for balanced Hebbian STDP. However, this situation is reversed for Anti-Hebbian cases. Moreover, for potentiation dominated STDP, the synaptic weights for the networks of neurons with lower input mean are more likely to be enhanced. In addition, these properties found from coupled neurons also hold for large recurrent networks in both theories and simulations. This study provides a self-consistent theoretical method for understanding how correlated spiking activity and STDP shape the network structure and an approach for predicting structures of large networks through the analysis of simple neural circuits.     

A note on exponential convergence of neural networks with unbounded distributed delays

This note examines issues concerning global exponential convergence of neural networks with unbounded distributed delays. Sufficient conditions are derived by exploiting exponentially fading memory property of delay kernel functions. The method is based on comparison principle of delay differential equations and does not need the construction of any Lyapunov functionals. It is simple yet effective in deriving less conservative exponential convergence conditions and more detailed componentwise decay estimates. The results of this note and [Chu T. An exponential convergence estimate for analog neural networks with delay. Phys Lett A 2001;283:113–8] suggest a class of neural networks whose globally exponentially convergent dynamics is completely insensitive to a wide range of time delays from arbitrary bounded discrete type to certain unbounded distributed type. This is of practical interest in designing fast and reliable neural circuits. Finally, an open question is raised on the nature of delay kernels for attaining exponential convergence in an unbounded distributed delayed neural network.     

Minimum power multicasting in wireless networks under probabilistic node failures

In this paper we deal with a probabilistic extension of the minimum power multicast (MPM) problem for wireless networks. The deterministic MPM problem consists in assigning transmission powers to the nodes, so that a multihop connection can be established between a source and a given set of destination nodes and the total power required is minimized. We present an extension to the basic problem, where node failure probabilities for the transmission are explicitly considered. This model reflects the necessity of taking uncertainty into account in the availability of the hosts. The novelty of the probabilistic minimum power multicast (PMPM) problem treated in this paper consists in the minimization of the assigned transmission powers, imposing at the same time a global reliability level to the solution network. An integer linear programming formulation for the PMPM problem is presented. Furthermore, an exact algorithm based on an iterative row and column generation procedure, as well as a heuristic method are proposed. Computational experiments are finally presented.     

Stochastic hybrid simulation

This is a summary of the author’s PhD thesis supervised by Bart Scheers and Antoine Van de Capelle and defended on 20 November 2009 at the Royal Military Academy, Brussels. The thesis () is written in English and is available from the author upon request. This work deals with an extension to the hybrid simulation paradigm, i.e. the combination of event-driven simulation and analytical modelling, applied to packet telecommunication networks. In order to speed up the simulation only a small part of all packets, the foreground traffic, is processed in an event-driven way. On each arrival of a foreground packet, the waiting time of the packet is sampled from the virtual waiting time distribution function of the combined foreground and background traffic. This distribution function is stochastically modelled by the exact large deviations asymptotic of the virtual waiting time in a many sources regime. This novel methodology is not only valid for wired point-to-point queueing networks having a fixed transmission capacity, but it can also be applied to queueing networks for which the transmission capacity varies with the traffic load of all the elements in the network. The results obtained by the stochastic hybrid simulator are compared to full-blown event-driven simulations. An important reduction in simulation run-time is gained without sacrificing accuracy.     

Price-directive decomposition applied to routing in telecommunication networks

The telecommunication network design problem is considered to study the level of transmission network. A heuristic approach is defined to solve the combined routing-grouping problem, where the grouping one is solved by a heuristic approach. The routing problem is defined considering reliability constraints, supplementary circuits demands and a piecewise linear objective function to take into account the influence of the grouping. This last model is solved using a price-directive decomposition method, which has allowed us to solve real networks using an exact method.     

Global exponential stability and periodicity of reaction–diffusion recurrent neural networks with distributed delays and Dirichlet boundary conditions

In this paper, global exponential stability and periodicity of a class of reaction–diffusion recurrent neural networks with distributed delays and Dirichlet boundary conditions are studied by constructing suitable Lyapunov functionals and utilizing some inequality techniques. We first prove global exponential convergence to 0 of the difference between any two solutions of the original neural networks, the existence and uniqueness of equilibrium is the direct results of this procedure. This approach is different from the usually used one where the existence, uniqueness of equilibrium and stability are proved in two separate steps. Secondly, we prove periodicity. Sufficient conditions ensuring the existence, uniqueness, and global exponential stability of the equilibrium and periodic solution are given. These conditions are easy to verify and our results play an important role in the design and application of globally exponentially stable neural circuits and periodic oscillatory neural circuits.     

Farey sequences and resistor networks

In this article, we employ the Farey sequence and Fibonacci numbers to establish strict upper and lower bounds for the order of the set of equivalent resistances for a circuit constructed from n equal resistors combined in series and in parallel. The method is applicable for networks involving bridge and non-planar circuits.     

Four correlates of complex behavioral networks: Differentiation,behavior, connectivity,and compartmentalization: Carving networks at their joints

Some of the most complex networks are those that (i) have been engineered under selective pressure (either economic or evolutionary), and (ii) are capable of eliciting network‐level behaviors. Some examples are nervous systems, ant colonies, electronic circuits and computer software. Here we provide evidence that many such selected, behavioral networks are similar in at least four respects. (1) Differentiation: Nodes of different types are used in a combinatorial fashion to build network structures through local connections, and networks accommodate more structure types via increasing the number of node types in the network (i.e., increasing differentiation), not via increasing the length of structures. (2) Behavior: Structures are themselves combined globally to implement behaviors, and networks accommodate a greater behavioral repertoire via increasing the number of lower‐level behavior types (including structures), not via increasing the length of behaviors. (3) Connectivity: In order for structures in behavioral networks to combine with other structures within a fixed behavior length, the network must maintain an invariant network diameter, and this is accomplished via increasing network connectivity in larger networks. (4) Compartmentalization: Finally, for reasons of economical wiring, behavioral networks become increasingly parcellated. Special attention is given to nervous systems and computer software, but data from a variety of other behavioral selected networks are also provided, including ant colonies, electronic circuits, web sites and businesses. A general framework is introduced illuminating why behavioral selected networks share these four correlates. Because the four above features appear to apply to computer software as well as to biological networks, computer software provides a useful framework for comprehending the large‐scale function and organization of biological networks. © 2005 Wiley Periodicals, Inc. Complexity 10: 13–40, 2005     

Computational algorithms for hierarchically structured project networks

A new approach to large size network management based on a structured network representation is proposed. Definitions of arc-structured and vertex-structured networks are given and an extension of topological sorting and time computation algorithms is described. A generalization of the concept of vertex-structured networks is discussed.     

Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks

In real road networks, the presence of no-left, no-right or no U-turn signs, restricts the movement of vehicles at intersections. These turn prohibitions must be considered when calculating the shortest path between a starting and an ending point in a road network. We propose an extension of Dijkstra’s algorithm to solve the shortest path problem with turn prohibitions. The method uses arc labeling and a network structure with low memory requirements. We compare the proposed method with the dual graph approach in a set of randomly generated networks and Bogotá’s large-scale road network. Our computational experiments show that the performance of the proposed method is better than that of the dual graph approach, both in terms of computing time and memory requirements. We co-developed a Web-based decision support system for computing shortest paths with turn prohibitions that uses the proposed method as the core engine.