A new deterministic complex network model with hierarchical structure

We introduce a new simple pseudo tree-like network model, deterministic complex network (DCN). The proposed DCN model may simulate the hierarchical structure nature of real networks appropriately and have the unique property of ‘skipping the levels’, which is ubiquitous in social networks. Our results indicate that the DCN model has a rather small average path length and large clustering coefficient, leading to the small-world effect. Strikingly, our DCN model obeys a discrete power-law degree distribution P(k)∝k^−γ, with exponent γ approaching 1.0. We also discover that the relationship between the clustering coefficient and degree follows the scaling law C(k)∼k⁻¹, which quantitatively determines the DCN's hierarchical structure.     

Epidemic outbreaks in growing scale-free networks with local structure

The class of generative models has already attracted considerable interest from researchers in recent years and much expanded the original ideas described in BA model. Most of these models assume that only one node per time step joins the network. In this paper, we grow the network by adding n interconnected nodes as a local structure into the network at each time step with each new node emanating m new edges linking the node to the preexisting network by preferential attachment. This successfully generates key features observed in social networks. These include power-law degree distribution p_k∼k^−(3+μ), where μ=(n−1)/m is a tuning parameter defined as the modularity strength of the network, nontrivial clustering, assortative mixing, and modular structure. Moreover, all these features are dependent in a similar way on the parameter μ. We then study the susceptible-infected epidemics on this network with identical infectivity, and find that the initial epidemic behavior is governed by both of the infection scheme and the network structure, especially the modularity strength. The modularity of the network makes the spreading velocity much lower than that of the BA model. On the other hand, increasing the modularity strength will accelerate the propagation velocity.     

Random pseudofractal networks with competition

In this paper, we present a simple rule which assigns fitness to each edge to generate random pseudofractal networks (RPNs). This RPN model is both scale-free and small-world. We obtain the theoretical results that the power-law exponent is γ=2+1/(1+α) for the tunable parameter α>-1, and that the degree distribution is of an exponential form for others. Analytical results also show that an RPN has a large clustering coefficient and can process hierarchical structure as C(k)∼k^-1 that is in accordance with many real networks. And we prove that the mean distance L(N) scales slower logarithmically with network size N. In particular, we explain the effect of nodes with degree 2 on the clustering coefficient. These results agree with numerical simulations very well.     

A model for cascading failures in scale-free networks with a breakdown probability

Considering that not all overload nodes will be removed from networks due to some effective measures to protect them, we propose a new cascading model with a breakdown probability. Adopting the initial load of a node j to be L_j=[k_j(∑_m∈Γjk_m)]^α with k_j and Γ_j being the degree of the node j and the set of its neighboring nodes, respectively, where α is a tunable parameter, we investigate the relationship between some parameters and universal robustness characteristics against cascading failures on scale-free networks. According to a new measure originated from a phase transition from the normal state to collapse, the numerical simulations show that Barabási-Albert (BA) networks reach the strongest robustness level against cascading failures when the tunable parameter α=0.5, while not relating to the breakdown probability. We furthermore explore the effect of the average degree 〈k〉 for network robustness, thus obtaining a positive correlation between 〈k〉 and network robustness. We then analyze the effect of the breakdown probability on the network robustness and confirm by theoretical predictions this universal robustness characteristic observed in simulations. Our work may have practical implications for controlling various cascading-failure-induced disasters in the real world.     

Edge-based-attack induced cascading failures on scale-free networks

Most previous existing works on cascading failures only focused on attacks on nodes rather than on edges. In this paper, we discuss the response of scale-free networks subject to two different attacks on edges during cascading propagation, i.e., edge removal by either the descending or ascending order of the loads. Adopting a cascading model with a breakdown probability p of an overload edge and the initial load (k_ik_j)^α of an edge ij, where k_i and k_j are the degrees of the nodes connected by the edge ij and α is a tunable parameter, we investigate the effects of two attacks for the robustness of Barabási-Albert (BA) scale-free networks against cascading failures. In the case of α<1, our investigation by the numerical simulations leads to a counterintuitive finding that BA scale-free networks are more sensitive to attacks on the edges with the lowest loads than the ones with the highest loads, not relating to the breakdown probability. In addition, the same effect of two attacks in the case of α=1 may be useful in furthering studies on the control and defense of cascading failures in many real-life networks. We then confirm by the theoretical analysis these results observed in simulations.     

Influence of network structure on rumor propagation

