An Efficient Reliability Evaluation Approach for Networks with Simultaneous Multiple‐Node‐Pair Flow Requirements

This paper proposes an efficient approach for reliability evaluation of multiple‐sources and multiple‐destinations flow networks. The proposed approach evaluates multiple node pair capacity related reliability. The proposed approach is a three‐step approach; in the first step, it enumerates network minimal cut sets. These network minimal cut sets are then used to enumerate subset cuts in the second step. Third step involves the evaluation of multiple node pair capacity related reliability from the enumerated subset cuts using a multi‐variable inversion sum‐of‐disjoint set approach. The proposed approach can be used for optimal network design as it combines multiple performance requirements, that is, flow requirements between multiple node pairs and network reliability, in a single criterion. Copyright © 2016 John Wiley & Sons, Ltd.     

Minimal cut sets of s–t networks with k-out-of-n nodes

In this paper, we extend traditional directed s–t network by letting nodes have k-out-of-n property: To generate output flows, a node must receive at least k flows from its n input links, where k is an integer assigned for the node and its value can be any number from 1 to n. To evaluate the system reliability, minimal cut sets for the extended network are defined for nodes. Under this definition, an extended network and its sink node have the same minimal cut sets. A new algorithm is designed to generate minimal cut sets for all nodes, starting with the source node and ending with the sink node. With different initializations, the algorithm can be applied for extended s–t networks with or without node failures.     

A Parallel Strategy for the Logical‐probabilistic Calculus‐based Method to Calculate Two‐terminal Reliability

The theory of network reliability has been applied to many complicated network structures, such as computer and communication networks, piping systems, electricity networks, and traffic networks. The theory is used to evaluate the operational performance of networks that can be modeled by probabilistic graphs. Although evaluating network reliability is an Non‐deterministic Polynomial‐time hard problem, numerous solutions have been proposed. However, most of them are based on sequential computing, which under‐utilizes the benefits of multi‐core processor architectures. This paper addresses this limitation by proposing an efficient strategy for calculating the two‐terminal (terminal‐pair) reliability of a binary‐state network that uses parallel computing. Existing methods are analyzed. Then, an efficient method for calculating terminal‐pair reliability based on logical‐probabilistic calculus is proposed. Finally, a parallel version of the proposed algorithm is developed. This is the first study to implement an algorithm for estimating terminal‐pair reliability in parallel on multi‐core processor architectures. The experimental results show that the proposed algorithm and its parallel version outperform an existing sequential algorithm in terms of execution time. Copyright © 2015 John Wiley & Sons, Ltd.     

通信网中最重要节点的确定方法

提出了一种确定通信网中最重要节点的方法——节点删除法,并给出了归一化的表达式。最重要的节点是去掉该节点以及相关联的链路后,使得图的生成树数目最小。节点删除法反映了某个节点失效时,对整个通信网可靠性的破坏程度。该方法可以评价全网范围内的节点重要性,通过比较生成树的数目,可以判断通信网中任意两个节点的相对重要性。实验结果证明了节点删除法的有效性。     

Element substitution algorithm for general two-terminal network reliability analyses

The computation of the reliability of two-terminal networks is a classical reliability problem. For these types of problems, one is interested, from a general perspective, in obtaining the probability that two specific nodes can communicate. This paper presents a holistic algorithm for the analysis of general networks that follow a two-terminal rationale. The algorithm is based on a set replacement approach and an element inheritance strategy that effectively obtains the minimal cut sets associated with a given network. The vast majority of methods available for obtaining two-terminal reliability are generally based on assumptions about the performance of the network. Some methods assume network components can be in one of two states: (i) either completely failed; or (ii) perfectly functioning, others usually assume that nodes are perfectly reliable and thus, these methods have to be complemented or transformed to account for node failure, and the remaining methods assume minimal cut sets can be readily computed in order to analyze more complex network and component behavior. The algorithm presented in this paper significantly differs from previous approaches available in the literature in the sense that it is based on a predecessor matrix and an element substitution technique that allows for the exact computation of minimal cut sets and the immediate inclusion of node failure without any changes to the pseudo-code. Several case networks are used to validate and illustrate the algorithms.     

The relationship between modularity and robustness in signalling networks

Many biological networks tend to have a high modularity structural property and the dynamic characteristic of high robustness against perturbations. However, the relationship between modularity and robustness is not well understood. To investigate this relationship, we examined real signalling networks and conducted simulations using a random Boolean network model. As a result, we first observed that the network robustness is negatively correlated with the network modularity. In particular, this negative correlation becomes more apparent as the network density becomes sparser. Even more interesting is that, the negative relationship between the network robustness and the network modularity occurs mainly because nodes in the same module with the perturbed node tend to be more sensitive to the perturbation than those in other modules. This result implies that dynamically similar nodes tend to be located in the same module of a network. To support this, we show that a pair of genes associated with the same disease or a pair of functionally similar genes is likely to belong to the same module in a human signalling network.     

