Accelerating networks: Effects of preferential connections

Networks are commonly observed structures in complex systems with interacting and interdependent parts that self-organize. For nonlinearly growing networks, when the total number of connections increases faster than the total number of nodes, the network is said to accelerate. We propose a systematic model for the dynamics of growing networks represented by distribution kinetics equations. We define the nodal-linkage distribution, construct a population dynamics equation based on the association-dissociation process, and perform the moment calculations to describe the dynamics of such networks. For nondirectional networks with finite numbers of nodes and connections, the moments are the total number of nodes, the total number of connections, and the degree (the average number of connections per node), represented by the average moment. Size independent rate coefficients yield an exponential network describing the network without preferential attachment, and size dependent rate coefficients produce a power law network with preferential attachment. The model quantitatively describes accelerating network growth data for a supercomputer (Earth Simulator), for regulatory gene networks, and for the Internet.     

Limited path percolation in complex networks

We study the stability of network communication after removal of a fraction q=1-p of links under the assumption that communication is effective only if the shortest path between nodes i and j after removal is shorter than al(ij)(a> or =1) where l(ij) is the shortest path before removal. For a large class of networks, we find analytically and numerically a new percolation transition at p(c)=(kappa(0)-1)((1-a)/a), where kappa(0) [triple bond] / and k is the node degree. Above p(c), order N nodes can communicate within the limited path length al(ij), while below p(c), N(delta) (delta<1) nodes can communicate. We expect our results to influence network design, routing algorithms, and immunization strategies, where short paths are most relevant.     

Stability and topology of scale-free networks under attack and defense strategies

We study tolerance and topology of random scale-free networks under attack and defense strategies that depend on the degree k of the nodes. This situation occurs, for example, when the robustness of a node depends on its degree or in an intentional attack with insufficient knowledge of the network. We determine, for all strategies, the critical fraction p(c) of nodes that must be removed for disintegrating the network. We find that, for an intentional attack, little knowledge of the well-connected sites is sufficient to strongly reduce p(c). At criticality, the topology of the network depends on the removal strategy, implying that different strategies may lead to different kinds of percolation transitions.     

Evolution of the Internet AS-level topology:From nodes and edges to components

Studying the topology of infrastructure communication networks(e.g., the Internet) has become a means to understand and develop complex systems. Therefore, investigating the evolution of Internet network topology might elucidate disciplines governing the dynamic process of complex systems. It may also contribute to a more intelligent communication network framework based on its autonomous behavior. In this paper, the Internet Autonomous Systems(ASes) topology from 1998 to 2013 was studied by deconstructing and analysing topological entities on three different scales(i.e., nodes,edges and 3 network components: single-edge component M1, binary component M2 and triangle component M3). The results indicate that: a) 95% of the Internet edges are internal edges(as opposed to external and boundary edges); b) the Internet network consists mainly of internal components, particularly M2 internal components; c) in most cases, a node initially connects with multiple nodes to form an M2 component to take part in the network; d) the Internet network evolves to lower entropy. Furthermore, we find that, as a complex system, the evolution of the Internet exhibits a behavioral series,which is similar to the biological phenomena concerned with the study on metabolism and replication. To the best of our knowledge, this is the first study of the evolution of the Internet network through analysis of dynamic features of its nodes,edges and components, and therefore our study represents an innovative approach to the subject.     

Complete condensation in a zero range process on scale-free networks

We study a zero range process on scale-free networks in order to investigate how network structure influences particle dynamics. The zero range process is defined with the rate p(n) = n(delta) at which particles hop out of nodes with n particles. We show analytically that a complete condensation occurs when delta < or = delta(c) triple bond 1/(gamma-1) where gamma is the degree distribution exponent of the underlying networks. In the complete condensation, those nodes whose degree is higher than a threshold are occupied by macroscopic numbers of particles, while the other nodes are occupied by negligible numbers of particles. We also show numerically that the relaxation time follows a power-law scaling tau approximately L(z) with the network size L and a dynamic exponent z in the condensed phase.     

Decorrelation of networked communication flow via load-dependent routing weights

Clever assignments of link weights are able to change communication routes in such a way that loads are distributed almost evenly across a network. This is achieved by weight assignments based on the link load. As demonstrated for scale-free as well as synthetic Internet networks, they decorrelate the loads of the nodes and links from the network structure and increase the transport capacity of the network. For various Internet scans the increase of transport capacity amounts to a factor of around five when compared to shortest-path routing.     