Rumor propagation in complex networks is studied analytically and numerically by using the SIR model. Analytically, a mean-field theory is worked out by considering the influence of network topological structure and the unequal footings of neighbors of an infected node in propagating the rumor. It is found that the final infected density of population with degree k   is ρ(k)=1−exp(−αk)$\rho (k)=1-\exp (-\alpha k)$, where α is a parameter related to network structure. The number of the total final infected nodes depends on the network topological structure and will decrease when the structure changes from random to scale-free network. Numerical simulations confirm the theoretical predictions.     

The emergence of scale-free networks with a seceding mechanism

In order to explore further the underlying mechanism of scale-free networks, we study stochastic secession as a mechanism for the creation of complex networks. In this evolution the network growth incorporates the addition of new nodes, the addition of new links between existing nodes, the deleting and rewiring of some existing links, and the stochastic secession of nodes. To random growing networks with preferential attachment, the model yields scale-free behavior for the degree distribution. Furthermore, we obtain an analytical expression of the power-law degree distribution with scaling exponent γ ranging from 1.1 to 9. The analytical expressions are in good agreement with the numerical simulation results.     

Growing networks with preferential deletion and addition of edges

A preferential attachment model for a growing network incorporating the deletion of edges is studied and the expected asymptotic degree distribution is analyzed. At each time step t=1,2,…, with probability π₁>0 a new vertex with one edge attached to it is added to the network and the edge is connected to an existing vertex chosen proportionally to its degree, with probability π₂ a vertex is chosen proportionally to its degree and an edge is added between this vertex and a randomly chosen other vertex, and with probability π₃=1−π₁−π₂<1/2 a vertex is chosen proportionally to its degree and a random edge of this vertex is deleted. The model is intended to capture a situation where high-degree vertices are more dynamic than low-degree vertices in the sense that their connections tend to be changing. A recursion formula is derived for the expected asymptotic fraction p_k of vertices with degree k, and solving this recursion reveals that, for π₃<1/3, we have p_k∼k^{−(3−7π₃)/(1−3π₃)}, while, for π₃>1/3, the fraction p_k decays exponentially at rate (π₁+π₂)/2π₃. There is hence a non-trivial upper bound for how much deletion the network can incorporate without losing the power-law behavior of the degree distribution. The analytical results are supported by simulations.     

Attack vulnerability of scale-free networks due to cascading failures

In this paper, adopting the initial load of a node i to be with k_i being the degree of the node i, we propose a cascading model based on a load local redistribution rule and examine cascading failures on the typical network, i.e., the BA network with the scale-free property. We find that the BA scale-free network reaches the strongest robustness level in the case of α=1 and the robustness of the network has a positive correlation with the average degree 〈k〉, where the robustness is quantified by a transition from normal state to collapse. In addition, we further discuss the effects of two different attacks for the robustness against cascading failures on our cascading model and find an interesting result, i.e., the effects of two different attacks, strongly depending to the value α. These results may be very helpful for real-life networks to avoid cascading-failure-induced disasters.     

An extended clique degree distribution and its heterogeneity in cooperation-competition networks

After Xiao et al. [W.-K. Xiao, J. Ren, F. Qi, Z.W. Song, M.X. Zhu, H.F. Yang, H.Y. Jin, B.-H. Wang, Tao Zhou, Empirical study on clique-degree distribution of networks, Phys. Rev. E 76 (2007) 037102], in this article we present an investigation on so-called k-cliques, which are defined as complete subgraphs of k (k>1) nodes, in the cooperation-competition networks described by bipartite graphs. In the networks, the nodes named actors are taking part in events, organizations or activities, named acts. We mainly examine a property of a k-clique called “k-clique act degree”, q, defined as the number of acts, in which the k-clique takes part. Our analytic treatment on a cooperation-competition network evolution model demonstrates that the distribution of k-clique act degrees obeys Mandelbrot distribution, P(q)∝(q+α)^−γ. To validate the analytical model, we have further studied 13 different empirical cooperation-competition networks with the clique numbers k=2 and k=3. Empirical investigation results show an agreement with the analytic derivations. We propose a new “heterogeneity index”, H, to describe the heterogeneous degree distributions of k-clique and heuristically derive the correlation between H and α and γ. We argue that the cliques, which take part in the largest number of acts, are the most important subgraphs, which can provide a new criterion to distinguish important cliques in the real world networks.     

Geographical dispersal of mobile communication networks

