Training neural networks with noisy data as an ill-posed problem

This paper is devoted to the analysis of network approximation in the framework of approximation and regularization theory. It is shown that training neural networks and similar network approximation techniques are equivalent to least-squares collocation for a corresponding integral equation with mollified data.Results about convergence and convergence rates for exact data are derived based upon well-known convergence results about least-squares collocation. Finally, the stability properties with respect to errors in the data are examined and stability bounds are obtained, which yield rules for the choice of the number of network elements.     

Path delays in communication networks

A communication network is modelled by a weighted graph. The vertices of the graph represent stations with storage capabilities, while the edges of the graph represent communication channels (or other information processing media). Channel capacity weights are assigned to the edges of the network. The network is assumed to operate in a store-and-forward manner, so that when a channel is busy the messages directed into it are stored at the station, joining there a queue which is governed by a first-come first-served service discipline. Assuming messages, with fixed length, to arrive at random at the network, following the statistics of a Poisson point process, we calculate the statistical characteristics of the message time-delays along a path in a communication network. We solve for the steadystate distributions of the message waiting-times along the path, for the distribution of the overall message delay-time, for the average memory size requirements at the stations, as well as for other statistical characteristics of the message flow and the queueing processes along a communication path.     

Tracking consensus of nonlinear MASs with asymmetric communication delays in noisy environments

This paper investigates the tracking consensus problem of nonlinear multi-agent systems (MASs) with asymmetric time-varying communication delays in noisy environments under the conditions of fixed and switching directed topologies. A novel stochastic analysis approach is proposed, which guarantees that the designed two distributed tracking protocols can guide the controlled systems to achieve tracking consensus in the sense of mean square. In order to further reveal the influence of asymmetric communication delays on the tracking consensus ability for MASs, some new delay-dependent sufficient conditions for mean-square consensus are also developed. A simple example is finally given to illustrate the effectiveness of the proposed theoretical results.     

Coding and control for communication networks

The purpose of this paper is to survey techniques for constructing effective policies for controlling complex networks, and to extend these techniques to capture special features of wireless communication networks under different networking scenarios. Among the key questions addressed are:

1. The relationship between static network equilibria, and dynamic network control.
2. The effect of coding on control and delay through rate regions.
3. Routing, scheduling, and admission control.

Through several examples, ranging from multiple-access systems to network coded multicast, we demonstrate that the rate region for a coded communication network may be approximated by a simple polyhedral subset of a Euclidean space. The polyhedral structure of the rate region, determined by the coding, enables a powerful workload relaxation method that is used for addressing complexity—the relaxation technique provides approximations of a highly complex network by a far simpler one. These approximations are the basis of a specific formulation of an h-MaxWeight policy for network routing. Simulations show a 50% improvement in average delay performance as compared to methods used in current practice.     

Jamming communication networks under complete uncertainty

This paper describes a problem of interdicting/jamming wireless communication networks in uncertain environments. Jamming communication networks is an important problem with many applications, but has received relatively little attention in the literature. Most of the work on network interdiction is focused on preventing jamming and analyzing network vulnerabilities. Here, we consider the case where there is no information about the network to be jammed. Thus, the problem is reduced to jamming all points in the area of interest. The optimal solution will determine the locations of the minimum number of jamming devices required to suppress the network. We consider a subproblem which places jamming devices on the nodes of a uniform grid over the area of interest. The objective here is to determine the maximum grid step size. We derive upper and lower bounds for this problem and provide a convergence result. Further, we prove that due to the cumulative effect of the jamming devices, the proposed method produces better solutions than the classical technique of covering the region with uniform circles.     

The Delay-Capacity product for store-and-forward communication networks: Tree networks

A store-and-forward communication network under a maximal message delay criterion is considered. It is shown that the overall channel capacityC and the associated minimal maximal delayγ, as well as the maximal delayγ and the associated minimal overall capacityC, are characterized by a unique Delay-Capacity (γC) product number. The latter is related to a Delay-Capacity product (γC)⁺ number, uniquely determined solely by the topological structure of the communication network. Basic characteristics of the optimal delay and capacity assignment, a useful algoritm for the calculation of (γC)⁺ and simple upper and lower bounds on (γC)⁺, are derived for store-and-forward tree networks. Synthesis considerations and applications to hierarchical communication networks are noted.     

Topological design of wide area communication networks

This paper develops a model for designing a backbone network. It assumes the location of the backbone nodes, the traffic between the backbone nodes and the link capacities are given. It determines the links to be included in the design and the routes used by the origin destination pairs. The objective is to obtain the least cost design where the system costs consist of connection costs and queueing costs. The connection costs depend on link capacity and queueing costs are incurred by users due to the limited capacity of links. The Lagrangian relaxation embedded in a subgradient optimization procedure is used to obtain lower bounds on the optimal solution of the problem. A heuristic based on the Lagrangian relaxation is developed to generate feasible solutions.     