Phase Transition in Recovery Process of Complex Networks

The dynamic characteristic of complex network failure and recovery is one of the main research topics in complex networks. Real world systems such as traffic jams and Internet recovery could be described by the complex network theory. We propose a model to study the recovery process in complex networks. Two different recovery mechanisms are considered in three kinds of networks: external recovery and internal recovery. By simulating the process of the nodes recovery in networks, it is found that the system exhibits the feature of first-order phase transition only when the external recovery is considered. Internal recovery cannot induce such a kind of transitions. As external recovery and internal recovery coexist on networks, the systems will retain the most efficient part of external recovery and internal recovery. Meanwhile, a hysteresis could be observed when increasing or decreasing the failure probability. Finally; a largest degree node protection strategy is proposed for improving the robustness of networks.     

虚拟网络行为对互联网整体特性的影响

虚拟网络是一种依赖Internet基础设施所提供的传输能力，但又具有独立拓扑结构和信息传递规则的应用层网络行为逻辑网络.提出了耦合虚拟网络行为与物理节点的抽象模型，对一类典型的虚拟网络逻辑拓扑给互联网整体特性带来的影响进行了分析.研究表明在虚拟网络作用下，节点数据包排队长度存在相变特性，但相变临界点比对规则网络发生了明显左移，网络性能相对恶化.当数据包注入速率小于相变临界速率时，节点数据包排队长度不相关或短程相关；在接近临界速率处，节点数据包排队长度长程相关，幂指数H增大，网络获得更强的长程相关性.同时，在注入速率大于或等于临界速率时，虚拟网络行为使网络呈现出一致的长程相关特性.     

用户需求行为对互联网动力学整体特性的影响

由Internet构成的复杂网络的动力学特性主要受到用户需求行为的影响,具备时域的统计规律性. 通过对区域群体用户需求行为的时域实验统计分析,发现用户对Web网站的访问频度及其生成的二分网络的入度分布也呈现幂律分布和集聚现象,其幂指数介于1.7到1.8之间. 建立了虚拟资源网络VRN和物理拓扑网络PTN双层模型,分析了双层模型映射机理,并对网络用户需求行为进行建模. 虚拟资源网络VRN对物理拓扑网络PTN映射过程的不同机理,模拟了Internet资源网络到物理网络的不同影响模式. 幂律分布的用户需求特性会 关键词： 复杂网络 无标度拓扑 用户需求 相变     

IKN-CF: An Approach to Identify Key Nodes in Inter-Domain Routing Systems Based on Cascading Failures

Inter-domain routing systems is an important complex network in the Internet. Research on the vulnerability of inter-domain routing network nodes is of great support to the stable operation of the Internet. For the problem of node vulnerability, we proposed a method for identifying key nodes in inter-domain routing systems based on cascading failures (IKN-CF). Firstly, we analyzed the topology of inter-domain routing network and proposed an optimal valid path discovery algorithm considering business relationships. Then, the reason and propagation mechanism of cascading failure in the inter-domain routing network were analyzed, and we proposed two cascading indicators, which can approximate the impact of node failure on the network. After that, we established a key node identification model based on improved entropy weight TOPSIS (EWT), and the key node sequence in the network can be obtained through EWT calculation. We compared the existing three methods in two real inter-domain routing networks. The results indicate that the ranking results of IKN-CF are high accuracy, strong stability, and wide applicability. The accuracy of the top 100 nodes of the ranking result can reach 83.6%, which is at least 12.8% higher than the average accuracy of the existing three methods.     

Entropic rigidity of randomly diluted two- and three-dimensional networks

In recent work, we presented evidence that site-diluted triangular central-force networks, at finite temperatures, have a nonzero shear modulus for all concentrations of particles above the geometric percolation concentration p(c). This is in contrast to the zero-temperature case where the (energetic) shear modulus vanishes at a concentration of particles p(r)>p(c). In the present paper we report on analogous simulations of bond-diluted triangular lattices, site-diluted square lattices, and site-diluted simple-cubic lattices. We again find that these systems are rigid for all p>p(c) and that near p(c) the shear modulus mu approximately (p-p(c))(f), where the exponent f approximately 1.3 for two-dimensional lattices and f approximately 2 for the simple-cubic case. These results support the conjecture of de Gennes that the diluted central-force network is in the same universality class as the random resistor network. We present approximate renormalization group calculations that also lead to this conclusion.     

