Iterative decomposition of Barabasi-Albert scale-free networks

We study a decomposition process where all nodes with a targeted degree are removed from the network. Each removal step results in changes in the degrees of the remaining nodes, and other nodes may attain the targeted degree. The processes continue iteratively until no more nodes with the targeted degree are present in the decomposed network. The network model used in our study is the well known Barabasi-Albert network, that is built with an iterative growth based on preferential attachment. Our results show an exponential decay of the number of nodes removed at each step. The total number of nodes removed in the whole process depends on the targeted degree and decay with a power law controlled by the same exponent as the degree distribution of the network.     

Change of network load due to node removal

The interplay between topology changes and the redistribution of traffic plays a significant role in many real-world networks. In this paper we study how the load of the remaining network changes when nodes are removed. This removal operation can model attacks and errors in networks, or the planned control of network topology. We consider a scenario similar to the data communication networks, and measure the load of a node by its betweenness centrality. By analysis and simulations, we show that when a single node is removed, the change of the remaining network’s load is positively correlated with the degree of the removed node. In multiple-node removal, by comparing several node removal schemes, we show in detail how significantly different the change of the remaining network’s load will be between starting the removal from small degree/betweenness nodes and from large degree/betweenness nodes. Moreover, when starting the removal from small degree/betweenness nodes, we not only observe that the remaining network’s load decreases, which is consistent with previous studies, but also find that the load of hubs keeps decreasing. These results help us to make a deeper understanding about the dynamics after topology changes, and are useful in planned control of network topology.     

An efficient approach of controlling traffic congestion in scale-free networks

We propose and study a model of traffic in communication networks. The underlying network has a structure that is tunable between a scale-free growing network with preferential attachments and a random growing network. To model realistic situations where different nodes in a network may have different capabilities, the message or packet creation and delivering rates at a node are assumed to depend on the degree of the node. Noting that congestions are more likely to take place at the nodes with high degrees in networks with scale-free character, an efficient approach of selectively enhancing the message-processing capability of a small fraction (e.g. 3%) of the nodes is shown to perform just as good as enhancing the capability of all nodes. The interplay between the creation rate and the delivering rate in determining non-congested or congested traffic in a network is studied more numerically and analytically.     

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

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

Synchronizability of dynamical scale-free networks subject to random errors

In this paper the robustness of network synchronizability against random deletion of nodes, i.e. errors, in dynamical scale-free networks was studied. To this end, two measures of network synchronizability, namely, the eigenratio of the Laplacian and the order parameter quantifying the degree of phase synchrony were adopted, and the synchronizability robustness on preferential attachment scale-free graphs was investigated. The findings revealed that as the network size decreases, the robustness of its synchronizability against random removal of nodes declines, i.e. the more the number of randomly removed nodes from the network, the worse its synchronizability. We also showed that this dependence of the synchronizability on the network size is different with that in the growing scale-free networks. The profile of a number of network properties such as clustering coefficient, efficiency, assortativity, and eccentricity, as a function of the network size was investigated in these two cases, growing scale-free networks and those with randomly removed nodes. The results showed that these processes are also different in terms of these metrics.     

Failure tolerance of spike phase synchronization in coupled neural networks

Neuronal synchronization plays an important role in the various functionality of nervous system such as binding, cognition, information processing, and computation. In this paper, we investigated how random and intentional failures in the nodes of a network influence its phase synchronization properties. We considered both artificially constructed networks using models such as preferential attachment, Watts-Strogatz, and Erdo?s-Re?nyi as well as a number of real neuronal networks. The failure strategy was either random or intentional based on properties of the nodes such as degree, clustering coefficient, betweenness centrality, and vulnerability. Hindmarsh-Rose model was considered as the mathematical model for the individual neurons, and the phase synchronization of the spike trains was monitored as a function of the percentage∕number of removed nodes. The numerical simulations were supplemented by considering coupled non-identical Kuramoto oscillators. Failures based on the clustering coefficient, i.e., removing the nodes with high values of the clustering coefficient, had the least effect on the spike synchrony in all of the networks. This was followed by errors where the nodes were removed randomly. However, the behavior of the other three attack strategies was not uniform across the networks, and different strategies were the most influential in different network structure.     

Solution of the unanimity rule on exponential, uniform and scalefree networks: A simple model for biodiversity collapse in foodwebs

We solve the Unanimity Rule on networks with exponential, uniform and scalefree degree distributions. In particular we arrive at equations relating the asymptotic number of nodes in one of two states to the initial fraction of nodes in this state. The solutions for exponential and uniform networks are exact, the analytical approximation for the scalefree case is in perfect agreement with simulation results. We use these solutions to provide a theoretical understanding for biodiversity loss in experimental data of foodwebs, which is available for the three network types discussed. The model allows in principle to estimate the critical value of species that have to be removed from the system to induce a complete diversity collapse.     

