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

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

Immunization of real complex communication networks

Most communication networks are complex. In this paper, we address one of the fundamental problems we are facing nowadays, namely, how we can efficiently protect these networks. To this end, we study an immunization strategy and found that it works almost as good as targeted immunization, but using only local information about the network topology. Our findings are supported with numerical simulations of the Susceptible-Infected-Removed (SIR) model on top of real communication networks, where immune nodes are previously identified by a covering algorithm. The results provide useful hints in the way to designing and deploying a digital immune system.     

Modelling the spread of sexually transmitted diseases on scale-free networks

In this paper a new model for the spread of sexually transmitted diseases (STDs) is presented. The dynamic behaviors of the model on a heterogenous scale-free (SF) network are considered, where the absence of a threshold on the SF network is demonstrated, and the stability of the disease-free equilibrium is obtained. Three immunization strategies, uniform immunization, proportional immunization and targeted immunization, are applied in this model. Analytical and simulated results are given to show that the proportional immunization strategy in the model is effective on SF networks.     

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

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

An improved local immunization strategy for scale-free networks with a high degree of clustering

The design of immunization strategies is an extremely important issue for disease or computer virus control and prevention. In this paper, we propose an improved local immunization strategy based on node’s clustering which was seldom considered in the existing immunization strategies. The main aim of the proposed strategy is to iteratively immunize the node which has a high connectivity and a low clustering coefficient. To validate the effectiveness of our strategy, we compare it with two typical local immunization strategies on both real and artificial networks with a high degree of clustering. Simulations on these networks demonstrate that the performance of our strategy is superior to that of two typical strategies. The proposed strategy can be regarded as a compromise between computational complexity and immune effect, which can be widely applied in scale-free networks of high clustering, such as social network, technological networks and so on. In addition, this study provides useful hints for designing optimal immunization strategy for specific network.     

Efficient immunization strategies for computer networks and populations

We present an effective immunization strategy for computer networks and populations with broad and, in particular, scale-free degree distributions. The proposed strategy, acquaintance immunization, calls for the immunization of random acquaintances of random nodes (individuals). The strategy requires no knowledge of the node degrees or any other global knowledge, as do targeted immunization strategies. We study analytically the critical threshold for complete immunization. We also study the strategy with respect to the susceptible-infected-removed epidemiological model. We show that the immunization threshold is dramatically reduced with the suggested strategy, for all studied cases.     

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.     

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.     

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.     

复杂网络的顶点着色及其在疾病免疫中的应用

在复杂网络研究中, 对于网络结构特征的分析已经引起了人们的极大关注, 而其中的网络着色问题却没有得到足够的重视. 为了理解网络结构与着色之间的关系, 本文研究了WS, BA网络以及不同宏观结构参量对于正常K色数的影响, 发现最大团数可以大致反映正常K色数的变化趋势, 而网络的平均度和匹配系数比异质性和聚类系数对于色数的影响更大. 对于一些实际网络的正常着色验证了本文的分析结果. 对复杂网络的顶点进行着色后, 根据独立集内任意两个顶点均不相邻的特点, 我们提出了基于独立集的免疫策略. 与全网随机免疫相比, 基于独立集的免疫策略可令网络更为脆弱, 从而有效抑制疾病的传播. 基于网络着色的独立集提供了一种崭新的免疫思路, 作为一个简单而适用的平台,有助于设计更为有效的免疫策略. 关键词： 复杂网络 正常着色 独立集 免疫策略     

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.     

考虑谣言清除过程的网络谣言传播与抑制

网络谣言传播是网络传播动力学的重要课题之一. 网络谣言传播常常同时混杂谣言感染和谣言清除两个过程, 对这一现象的分析可以帮助我们更好地认识社会网络中的信息传播. 本文在susceptible-infective-refractory谣言传播模型的基础上增加谣言清除者, 定义了谣言感染和谣言清除的规则, 提出SIERsEs谣言传播模型, 建立了模型的平均场方程, 从理论上分析了谣言传播的稳态, 并求解出谣言传播的感染阈值和清除阈值. 仿真计算分析了感染和清除过程同时作用时, 感染率、清除率和网络平均度对谣言传播的影响. 研究发现, 网络平均度过小或过大, 谣言传播稳定后的影响力都将处于低水平. 分析了目标免疫和熟人免疫等传统免疫策略的不足, 针对网络环境下谣言抑制的特点, 提出主动免疫和被动免疫两种网络谣言免疫策略, 并研究了传播者遗忘率、清除者遗忘率和开始免疫时间参数对这两种谣言免疫策略有效性的影响. 需要重视的是: 研究发现一些直观看来有效的谣言抑制措施反而可能提高谣言的影响力. 研究结果有助于深化对于网络传播动力学的理解, 同时为发展有效的网络谣言抑制策略提供新的思路.     

Immunization of susceptible-infected model on scale-free networks

In this paper, we investigate two major immunization strategies, random immunization and targeted immunization, of the susceptible-infected (SI) model on the Barabási-Albert (BA) networks. For the heterogeneous structure, the random strategy is quite ineffective if the vaccinated proportion is small, while the targeted one which prefers to vaccinate the individuals with the largest degree can sharply depress the epidemic spreading even only a tiny fraction of population are vaccinated. The analytical solution is also obtained, which can capture the trend of velocity change vs. the amount of vaccinated population.     

The most common friend first immunization

