相依网络上基于相连边的择优恢复算法

如何有效地应对和控制故障在相依网络上的级联扩散避免系统发生结构性破碎,对于相依网络抗毁性研究具有十分重要的理论价值和现实意义.最新的研究提出一种基于相依网络的恢复模型,该模型的基本思想是通过定义共同边界节点,在每轮恢复阶段找出符合条件的共同边界节点并以一定比例实施恢复.当前的做法是按照随机概率进行选择.这种方法虽然简单直观,却没有考虑现实世界中资源成本的有限性和择优恢复的必然性.为此,针对相依网络的恢复模型,本文利用共同边界节点在极大连通网络内外的连接边数计算边界节点的重要性,提出一种基于相连边的择优恢复算法(preferential recovery based on connectivity link,PRCL)算法.利用渗流理论的随机故障模型,通过ER随机网络和无标度网络构建的不同结构相依网络上的级联仿真结果表明,相比随机方法和度数优先以及局域影响力优先的恢复算法,PRCL算法具备恢复能力强、起效时间早且迭代步数少的优势,能够更有效、更及时地遏制故障在网络间的级联扩散,极大地提高了相依网络遭受随机故障时的恢复能力.     

Robustness of a network of networks

Network research has been focused on studying the properties of a single isolated network, which rarely exists. We develop a general analytical framework for studying percolation of n interdependent networks. We illustrate our analytical solutions for three examples: (i) For any tree of n fully dependent Erd?s-Rényi (ER) networks, each of average degree k, we find that the giant component is P∞ =p[1-exp(-kP∞)](n) where 1-p is the initial fraction of removed nodes. This general result coincides for n = 1 with the known second-order phase transition for a single network. For any n>1 cascading failures occur and the percolation becomes an abrupt first-order transition. (ii) For a starlike network of n partially interdependent ER networks, P∞ depends also on the topology-in contrast to case (i). (iii) For a looplike network formed by n partially dependent ER networks, P∞ is independent of n.     

Connectivity and percolation in simulated grain-boundary networks

Random percolation theory is a common basis for modelling intergranular phenomena such as cracking, corrosion or diffusion. However, crystallographic constraints in real microstructures dictate that grain boundaries are not assembled at random. In this work a Monte Carlo method is used to construct physically realistic networks composed of high-angle grain boundaries that are susceptible to intergranular attack, as well as twin-variant boundaries that are damage resistant. When crystallographic constraints are enforced, the simulated networks exhibit triple-junction distributions that agree with experiment and reveal the non-random nature of grain-boundary connectivity. The percolation threshold has been determined for several constrained boundary networks and is substantially different from the classical result of percolation theory; compared with a randomly assembled network, about 50-75% more resistant boundaries are required to break up the network of susceptible boundaries. Triple-junction distributions are also shown to capture many details of the correlated percolation problem and to provide a simple means of ranking microstructures.     

Modeling wireless sensor networks using random graph theory

A critical issue in wireless sensor networks (WSNs) is represented by limited availability of energy within network nodes. Therefore, making good use of energy is necessary in modeling sensor networks. In this paper we proposed a new model of WSNs on a two-dimensional plane using site percolation model, a kind of random graph in which edges are formed only between neighbouring nodes. Then we investigated WSNs connectivity and energy consumption at percolation threshold when a so-called phase transition phenomena happen. Furthermore, we proposed an algorithm to improve the model; as a result the lifetime of networks is prolonged. We analyzed the energy consumption with Markov process and applied these results to simulation.     

The Geometric and Thermodynamic Properties of Grain Boundary Junctions

We provide an overview of the properties of triple junctions and quadruple points. It is shown that these junctions may exhibit distinct behaviors that imply that they have and thermodynamically distinct properties in the same way that grain boundaries can be considered as thermodynamically distinct phases, separate from the material that they inhabit. It is shown that the treatment of triple junctions as thermodynamically distinct defects is a natural extension of the treatment of grain boundaries, and that it can be further extended to other junctions such as quadruple nodes. Equilibrium dihedral angles under conditions of anisotropic interfacial energy are explored, and it is found that the dihedral angles may be variable under a range of different conditions.     

Damage spreading and criticality in finite random dynamical networks

We systematically study and compare damage spreading at the sparse percolation (SP) limit for random Boolean and threshold networks with perturbations that are independent of the network size N. This limit is relevant to information and damage propagation in many technological and natural networks. Using finite-size scaling, we identify a new characteristic connectivity Ks, at which the average number of damaged nodes d[over ], after a large number of dynamical updates, is independent of N. Based on marginal damage spreading, we determine the critical connectivity Kc(sparse)(N) for finite N at the SP limit and show that it systematically deviates from Kc, established by the annealed approximation, even for large system sizes. Our findings can potentially explain the results recently obtained for gene regulatory networks and have important implications for the evolution of dynamical networks that solve specific tasks.     

