Comparison of immunization strategies in geographical networks

The epidemic spread and immunizations in geographically embedded scale-free (SF) and Watts-Strogatz (WS) networks are numerically investigated. We make a realistic assumption that it takes time which we call the detection time, for a vertex to be identified as infected, and implement two different immunization strategies: one is based on connection neighbors (CN) of the infected vertex with the exact information of the network structure utilized and the other is based on spatial neighbors (SN) with only geographical distances taken into account. We find that the decrease of the detection time is crucial for a successful immunization in general. Simulation results show that for both SF networks and WS networks, the SN strategy always performs better than the CN strategy, especially for more heterogeneous SF networks at long detection time. The observation is verified by checking the number of the infected nodes being immunized. We found that in geographical space, the distance preferences in the network construction process and the geographically decaying infection rate are key factors that make the SN immunization strategy outperforms the CN strategy. It indicates that even in the absence of the full knowledge of network connectivity we can still stop the epidemic spread efficiently only by using geographical information as in the SN strategy, which may have potential applications for preventing the real epidemic spread.     

Imperfect targeted immunization in scale-free networks

Scale-free networks are prone to epidemic spreading. To provide cost-effective protection for such networks, targeted immunization was proposed to selectively immunize the hub nodes. In many real-life applications, however, the targeted immunization may not be perfect, either because some hub nodes are hidden and consequently not immunized, or because the vaccination simply cannot provide perfect protection. We investigate the effects of imperfect targeted immunization in scale-free networks. Analysis and simulation results show that there exists a linear relationship between the inverse of the epidemic threshold and the effectiveness of targeted immunization. Therefore, the probability of epidemic outbreak cannot be significantly lowered unless the protection is reasonably strong. On the other hand, even a relatively weak protection over the hub nodes significantly decreases the number of network nodes ever getting infected and therefore enhances network robustness against virus. We show that the above conclusions remain valid where there exists a negative correlation between nodal degree and infectiousness.     

Choosing effective controlled nodes for scale-free network synchronization

Previous studies concerning pinning control of complex-network synchronization have very often demonstrated that in an unweighted symmetrical scale-free network, controlling the high-degree nodes is more efficient than controlling randomly chosen ones; due to the heterogeneity of the node-degree or edge-connection distribution of the scale-free network, small-degree nodes have relatively high probabilities of being chosen at random but their control has less influence on the other nodes through the network. This raises the question of whether or not controlling the high-degree nodes is always better than controlling the small ones in scale-free networks. Our answer to this is yes and no. In this study, we carry out extensive numerical simulations to show that in an unweighted symmetrical Barabasi-Albert scale-free network, when the portion of controlled nodes is relatively large, controlling the small nodes becomes better than controlling the big nodes and controlling randomly chosen nodes has approximately the same effect as controlling the big ones. However, we also show that for normalized weighted scale-free networks, controlling the big nodes is in fact always better than controlling the small ones.     

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

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

Adaptive synchronization of weighted complex dynamical networks through pinning

This paper considers the problem of controlling weighted complex dynamical networks by applying adaptive control to a fraction of network nodes. We investigate the local and global synchronization of the controlled dynamical network through the construction of a master stability function and a Lyapunov function. Analytical results show that a certain number of nodes can be controlled by using adaptive pinning to ensure the synchronization of the entire network. We present numerical simulations to verify the effectiveness of the proposed scheme. In comparison with feedback pinning, the proposed pinning control scheme is robust when tested by noise, different weighting and coupling structures, and time delays.     

Controlling a complex dynamical network to attain an inhomogeneous equilibrium

Many networks are made up of a few groups, with nodes in the same group having the same kind of function. In this work, the problem of controlling a complex dynamical network to attain an inhomogeneous equilibrium point is investigated, which means that nodes in the same group achieve the same equilibrium point as an isolated node, while different groups correspond to different equilibrium points. An open-loop constant control approach is first proposed to obtain the inhomogeneous equilibrium point of the network. Then, the feedback pinning control approach is applied to make the inhomogeneous equilibrium point asymptotically stable.     

基于传播免疫的复杂网络可控性研究

复杂网络控制反映了人类对复杂系统的认识深度和改造能力. 最新研究成果基于线性系统控制理论建立了复杂网络可控性的理论架构, 能够发现任意拓扑结构的线性时不变复杂网络中控制全部节点状态的最小驱动节点集, 但是该模型未考虑免疫节点或失效节点对控制信号传播的阻断.在继承该模型优点的前提下, 重新构建了基于传播免疫的复杂网络控制模型.在采用分属于随机免疫和目标免疫两种策略的 4个方法确定免疫节点的情况下,分析14个真实网络的可控性.结果表明:如果将网络中度数、 介数和紧密度指标较高的节点作为免疫节点,将极大地提高控制复杂网络的难度. 从而在一定程度上丰富了以往模型的结论.     

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.     

Pinning control of weighted general complex dynamical networks with time delay

