Deterministic scale-free small-world networks of arbitrary order

In many real-life networks, both the scale-free distribution of degree and small-world behavior are important features. There are many random or deterministic models of networks to simulate these features separately. However, there are few models that combine the scale-free effect and small-world behavior, especially in terms of deterministic versions. What is more, all the existing deterministic algorithms running in the iterative mode generate networks with only several discrete numbers of nodes. This contradicts the purpose of creating a deterministic network model on which we can simulate some dynamical processes as widely as possible. According to these facts, this paper proposes a deterministic network generation algorithm, which can not only generate deterministic networks following a scale-free distribution of degree and small-world behavior, but also produce networks with arbitrary number of nodes. Our scheme is based on a complete binary tree, and each newly generated leaf node is further linked to its full brother and one of its direct ancestors. Analytical computation and simulation results show that the average degree of such a proposed network is less than 5, the average clustering coefficient is high (larger than 0.5, even for a network of size 2 million) and the average shortest path length increases much more slowly than logarithmic growth for the majority of small-world network models.     

蛋白质相互作用网络特征的理论再现

无标度性、小世界性、功能模块结构及度负关联性是大量生物网络共同的特征. 为了理解生物网络无标度性、小世界性和度负关联性的形成机制, 研究者已经提出了各种各样基于复制和变异的网络增长模型. 在本文中,我们从生物学的角度通过引入偏爱小复制原则及变异和非均匀的异源二聚作用构建了一个简单的蛋白质相互作用网络演化模型.数值模拟结果表明,该演化模型几乎可以再现现在实测结果所公认的蛋白质相互作用网络的性质：无标度性、小世界性、度负关联性和功能模块结构. 我们的演化模型对理解蛋白质相互作用网络演化过程中的可能机制提供了一定的帮助. 关键词： 蛋白质相互作用网络 偏爱小 非均匀的异源二聚作用 功能模块结构     

Emergence of modularity and disassortativity in protein-protein interaction networks

In this paper, we present a simple evolution model of protein-protein interaction networks by introducing a rule of small-preference duplication of a node, meaning that the probability of a node chosen to duplicate is inversely proportional to its degree, and subsequent divergence plus nonuniform heterodimerization based on some plausible mechanisms in biology. We show that our model cannot only reproduce scale-free connectivity and small-world pattern, but also exhibit hierarchical modularity and disassortativity. After comparing the features of our model with those of real protein-protein interaction networks, we believe that our model can provide relevant insights into the mechanism underlying the evolution of protein-protein interaction networks.     

Effect of node deleting on network structure

The ever-increasing knowledge of the structure of various real-world networks has uncovered their complex multi-mechanism-governed evolution processes. Therefore, a better understanding of the structure and evolution of these networked complex systems requires us to describe such processes in a more detailed and realistic manner. In this paper, we introduce a new type of network growth rule which comprises addition and deletion of nodes, and propose an evolving network model to investigate the effect of node deleting on network structure. It is found that, with the introduction of node deleting, network structure is significantly transformed. In particular, degree distribution of the network undergoes a transition from scale-free to exponential forms as the intensity of node deleting increases. At the same time, nontrivial disassortative degree correlation develops spontaneously as a natural result of network evolution in the model. We also demonstrate that node deleting introduced in the model does not destroy the connectedness of a growing network so long as the increasing rate of edges is not excessively small. In addition, it is found that node deleting will weaken but not eliminate the small-world effect of a growing network, and generally it will decrease the clustering coefficient in a network.     

基于感知流量算法的复杂网络拥塞问题研究

研究了在具有感知流量的路由策略下,复杂网络的拓扑结构对网络中传输流量的影响.为了描述数据包传输过程的有效性,通过引入一个状态参数,利用由稳态到拥塞的指标流量相变值来刻画网络的吞吐量.基于每个节点的数据包处理能力与该节点的度或介数成比例提出两种模型并进行仿真.仿真结果表明,平均度相同的情况下,模型Ⅰ中,WS小世界网络比ER随机网络和BA无标度网络更容易产生拥塞;模型Ⅱ中,所有网络容量都得到较大的提高,尤其是WS小世界网络.但当网络的基本连接参数改变时,哪种模型更利于网络的流量传输,还要依据网络本身的结构特性 关键词： 复杂网络 无标度网络 感知流量 拥塞     

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.     

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.     

小世界网络与无标度网络的社区结构研究

