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.     

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.     

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

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

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.     

Novel hybrid mitigation strategy for improving the resiliency of hierarchical networks subjected to attacks

This paper studies the resiliency of hierarchical networks when subjected to random errors, static attacks, and cascade attacks. The performance is compared with existing Erdös–Rényi (ER) random networks and Barabasi and Albert (BA) scale-free networks using global efficiency as the common performance metric. The results show that critical infrastructures modeled as hierarchical networks are intrinsically efficient and are resilient to random errors, however they are more vulnerable to targeted attacks than scale-free networks. Based on the response dynamics to different attack models, we propose a novel hybrid mitigation strategy that combines discrete levels of critical node reinforcement with additional edge augmentation. The proposed modified topology takes advantage of the high initial efficiency of the hierarchical network while also making it resilient to attacks. Experimental results show that when the level of damage inflicted on a critical node is low, the node reinforcement strategy is more effective, and as the level of damage increases, the additional edge augmentation is highly effective in maintaining the overall network resiliency.     

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.     

Immunization for scale-free networks by random walker

Based on the random walk and the intentional random walk, we propose two types of immunization strategies which require only local connectivity information. On several typical scale-free networks, we demonstrate that these strategies can lead to the eradication of the epidemic by immunizing a small fraction of the nodes in the networks. Particularly, the immunization strategy based on the intentional random walk is extremely efficient for the assortatively mixed networks.     

Clustering coefficient and community structure of bipartite networks

Many real-world networks display natural bipartite structure, where the basic cycle is a square. In this paper, with the similar consideration of standard clustering coefficient in binary networks, a definition of the clustering coefficient for bipartite networks based on the fraction of squares is proposed. In order to detect community structures in bipartite networks, two different edge clustering coefficients LC₄ and LC₃ of bipartite networks are defined, which are based on squares and triples respectively. With the algorithm of cutting the edge with the least clustering coefficient, communities in artificial and real world networks are identified. The results reveal that investigating bipartite networks based on the original structure can show the detailed properties that is helpful to get deep understanding about the networks.     

Evolutionary minority game on complex networks

In this work we investigate the dynamics of networked evolutionary minority game (NEMG) wherein each agent is allowed to evolve its strategy according to the information obtained from its neighbors in the network. We investigate four kinds of networks, including star network, regular network, random network and scale-free network. Simulation results indicate that the dynamics of the system depends crucially on the structure of the underlying network. The strategy distribution in a star network is sensitive to the precise value of the mutation magnitude L, in contrast to the strategy distribution in regular, random and scale-free networks, which is easily affected by the value of the prize-to-fine ratio R. Under a simple evolutionary scheme, the networked system with suitable parameters evolves to a high level of global coordination among its agents. In particular, the performance of the system is correlated to the clustering property of the network, where larger clustering coefficient leads to better performance.     

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

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

Generating random graphs with tunable clustering coefficients

Most real-world networks exhibit a high clustering coefficient—the probability that two neighbors of a node are also neighbors of each other. We propose two algorithms, Conf and Throw, that take triangle and single edge degree sequences as input and generate a random graph with a target clustering coefficient. We analyze them theoretically for the case of a regular graph. Conf generates a random graph with the input degree sequence and the clustering coefficient anticipated from the input. Experimental results match quite well with the anticipated clustering coefficient except for highly dense graphs, in which case the experimental clustering coefficient is higher than the anticipated value. For Throw, the degree sequence and the clustering coefficient of the generated graph varies from the input. However, it maintains the expected degree distribution, and the clustering coefficient of the generated graph can also be predicted using analytical results. Experiments show that, for Throw, the results match quite well with the analytical results. Typically, only information about degree distribution is available. We also propose an algorithm Deg that takes degree sequence and clustering coefficient as input and generates a graph with the same properties. Experiments show results for Deg that are quite similar to those for Conf.     

一种基于布朗粒子的混合搜索模型

基于网络上的布朗粒子运动基本原理,提出了一种单粒子和多粒子相结合的混合搜索模型.该模型将一次搜索过程分成单粒子搜索与多粒子搜索两个阶段,既克服了单粒子搜索效率低下的缺点,又降低了多粒子搜索的硬件代价.在各种复杂网络拓扑上实施该模型,并与混合导航模型进行比较.结果表明,混合搜索模型的平均搜索时间收敛更快,硬件代价更小.将度大优先的目标选择策略与混合搜索模型相结合,能进一步提高搜索效率.此外通过仿真发现,在无标度网络上混合搜索模型的效率远高于单粒子随机行走,与多粒子随机行走的效率相当,但硬件代价远小于多粒子行走.最后针对该模型给出了一种能有效降低负载的"吸收"策略.     

Phase transitions for information diffusion in random clustered networks

We study the conditions for the phase transitions of information diffusion in complexnetworks. Using the random clustered network model, a generalisation of the Chung-Lurandom network model incorporating clustering, we examine the effect of clustering underthe Susceptible-Infected-Recovered (SIR) epidemic diffusion model with heterogeneouscontact rates. For this purpose, we exploit the branching process to analyse informationdiffusion in random unclustered networks with arbitrary contact rates, and provide noveliterative algorithms for estimating the conditions and sizes of global cascades,respectively. Showing that a random clustered network can be mapped into a factor graph,which is a locally tree-like structure, we successfully extend our analysis to randomclustered networks with heterogeneous contact rates. We then identify the conditions forphase transitions of information diffusion using our method. Interestingly, for variouscontact rates, we prove that random clustered networks with higher clustering coefficientshave strictly lower phase transition points for any given degree sequence. Finally, weconfirm our analytical results with numerical simulations of both synthetically-generatedand real-world networks.     

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

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