Time delays commonly exist in the real world. In the present work we consider weighted general complex dynamical networks with time delay, which are undirected and connected. Control of such networks, by applying local feedback injections to a fraction of network nodes, is investigated for both continuous-time and discrete-time cases. Both delay-independent and delay-dependent asymptotical stability criteria for network stabilization are derived. It is also shown that the whole network can be stabilized by controlling only one node. The efficiency of the derived results was illustrated by numerical examples.     

Cost and effect of pinning control for network synchronization

The problem of pinning control for the synchronization of complex dynamical networks is discussed in this paper. A cost function of the controlled network is defined by the feedback gain and the coupling strength of the network. An interesting result is that a lower cost is achieved by using the control scheme of pinning nodes with smaller degrees. Some strict mathematical analyses are presented for achieving a lower cost in the synchronization of different star-shaped networks. Numerical simulations on some non-regular complex networks generated by the Barabási--Albert model and various star-shaped networks are performed for verification and illustration.     

An Efficient Control Strategy of Epidemic Spreading on Scale-Free Networks

We present a novel and effective method for controlling epidemic spreading on complex networks, especially on scale-free networks. The proposed strategy is performed by deleting edges according to their significances （the significance of an edge is defined as the product of the degrees of two nodes of this edge）. In contrast to other methods, e.g., random immunization, proportional immunization, targeted immunization, acquaintance immunization and so on, which mainly focus on how to delete nodes to realize the control of epidemic spreading on complex networks, our method is more effective in realizing the control of epidemic spreading on complex networks, moreover, such a method can better retain the integrity of complex networks.     

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

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

利用邻域“结构洞”寻找社会网络中最具影响力节点

识别复杂网络中的关键节点对网络结构优化和鲁棒性增强具有十分重要的意义. 经典的关键节点测量方法在一定程度上能够辨识网络中影响力节点, 但存在一定局限性: 局部中心性测量方法仅考虑节点邻居的数目, 忽略了邻居间的拓扑关系, 不能在计算中反映邻居节点间的相互作用; 全局测量方法则由于算法本身的复杂性而不能应用于大规模社会网络的分析, 另外, 经典的关键节点测量方法也没有考虑社会网络特有的社区特征. 为高效、准确地辨识具有社区结构的社会网络中最具影响力节点, 提出了一种基于节点及其邻域结构洞的局部中心性测量方法, 该方法综合考虑了节点的邻居数量及其与邻居间的拓扑结构, 在节点约束系数的计算中同时体现了节点的度属性和“桥接”属性. 利用SIR(易感-感染-免疫)模型在真实社会网络数据上对节点传播能力进行评价后发现, 所提方法可以准确地评价节点的传播能力且具有强的鲁棒性.     

基于复杂网络理论的微博用户关系网络演化模型研究

微博给人们提供便利的同时也产生了较大的负面影响.为获取微博谣言的传播规律,进而采取有效措施防控其传播,本文基于复杂网络理论研究微博用户关系网络的内部特征,提出一种微博用户关系网络演化模型,借助于平均场理论,分析该演化模型的拓扑统计特性,以及谣言在该演化模型上的传播动力学行为.理论分析和仿真实验表明,由该模型演化生成的微博用户关系网络具有无标度特性.度分布指数不仅与反向连接概率有关,而且还取决于节点的吸引度分布.研究还发现,与指数分布和均匀分布相比,当节点吸引度满足幂律分布时,稳态时的谣言传播程度较大.此外,随着反向连接概率或节点初始连边数量的增加,谣言爆发的概率以及网络中最终接受谣言的节点数量都会明显增大.     

The spreading of opposite opinions on online social networks with authoritative nodes

The study of opinion dynamics, such as spreading and controlling of rumors, has become an important issue on social networks. Numerous models have been devised to describe this process, including epidemic models and spin models, which mainly focus on how opinions spread and interact with each other, respectively. In this paper, we propose a model that combines the spreading stage and the interaction stage for opinions to illustrate the process of dispelling a rumor. Moreover, we set up authoritative nodes, which disseminate positive opinion to counterbalance the negative opinion prevailing on online social networking sites. With analysis of the relationship among positive opinion proportion, opinion strength and the density of authoritative nodes in networks with different topologies, we demonstrate that the positive opinion proportion grows with the density of authoritative nodes until the positive opinion prevails in the entire network. In particular, the relationship is linear in homogeneous topologies. Besides, it is also noteworthy that initial locations of the negative opinion source and authoritative nodes do not influence positive opinion proportion in homogeneous networks but have a significant impact on heterogeneous networks. The results are verified by numerical simulations and are helpful to understand the mechanism of two different opinions interacting with each other on online social networking sites.     

Feedback arcs and node hierarchy in directed networks

Directed networks such as gene regulation networks and neural networks are connected by arcs(directed links). The nodes in a directed network are often strongly interwound by a huge number of directed cycles, which leads to complex information-processing dynamics in the network and makes it highly challenging to infer the intrinsic direction of information flow. In this theoretical paper, based on the principle of minimum-feedback, we explore the node hierarchy of directed networks and distinguish feedforward and feedback arcs. Nearly optimal node hierarchy solutions, which minimize the number of feedback arcs from lower-level nodes to higher-level nodes, are constructed by belief-propagation and simulated-annealing methods. For real-world networks, we quantify the extent of feedback scarcity by comparison with the ensemble of direction-randomized networks and identify the most important feedback arcs. Our methods are also useful for visualizing directed networks.     