模块性(modularity)是度量网络社区结构(community structure)的主要参数.探讨了Watts和Strogatz的小世界网络(简称W-S模型)以及Barabàsi 等的B-A无标度网络(简称B-A模型)两类典型复杂网络模块性特点.结果显示，网络模块性受到网络连接稀疏的影响，W-S模型具有显著的社区结构，而B-A模型的社区结构特征不明显.因此，应用中应该分别讨论网络的小世界现象和无标度特性.社区结构不同于小世界现象和无标度特性，并可以利用模块性区别网络类型，因此网络复杂性指标应该包括 关键词： 模块性 社区结构 小世界网络 无标度网络     

手机短信息传播过程和短信息寿命研究

比较了短信息在无标度网络、小世界网络和实际的短信息网络三种网络中的传播过程,寻找影响短信息传播的因素.研究发现,网络拓扑结构和手机用户的转发短信行为均会影响短信息传播过程.在无标度网络中短信息传播速率快于小世界网络和实际的短信息网络,而无标度网络的短信息寿命较小世界网络和实际的短信息网络短;网络中手机用户的转发短信息行为明显影响短信息的传播过程.同时还发现短信息寿命与网络直径有关. 关键词： 复杂网络 短信息 信息传播 人类行为     

Complex networks: Dynamics and security

This paper presents a perspective in the study of complex networks by focusing on how dynamics may affect network security under attacks. In particular, we review two related problems: attack-induced cascading breakdown and range-based attacks on links. A cascade in a network means the failure of a substantial fraction of the entire network in a cascading manner, which can be induced by the failure of or attacks on only a few nodes. These have been reported for the internet and for the power grid (e.g., the August 10, 1996 failure of the western United States power grid). We study a mechanism for cascades in complex networks by constructing a model incorporating the flows of information and physical quantities in the network. Using this model we can also show that the cascading phenomenon can be understood as a phase transition in terms of the key parameter characterizing the node capacity. For a parameter value below the phase-transition point, cascading failures can cause the network to disintegrate almost entirely. We will show how to obtain a theoretical estimate for the phase-transition point. The second problem is motivated by the fact that most existing works on the security of complex networks consider attacks on nodes rather than on links. We address attacks on links. Our investigation leads to the finding that many scale-free networks are more sensitive to attacks on short-range than on long-range links. Considering that the small-world phenomenon in complex networks has been identified as being due to the presence of long-range links, i.e., links connecting nodes that would otherwise be separated by a long node-to-node distance, our result, besides its importance concerning network efficiency and security, has the striking implication that the small-world property of scale-free networks is mainly due to short-range links.     

一类高聚类系数的加权无标度网络及其同步能力分析

针对真实世界中大规模网络都具有明显聚类效应的特点, 提出一类具有高聚类系数的加权无标度网络演化模型, 该模型同时考虑了优先连接、三角结构、随机连接和社团结构等四种演化机制. 在模型演化规则中, 以概率p增加单个节点, 以概率1–p增加一个社团. 与以往研究的不同在于新边的建立, 以概率φ在旧节点之间进行三角连接, 以概率1–φ进行随机连接. 仿真分析表明, 所提出的网络度、强度和权值分布都是服从幂律分布的形式, 且具有高聚类系数的特性, 聚类系数的提高与社团结构和随机连接机制有直接的关系. 最后通过数值仿真分析了网络演化机制对同步动态特性的影响, 数值仿真结果表明, 网络的平均聚类系数越小, 网络的同步能力越强. 关键词： 无标度网络 加权网络 聚类系数 同步能力     

A computational model for cancer growth by using complex networks

In this work we propose a computational model to investigate the proliferation of cancerous cell by using complex networks. In our model the network represents the structure of available space in the cancer propagation. The computational scheme considers a cancerous cell randomly included in the complex network. When the system evolves the cells can assume three states: proliferative, non-proliferative, and necrotic. Our results were compared with experimental data obtained from three human lung carcinoma cell lines. The computational simulations show that the cancerous cells have a Gompertzian growth. Also, our model simulates the formation of necrosis, increase of density, and resources diffusion to regions of lower nutrient concentration. We obtain that the cancer growth is very similar in random and small-world networks. On the other hand, the topological structure of the small-world network is more affected. The scale-free network has the largest rates of cancer growth due to hub formation. Finally, our results indicate that for different average degrees the rate of cancer growth is related to the available space in the network.     

Unified Model for Generation Complex Networks with Utility Preferential Attachment

In this paper, based on the utility preferential attachment, we propose a new unified model to generate different network topologies such as scale-free, small-world and random networks. Moreover, a new network structure named super scale network is found, which has monopoly characteristic in our simulation experiments. Finally, the characteristics ofthis new network are given.     