In this paper, we analyze statistical properties of a communication network constructed from the records of a mobile phone company. The network consists of 2.5 million customers that have placed 810 million communications (phone calls and text messages) over a period of 6 months and for whom we have geographical home localization information. It is shown that the degree distribution in this network has a power-law degree distribution k⁻⁵ and that the probability that two customers are connected by a link follows a gravity model, i.e. decreases as d⁻², where d is the distance between the customers. We also consider the geographical extension of communication triangles and we show that communication triangles are not only composed of geographically adjacent nodes but that they may extend over large distances. This last property is not captured by the existing models of geographical networks and in a last section we propose a new model that reproduces the observed property. Our model, which is based on the migration and on the local adaptation of agents, is then studied analytically and the resulting predictions are confirmed by computer simulations.     

A weighted network evolution with traffic flow

In this paper, we propose a simple weighted network model that generalizes the complex network model evolution with traffic flow previously presented to investigate the relationship between traffic flow and network structure. In the model, the nodes in the network are represented by the traffic flow states, the links in the network are represented by the transform of the traffic flow states, and the traffic flow transported when performing the transform of the traffic flow states is considered as the weight of the link. Several topological features of this generalized weighted model, such as the degree distribution and strength distribution, have been numerically studied. A scaling behavior between the strength and degree s∼klogk is obtained. By introducing some constraints to the generalized weighted model, we study its subnetworks and find that the scaling behavior between the strength and degree is conserved, though the topology properties are quite sensitive to the constraints.     

Diffusive capture processes for information search

We show how effectively the diffusive capture processes (DCP) on complex networks can be applied to information search in the networks. Numerical simulations show that our method generates only 2% of traffic compared with the most popular flooding-based query-packet-forwarding (FB) algorithm. We find that the average searching time, 〈T〉, of the our model is more scalable than another well known n-random walker model and comparable to the FB algorithm both on real Gnutella network and scale-free networks with γ=2.4. We also discuss the possible relationship between 〈T〉 and 〈k²〉, the second moment of the degree distribution of the networks.     

A Monte Carlo model for networks between professionals and society

We propose a network model with a fixed number of nodes and links and with a dynamic which favors links between nodes differing in connectivity. We observe a phase transition and parameter regimes with degree distributions following power laws, P(k)∼k^-γ$P(k)\sim k^{-\gamma }$, with γ$\gamma$ ranging from 0.2$0.2$ to 0.5$0.5$, small-world properties, with a network diameter following D(N)∼logN$D(N)\sim \log N$ and relative high clustering, following C(N)∼1/N$C(N)\sim 1/N$ and C(k)∼k^-α$C(k)\sim k^{-\alpha }$, with α$\alpha$ close to 3. We compare our results with data from real-world protein interaction networks.     

Evolutionary games on scale-free networks with a preferential selection mechanism

Considering the heterogeneity of individuals’ influence in the real world, we introduce a preferential selection mechanism to evolutionary games (the Prisoner’s Dilemma Game and the Snowdrift Game) on scale-free networks and focus on the cooperative behavior of the system. In every step, each agent chooses an individual from all its neighbors with a probability proportional to k^α indicating the influence of the neighbor, where k is the degree. Simulation results show that the cooperation level has a non-trivial dependence on α. To understand the effect of preferential selection mechanism on the evolution of the system, we investigate the time series of the cooperator frequency in detail. It is found that the cooperator frequency is greatly influenced by the initial strategy of hub nodes when α>0. This observation is confirmed by investigating the system behavior when some hub nodes’ strategies are fixed.     

Power-law behavior in complex organizational communication networks during crisis

Communication networks can be described as patterns of contacts which are created due to the flow of messages and information shared among participating actors. Contemporary organizations are now commonly viewed as dynamic systems of adaptation and evolution containing several parts, which interact with one another both in internal and in external environment. Although there is limited consensus among researchers on the precise definition of organizational crisis, there is evidence of shared meaning: crisis produces individual crisis, crisis can be associated with positive or negative conditions, crises can be situations having been precipitated quickly or suddenly or situations that have developed over time and are predictable etc. In this research, we study the power-law behavior of an organizational email communication network during crisis from complexity perspective. Power law simply describes that, the probability that a randomly selected node has k links (i.e. degree k) follows P(k)∼k^−γ, where γ is the degree exponent. We used social network analysis tools and techniques to analyze the email communication dataset. We tested two propositions: (1) as organization goes through crisis, a few actors, who are prominent or more active, will become central, and (2) the daily communication network as well as the actors in the communication network exhibit power-law behavior. Our preliminary results support these two propositions. The outcome of this study may provide significant advancement in exploring organizational communication network behavior during crisis.     

Preferential survival in models of complex ad hoc networks