一种基于势博弈的无线传感器网络拓扑控制算法

在实际的应用中,无线传感器网络常常由大量电池资源有限的传感器节点组成.如何降低网络功耗,最大化网络生存时间,是传感器网络拓扑控制技术的重要研究目标.随着传感节点的运行,节点的能量分布可能越来越不均衡,需要在考虑该因素的情况下,动态地调整节点的网络负载以均衡节点的能耗,达到延长网络生存时间的目的.该文引入博弈理论和势博弈的概念,综合考虑节点的剩余能量和节点发射功率等因素,设计了一种基于势博弈的拓扑控制模型,并证明了该模型纳什均衡的存在性.通过构造兼顾节点连通性和能耗均衡性的收益函数,以确保降低节点功耗的同时维持网络的连通性.通过提高邻居节点的平均剩余能量值以实现将剩余能量多的节点选择作为自身的邻居节点,提高节点能耗的均衡性.在此基础上,提出了一种分布式的能耗均衡拓扑控制算法.理论分析证明了该算法能保持网络的连通性.与现有基于博弈理论的DIA算法和MLPT算法相比,本算法形成的拓扑负载较重、剩余能量较小的瓶颈节点数量较少,节点剩余能量的方差较小,网络生存时间更长.     

Resilience of the internet to random breakdowns

A common property of many large networks, including the Internet, is that the connectivity of the various nodes follows a scale-free power-law distribution, P(k) = ck(-alpha). We study the stability of such networks with respect to crashes, such as random removal of sites. Our approach, based on percolation theory, leads to a general condition for the critical fraction of nodes, p(c), that needs to be removed before the network disintegrates. We show analytically and numerically that for alpha0.99.     

Evolutionary construction of geographical networks with nearly optimal robustness and efficient routing properties

Robust and efficient design of networks on a realistic geographical space is one of the important issues for the realization of dependable communication systems. In this paper, based on a percolation theory and a geometric graph property, we investigate such a design from the following viewpoints: (1) network evolution according to a spatially heterogeneous population, (2) trimodal low degrees for the tolerant connectivity against both failures and attacks, and (3) decentralized routing within short paths. Furthermore, we point out the weakened tolerance by geographical constraints on local cycles, and propose a practical strategy by adding a small fraction of shortcut links between randomly chosen nodes in order to improve the robustness to a similar level to that of the optimal bimodal networks with a larger degree for the network size N. These properties will be useful for constructing future ad hoc networks in wide-area communications.     

LCH: A local clustering H-index centrality measure for identifying and ranking influential nodes in complex networks

Identifying influential nodes in complex networks is one of the most significant and challenging issues, which may contribute to optimizing the network structure, controlling the process of epidemic spreading and accelerating information diffusion. The node importance ranking measures based on global information are not suitable for large-scale networks due to their high computational complexity. Moreover, they do not take into account the impact of network topology evolution over time, resulting in limitations in some applications. Based on local information of networks, a local clustering H-index (LCH) centrality measure is proposed, which considers neighborhood topology, the quantity and quality of neighbor nodes simultaneously. The proposed measure only needs the information of first-order and second-order neighbor nodes of networks, thus it has nearly linear time complexity and can be applicable to large-scale networks. In order to test the proposed measure, we adopt the susceptible-infected-recovered (SIR) and susceptible-infected (SI) models to simulate the spreading process. A series of experimental results on eight real-world networks illustrate that the proposed LCH can identify and rank influential nodes more accurately than several classical and state-of-the-art measures.     

Complexity in human transportation networks: a comparative analysis of worldwide air transportation and global cargo-ship movements

We present a comparative network-theoretic analysis of the two largest global transportation networks: the worldwide air-transportation network (WAN) and the global cargo-ship network (GCSN). We show that both networks exhibit surprising statistical similarities despite significant differences in topology and connectivity. Both networks exhibit a discontinuity in node and link betweenness distributions which implies that these networks naturally segregate into two different classes of nodes and links. We introduce a technique based on effective distances, shortest paths and shortest path trees for strongly weighted symmetric networks and show that in a shortest path tree representation the most significant features of both networks can be readily seen. We show that effective shortest path distance, unlike conventional geographic distance measures, strongly correlates with node centrality measures. Using the new technique we show that network resilience can be investigated more precisely than with contemporary techniques that are based on percolation theory. We extract a functional relationship between node characteristics and resilience to network disruption. Finally we discuss the results, their implications and conclude that dynamic processes that evolve on both networks are expected to share universal dynamic characteristics.     

