Generation of scale-free networks using a simple preferential rewiring dynamics

We propose a model that generates a new class of networks exhibiting power-law degree distribution with a spectrum of exponents depending on the number of links ($m$) with which incoming nodes join the existing network. Unlike the Barab\'{a}si-Albert (BA) model, each new node first picks an existing node at random, and connects not with this but with $m$ of its neighbors also picked at random. Counterintuitively enough, such a mediation-driven attachment rule results not only...

Power law distribution seems to be an important characteristic of web graphs. Several existing web graph models generate power law graphs by adding new vertices and non-uniform edge connectivities to existing graphs. Researchers have conjectured that preferential connectivity and incremental growth are both required for the power law distribution. In this paper, we propose a different web graph model with power law distribution that does not require incremental growth. We als...

We propose a local strategy for constructing scale-free networks of arbitrary degree distributions, based on the redirection method of Krapivsky and Redner [Phys. Rev. E 63, 066123 (2001)]. Our method includes a set of external parameters that can be tuned at will to match detailed behavior at small degree k, in addition to the scale-free power-law tail signature at large k. The choice of parameters determines other network characteristics, such as the degree of clustering. T...

We propose a method of generating different scale-free networks, which has several input parameters in order to adjust the structure, so that they can serve as a basis for computer simulation of real-world phenomena. The topological structure of these networks was studied to determine what kind of networks can be produced and how can we give the appropriate values of parameters to get a desired structure.

Through the distinction between ``real'' and ``virtual'' links between the nodes of a graph, we develop a set of simple rules leading to scale-free networks with a tunable degree distribution exponent. Albeit sharing some similarities with preferential attachment, our procedure is both faster than a na\"ive implementation of the Barab\'asi and Albert model and exhibits different clustering properties. The model is thoroughly studied numerically and suggests that reducing the ...

Unlike the well-studied models of growing networks, where the dominant dynamics consist of insertions of new nodes and connections, and rewiring of existing links, we study {\em ad hoc} networks, where one also has to contend with rapid and random deletions of existing nodes (and, hence, the associated links). We first show that dynamics based {\em only} on the well-known preferential attachments of new nodes {\em do not} lead to a sufficiently heavy-tailed degree distributio...

Scaling behavior of scale-free evolving networks arising in communications, citations, collaborations, etc. areas is studied. We derive universal scaling relations describing properties of such networks and indicate limits of their validity. We show that main properties of scale-free evolving networks may be described in frames of a simple continuous approach. The simplest models of networks, which growth is determined by a mechanism of preferential linking, are used. We cons...

Using a steady state process of node duplication and deletion we produce networks with 1/k scale-free degree distributions in the limit of vanishing connectance. This occurs even though there is no growth involved and inherent preferential attachment is counterbalanced by preferential detachment. The mean field evolution is considered and the 1/k law is verified under certain approximations. An ansatz for the degree distribution is proposed on the basis of symmetry considerat...

The rate equations are used to study the scale-free behavior of the weight distribution in evolving networks whose topology is determined only by degrees of preexisting vertices. An analysis of these equations shows that the degree distribution and thereby the weight distribution remain unchanged when the probability rate of attaching new nodes is replaced with some unnormalized rate determined by the ratio of the degree of a randomly selected old node to the maximal node deg...

Scale-free power law structure describes complex networks derived from a wide range of real world processes. The extensive literature focuses almost exclusively on networks with power law exponent strictly larger than 2, which can be explained by constant vertex growth and preferential attachment. The complementary scale-free behavior in the range between 1 and 2 has been mostly neglected as atypical because there is no known generating mechanism to explain how networks with ...