Research on the search ability of Brownian particles on networks with an adaptive mechanism

In this paper, we focus on the search ability of Brownian particles with an adaptive mechanism. In the adaptive mechanism, nodes are allowed to be able to change their own accepting probability according to their congestion states. Two searching-traffic models, the static one in which nodes have fixed accepting probability to the incoming particles and the adaptive one in which nodes have adaptive accepting probability to the incoming particles are presented for testing the adaptive mechanism. Instead of number of hops, we use the traveling time, which includes not only the number of hops for a particle to jump from the source node to the destination but also the time that the particle stays in the queues of nodes, to evaluate the search ability of Brownian particles. We apply two models to different networks. The experiment results show that the adaptive mechanism can decrease the network congestion and the traveling time of the first arriving particle. Furthermore, we investigate the influence of network topologies on the congestion of networks by addressing several main properties: degree distribution, average path length, and clustering coefficient. We show the reason why random topologies are more able to deal with congested traffic states than others. We also propose an absorption strategy to deal with the additional Brownian particles in networks. The experiment results on Barabási–Albert (BA) scale-free networks show that the absorption strategy can increase the probability of a successful search and decrease the average per-node particles overhead for our models.     

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.     

Error and attack tolerance of synchronization in Hindmarsh–Rose neural networks with community structure

Synchronization is one of the most important features observed in large-scale complex networks of interacting dynamical systems. As is well known, there is a close relation between the network topology and the network synchronizability. Using the coupled Hindmarsh–Rose neurons with community structure as a model network, in this paper we explore how failures of the nodes due to random errors or intentional attacks affect the synchronizability of community networks. The intentional attacks are realized by removing a fraction of the nodes with high values in some centrality measure such as the centralities of degree, eigenvector, betweenness and closeness. According to the master stability function method, we employ the algebraic connectivity of the considered community network as an indicator to examine the network synchronizability. Numerical evidences show that the node failure strategy based on the betweenness centrality has the most influence on the synchronizability of community networks. With this node failure strategy for a given network with a fixed number of communities, we find that the larger the degree of communities, the worse the network synchronizability; however, for a given network with a fixed degree of communities, we observe that the more the number of communities, the better the network synchronizability.     

Detecting overlapping communities based on vital nodes in complex networks

Detection of community structures in the complex networks is significant to understand the network structures and analyze the network properties. However, it is still a problem on how to select initial seeds as well as to determine the number of communities. In this paper, we proposed the detecting overlapping communities based on vital nodes algorithm(DOCBVA), an algorithm based on vital nodes and initial seeds to detect overlapping communities. First, through some screening method, we find the vital nodes and then the seed communities through the pretreatment of vital nodes. This process differs from most existing methods, and the speed is faster. Then the seeds will be extended. We also adopt a new parameter of attribution degree to extend the seeds and find the overlapping communities. Finally, the remaining nodes that have not been processed in the first two steps will be reprocessed. The number of communities is likely to change until the end of algorithm. The experimental results using some real-world network data and artificial network data are satisfactory and can prove the superiority of the DOCBVA algorithm.     

The architectonic fold similarity network in protein fold space

By constructing the fold similarity network (FSN), we present an alternative approach to the characteristic and architecture of protein fold space. The degree distribution P(k) of FSN differs far from that of the random network with the same number of nodes and connections. The investigation shows that FSN possesses small-world property and broad-scale feature. In order to access to the assumption of the dynamics behavior for FSN, we design a simple evolutionary dynamics model based on the duplication and variation fashions of protein folds. The simulation network generated by this model is a small-world one and reproduces the broad-scale degree distribution consistent with that of FSN. It seems that this model can be used to depict the divergent evolution and expanding progress of protein fold space.     

Jamming transition in air transportation networks

In this work we present a model of an air transportation traffic system from the complex network modelling viewpoint. In the network, every node corresponds to a given airport, and two nodes are connected by means of flight routes. Each node is weighted according to its load capacity, and links are weighted according to the Euclidean distance that separates each pair of nodes. Local rules describing the behaviour of individual nodes in terms of the surrounding flow have been also modelled, and a random network topology has been chosen in a baseline approach. Numerical simulations describing the diffusion of a given number of agents (aircraft) in this network show the onset of a jamming transition that distinguishes an efficient regime with null amount of airport queues and high diffusivity (free phase) and a regime where bottlenecks suddenly take place, leading to a poor aircraft diffusion (congested phase). Fluctuations are maximal around the congestion threshold, suggesting that the transition is critical. We then proceed by exploring the robustness of our results in neutral random topologies by embedding the model in heterogeneous networks. Specifically, we make use of the European air transportation network formed by 858 airports and 11 170 flight routes connecting them, which we show to be scale-free. The jamming transition is also observed in this case. These results and methodologies may introduce relevant decision-making procedures in order to optimize the air transportation traffic.     