Efficient and fair routing for mesh networks

Inspired by the One Laptop Per Child project, we consider mesh networks that connect devices that cannot recharge their batteries easily. We study how the mesh should retransmit information to make use of the energy stored in each of the nodes effectively. The solution that minimizes the total energy spent by the whole network may be very unfair to some nodes because they bear a disproportionate burden of the traffic. A Nash equilibrium—achieved when nodes minimize the energy they spend—does not model the situation well because, as retransmissions consume battery without increasing the node’s utility, it predicts that nodes refuse to participate. Actually, there are wireless communication protocols, peer-to-peer networks and other systems that provide incentives or impose penalties to encourage nodes to be active and to participate. We explicitly aim at the solution that minimizes the total energy spent by nodes among those that satisfy a fairness constraint. Although this does not guarantee that the solution is at equilibrium, nodes do not have a big incentive to deviate from the proposed solution since they do not view the situation as extremely unfair to them. This is consistent with the recommendation of Beccaria and Bolelli (Proceedings of the 3rd IEEE Vehicle Navigation & Information Systems Conference, pp. 117–126, Oslo, 1992) who proposed to optimize social welfare keeping user needs as constraints. We propose a distributed and online routing algorithm and compare it to an offline, centralized approach. The centralized approach, besides being unrealistic in terms of information requirements, is also NP-hard to solve. For both reasons, we focus on the former and evaluate it by conducting an extensive set of computational experiments that evaluate the efficiency and fairness achieved by our algorithm.     

Efficient identification of independence networks using mutual information

Conditional independence graphs are now widely applied in science and industry to display interactions between large numbers of variables. However, the computational load of structure identification grows with the number of nodes in the network and the sample size. A tailored version of the PC algorithm is proposed which is based on mutual information tests with a specified testing order, combined with false negative reduction and false positive control. It is found to be competitive with current structure identification methodologies for both estimation accuracy and computational speed and outperforms these in large scale scenarios. The methodology is also shown to approximate dense networks. The comparisons are made on standard benchmarking data sets and an anonymized large scale real life example.     

Routing optimization in packet switching communication networks

For routing assignments a special model and an optimization algorithm are proposed. The efficiency of the routing assignments is evaluated by the average value of the total cost of delays for all packets in the network. It is the objective function. The main idea is that traffic, which is transmitted from the source node to the destination node, can be split between two or more logical paths. The minimum of the objective function can be found by varying the traffic on every path and simultaneously from all the source nodes to the destination nodes. If this approach is applied, then the objective function is nonseparable and nonlinear. Because its shape is unknown in advance, an adaptive nonlinear optimization algorithm is proposed. For evaluating its efficiency a special set of test functions has been used.     

Set to set broadcasting in communication networks

Suppose G = (V,E) is a graph whose vertices represent people and edges represent telephone lines between pairs of people. Each person knows a unique message and is ignorant of the messages of other people at the beginning. These messages are then spread by telephone calls. In each call, two people exchange all information they have so far in exactly one unit of time. Suppose A and B are two nonempty subsets of V. The main purpose of this paper is to study the minimum number b(A,B,G) of telephone calls by which A broadcasts to B; and the minimum time t(A,B,G) such that A broadcasts to B. In particular, we give an exact formula for b(A,B,K_n) and linear-time algorithms for computing b(A,B,T) and t(A,B,T) of a tree T.     

Optimal and suboptimal capacity allocation in communication networks

Gomory and Hu (Ref. 1) formulated the optimal allocation of capacities to the links of a communication networks as a problem in linear programming. The application of this formulation to the solution of problems of realistic size does, however, require an excessive amount of computation. In the present paper, a slightly different formulation is given. The resulting optimality conditions readily lend themselves to the construction of problems with known optimal solutions, thereby providing suitable examples for the assessment of the efficiencies of approximate methods. An approximate method that has been found highly efficient in many cases is illustrated by an example.     

Endogenous effort in communication networks under strategic complementarity

This article examines individual incentives to produce information on communication networks. In our setting, efforts are strategic complements along communication paths with convex decay. We analyze the relationship between efforts and centrality on a set of networks which are unambiguous in terms of ordinal centrality. We first show that in both dominant and dominated equilibria central agents exert more effort. Second, we explore the issue of social coordination induced by our game.     

On routing in VLSI design and communication networks