In this paper, a standard susceptible-infected-recovered-susceptible(SIRS) epidemic model based on the Watts–Strogatz(WS) small-world network model and the Barabsi–Albert(BA) scale-free network model is established, and a new immunization scheme — "the most common friend first immunization" is proposed, in which the most common friend's node is described as being the first immune on the second layer protection of complex networks. The propagation situations of three different immunization schemes — random immunization, high-risk immunization, and the most common friend first immunization are studied. At the same time, the dynamic behaviors are also studied on the WS small-world and the BA scale-free network. Moreover, the analytic and simulated results indicate that the immune effect of the most common friend first immunization is better than random immunization, but slightly worse than high-risk immunization. However,high-risk immunization still has some limitations. For example, it is difficult to accurately define who a direct neighbor in the life is. Compared with the traditional immunization strategies having some shortcomings, the most common friend first immunization is effective, and it is nicely consistent with the actual situation.     

Controlling self-organized criticality in complex networks

A control scheme to reduce the size of avalanches of the Bak-Tang-Wiesenfeld model on complex networks is proposed. Three network types are considered: those proposed by Erdős-Renyi, Goh-Kahng-Kim, and a real network representing the main connections of the electrical power grid of the western United States. The control scheme is based on the idea of triggering avalanches in the highest degree nodes that are near to become critical. We show that this strategy works in the sense that the dissipation of mass occurs most locally avoiding larger avalanches. We also compare this strategy with a random strategy where the nodes are chosen randomly. Although the random control has some ability to reduce the probability of large avalanches, its performance is much worse than the one based on the choice of the highest degree nodes. Finally, we argue that the ability of the proposed control scheme is related to its ability to reduce the concentration of mass on the network.     

Global forward-predicting dynamic routing for traffic concurrency space stereo multi-layer scale-free network

Many real communication networks, such as oceanic monitoring network and land environment observation network,can be described as space stereo multi-layer structure, and the traffic in these networks is concurrent. Understanding how traffic dynamics depend on these real communication networks and finding an effective routing strategy that can fit the circumstance of traffic concurrency and enhance the network performance are necessary. In this light, we propose a traffic model for space stereo multi-layer complex network and introduce two kinds of global forward-predicting dynamic routing strategies, global forward-predicting hybrid minimum queue(HMQ) routing strategy and global forward-predicting hybrid minimum degree and queue(HMDQ) routing strategy, for traffic concurrency space stereo multi-layer scale-free networks. By applying forward-predicting strategy, the proposed routing strategies achieve better performances in traffic concurrency space stereo multi-layer scale-free networks. Compared with the efficient routing strategy and global dynamic routing strategy, HMDQ and HMQ routing strategies can optimize the traffic distribution, alleviate the number of congested packets effectively and reach much higher network capacity.     

可变聚类无标度网络上的谣言免疫策略

提出一种聚类免疫策略,使用改进的经典谣言传播模型,在可变聚类无标度网络上研究其免疫效果.研究发现,聚类免疫的效果随着网络聚类系数的增加而变好.在不同聚类系数下,比较目标免疫、介数免疫、紧密度免疫和聚类免疫的免疫效果发现,无论网络的聚类特性如何,介数免疫始终是几种免疫策略中效果最好的,当网络聚类系数较大时,聚类免疫的效果超过紧密度免疫接近目标免疫,进一步增大网络的聚类系数,聚类免疫的效果超过目标免疫而接近介数免疫.     

Immunization and epidemic dynamics in complex networks

We study the behavior of epidemic spreading in networks, and, in particular, scale free networks. We use the Susceptible-Infected-Removed (SIR) epidemiological model. We give simulation results for the dynamics of epidemic spreading. By mapping the model into a static bond-percolation model we derive analytical results for the total number of infected individuals. We study this model with various immunization strategies, including random, targeted and acquaintance immunization.Received: 3 November 2003, Published online: 14 May 2004PACS: 02.50.Cw Probability theory - 02.10.Ox Combinatorics; graph theory - 89.20.Hh World Wide Web, Internet - 64.60.-i General studies of phase transitions     

Eigenvector Localization in Real Networks and Its Implications for Epidemic Spreading

The spectral properties of the adjacency matrix, in particular its largest eigenvalue and the associated principal eigenvector, dominate many structural and dynamical properties of complex networks. Here we focus on the localization properties of the principal eigenvector in real networks. We show that in most cases it is either localized on the star defined by the node with largest degree (hub) and its nearest neighbors, or on the densely connected subgraph defined by the maximum K-core in a K-core decomposition. The localization of the principal eigenvector is often strongly correlated with the value of the largest eigenvalue, which is given by the local eigenvalue of the corresponding localization subgraph, but different scenarios sometimes occur. We additionally show that simple targeted immunization strategies for epidemic spreading are extremely sensitive to the actual localization set.

     

The effect of TTL on the information traffic

In real communication protocols, the information packets have a finite Time-to-Live (TTL) to avoid the waste of network resources, such as infinite loop induced by routing error or too long transferring time. In this paper, we introduce TTL into the information traffic model on Barabási-Albert scale-free networks under local routing strategy and focus on its effect on the network capacity measured by the critical point (R_c) of phase transition from free flow to congestion. Simulations show that the network capacity and the communication velocity are improved. However, some packets are dropped before they arrived at destinations. It is found that the share of successfully arrived packets monotonously increases with the increment of TTL and it is considerably acceptable if TTL is not very small. We also examine the effect of TTL on the positive-feedback preference (PFP) internet model and the results are alike. Our work may be helpful in quantifying the effect of packet lifetime in real communication networks and in routing strategy designing.