State-dependent Coupling of Quasireversible Nodes

The seminal paper of Jackson began a chain of research on queueing networks with product-form stationary distributions which continues strongly to this day. Hard on the heels of the early results on queueing networks followed a series of papers which discussed the relationship between product-form stationary distributions and the quasireversibility of network nodes. More recently, the definition of quasireversibility and the coupling mechanism between nodes have been extended so that they apply to some of the later product-form queueing networks incorporating negative customers, signals, and batch movements.In parallel with this research, it has been shown that some special queueing networks can have arrival and service parameters which depend upon the network state, rather than just the node state, and still retain a generalised product-form stationary distribution.In this paper we begin by offering an alternative proof of a product-form result of Chao and Miyazawa and then build on this proof by postulating a state-dependent coupling mechanism for a quasireversible network. Our main theorem is that the resultant network has a generalised product form stationary distribution. We conclude the paper with some examples.     

Markov network processes with product form stationary distributions

This study concerns the equilibrium behavior of a general class of Markov network processes that includes a variety of queueing networks and networks with interacting components or populations. The focus is on determining when these processes have product form stationary distributions. The approach is to relate the marginal distributions of the process to the stationary distributions of “node transition functions” that represent the nodes in isolation operating under certain fictitious environments. The main result gives necessary and sufficient conditions on the node transition functions for the network process to have a product form stationary distribution. This result yields a procedure for checking for a product form distribution and obtaining such a distribution when it exits. An important subclass of networks are those in which the node transition rates have Poisson arrival components. In this setting, we show that the network process has a product form distribution and is “biased locally balanced” if and only if the network is “quasi-reversible” and certain traffic equations are satisfied. Another subclass of networks are those with reversible routing. We weaken the known sufficient condition for such networks to be product form. We also discuss modeling issues related to queueing networks including time reversals and reversals of the roles of arrivals and departures. The study ends by describing how the results extend to networks with multi-class transitions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Traffic Flows and Product Form Solutions in Stochastic Transfer Networks

This paper focuses on product form and related tractable stationary distributions in a general class of stochastic networks with finite numbers of nodes such that their network states are changed through signal transfers as well as internal transitions. Signals may be customers in traditional queueing applications, but we do not make any restriction on their effects at departing as well as arriving nodes. They may also instantaneously move around among different nodes. Furthermore, signal routing may depend on the whole network state. For analytical simplicity, we assume that the state space is countable. For such a network, we propose an abstract model, called a stochastic transfer network, and consider the stationary distribution of the network state. We introduce conditional traffic rates for arrivals and departures. Using them, we consider when the network has product form or some other tractable stationary distributions.     

Leverage centrality analysis of infrastructure networks

Leverage centrality is a novel centrality measure proposed to identify the critical nodes that are highly influential within the network. Leverage centrality considers the extent of connectivity of a node relative to the connectivity of its neighbors. The leverage centrality of a node in a network is determined by the extent to which its direct neighbors rely on that node for information. In this paper, leverage centralities of the nodes of infrastructure networks are computed and critical nodes within the network are identified.     

Wireless random-access networks with bipartite interference graphs

We consider random-access networks where nodes represent servers with a queue and can be either active or inactive. A node deactivates at unit rate, while it activates at a rate that depends on its queue length, provided none of its neighbors is active. We consider arbitrary bipartite graphs in the limit as the initial queue lengths become large and identify the transition time between the two states where one half of the network is active and the other half is inactive. The transition path is decomposed into a succession of transitions on complete bipartite subgraphs. We formulate a randomized greedy algorithm that takes the graph as input and gives as output the set of transition paths the network is most likely to follow. Along each path we determine the mean transition time and its law on the scale of its mean. Depending on the activation rates, we identify three regimes of behavior.     

Viral conductance: Quantifying the robustness of networks with respect to spread of epidemics

In this paper, we propose a novel measure, viral conductance (VC), to assess the robustness of complex networks with respect to the spread of SIS epidemics. In contrast to classical measures that assess the robustness of networks based on the epidemic threshold above which an epidemic takes place, the new measure incorporates the fraction of infected nodes at steady state for all possible effective infection strengths. Through examples, we show that VC provides more insight about the robustness of networks than does the epidemic threshold. We also address the paradoxical robustness of Barabási–Albert preferential attachment networks. Even though this class of networks is characterized by a vanishing epidemic threshold, the epidemic requires high effective infection strength to cause a major outbreak. On the contrary, in homogeneous networks the effective infection strength does not need to be very much beyond the epidemic threshold to cause a major outbreak. To overcome computational complexities, we propose a heuristic to compute the VC for large networks with high accuracy. Simulations show that the heuristic gives an accurate approximation of the exact value of the VC. Moreover, we derive upper and lower bounds of the new measure. We also apply the new measure to assess the robustness of different types of network structures, i.e. Watts–Strogatz small world, Barabási–Albert, correlated preferential attachment, Internet AS-level, and social networks. The extensive simulations show that in Watts–Strogatz small world networks, the increase in probability of rewiring decreases the robustness of networks. Additionally, VC confirms that the irregularity in node degrees decreases the robustness of the network. Furthermore, the new measure reveals insights about design and mitigation strategies of infrastructure and social networks.     