In this paper, we study the global routing problem in VLSI design and the multicast routing problem in communication networks. First we propose new and realistic models for both problems. In the global routing problem in VLSI design, we are given a lattice graph and subsets of the vertex set. The goal is to generate trees spanning these vertices in the subsets to minimize a linear combination of overall wirelength (edge length) and the number of bends of trees with respect to edge capacity constraints. In the multicast routing problem in communication networks, a graph is given to represent the network, together with subsets of the vertex set. We are required to find trees to span the given subsets and the overall edge length is minimized with respect to capacity constraints. Both problems are APX-hard. We present the integer linear programming (LP) formulation of both problems and solve the LP relaxations by the fast approximation algorithms for min-max resource-sharing problems in [K. Jansen, H. Zhang, Approximation algorithms for general packing problems and their application to the multicast congestion problem, Math. Programming, to appear, doi:10.1007/s10107-007-0106-8] (which is a generalization of the approximation algorithm proposed by Grigoriadis and Khachiyan [Coordination complexity of parallel price-directive decomposition, Math. Oper. Res. 2 (1996) 321-340]). For the global routing problem, we investigate the particular property of lattice graphs and propose a combinatorial technique to overcome the hardness due to the bend-dependent vertex cost. Finally, we develop asymptotic approximation algorithms for both problems with ratios depending on the best known approximation ratio for the minimum Steiner tree problem. They are the first known theoretical approximation bound results for the problems of minimizing the total costs (including both the edge and the bend costs) while spanning all given subsets of vertices.     

Chaotic synchronization of nearest-neighbor diffusive coupling Hindmarsh–Rose neural networks in noisy environments

The chaotic synchronization of Hindmarsh–Rose neural networks linked by a nonlinear coupling function is discussed. The HR neural networks with nearest-neighbor diffusive coupling form are treated as numerical examples. By the construction of a special nonlinear-coupled term, the chaotic system is coupled symmetrically. For three and four neurons network, a certain region of coupling strength corresponding to full synchronization is given, and the effect of network structure and noise position are analyzed. For five and more neurons network, the full synchronization is very difficult to realize. All the results have been proved by the calculation of the maximum conditional Lyapunov exponent.     

Planning for optimal expansion of leased line communication networks

We report a new heuristic algorithm useful for developing least-cost expansion plans for leased telecommunications networks in which there is a hierarchy of possible transmission facilities. The problem combines network topology design and capacity expansion problems. Implemented on a PC, the algorithm has successfully developed topology growth plans for twenty periods on networks with up to 31 nodes.     

A self-tuning heuristic for the design of communication networks

This paper addresses the design of communication networks that has a large application area. The problem is to design a minimum cost network subject to a given reliability level. Complexity of the problem is twofold: (1) finding a minimum-cost network topology that every pair of nodes can communicate with each other and (2) computing overall reliability to provide the reliability constraint. Over the last two decades, metaheuristic algorithms have been widely applied to solve this problem due to its NP-hardness. In this study, a self-tuning heuristic (STH), which is a new approach free from parameter tuning, is applied to the design of communication networks. Extensive computational results confirm that STH generates superior solutions to the problem in comparison to some well-known local search metaheuristics, and also more sophisticated metaheuristics proposed in the literature. The practical advantage of STH lies in both its effectiveness and simplicity in application to the design problem.     

Upper bounds for the forwarding indices of communication networks

The decision version of the forwarding index problem is, given a connected graph G and an integer ξ, to find a way of connecting each ordered pair of vertices by a path so that every vertex is an internal point of at most such paths. The optimization version of the problem is to find the smallest ξ for which a routing of this kind exists. Such a problem arises in the design of communication networks and distributed architectures. A model of parallel computation is represented by a network of processors, or machines processing and forwarding (synchronous) messages to each other, subject to physical constraints bearing on either the number of messages that can be processed by a single machine or the number of messages that can be sent through a connection. It was in this context that the problem was first introduced by Chung et al. (IEEE Trans. Inform. Theory 33 (1987) 224). The aim of this paper is to establish upper bounds for the optimal ξ as a function of the connectivity of the graph.     

The structure of branched transportation networks

The transportation problem can be formalized as the problem of finding the optimal paths to transport a measure μ ⁺ onto a measure μ ⁻ with the same mass. In contrast with the Monge–Kantorovich formalization, recent approaches model the branched structure of such supply networks by an energy functional whose essential feature is to favor wide roads. Given a flow s in a road or a tube or a wire, the transportation cost per unit length is supposed to be proportional to s ^α with 0 < α < 1. For the Monge–Kantorovich energy α = 1 so that it is equivalent to have two roads with flow 1/2 or a larger one with flow 1. If instead 0 < α < 1, a road with flow is preferable to two individual roads s ₁ and s ₂ because . Thus, this very simple model intuitively leads to branched transportation structures. Such a branched structure is observable in ground transportation networks, in draining and irrigation systems, in electric power supply systems and in natural objects like the blood vessels or the trees. When such structures can irrigate a whole bounded open set of . The aim of this paper is to give a mathematical proof of several structure and regularity properties empirically observed in transportation networks. It is first proven that optimal transportation networks have a tree structure and can be monotonically approximated by finite graphs. An interior regularity result is then proven according to which an optimal network is a finite graph away from the irrigated measure. It is also proven that the branching number of optimal networks has everywhere a universal explicit bound. These results answer questions raised in two recent papers by Xia.