多波长光网络的动态路由等效算法

针对多波长光网络的特点，提出了一种动态路由和波长分配的等效算法。采用波长图、增加虚拟源节点和目的节点等技术，把多波长网络转化为等效的单波长网络，避免了求解路由和波长分配两个复杂子问题，简化了算法的程序设计。利用最短径算法进行路由和波长分配可以求得问题的最优解，从而有效地降低了网络阻塞率。仿真结果表明：与FAR-2D算法相比，在4和8波长的全波长转换网络中，采用等效算法阻塞率最大降幅分别达到0．02、0．025。     

Cutset enumeration of network systems with link and node failures

Network reliability analysis has received considerable attention and is thus widely studied to predict and prevent any network failure. However, most of such works presume perfectly reliable nodes. Although a few studies have considered both link and node failures, none of these methods has utilized the minimal paths or cuts, which are considered as fundamental approaches in the network reliability evaluation. An efficient method for deducing the minimal cutsets of a system subject to both link and node failures from the minimal cutsets of the system, which assumes perfect node reliability, is presented. The proposed method does not require re-enumeration of minimal cutsets for the additional consideration of the node failures. For a simple extension of such a method, the proposed approach can be embedded in any exact or approximate algorithm to account for link failures as well as node failures. As a result, the application of this method would be more realistic and valuable in practice for the reliability evaluation of networks with unreliable nodes.     

Stability in flux: community structure in dynamic networks

The structure of many biological, social and technological systems can usefully be described in terms of complex networks. Although often portrayed as fixed in time, such networks are inherently dynamic, as the edges that join nodes are cut and rewired, and nodes themselves update their states. Understanding the structure of these networks requires us to understand the dynamic processes that create, maintain and modify them. Here, we build upon existing models of coevolving networks to characterize how dynamic behaviour at the level of individual nodes generates stable aggregate behaviours. We focus particularly on the dynamics of groups of nodes formed endogenously by nodes that share similar properties (represented as node state) and demonstrate that, under certain conditions, network modularity based on state compares well with network modularity based on topology. We show that if nodes rewire their edges based on fixed node states, the network modularity reaches a stable equilibrium which we quantify analytically. Furthermore, if node state is not fixed, but can be adopted from neighbouring nodes, the distribution of group sizes reaches a dynamic equilibrium, which remains stable even as the composition and identity of the groups change. These results show that dynamic networks can maintain the stable community structure that has been observed in many social and biological systems.     

An efficient method for reliability evaluation of multistate networks given all minimal path vectors

The multistate networks under consideration consist of a source node, a sink node, and some independent failure-prone components in between the nodes. The components can work at different levels of capacity. For such a network, we are interested in evaluating the probability that the flow from the source node to the sink node is equal to or greater than a demanded flow of d units. A general method for reliability evaluation of such multistate networks is using minimal path (cut) vectors. A minimal path vector to system state d is called a d-MP. Approaches for generating all d-MPs have been reported. Given that all d-MPs have been found, the issue becomes how to evaluate the probability of the union of the events that the component state vector is greater than or equal to at least one of the d-MPs. There is a need for a more efficient method of determining the probability of this union of events. In this paper, we report an efficient recursive algorithm for this union probability evaluation based on the Sum of Disjoint Products (SDP) principle, and name it the Recursive Sum of Disjoint Products (RSDP) algorithm. The basic idea is that, based on the SDP principle and a specially defined “maximum” operator, “⊕”, the probability of a union with L vectors can be calculated via calculating the probabilities of several unions with L-1 vectors or less. The correctness of RSDP is illustrated. The efficiency of this algorithm is investigated by comparing it with an existing algorithm that is generally accepted to be efficient. It is found that RSDP is more efficient than the existing algorithm when the number of components of a system is not too small. RSDP provides us with an efficient, systematic and simple approach for evaluating multistate network reliability given all d-MPs.     

An overview of the reliability metrics for power grids and telecommunication networks

Power grids deliver energy, and telecommunication networks transmit information. These two facilities are critical to human society. In this study, we conduct a comprehensive overview of the development of reliability metrics for power grids and telecommunication networks. The main purpose of this review is to promote and support the formulation of communication network reliability metrics with reference to the development of power grid reliability. We classify the metrics of power grid into the reliability of power distribution and generation/transmission and the metrics of telecommunication network into connectivity-based, performance-based, and state-based metrics. Then, we exhibit and discuss the difference between the situations of the reliability metrics of the two systems. To conclude this study, we conceive a few topics for future research and development for telecommunication network reliability metrics.     

