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.     

推荐重要节点部署防御策略的优化模型

当前网络安全防御策略集中部署于高连接度节点主要有2个方面的不足: 一是高连接度节点在很多场合中并不是网络通信的骨干节点; 二是该类节点对信息的转发和传播并非总是最有效的.针对以上传统部署策略的不足, 改进了恶意病毒程序传播的离散扩散模型并采用中间路径跳数来衡量网络节点的重要程度, 提出了基于介数中心控制力和接近中心控制力模型的重要节点优先推荐部署技术.实验结果显示具有高介数中心控制力和低接近中心控制力的节点相对于传统的高连接度节点无论在无标度网络还是小世界网络均能够对恶意病毒程序的疫情扩散和早期传播速度起到更加有效的抑制作用, 同时验证了网络分簇聚类行为产生的簇团特性也将对恶意程序的传播起到一定的负面影响.     

基于低阶矩阵最大特征值的复杂网络牵制混沌同步

虽已对复杂网络牵制同步需要牵制结点数量及牵制结点数量与耦合强度的关系进行了研究,然而快速计算牵制结点数量仍是大规模复杂网络面临的一个重要问题.研究发现了复杂网络耦合矩阵主子阵最大值递减规律,由此提出了快速计算复杂网络牵制结点数量的方法,揭示了不同的牵制策略与牵制结点数量之间的关系.数值仿真显示了在无标度网络和小世界网络上三种不同的牵制策略下,牵制结点数与主子阵最大特征值的变化规律;最后给出了一个在无标度网络上采用随机选择结点策略的牵制同步实例.     

Connectivity recovery of multi-agent systems based on connecting neighbor set

This paper investigates robust and fast consensus of multi-agent systems subject to external attacks. The strategy of connecting neighbor set is proposed to recover the connectivity of the resulting interconnected network, to improve the robustness against next external attacks, and to guarantee the fast consensus of the resulting multi-agent systems. Two strategies are provided to optimize the robustness against next external attacks and the convergence speed of achieving consensus, respectively. Meanwhile it turns out that there exists a trade-off between improving the robustness against next external attacks and enhancing the convergence speed of achieving consensus. Several simulations are provided to demonstrate the effectiveness of the theoretical results.     

A preliminary investigation on the topology of Chinese and climate networks

Complex networks have been studied across many fields of science in recent years. In this paper, we give a brief introduction of networks, then follow the original works by Tsonis et al (2004, 2006) starting with data of the surface temperature from 160 Chinese weather observations to investigate the topology of Chinese climate networks. Results show that the Chinese climate network exhibits a characteristic of regular, almost fully connected networks, which means that most nodes in this case have the same number of links, and so-called super nodes with a very large number of links do not exist there. In other words, though former results show that nodes in the extratropical region provide a property of scale-free networks, they still have other different local fine structures inside. We also detect the community of the Chinese climate network by using a Bayesian technique; the effective number of communities of the Chinese climate network is about four in this network. More importantly, this technique approaches results in divisions which have connections with physics and dynamics; the division into communities may highlight the aspects of the dynamics of climate variability.     

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.     

Finding a better immunization strategy

The problem of finding the best strategy to immunize a population or a computer network with a minimal number of immunization doses is of current interest. It has been accepted that the targeted strategies on most central nodes are most efficient for model and real networks. We present a newly developed graph-partitioning strategy which requires 5% to 50% fewer immunization doses compared to the targeted strategy and achieves the same degree of immunization of the network. We explicitly demonstrate the effectiveness of our proposed strategy on several model networks and also on real networks.     

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.     

具有双重时滞的时变耦合复杂网络的牵制外同步研究

针对同时具有节点时滞和耦合时滞的时变耦合复杂网络的外同步问题, 提出一种简单有效的自适应牵制控制方法. 首先构建一种贴近实际的驱动-响应复杂网络模型, 在模型中引入双重时滞和时变不对称外部耦合矩阵. 进一步设计易于实现的自适应牵制控制器, 对网络中的一部分关键节点进行控制. 构造适当的Lyapunov泛函, 利用 LaSalle不变集原理和线性矩阵不等式, 给出两个复杂网络实现外同步的充分条件. 最后, 仿真结果表明所提同步方法的有效性, 同时揭示耦合时滞对同步收敛速度的影响.     