Stable network topologies using the notion of covering

An alternative perspective to evaluate networks and network evolution is introduced, based on the notion of covering. For a particular node in a network covering captures the idea of being outperformed by another node in terms of, for example, visibility and possibility of information gathering. In this paper, we focus on networks where these subdued network positions do not exist. We call these networks stable. Within this set we identify the minimal stable networks, which frequently have a ‘bubble-like’ structure. Severing a link in such a network results in at least one of the nodes being covered. In a minimal stable network therefore all nodes cooperate to avoid that one of the nodes ends up in a subdued position. Our results can be applied to, for example, the design of (covert) communication networks and the dynamics of social and information networks.     

Application of modal analysis in assessing attack vulnerability of complex networks

In this paper we propose an alternative way to study robustness and vulnerability of complex networks, applying a modal analysis. The modal weights of the network nodes are considered as a measure for their busyness, which is further used for preferential removal of nodes and attack simulation. Analyses of the attack vulnerability are carried out for several generic graphs, generated according to ER and BA algorithms, as well as for some examples of manmade networks. It was found that a modal weight based attack causes significant disintegration of manmade networks by removing a small fraction of the busiest nodes, comparable to the one based on the node degree and betweenness centrality.     

An analysis of the topological properties of the interlaced bypass torus (iBT) networks

We analyze a new class of interconnection networks that are constructed by interlacing bypass rings to the torus network (iBT network). We establish the minimum conditions a bypass scheme needs to satisfy for generating a qualified iBT network and then we develop a recursive algorithm to calculate all of the qualified bypass schemes for a given network size and node degree. Our algorithm enables us to discover a class of the most efficient networks with up to 1 million nodes when considering the diameters of various iBT networks as a function of the bypass schemes. These analyses help achieve maximal performance improvement by the best bypass schemes.     

Modeling centrality measures in social network analysis using bi-criteria network flow optimization problems

Centrality measures play an important role in the field of network analysis. In the particular case of social networks, the flow represents the way in which information passes through the network nodes. Freeman et al. (1991) were the first authors to relate centrality measures to network flow optimization problems in terms of betweenness, closeness, and the influence of one node over another one. Such measures are single dimensional and, in general, they amalgamate several heterogeneous dimensions into a single one, which is not suitable for dealing with most real-world problems. In this paper we extend the betweenness centrality measure (or concept) to take into account explicitly several dimensions (criteria). A new closeness centrality measure is defined to deal not only with the maximum flow between every ordered pair of nodes, but also with the cost associated with communications. We shall show how the classical measures can be enhanced when the problem is modeled as a bi-criteria network flow optimization problem.     

Percolation of interdependent network of networks

Complex networks appear in almost every aspect of science and technology. Previous work in network theory has focused primarily on analyzing single networks that do not interact with other networks, despite the fact that many real-world networks interact with and depend on each other. Very recently an analytical framework for studying the percolation properties of interacting networks has been introduced. Here we review the analytical framework and the results for percolation laws for a Network Of Networks (NONs) formed by n interdependent random networks. The percolation properties of a network of networks differ greatly from those of single isolated networks. In particular, because the constituent networks of a NON are connected by node dependencies, a NON is subject to cascading failure. When there is strong interdependent coupling between networks, the percolation transition is discontinuous (first-order) phase transition, unlike the well-known continuous second-order transition in single isolated networks. Moreover, although networks with broader degree distributions, e.g., scale-free networks, are more robust when analyzed as single networks, they become more vulnerable in a NON. We also review the effect of space embedding on network vulnerability. It is shown that for spatially embedded networks any finite fraction of dependency nodes will lead to abrupt transition.     

一类输出耦合混沌复杂动态网络不稳定平衡点的控制

研究节点输出耦合混沌复杂动态网络不稳定平衡点的控制问题,基于输出控制思想,提出网络节点不稳定平衡点的全局控制方法以及牵制控制方法,将混沌复杂动态网络的所有节点镇定到其平衡点.利用李稚普诺夫稳定性理论,得到控制器参数选择条件,以蔡氏混沌电路作为网络节点动态进行仿真研究,证明该方法的有效性.     

A unified network performance measure with importance identification and the ranking of network components

In this paper, we propose the first network performance measure that can be used to assess the efficiency of a network in the case of either fixed or elastic demands. Such a measure is needed for many different applications since only when the performance of a network can be quantifiably measured can the network be appropriately managed. Moreover, as we demonstrate, the proposed performance measure, which captures flow information and behavior, allows one to determine the criticality of various nodes (as well as links) through the identification of their importance and ranking. We present specific networks for which the performance/efficiency is computed along with the importance rankings of the nodes and links. The new measure can be applied to transportation networks, supply chains, financial networks, electric power generation and distribution networks as well as to the Internet and can be used to assess the vulnerability of a network to disruptions.     

Individual customer’s behaviour in networks with state-dependent arrival rates