基于模体的复杂网络测度量研究

针对复杂网络拓扑结构中模体的存在性, 在传统的顶点度和边聚类系数定义的基础上, 提出了基于模体的顶点度和边度来衡量网络中顶点和边的重要性. 用Rand-ESU算法对不同规模的8个网络进行模体检测, 验证了网络中模体的存在性, 重点分析了Karate网络和Dolphin网络中模体的结构和特征. 用Pearson相关系数衡量基于模体的顶点度与传统顶点度、基于模体的边度与边聚类系数的相关性, 仿真分析结果表明相关性大小与模体种类有关, 基于模体的顶点度和边度是对原定义的一种改进和拓展, 更全面地刻画了顶点和边在网络中的重要性. 关键词： 模体 顶点度 边度 Pearson相关系数     

A model of the effects of authority on consensus formation in adaptive networks: Impact on network topology and robustness

Opinions of individuals in real social networks are arguably strongly influenced by external determinants, such as the opinions of those perceived to have the highest levels of authority. In order to model this, we have extended an existing model of consensus formation in an adaptive network by the introduction of a parameter representing each agent’s level of ‘authority’, based on their opinion relative to the overall opinion distribution. We found that introducing this model, along with a randomly varying opinion convergence factor, significantly impacts the final state of converged opinions and the number of interactions required to reach that state. We also determined the relationship between initial and final network topologies for this model, and whether the final topology is robust to node removals. Our results indicate firstly that the process of consensus formation with a model of authority consistently transforms the network from an arbitrary initial topology to one with distinct measurements in mean shortest path, clustering coefficient, and degree distribution. Secondly, we found that subsequent to the consensus formation process, the mean shortest path and clustering coefficient are less affected by both random and targeted node disconnection. Speculation on the relevance of these results to real world applications is provided.     

Modeling the clustering in citation networks

For the study of citation networks, a challenging problem is modeling the high clustering. Existing studies indicate that the promising way to model the high clustering is a copying strategy, i.e., a paper copies the references of its neighbor as its own references. However, the line of models highly underestimates the number of abundant triangles observed in real citation networks and thus cannot well model the high clustering. In this paper, we point out that the failure of existing models lies in that they do not capture the connecting patterns among existing papers. By leveraging the knowledge indicated by such connecting patterns, we further propose a new model for the high clustering in citation networks. Experiments on two real world citation networks, respectively from a special research area and a multidisciplinary research area, demonstrate that our model can reproduce not only the power-law degree distribution as traditional models but also the number of triangles, the high clustering coefficient and the size distribution of co-citation clusters as observed in these real networks.     

Finding communities in directed networks by PageRank random walk induced network embedding

Community structure has been found to exist ubiquitously in many different kinds of real world complex networks. Most of the previous literature ignores edge directions and applies methods designed for community finding in undirected networks to find communities. Here, we address the problem of finding communities in directed networks. Our proposed method uses PageRank random walk induced network embedding to transform a directed network into an undirected one, where the information on edge directions is effectively incorporated into the edge weights. Starting from this new undirected weighted network, previously developed methods for undirected network community finding can be used without any modification. Moreover, our method improves on recent work in terms of community definition and meaning. We provide two simulated examples, a real social network and different sets of power law benchmark networks, to illustrate how our method can correctly detect communities in directed networks.     

Patent citation network in nanotechnology (1976–2004)

The patent citation networks are described using critical node, core network, and network topological analysis. The main objective is understanding of the knowledge transfer processes between technical fields, institutions and countries. This includes identifying key influential players and subfields, the knowledge transfer patterns among them, and the overall knowledge transfer efficiency. The proposed framework is applied to the field of nanoscale science and engineering (NSE), including the citation networks of patent documents, submitting institutions, technology fields, and countries. The NSE patents were identified by keywords “full-text” searching of patents at the United States Patent and Trademark Office (USPTO). The analysis shows that the United States is the most important citation center in NSE research. The institution citation network illustrates a more efficient knowledge transfer between institutions than a random network. The country citation network displays a knowledge transfer capability as efficient as a random network. The technology field citation network and the patent document citation network exhibit a␣less efficient knowledge diffusion capability than a random network. All four citation networks show a tendency to form local citation clusters.     

Identifying Functional Modules in Complex Networks

In this paper, we propose a new method that enables us to detect and describe the functional modules in complex networks. Using the proposed method, we can classify the nodes of networks into different modules according to their pattern of intra- and extra-module links. We use our method to analyze the modular structures of the ER random networks. We find that different modules of networks have different structure properties, such as the clustering coefficient. Moreover, at the same time, many nodes of networks participate different modules. Remarkably, we find that in the ER random networks, when the probability p is small, different modules or different roles of nodes can be Mentified by different regions in the c-p parameter space.