Modelling one-dimensional driven diffusive systems by the Zero-Range Process

In order to characterize networks in the scale-free network class we study the frequency of cycles of length h that indicate the ordering of network structure and the multiplicity of paths connecting two nodes. In particular we focus on the scaling of the number of cycles with the system size in off-equilibrium scale-free networks. We observe that each off-equilibrium network model is characterized by a particular scaling in general not equal to the scaling found in equilibrium scale-free networks. We claim that this anomalous scaling can occur in real systems and we report the case of the Internet at the Autonomous System Level.Received: 15 January 2004, Published online: 14 May 2004PACS: 89.75.-k Complex systems - 89.75.Hc Networks and genealogical trees     

Theory of rumour spreading in complex social networks

We introduce a general stochastic model for the spread of rumours, and derive mean-field equations that describe the dynamics of the model on complex social networks (in particular, those mediated by the Internet). We use analytical and numerical solutions of these equations to examine the threshold behaviour and dynamics of the model on several models of such networks: random graphs, uncorrelated scale-free networks and scale-free networks with assortative degree correlations. We show that in both homogeneous networks and random graphs the model exhibits a critical threshold in the rumour spreading rate below which a rumour cannot propagate in the system. In the case of scale-free networks, on the other hand, this threshold becomes vanishingly small in the limit of infinite system size. We find that the initial rate at which a rumour spreads is much higher in scale-free networks than in random graphs, and that the rate at which the spreading proceeds on scale-free networks is further increased when assortative degree correlations are introduced. The impact of degree correlations on the final fraction of nodes that ever hears a rumour, however, depends on the interplay between network topology and the rumour spreading rate. Our results show that scale-free social networks are prone to the spreading of rumours, just as they are to the spreading of infections. They are relevant to the spreading dynamics of chain emails, viral advertising and large-scale information dissemination algorithms on the Internet.     

Duplication： a Mechanism Producing Disassortative Mixing Networks in Biology

Assortative/disassortative mixing is an important topological property of a network. A network is called assortative mixing if the nodes in the network tend to connect to their connectivity peers, or disassortative mixing if nodes with low degrees are more likely to connect with high-degree nodes. We have known that biological networks such as protein-protein interaction networks （PPI）, gene regulatory networks, and metabolic networks tend to be disassortative. On the other hand, in biological evolution, duplication and divergence are two fundamental processes. In order to make the relationship between the property of disassortative mixing and the two basic biological principles clear and to study the cause of the disassortative mixing property in biological networks, we present a random duplication model and an anti-preference duplication model. Our results show that disassortative mixing networks can be obtained by both kinds of models from uncorrelated initial networks. Moreover, with the growth of the network size, the disassortative mixing property becomes more obvious.     

Scaling of mean first-passage time as efficiency measure of nodes sending information on scale-free Koch networks

Random walks on complex networks, especially scale-free networks, have attracted considerable interest in the past few years. A lot of previous work showed that the average receiving time (ART), i.e., the average of mean first-passage time (MFPT) for random walks to a given hub node (node with maximum degree) averaged over all starting points in scale-free small-world networks exhibits a sublinear or linear dependence on network order N (number of nodes), which indicates that hub nodes are very efficient in receiving information if one looks upon the random walker as an information messenger. Thus far, the efficiency of a hub node sending information on scale-free small-world networks has not been addressed yet. In this paper, we study random walks on the class of Koch networks with scale-free behavior and small-world effect. We derive some basic properties for random walks on the Koch network family, based on which we calculate analytically the average sending time (AST) defined as the average of MFPTs from a hub node to all other nodes, excluding the hub itself. The obtained closed-form expression displays that in large networks the AST grows with network order as N ln N, which is larger than the linear scaling of ART to the hub from other nodes. On the other hand, we also address the case with the information sender distributed uniformly among the Koch networks, and derive analytically the global mean first-passage time, namely, the average of MFPTs between all couples of nodes, the leading scaling of which is identical to that of AST. From the obtained results, we present that although hub nodes are more efficient for receiving information than other nodes, they display a qualitatively similar speed for sending information as non-hub nodes. Moreover, we show that that AST from a starting point (sender) to all possible targets is not sensitively affected by the sender’s location. The present findings are helpful for better understanding random walks performed on scale-free small-world networks.     

Breakdown of the internet under intentional attack