Effective vaccination strategies for realistic social networks

We consider the effectiveness of targeted vaccination at preventing the spread of infectious disease in a realistic social network. We compare vaccination strategies based on no information (random vaccination) to complete information (PageRank) about the network. The most effective strategy we find is to vaccinate those people with the most unvaccinated contacts. However, this strategy requires considerable information and computational effort which may not be practical. The next best strategies vaccinate people with many contacts who in turn have few contacts.     

Trajectory Control of Scale-Free Dynamical Networks with Exogenous Disturbances

In this paper, the trajectory control of multi-agent dynamical systems with exogenous disturbances is studied. Suppose multiple agents composing of a scale-free network topology, the performance of rejecting disturbances for the low degree node and high degree node is analyzed. Firstly, the consensus of multi-agent systems without disturbances is studied by designing a pinning control strategy on a part of agents, where this pinning control can bring multiple agents' states to an expected consensus track. Then, theinfluence of the disturbances is considered by developing disturbance observers, and disturbance observers based control (DOBC) are developed for disturbances generated by an exogenous system to estimate the disturbances. Asymptotical consensus of the multi-agent systems with disturbances under the composite controller can be achieved for scale-free network topology. Finally, by analyzing examples of multi-agent systems with scale-free network topology and exogenous disturbances, the verities of the results are proved. Under the DOBC with the designed parameters, the trajectory convergence of multi-agent systems is researched by pinning two class of the nodes. We have found that it has more stronger robustness to exogenous disturbances for the high degree node pinned than that of the lowdegree node pinned.     

Incremental routing strategy on scale-free networks

The most important function of a network is for transporting traffic. Due to the low traffic capacity of network systems under the global shortest path routing, plenty of heuristic routing strategies are emerging. In this paper, we propose a heuristic routing strategy called the incremental routing algorithm to improve the traffic capacity of complex networks. We divide the routing process into N$N$(the network size) steps and, at each step, we heuristically calculate all the routes for one source node considering both the dynamic efficient betweenness centrality and node degree information. We do extensive simulations on scale-free networks to confirm the effectiveness of the proposed incremental routing strategy. The simulation results show that the traffic capacity has been enhanced by a substantial factor at the expense of a slight lengthening in the average path.     

An extended improved global structure model for influential node identification in complex networks

Accurate identification of influential nodes facilitates the control of rumor propagation and interrupts the spread of computer viruses. Many classical approaches have been proposed by researchers regarding different aspects. To explore the impact of location information in depth, this paper proposes an improved global structure model to characterize the influence of nodes. The method considers both the node's self-information and the role of the location information of neighboring nodes. First, degree centrality of each node is calculated, and then degree value of each node is used to represent self-influence, and degree values of the neighbor layer nodes are divided by the power of the path length, which is path attenuation used to represent global influence. Finally, an extended improved global structure model that considers the nearest neighbor information after combining self-influence and global influence is proposed to identify influential nodes. In this paper, the propagation process of a real network is obtained by simulation with the SIR model, and the effectiveness of the proposed method is verified from two aspects of discrimination and accuracy. The experimental results show that the proposed method is more accurate in identifying influential nodes than other comparative methods with multiple networks.     

Identifying influential waypoints in air route networks based on network agglomeration relative entropy

Air route network (ARN) is one of the most important transportation networks and the key waypoints (nodes) have significant influence on the stability and robustness of the ARN. In this paper, a network agglomeration relative entropy centrality (NAREC) method to identify influential nodes in ARNs is proposed, based on the network agglomeration and relative entropy theory. The basic topological features of the regional ARNs in Beijing, Shanghai and Guangzhou are analyzed and then the proposed method is applied to identifying influential nodes in the three networks. At last, the effectiveness of the NAREC method is demonstrated by the susceptible-infected-removed (SIR) model and the Kendall's tau coefficient. Results show that the proposed method is applicable and effective.     

复Ginzburg-Landau方程时空混沌的网络同步与参量辨识

