Correlations in scale-free networks: tomography and percolation

Degree-based attacks and defense strategies in complex networks

We study the stability of random scale-free networks to degree-dependent attacks. We present analytical and numerical results to compute the critical fraction p_{c} of nodes that need to be removed for destroying the network under this attack for different attack parameters. We study the effect of different defense strategies, based on the addition of a constant number of links on network robustness. We test defense strategies based on adding links to either low degree, middegree or high degree nodes. We find using analytical results and simulations that the middegree nodes defense strategy leads to the largest improvement to the network robustness against degree-based attacks. We also test these defense strategies on an internet autonomous systems map and obtain similar results.

Uncorrelatedness in growing networks with preferential survival of nodes

The emergence of uncorrelated growing networks is proved when nodes are removed either uniformly or under the preferential survival rule recently observed in the World Wide Web evolution. To this aim, the rate equation for the joint probability of degrees is derived, and stationary symmetrical solutions are obtained, by passing to the continuum limit. When a uniformly random removal of extant nodes and linear preferential attachment of new nodes are at work, we prove that the only stationary solution corresponds to uncorrelated networks for any removal rate r∈(0,1). In the more general case of preferential survival of nodes, uncorrelated solutions are also obtained. These results generalize the uncorrelatedness displayed by the (undirected) Barabási-Albert network model to models with uniformly random and selective (against low degrees) removal of nodes.

Percolation transition in networks with degree-degree correlation

We introduce an exponential random graph model for networks with a fixed degree distribution and a tunable degree-degree correlation. We then investigate the nature of the percolation transition in a correlated network with a Poisson degree distribution. It is found that negative correlation is irrelevant in that the percolation transition in the disassortative network belongs to the same universality class as in the uncorrelated network. Positive correlation turns out to be relevant. The percolation transition in the assortative network is characterized by the nondiverging mean size of finite clusters and power-law scalings of the density of the largest cluster and the cluster size distribution in the nonpercolating phase as well as at the critical point. Our results suggest that the unusual type of percolation transition in the growing network models reported recently may be inherited from the assortative degree-degree correlation.

Finite-size effects in Barabási-Albert growing networks

We investigate the influence of the network's size on the degree distribution pi k in Barabási-Albert model of growing network with initial attractiveness. Our approach based on moments of pi k allows us to treat analytically several variants of the model and to calculate the cutoff function, giving finite-size corrections to pi k. We study the effect of initial configuration as well as of addition of more than one link per time step. The results indicate that asymptotic properties of the cutoff depend only on the exponent gamma in the power-law describing the tail of the degree distribution. The method presented in this paper is very general and can be applied to other growing networks.

Growing networks under geographical constraints

Inspired by the structure of technological weblike systems, we discuss network evolution mechanisms which give rise to topological properties found in real spatial networks. Thus, we suggest that the peculiar structure of transport and distribution networks is fundamentally determined by two factors. These are the dependence of the spatial interaction range of vertices on the vertex attractiveness (or importance within the network) and on the inhomogeneous distribution of vertices in space. We propose and analyze numerically a simple model based on these generating mechanisms which seems, for instance, to be able to reproduce known structural features of the Internet.

Tomography of scale-free networks and shortest path trees

In this paper we model the tomography of scale-free networks by studying the structure of layers around an arbitrary network node. We find, both analytically and empirically, that the distance distribution of all nodes from a specific network node consists of two regimes. The first is characterized by rapid growth, and the second decays exponentially. We also show analytically that the nodes degree distribution at each layer exhibits a power-law tail with an exponential cutoff. We obtain similar empirical results for the layers surrounding the root of shortest path trees cut from such networks, as well as the Internet.

Scaling of optimal-path-lengths distribution in complex networks

We study the distribution of optimal path lengths in random graphs with random weights associated with each link ("disorder"). With each link i we associate a weight tau(i) = exp (a r(i)), where r(i) is a random number taken from a uniform distribution between 0 and 1, and the parameter a controls the strength of the disorder. We suggest, in an analogy with the average length of the optimal path, that the distribution of optimal path lengths has a universal form that is controlled by the expression (1/p(c)) (l(infinity)/a), where l(infinity) is the optimal path length in strong disorder (a --> infinity) and p(c) is the percolation threshold. This relation is supported by numerical simulations for Erdos-Rényi and scale-free graphs. We explain this phenomenon by showing explicitly the transition between strong disorder and weak disorder at different length scales in a single network.

Reshuffling scale-free networks: from random to assortative

To analyze the role of assortativity in networks we introduce an algorithm which produces assortative mixing to a desired degree. This degree is governed by one parameter p . Changing this parameter one can construct networks ranging from fully random (p=0) to totally assortative (p=1) . We apply the algorithm to a Barabási-Albert scale-free network and show that the degree of assortativity is an important parameter governing the geometrical and transport properties of networks. Thus, the average path length of the network increases dramatically with the degree of assortativity. Moreover, the concentration dependences of the size of the giant component in the node percolation problem for uncorrelated and assortative networks are strongly different. The behavior of the clustering coefficient is also discussed.