We study the tolerance of random networks to intentional attack, whereby a fraction p of the most connected sites is removed. We focus on scale-free networks, having connectivity distribution P(k) approximately k(-alpha), and use percolation theory to study analytically and numerically the critical fraction p(c) needed for the disintegration of the network, as well as the size of the largest connected cluster. We find that even networks with alpha < or = 3, known to be resilient to random removal of sites, are sensitive to intentional attack. We also argue that, near criticality, the average distance between sites in the spanning (largest) cluster scales with its mass, M, as square root of [M], rather than as log (k)M, as expected for random networks away from criticality.     

具有幂率度分布的因特网平均最短路径长度估计

针对具有幂律度分布的复杂网络的平均最短路径长度进行了研究.给出了一个计算因特网平 均最短路径长度的公式.提出因特网的整体构造实质是以最小代价换取最大收益，从此出 发通过对因特网这类复杂网络平均最短路径长度影响因素分析，推断出网络最短路径长度分 布P(l)的基本性质，进而构造了一个只含参数α的P(l)的简洁形式，直接打通了拓扑具有幂 律度分布的因特网的度分布P(k)与网络最短路径长度分布P(l)之间的关系.然后说明了导出 的公式的物理意义，即参数α代表网络节点连接方式和网络的总边数对平均最短路径长 度的影响.此公式意味着只要掌握幂律P(k)～k-α中α值，就可以直接计算相应网 络的平均最短路径长度.通过对已知数据的计算，验证了公式的有效性.阐明了参数 α对网络设计的重要性和对网络功能的影响. 关键词： 复杂网络 幂律 度分布 平均最短路径长度     

虚拟社区网络的演化过程研究

模拟了虚拟社区网络的演化过程并研究其拓扑结构.发现虚拟社区网络在演化过程中,节点的加入、边的加入、网络中度分布、节点的度与其加入网络时间的关系、平均度随时间的变化等方面与传统的无标度网络有所不符.根据国内某论坛的实际网络数据统计与分析,提出了虚拟社区网络的演化机理——虚拟社区网络构造算法.仿真结果表明,模拟以互联网论坛为代表的虚拟社区网络时,该模型能够得到与真实网络相符的特性. 关键词： 复杂网络 虚拟社区 无标度网络     

Quantum Key Distribution in Large Scale Quantum Network Assisted by Classical Routing Information

Recently, small-scale Quantum Key Distribution (QKD) networks have been demonstrated and continuously operated in field environment. However, nodes of these QKD networks are less than 10 nodes. When the scale and structure of these networks becomes large and complex, such networks will subject to problem of intractable routing selection and limited transmission distance. We present a novel quantum network model and the corresponding protocol to solve these problems. The proposed quantum network model integrates classical communication network with quantum key distribution layer. Nodes in this quantum network model are divided into communication nodes for classical communication and quantum nodes for quantum key distribution. We use atomic ensembles to create entangled photons inside quantum nodes. Quantum repeaters are used to establish entanglement between remote quantum nodes so the maximum distribution distance of entangled photons can be extended. The main idea is to establish an appropriate key distribution path in the quantum key distribution layer based on the routing information obtained by the upper classical communication network. After the entanglement has been established between remote quantum nodes, these nodes will use the Ekert91 or BBM92 protocol to generate secret keys shared between each other. Then, these keys can be used to ensure the security of communication in the classical communication network.     

Extracting hidden fluctuation patterns of Hang Seng stock index from network topologies

We present a model of complex network generated from Hang Seng index (HSI) of Hong Kong stock market, which encodes stock market relevant both interconnections and interactions between fluctuation patterns of HSI in the network topologies. In the network, the nodes (edges) represent all kinds of patterns of HSI fluctuation (their interconnections). Based on network topological statistic, we present efficient algorithms, measuring betweenness centrality (BC) and inverse participation ratio (IPR) of network adjacency matrix, for detecting topological important nodes. We have at least obtained three uniform nodes of topological importance, and find the three nodes, i.e. 18.7% nodes undertake 71.9% betweenness centrality and closely correlate other nodes. From these topological important nodes, we can extract hidden significant fluctuation patterns of HSI. We also find these patterns are independent the time intervals scales. The results contain important physical implication, i.e. the significant patterns play much more important roles in both information control and transport of stock market, and should be useful for us to more understand fluctuations regularity of stock market index. Moreover, we could conclude that Hong Kong stock market, rather than a random system, is statistically stable, by comparison to random networks.