Grain boundary,triple junction and quadruple point mobility controlled normal grain growth

Reduction in stored free energy provides the thermodynamic driving force for grain and bubble growth in polycrystals and foams. Evolution of polycrystalline networks exhibit the additional complication that grain growth may be controlled by several kinetic mechanisms through which the decrease in network energy occurs. Polyhedral boundaries, triple junctions (TJs), and quadruple points (QPs) are the geometrically distinct elements of three dimensional networks that follow Plateau’s rules, provided that grain growth is limited by diffusion through, and motion of, cell boundaries. Shvindlerman and co-workers have long recognized the kinetic influences on polycrystalline grain growth of network TJs and QPs. Moreover, the emergence of interesting polycrystalline nanomaterials underscored that TJs can indeed influence grain growth kinetics. Currently there exist few detailed studies concerned either with network distributions of grain size, number of faces per grain, or with ‘grain trajectories’, when grain growth is limited by the motion of its TJs or QPs. By contrast there exist abundant studies of classical grain growth limited by boundary mobility. This study is focused on a topological/geometrical representation of polycrystals to obtain statistical predictions of the grain size and face number distributions, as well as growth ‘trajectories’ during steady-state grain growth. Three limits to grain growth are considered, with grain growth kinetics controlled by boundary, TJ, and QP mobilities.     

Exactly solvable models of adaptive networks

A satisfiability-unsatisfiability (SAT-UNSAT) transition takes place for many optimization problems when the number of constraints, graphically represented by links between variables nodes, is brought above some threshold. If the network of constraints is allowed to adapt by redistributing its links, the SAT-UNSAT transition may be delayed and preceded by an intermediate phase where the structure self-organizes to satisfy the constraints. We present an analytic approach, based on the recently introduced cavity method for large deviations, which exactly describes the two phase transitions delimiting this adaptive intermediate phase. We give explicit results for random bond models subject to the connectivity or rigidity percolation transitions, and compare them with numerical simulations.     

Continuum Percolation with Unreliable and Spread-Out Connections

We derive percolation results in the continuum plane that lead to what appears to be a general tendency of many stochastic network models. Namely, when the selection mechanism according to which nodes are connected to each other, is sufficiently spread out, then a lower density of nodes, or on average fewer connections per node, are sufficient to obtain an unbounded connected component. We look at two different transformations that spread-out connections and decrease the critical percolation density while preserving the average node degree. Our results indicate that real networks can exploit the presence of spread-out and unreliable connections to achieve connectivity more easily, provided they can maintain the average number of functioningconnections per node.     

The supergroup manifold formulation of the Wess-Zumino multiplet revisited: The supercurrent and the supergravity auxiliary fields

In this paper we provide a consistent first-order group-manifold formulation of the Wess-Zumino system. It is shownhow the well-known auxiliary fields of the ($\text{1}\text{2}$, 0, 0) system arise by supplementing Bianchi identities with the “second-order constraints”; that is, those equations allowing the transition from the first order to the second order of the theory. When the ($\text{1}\text{2}$, 0, 0) multiplet is coupled to N = 1 supergravity and the torsion “second-order constraint” is implemented, we get a non-minimal set of auxiliary fields (scalar, pseudoscalar axial vector and a spinor). We argue this to be the fundamental set of auxiliary fields. The so-called “minimal set” is not coordinate invariant and can be recovered only by adding a non-geometrical constraint.     

Characteristics of microRNA co-target networks

The database of microRNAs and their predicted target genes in humans were used to extract a microRNA co-target network. Based on the finding that more than two miRNAs can target the same gene, we constructed a microRNA co-target network and analyzed it from the perspective of the complex network. We found that a network having a positive assortative mixing can be characterized by small-world and scale-free characteristics which are found in most complex networks. The network was further analyzed by the nearest-neighbor average connectivity, and it was shown that the more assortative a microRNA network is, the wider the range of increasing average connectivity. In particular, an assortative network has a power-law relationship of the average connectivity with a positive exponent. A percolation analysis of the network showed that, although the network is diluted, there is no percolation transition in the network. From these findings, we infer that the microRNAs in the network are clustered together, forming a core group. The same analyses carried out on different species confirmed the robustness of the main results found in the microRNA networks of humans.     