Adaptive bridge control strategy for opinion evolution on social networks

In this paper, we present an efficient opinion control strategy for complex networks, in particular, for social networks. The proposed adaptive bridge control (ABC) strategy calls for controlling a special kind of nodes named bridge and requires no knowledge of the node degrees or any other global or local knowledge, which are necessary for some other immunization strategies including targeted immunization and acquaintance immunization. We study the efficiency of the proposed ABC strategy on random networks, small-world networks, scale-free networks, and the random networks adjusted by the edge exchanging method. Our results show that the proposed ABC strategy is efficient for all of these four kinds of networks. Through an adjusting clustering coefficient by the edge exchanging method, it is found out that the efficiency of our ABC strategy is closely related with the clustering coefficient. The main contributions of this paper can be listed as follows: (1) A new high-order social network is proposed to describe opinion dynamic. (2) An algorithm, which does not require the knowledge of the nodes' degree and other global∕local network structure information, is proposed to control the "bridges" more accurately and further control the opinion dynamics of the social networks. The efficiency of our ABC strategy is illustrated by numerical examples. (3) The numerical results indicate that our ABC strategy is more efficient for networks with higher clustering coefficient.     

激光局域网络的混沌控制及并行队列同步

本文提出并研究了"单队列-双参数"光电延时反馈控制条件下的激光局域网络的混沌控制及串联的动力学行为的并行队列"交叉驱动-反馈"网络同步实现,建立了该光学局域网络的数学物理控制模型.通过含时延超越方程理论的分析,预言了该光学局域网络是可以实现混沌控制的,且网络两路结点队列是可以实现实时引导控制到多个类周期状态上的,并通过并行队列同步方程理论证明并行串联队列同步是可以获得的.结果发现在可控的激光局域网络两个并行串联队列光路上,分别实现了网络队列结点的混沌控制并能够实现多个类周期的网络结点的并行串联队列同步,实现了络网结点激光器的2周期、3周期、4周期等状态的并行队列同步,以及其他多个类周期的队列并行同步和动态同步.还发现了两个类周期并行队列网络同步控制区域.本文还给出了激光局域网络"并行多点混沌载波同步发射及其在光学超宽带通信中应用"的一个案例并成功实现.这是一种新型的激光混沌局域网络控制系统,具有光局域网络光传送与光联接核心控制技术要素,具有复杂动力学系统与网络的多变量、多空间维度及并行两路不同队列混沌控制技术特点,还具有光网络超宽带通信功能等.其研究结果对局域网络、光网络的控制与同步、激光技术以及混沌的研究具有重要的参考价值.     

面向成本-收益好的无标度耦合网络构建方法

较大平均路径长度的网络会带来较大的网络延迟, 难以支持时间敏感业务与应用. 通过增加连接可以降低源和目的节点之间的跳数, 进而降低网络平均延迟, 使得更加快速地传播信息, 但是增加连接的同时也增加了网络构建成本. 分层网络是研究网络耦合的一个有效方法, 但目前网络构建过程中将每层网络分别处理并认为每层网络之间没有强相关性. 本文提出了一种面向成本-收益的无标度网络动态构建方法. 此方法将网络分为多层, 基于连续论在高层网络中添加连接, 使得网络演化为无标度网络. 此连续过程包括节点度增加过程和局部网络半径增长两个连续过程, 在增加连接的过程中引入表征网络构建成本和收益的成本-收益指标. 模拟结果表明引入成本-收益指标的无标度耦合网络构建方法能够在合理范围内有效降低网络平均路径长度, 提升网络性能, 并且本文给出了耦合网络的动态业务性能, 通过调整高层网络避免网络拥塞.     

Rapid self-organised initiation of ad hoc sensor networks close above the percolation threshold

This work shows potentials for rapid self-organisation of sensor networks where nodes collaborate to relay messages to a common data collecting unit (sink node). The study problem is, in the sense of graph theory, to find a shortest path tree spanning a weighted graph. This is a well-studied problem where for example Dijkstra’s algorithm provides a solution for non-negative edge weights. The present contribution shows by simulation examples that simple modifications of known distributed approaches here can provide significant improvements in performance. Phase transition phenomena, which are known to take place in networks close to percolation thresholds, may explain these observations. An initial method, which here serves as reference, assumes the sink node starts organisation of the network (tree) by transmitting a control message advertising its availability for its neighbours. These neighbours then advertise their current cost estimate for routing a message to the sink. A node which in this way receives a message implying an improved route to the sink, advertises its new finding and remembers which neighbouring node the message came from. This activity proceeds until there are no more improvements to advertise to neighbours. The result is a tree network for cost effective transmission of messages to the sink (root). This distributed approach has potential for simple improvements which are of interest when minimisation of storage and communication of network information are a concern. Fast organisation of the network takes place when the number k of connections for each node (degree) is close above its critical value for global network percolation and at the same time there is a threshold for the nodes to decide to advertise network route updates.