Unified Model for Generation Complex Networks with Utility Preferential Attachment

In this paper, based on the utility preferential attachment, we propose a new unified model to generate different network topologies such as scale-free, small-world and random networks. Moreover, a new network structure named super scale network is found, which has monopoly characteristic in our simulation experiments. Finally, the characteristics of this new network are given.     

A last updating evolution model for online social networks

As information technology has advanced, people are turning to electronic media more frequently for communication, and social relationships are increasingly found on online channels. However, there is very limited knowledge about the actual evolution of the online social networks. In this paper, we propose and study a novel evolution network model with the new concept of “last updating time”, which exists in many real-life online social networks. The last updating evolution network model can maintain the robustness of scale-free networks and can improve the network reliance against intentional attacks. What is more, we also found that it has the “small-world effect”, which is the inherent property of most social networks. Simulation experiment based on this model show that the results and the real-life data are consistent, which means that our model is valid.     

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

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

Influence of topology in the evolution of coordination in complex networks under information diffusion constraints

In this paper, we study the influence of the topological structure of social systems on the evolution of coordination in them. We simulate a coordination game (“Stag-hunt”) on four well-known classes of complex networks commonly used to model social systems, namely scale-free, small-world, random and hierarchical-modular, as well as on the well-mixed model. Our particular focus is on understanding the impact of information diffusion on coordination, and how this impact varies according to the topology of the social system. We demonstrate that while time-lags and noise in the information about relative payoffs affect the emergence of coordination in all social systems, some topologies are markedly more resilient than others to these effects. We also show that, while non-coordination may be a better strategy in a society where people do not have information about the payoffs of others, coordination will quickly emerge as the better strategy when people get this information about others, even with noise and time lags. Societies with the so-called small-world structure are most conducive to the emergence of coordination, despite limitations in information propagation, while societies with scale-free topologies are most sensitive to noise and time-lags in information diffusion. Surprisingly, in all topologies, it is not the highest connected people (hubs), but the slightly less connected people (provincial hubs) who first adopt coordination. Our findings confirm that the evolution of coordination in social systems depends heavily on the underlying social network structure.     

Cascading failure in the wireless sensor scale-free networks

In the practical wireless sensor networks(WSNs), the cascading failure caused by a failure node has serious impact on the network performance. In this paper, we deeply research the cascading failure of scale-free topology in WSNs. Firstly,a cascading failure model for scale-free topology in WSNs is studied. Through analyzing the influence of the node load on cascading failure, the critical load triggering large-scale cascading failure is obtained. Then based on the critical load,a control method for cascading failure is presented. In addition, the simulation experiments are performed to validate the effectiveness of the control method. The results show that the control method can effectively prevent cascading failure.     

Evolutionary ultimatum game on complex networks under incomplete information

This paper studies the evolutionary ultimatum game on networks when agents have incomplete information about the strategies of their neighborhood agents. Our model assumes that agents may initially display low fairness behavior, and therefore, may have to learn and develop their own strategies in this unknown environment. The Genetic Algorithm Learning Classifier System (GALCS) is used in the model as the agent strategy learning rule. Aside from the Watts-Strogatz (WS) small-world network and its variations, the present paper also extends the spatial ultimatum game to the Barabási-Albert (BA) scale-free network. Simulation results show that the fairness level achieved is lower than in situations where agents have complete information about other agents’ strategies. The research results display that fairness behavior will always emerge regardless of the distribution of the initial strategies. If the strategies are randomly distributed on the network, then the long-term agent fairness levels achieved are very close given unchanged learning parameters. Neighborhood size also has little effect on the fairness level attained. The simulation results also imply that WS small-world and BA scale-free networks have different effects on the spatial ultimatum game. In ultimatum game on networks with incomplete information, the WS small-world network and its variations favor the emergence of fairness behavior slightly more than the BA network where agents are heterogeneously structured.     

An evolving network model with modular growth

In this paper, we propose an evolving network model growing fast in units of module, according to the analysis of the evolution characteristics in real complex networks. Each module is a small-world network containing several interconnected nodes and the nodes between the modules are linked by preferential attachment on degree of nodes. We study the modularity measure of the proposed model, which can be adjusted by changing the ratio of the number of inner-module edges and the number of inter-module edges. In view of the mean-field theory, we develop an analytical function of the degree distribution, which is verified by a numerical example and indicates that the degree distribution shows characteristics of the small-world network and the scale-free network distinctly at different segments. The clustering coefficient and the average path length of the network are simulated numerically, indicating that the network shows the small-world property and is affected little by the randomness of the new module.