There has been a rich interplay in recent years between (i) empirical investigations of real-world dynamic networks, (ii) analytical modeling of the microscopic mechanisms that drive the emergence of such networks, and (iii) harnessing of these mechanisms to either manipulate existing networks, or engineer new networks for specific tasks. We continue in this vein, and study the deletion phenomenon in the web by the following two different sets of websites (each comprising more than 150,000 pages) over a one-year period. Empirical data show that there is a significant deletion component in the underlying web networks, but the deletion process is not uniform. This motivates us to introduce a new mechanism of preferential survival (PS), where nodes are removed according to the degree-dependent deletion kernel, D(k)∝k^−α, with α≥0. We use the mean-field rate equation approach to study a general dynamic model driven by Preferential Attachment (PA), Double PA (DPA), and a tunable PS (i.e., with any α>0), where c nodes (c<1) are deleted per node added to the network, and verify our predictions via large-scale simulations. One of our results shows that, unlike in the case of uniform deletion (i.e., where α=0), the PS kernel when coupled with the standard PA mechanism, can lead to heavy-tailed power-law networks even in the presence of extreme turnover in the network. Moreover, a weak DPA mechanism, coupled with PS, can help to make the network even more heavy-tailed, especially in the limit when deletion and insertion rates are almost equal, and the overall network growth is minimal. The dynamics reported in this work can be used to design and engineer stable ad hoc networks and explain the stability of the power-law exponents observed in real-world networks.     

High-performance distribution of limited resources via a dynamical reallocation scheme

Using the context of routing efficiency in a complex scale-free network, we study the problem of how a limited amount of resources should be distributed to the nodes in a network so as to achieve a better performance, without imposing a certain pre-determined distribution. A dynamical reallocation scheme, based on the willingness of sharing resources with a busy neighboring node, is proposed as a tool for allowing an initially uniform distribution of resource to evolve to a high-performance distribution. The resulting distribution gives a critical packet generation rate R_c that is significantly enhanced when compared with evenly distributing the same amount of resources on the nodes. There emerges a relation between the resource allocated to a node and the degree of the node in the form of . The exponent γ is found to vary with the packet generation rate R. For R<R_c, γ takes on a high value and shows a weak dependence on R; for R>R_c, γ drops with R; and for R?R_c, γ saturates. For good performance, the values of γ indicate a behavior different from that linear in k, as often assumed in previous studies. The resource distribution is also analyzed in terms of the betweenness of the nodes.     

Percolation on bipartite scale-free networks

Recent studies introduced biased (degree-dependent) edge percolation as a model for failures in real-life systems. In this work, such process is applied to networks consisting of two types of nodes with edges running only between nodes of unlike type. Such bipartite graphs appear in many social networks, for instance in affiliation networks and in sexual-contact networks in which both types of nodes show the scale-free characteristic for the degree distribution. During the depreciation process, an edge between nodes with degrees k and q is retained with a probability proportional to (kq)^−α, where α is positive so that links between hubs are more prone to failure. The removal process is studied analytically by introducing a generating functions theory. We deduce exact self-consistent equations describing the system at a macroscopic level and discuss the percolation transition. Critical exponents are obtained by exploiting the Fortuin-Kasteleyn construction which provides a link between our model and a limit of the Potts model.     

Network topology and correlation features affiliated with European airline companies

The physics information of four specific airline flight networks in European Continent, namely the Austrian airline, the British airline, the France-Holland airline and the Lufthhansa airline, was quantitatively analyzed by the concepts of a complex network. It displays some features of small-world networks, namely a large clustering coefficient and small average shortest-path length for these specific airline networks. The degree distributions for the small degree branch reveal power law behavior with an exponent value of 2-3 for the Austrian and the British flight networks, and that of 1-2 for the France-Holland and the Lufthhansa airline flight networks. So the studied four airlines are sorted into two classes according to the topology structure. Similarly, the flight weight distributions show two kinds of different decay behavior with the flight weight: one for the Austrian and the British airlines and another for the France-Holland airline and the Lufthhansa airlines. In addition, the degree-degree correlation analysis shows that the network has disassortative behavior for all the value of degree k, and this phenomenon is different from the international airline network and US airline network. Analysis of the clustering coefficient (C(k)) versus k, indicates that the flight networks of the Austrian Airline and the British Airline reveal a hierarchical organization for all airports, however, the France-Holland Airline and the Lufthhansa Airline show a hierarchical organization mostly for larger airports. The correlation of node strength (S(k)) and degree is also analyzed, and a power-law fit S(k)∼k^1.1 can roughly fit all data of these four airline companies. Furthermore, we mention seasonal changes and holidays may cause the flight network to form a different topology. An example of the Austrian Airline during Christmas was studied and analyzed.