A Resiliency-Connectivity metric in wireless sensor networks with key predistribution schemes and node compromise attacks

Applications for wireless sensor networks require widespread, highly reliable communications even in the face of adversarial influences. Maintaining connectivity and secure communications between entities are vital networking properties towards ensuring the successful and accurate completion of desired sensing tasks. We examine the required communication range for nodes in a wireless sensor network with respect to several parameters. Network properties such as key predistribution schemes and node compromise attacks are modelled with several network parameters and studied in terms of how they influence global network connectivity. These networks are physically vulnerable to malicious behavior by way of node compromise attacks that may affect global connectivity. We introduce a metric that determines the resilience of a network employing a key predistribution scheme with respect to node compromise attacks. In this work,we provide the first study of global network connectivity and its relationship to node compromise attacks. Existing work considers the relationship between the probability of node compromise and the probability of link compromise and the relationship of the probability of secure link establishment and overall network connectivity for the Erdős network model. Here, we present novel work which combines these two relationships to study the relationship between node compromise attacks and global network connectivity. Our analysis is performed with regard to large-scale networks; however, we provide simulation results for both large-scale and small-scale networks. First, we derive a single expression to determine the required communication radius for wireless sensor networks to include the effects of key predistribution schemes. From this, we derive an expression for determining required communication range after an adversary has compromised a fraction of the nodes in the network. The required communication range represents the resource usage of nodes in a network to cope with key distribution schemes and node compromise attacks. We introduce the Resiliency-Connectivity metric, which measures the resilience of a network in expending its resources to provide global connectivity in adverse situations.     

Twin Junctions in Monoclinic Zirconia

Analysis of high-resolution transmission electron microscopy images of the microstructure of monoclinic zirconia film has revealed that some areas are built entirely of twins. Twin boundaries form triple and quadruple junctions. While the misorientations of the constituent boundaries are completely balanced at quadruple junctions, there is a small rotational mismatch at the junctions of three twin boundaries. This mismatch is compensated by wedge disclinations. Crystallography of the triple junctions is considered and factors stabilizing intrinsic junction disclinations are discussed.     

Explosive phenomena in complex networks

The emergence of large-scale connectivity and synchronization are crucial to the structure, function and failure of many complex socio-technical networks. Thus, there is great interest in analyzing phase transitions to large-scale connectivity and to global synchronization, including how to enhance or delay the onset. These phenomena are traditionally studied as second-order phase transitions where, at the critical threshold, the order parameter increases rapidly but continuously. In 2009, an extremely abrupt transition was found for a network growth process where links compete for addition in an attempt to delay percolation. This observation of ‘explosive percolation’ was ultimately revealed to be a continuous transition in the thermodynamic limit, yet with very atypical finite-size scaling, and it started a surge of work on explosive phenomena and their consequences. Many related models are now shown to yield discontinuous percolation transitions and even hybrid transitions. Explosive percolation enables many other features such as multiple giant components, modular structures, discrete scale invariance and non-self-averaging, relating to properties found in many real phenomena such as explosive epidemics, electric breakdowns and the emergence of molecular life. Models of explosive synchronization provide an analytic framework for the dynamics of abrupt transitions and reveal the interplay between the distribution in natural frequencies and the network structure, with applications ranging from epileptic seizures to waking from anesthesia. Here we review the vast literature on explosive phenomena in networked systems and synthesize the fundamental connections between models and survey the application areas. We attempt to classify explosive phenomena based on underlying mechanisms and to provide a coherent overview and perspective for future research to address the many vital questions that remained unanswered.     

Effects of ramification and connectivity degree on site percolation threshold on regular lattices and fractal networks

This Letter is focused on the impact of network topology on the site percolation. Specifically, we study how the site percolation threshold depends on the network dimensions (topological d and fractal D), degree of connectivity (quantified by the mean coordination number $Z_{\infty }$), and arrangement of bonds (characterized by the connectivity index Q also called the ramification exponent). Using the Fisher's containment principle, we established exact inequalities between percolation thresholds on fractal networks contained in the square lattice. The values of site percolation thresholds on some fractal lattices were found by numerical simulations. Our findings suggest that the most relevant parameters to describe properly the values of site percolation thresholds on fractal networks contained in square lattice (Sierpiński carpets and Cantor tartans) and based on the square lattice (weighted planar stochastic fractal and Cantor lattices) are the mean coordination number and ramification exponent, but not the fractal dimension. Accordingly, we propose an empirical formula providing a good approximation for the site percolation thresholds on these networks. We also put forward an empirical formula for the site percolation thresholds on d-dimensional simple hypercubic lattices.