Non-monotonic increase of robustness with capacity tolerance in power grids

The robustness of different scale power grids is analyzed based on complex network theory in terms of electrical betweenness and weighted efficiency. The robustness of a power grid does not always increase monotonically with the capacity. This property is different from the results obtained in previous studies, which have indicated that the robustness increases monotonically with capacity. To understand the non-monotonic phenomenon, the cascading failure is divided into several sub-stages, and we analyze the number of overloaded nodes and the average remaining load in each sub-stage. The results indicate that the increasing capacity is barely able to reduce the number of overloaded nodes at the beginning of malfunction, which may lead to more nodes being removed subsequently, including certain nodes with many connections or large load. More loads remain in the power grid such that certain nodes cannot take the load. This eventually causes overloading of more nodes and a decline in the robustness of the power grid. The conclusion may be useful for power grid planners seeking to design grids with cost-effective capacity.     

Modeling Dynamic Evolution of Online Friendship Network

In this paper,we study the dynamic evolution of friendship network in SNS (Social Networking Site).Our analysis suggests that an individual joining a community depends not only on the number of friends he or she has within the community,but also on the friendship network generated by those friends.In addition,we propose a model which is based on two processes:first,connecting nearest neighbors;second,strength driven attachment mechanism.The model reflects two facts:first,in the social network it is a universal phenomenon that two nodes are connected when they have at least one common neighbor;second,new nodes connect more likely to nodes which have larger weights and interactions,a phenomenon called strength driven attachment (also called weight driven attachment).From the simulation results,we find that degree distribution P(k),strength distribution P(s),and degree-strength correlation are all consistent with empirical data.     

Accelerating networks: Effects of preferential connections

Networks are commonly observed structures in complex systems with interacting and interdependent parts that self-organize. For nonlinearly growing networks, when the total number of connections increases faster than the total number of nodes, the network is said to accelerate. We propose a systematic model for the dynamics of growing networks represented by distribution kinetics equations. We define the nodal-linkage distribution, construct a population dynamics equation based on the association-dissociation process, and perform the moment calculations to describe the dynamics of such networks. For nondirectional networks with finite numbers of nodes and connections, the moments are the total number of nodes, the total number of connections, and the degree (the average number of connections per node), represented by the average moment. Size independent rate coefficients yield an exponential network describing the network without preferential attachment, and size dependent rate coefficients produce a power law network with preferential attachment. The model quantitatively describes accelerating network growth data for a supercomputer (Earth Simulator), for regulatory gene networks, and for the Internet.     

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.     

Sudden spreading of infections in an epidemic model with a finite seed fraction

We study a simple case of the susceptible-weakened-infected-removed model in regular random graphs in a situation where an epidemic starts from a finite fraction of initially infected nodes (seeds). Previous studies have shown that, assuming a single seed, this model exhibits a kind of discontinuous transition at a certain value of infection rate. Performing Monte Carlo simulations and evaluating approximate master equations, we find that the present model has two critical infection rates for the case with a finite seed fraction. At the first critical rate the system shows a percolation transition of clusters composed of removed nodes, and at the second critical rate, which is larger than the first one, a giant cluster suddenly grows and the order parameter jumps even though it has been already rising. Numerical evaluation of the master equations shows that such sudden epidemic spreading does occur if the degree of the underlying network is large and the seed fraction is small.     

新节点的边对网络无标度性影响

分析新节点边对网络无标度性的影响.虽然亚线性增长网络瞬态平均度分布尾部表现出了幂律分布性质，但是，这个网络的稳态度分布并不是幂律分布，由此可见，计算机模拟预测不出网络稳态度分布，它只能预测网络的瞬态度分布.进而建立随机增长网络模型，利用随机过程理论得到了这个模型的度分布的解析表达式，结果表明这个网络是无标度网络.     

新节点的边对网络无标度性影响

分析新节点边对网络无标度性的影响.虽然亚线性增长网络瞬态平均度分布尾部表现出了幂律分布性质,但是,这个网络的稳态度分布并不是幂律分布,由此可见,计算机模拟预测不出网络稳态度分布,它只能预测网络的瞬态度分布.进而建立随机增长网络模型,利用随机过程理论得到了这个模型的度分布的解析表达式,结果表明这个网络是无标度网络. 关键词： 复杂网络 无标度网络 小世界网络 度分布