研究了参量未知的时空混沌系统构成复杂网络的同步与参量辨识问题. 设计的参量辨识律可以有效地辨识复杂网络中所有节点时空混沌系统中的未知参量. 基于稳定性定理, 通过构造适当的Lyapunov函数, 确定了网络完全同步的条件. 以参量未知的一维复Ginzburg-Landau方程作为网络节点为例, 通过仿真模拟检验了参量辨识律以及同步方法的有效性.     

复杂网络牵制控制优化选点算法及节点组重要性排序

本文研究复杂网络动力学模型的无向网络牵制控制的优化选点及节点组重要性排序问题.根据牵制控制的同步准则,网络的牵制控制同步取决于网络的Laplacian删后矩阵的最小特征值.因此,通过合理选择受控节点集得到一个较大的Laplacian删后矩阵最小特征值,是牵制控制优化选点问题的核心所在.基于Laplacian删后矩阵最小特征值的图谱性质,本文提出了多个受控节点选取的递归迭代算法,该算法适用于任意类型的网络.通过BA无标度网络、NW小世界网络及一些实际网络中的仿真实验表明:该算法在控制节点数较少时,能有效找到最优受控节点集.最后讨论了在复杂网络牵制控制背景下节点组重要性排序问题,提出节点组的重要性排序与受控节点的数目有关.     

Studies on controllability of directed networks with extremal optimization

Almost all natural, social and man-made-engineered systems can be represented by a complex network to describe their dynamic behaviors. To make a real-world complex network controllable with its desired topology, the study on network controllability has been one of the most critical and attractive subjects for both network and control communities. In this paper, based on a given directed–weighted network with both state and control nodes, a novel optimization tool with extremal dynamics to generate an optimal network topology with minimum control nodes and complete controllability under Kalman’s rank condition has been developed. The experimental results on a number of popular benchmark networks show the proposed tool is effective to identify the minimum control nodes which are sufficient to guide the whole network’s dynamics and provide the evolution of network topology during the optimization process. We also find the conclusion: “the sparse networks need more control nodes than the dense, and the homogeneous networks need fewer control nodes compared to the heterogeneous” (Liu et al., 2011  [18]), is also applicable to network complete controllability. These findings help us to understand the network dynamics and make a real-world network under the desired control. Moreover, compared with the relevant research results on structural controllability with minimum driver nodes, the proposed solution methodology may also be applied to other constrained network optimization problems beyond complete controllability with minimum control nodes.     

考虑网络流量的无标度网络病毒免疫策略研究

考虑网络交通流量对病毒传播行为的影响,基于平均场理论研究无标度网络上的病毒免疫策略,提出一种改进的熟人免疫机理.理论分析表明,在考虑网络交通流量影响的情况下,当免疫节点密度较小时,随机免疫几乎不能降低病毒的传播速率,而对网络实施目标免疫则能够有效抑制病毒的传播,并且选择度最大的节点进行免疫与选择介数最大的节点进行免疫的效果基本相同.研究还发现,对于网络全局信息未知的情况,与经典熟人免疫策略相比,所提出的免疫策略能够获得更好的免疫效果.通过数值仿真对理论分析进行了验证. 关键词： 无标度网络 病毒传播 交通流量 免疫策略     

Synchronization of impulsively coupled complex systems with delay

This paper investigates the synchronization of complex systems with delay that are impulsively coupled at discrete instants only. Based on the comparison theorem of impulsive differential system, a distributed impulsive control scheme is proposed to achieve the synchronization for systems with delay. In the control strategy, the influence of all nodes to network synchronization relies on its weight. The proposed control scheme is applied to the chaotic delayed Hopfield neural networks and numerical simulations are presented to demonstrate the effectiveness of the proposed scheme.     

环形加权网络的时空混沌延迟同步

研究了环形加权网络的时空混沌延迟同步问题.以随时间和空间演化均呈现混沌行为的时空混沌系统作为网络的节点,通过环形加权连接使所有节点建立关联.基于线性稳定性定理,通过确定网络的最大Lyapunov指数,得到了实现网络延迟同步的条件.在最大Lyapunov指数小于零的区域内,任取节点之间耦合强度的权重值,均可以使整个网络实现延迟同步.采用具有时空混沌行为的自催化反应扩散系统作为网络节点,仿真模拟验证了该方法的有效性. 关键词： 延迟同步 加权网络 时空混沌 Lyapunov指数