An Energy Based Dynamic AODV Routing Protocol in Wireless Ad Hoc Networks

In recent years, with the rapid development of the Internet and wireless communication technology, wireless Ad hoc networks have received more attention. Due to the limited transmission range and energy of nodes in Ad hoc networks, it is important to establish a reliable and energy-balanced transmission path in Ad hoc networks. This paper proposes an energy-based dynamic routing protocol based on the existing AODV routing protocol, which has the following two aspects of improvement: (1) In the route discovery process, a node selects a suitable route from the minimum energy consumption route and the energy-balanced route designed in this paper according to a “Mark” bit that representing remaining energy of a node. (2) Based on (1), a route interruption update strategy was proposed to restart the route discovery process when node energy was used excessively. Simulation results demonstrate that compared with AODV and other existing routing protocols, proposed algorithm can reduce network energy consumption and balance node energy, thus extending the network lifetime.     

Reliability analysis of cluster-based ad-hoc networks

The mobile ad-hoc wireless network (MAWN) is a new and emerging network scheme that is being employed in a variety of applications. The MAWN varies from traditional networks because it is a self-forming and dynamic network. The MAWN is free of infrastructure and, as such, only the mobile nodes comprise the network. Pairs of nodes communicate either directly or through other nodes. To do so, each node acts, in turn, as a source, destination, and relay of messages. The virtue of a MAWN is the flexibility this provides; however, the challenge for reliability analyses is also brought about by this unique feature. The variability and volatility of the MAWN configuration makes typical reliability methods (e.g. reliability block diagram) inappropriate because no single structure or configuration represents all manifestations of a MAWN. For this reason, new methods are being developed to analyze the reliability of this new networking technology. New published methods adapt to this feature by treating the configuration probabilistically or by inclusion of embedded mobility models. This paper joins both methods together and expands upon these works by modifying the problem formulation to address the reliability analysis of a cluster-based MAWN. The cluster-based MAWN is deployed in applications with constraints on networking resources such as bandwidth and energy. This paper presents the problem's formulation, a discussion of applicable reliability metrics for the MAWN, and illustration of a Monte Carlo simulation method through the analysis of several example networks.     

Prophet_TD Routing Algorithm Based on Historical Throughput and Encounter Duration

Opportunistic networks are self-organizing networks that do not require a complete path between the source node and the destination node as it uses encounter opportunities brought by nodes movement to achieve network communication. Opportunistic networks routing algorithms are numerous and can be roughly divided into four categories based on different forwarding strategies. The Prophet routing algorithm is an important routing algorithm in opportunistic networks. It forwards messages based on the encounter probability between nodes, and has good innovation significance and optimization potential. However, the Prophet routing algorithm does not consider the impact of the historical throughput of the node on message transmission, nor does it consider the impact of the encounter duration between nodes on message transmission. Therefore, to improve the transmission efficiency of opportunistic networks, this paper based on the Prophet routing algorithm, fuses the impact of the historical throughput of the node and the encounter duration between nodes on message transmission at the same time, and proposes the Prophet_TD routing algorithm based on the historical throughput and the encounter duration. This paper uses the Opportunistic Networks Environment v1.6.0 (the ONE v1.6.0) as the simulation platform, controls the change of running time and the number of nodes respectively, conducts simulation experiments on the Prophet_TD routing algorithm. The simulation results show that compared to the traditional Prophet routing algorithm, on the whole, the Prophet_TD routing algorithm has a higher message delivery rate and a lower network overhead rate, and its average latency is also lower when node density is large.     

Reliability-oriented multi-resource allocation in a stochastic-flow network

A stochastic-flow network consists of a set of nodes, including source nodes which supply various resources and sink nodes at which resource demands take place, and a collection of arcs whose capacities have multiple operational states. The network reliability of such a stochastic-flow network is the probability that resources can be successfully transmitted from source nodes through multi-capacitated arcs to sink nodes. Although the evaluation schemes of network reliability in stochastic-flow networks have been extensively studied in the literature, how to allocate various resources at source nodes in a reliable means remains unanswered. In this study, a resource allocation problem in a stochastic-flow network is formulated that aims to determine the optimal resource allocation policy at source nodes subject to given resource demands at sink nodes such that the network reliability of the stochastic-flow network is maximized, and an algorithm for computing the optimal resource allocation is proposed that incorporates the principle of minimal path vectors. A numerical example is given to illustrate the proposed algorithm.     

Minimum steering node set of complex networks and its applications to biomolecular networks