We consider Jackson networks with state-dependent arrival and service rates which show product form or nearly product form steady-states and come up with examples of load-dependent admission control. For these networks we prove an arrival theorem for external as well as for internal arrivals. In case of open tandem systems with state-independent service rates we compute the joint distribution of the sojourn times of a customer in the nodes and the distribution of the customer’s end-to-end-delay. This revised version was published online in June 2006 with corrections to the Cover Date.     

Architectures,stability and optimization for clock distribution networks

Synchronous telecommunication networks, distributed control systems and integrated circuits have its accuracy of operation dependent on the existence of a reliable time basis signal extracted from the line data stream and acquirable to each node. In this sense, the existence of a sub-network (inside the main network) dedicated to the distribution of the clock signals is crucially important. There are different solutions for the architecture of the time distribution sub-network and choosing one of them depends on cost, precision, reliability and operational security. In this work we expose: (i) the possible time distribution networks and their usual topologies and arrangements. (ii) How parameters of the network nodes can affect the reachability and stability of the synchronous state of a network. (iii) Optimizations methods for synchronous networks which can provide low cost architectures with operational precision, reliability and security.     

Natural synchronization in power-grids with anti-correlated units

Synchronization between spatially distributed nodes of a power-grid is a crucial requirement for its proper operation. Using a Kuramoto-like network as a realistic physical model for the distribution of electrical power in a power-grid, we obtain coupling strengths and topological characteristics that favor the synchronous state of those technological networks. Power-grids are highly heterogeneous. They are composed of different classes of nodes and each node behaves differently. We show in this work that if a power-grid is extensive and nodes are highly connected, the coupling strength that leads to synchronization depends mainly on the eigenvalues of the Laplacian matrix, as it happens in homogeneous networks composed of equal nodes. On the other hand, if a power-grid is sparsely connected, the coupling strength that leads to synchronization is also strongly related to the correlation coefficient of the network, which means that a high number of connections between similar nodes (two power plants or two consumer centers) disfavor the synchronizability of the power-grid. We apply our results to the Brazilian power-grid system.     

Exact identification of critical nodes in sparse networks via new compact formulations

Critical node detection problems aim to optimally delete a subset of nodes in order to optimize or restrict a certain metric of network fragmentation. In this paper, we consider two network disruption metrics which have recently received substantial attention in the literature: the size of the remaining connected components and the total number of node pairs connected by a path. Exact solution methods known to date are based on linear 0–1 formulations with at least $\varTheta (n^3)$ entities and allow one to solve these problems to optimality only in small sparse networks with up to 150 nodes. In this work, we develop more compact linear 0–1 formulations for the considered types of problems with $\varTheta (n^2)$ entities. We also provide reformulations and valid inequalities that improve the performance of the developed models. Computational experiments show that the proposed formulations allow finding exact solutions to the considered problems for real-world sparse networks up to 10 times larger and with CPU time up to 1,000 times faster compared to previous studies.     

A generalized activity network model

In recent years activity networks for projects with both random and deterministic alternative outcomes in key nodes have been considered. The developed control algorithm chooses an optimal outcome direction at every deterministic alternative node which is reached in the course of the project's realization. At each routine decision-making node, the algorithm singles out all the subnetworks (the so-called joint variants) which correspond to all possible outcomes from that node. Decision-making results in determining the optimal joint variant and following the optimal direction up to the next decision-making node. However, such models cover a limited class of alternative networks, namely, only fully-divisible networks which can be subdivided into nonintersecting fragments. In this paper, a more generalized activity network is considered. The model can be applied to a broader spectrum of R&D projects and can be used for all types of alternative networks, for example, for non-divisible networks comprising nodes with simultaneously ‘must follow’, random ‘exclusive OR’ and deterministic ‘exclusive or’ emitters. The branching activities of the third type refer to decision-making outcomes; choosing the optimal outcome is the sole prerogative of the project's management. Such a model is a more universal activity network; we will call it GAAN—Generalized Alternative Activity Network. The problem is to determine the joint variant optimizing the mean value of the objective function subject to restricted mean values of several other criteria. We will prove that such a problem is a NP-complete one. Thus, in general, the exact solution of the problem may be obtained only by looking through all the joint variants on the basis of their proper enumeration. To enumerate the joint variants we will use the lexicographical method in combination with some techniques of discrete optimization. A numerical example will be presented. Various application areas are considered.     

On distributed scheduling with heterogeneously delayed network-state information

We study the problem of distributed scheduling in wireless networks, where each node makes individual scheduling decisions based on heterogeneously delayed network state information (NSI). This leads to inconsistency in the views of the network across nodes, which, coupled with interference, makes it challenging to schedule for high throughputs. We characterize the network throughput region for this setup, and develop optimal scheduling policies to achieve the same. Our scheduling policies have a threshold-based structure and, moreover, require the nodes to use only the “smallest critical subset” of the available delayed NSI to make decisions. In addition, using Markov chain mixing techniques, we quantify the impact of delayed NSI on the throughput region. This not only highlights the value of extra NSI for scheduling, but also characterizes the loss in throughput incurred by lower complexity scheduling policies which use homogeneously delayed NSI.     

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.