Many systems of interests in practices can be represented as complex networks. For biological systems, biomolecules do not perform their functions alone but interact with each other to form so‐called biomolecular networks. A system is said to be controllable if it can be steered from any initial state to any other final state in finite time. The network controllability has become essential to study the dynamics of the networks and understand the importance of individual nodes in the networks. Some interesting biological phenomena have been discovered in terms of the structural controllability of biomolecular networks. Most of current studies investigate the structural controllability of networks in notion of the minimum driver node sets (MDSs). In this study, the authors analyse the network structural controllability in notion of the minimum steering node sets (MSSs). They first develop a graph‐theoretic algorithm to identify the MSS for a given network and then apply it to several biomolecular networks. Application results show that biomolecules identified in the MSSs play essential roles in corresponding biological processes. Furthermore, the application results indicate that the MSSs can reflect the network dynamics and node importance in controlling the networks better than the MDSs.Inspec keywords: molecular biophysics, biocontrol, graph theoryOther keywords: graph‐theoretic algorithm, MSS, minimum driver node sets, structural controllability, network dynamics, network controllability, biological systems, biomolecular networks, complex networks, minimum steering node set     

用OBDD算法评估无线传感网的可靠度和结点重要性

基于有序二叉判定图(OBDD),提出用结点扩张(NE)算法来评估无线传感网的可靠度和结点重要性.NE算法执行结点扩张操作来处理不可靠结点,从两方面增强了计算效率:利用OBDD结构表示网络状态,减少了大量冗余的等价状态;利用Hash表存储同构子网的OBDD,减少了同构子网的重复计算.另外,该算法对结点重要性进行了评估,为脆弱结点的保护提供参考.实验结果表明NE算法的计算开销比传统的factoring算法低,能有效评估无线传感网的可靠度.     

Detecting outbreaks in temporally dependent networks

Dynamic networks require effective methods of monitoring and surveillance in order to respond promptly to unusual disturbances. In many applications, it is of interest to identify anomalous behavior within a dynamic interacting system. Such anomalous interactions are reflected by structural changes in the network representation of the system. In this paper, a dynamic random graph model is proposed that takes into account the past activities of the individuals in the social network and also represents temporal dependency of the network. The model parameters are appearance and disappearance probabilities of an edge which are estimated using a maximum likelihood approach. A generalization of a single path‐dependent likelihood ratio test is employed to detect changes in the parameters of the proposed model. Through monitoring the estimated parameters, one can effectively detect structural changes in a temporal‐dependent network. The proposed model is employed to describe the behavior of a real network, and its parameters are monitored via dependent likelihood ratio test and multivariate exponentially weighted moving average control chart. Results indicate that the proposed dynamic random graph model is a reliable mean to modeling and detecting changes in temporally dependent networks.     

Reliability evaluation of capacitated-flow networks with budget constraints

Many real-world systems such as transportation systems and manufacturing systems can be regarded as flow networks whose arcs have independent, finite and multi-valued random capacities. Such a flow network is indeed a multistate system with multistate components and so its reliability for level (d,c), i.e., the probability that d units of flow can be transmitted from the source node to the sink node such that the total transmission cost is less than or equal to c, can be computed in terms of minimal path vectors to level (d,c) (named (d,c)-MPs here). The main objective of this paper is to present a simple algorithm to generate all (d,c)-MPs of such a system for each level (d,c) in terms of minimal pathsets. Two examples are given to illustrate how all (d,c)-MPs are generated by our algorithm and then the reliability of one example is computed.     

Heterogeneous Hyperedge Convolutional Network

Graph convolutional networks (GCNs) have been developed as a general and powerful tool to handle various tasks related to graph data. However, current methods mainly consider homogeneous networks and ignore the rich semantics and multiple types of objects that are common in heterogeneous information networks (HINs). In this paper, we present a Heterogeneous Hyperedge Convolutional Network (HHCN), a novel graph convolutional network architecture that operates on HINs. Specifically, we extract the rich semantics by different metastructures and adopt hyperedge to model the interactions among metastructure-based neighbors. Due to the powerful information extraction capabilities of metastructure and hyperedge, HHCN has the flexibility to model the complex relationships in HINs by setting different combinations of metastructures and hyperedges. Moreover, a metastructure attention layer is also designed to allow each node to select the metastructures based on their importance and provide potential interpretability for graph analysis. As a result, HHCN can encode node features, metastructure-based semantics and hyperedge information simultaneously by aggregating features from metastructure-based neighbors in a hierarchical manner. We evaluate HHCN by applying it to the semi-supervised node classification task. Experimental results show that HHCN outperforms state-of-the-art graph embedding models and recently proposed graph convolutional network models.