Emergence of scaling in random networks

Emergence of scaling in random networks (Citations: 4240)


	BibTex \| EndNote \| RefWorks Download

Systems as diverse as genetic networks or the world wide web are best described as networks with complex topology. A common property of many large networks is that the vertex connectivities follow a scale-free power-law distribution. This feature is found to be a consequence of the two generic mechanisms that networks expand continuously by the addition of new vertices, and new vertices attach preferentially to already well connected sites. A model based on these two ingredients reproduces the observed stationary scale-free distributions, indicating that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.

Published in 1999.

Cumulative Annual

View Publication

( arxiv.org )

( www2.mta.ac.il )

Citation Context (967)

- ...They have small-world characteristics (a large clustering with small average distance) and they are minors of the pseudo-fractal networks [13] and Apollonian graphs [2], but in these cases the graphs are also scalefree (their degree distribution follows a power-law), see [4], while in our case the degrees follow an exponential distribution...
Zhongzhi Zhang, et al. Farey graphs as models for complex networks
- ...Remark 1.4. Suppose that Xn = Yn. If P(Xn 2 An) ! for some sequence of (measurable) sets An and some 2 [0; 1], then P(Yn2 An)! too...
- ...If pij, 1 i < j n, are given probabilities in [0,1], let G(n;fpijg) be the random graph on [n] where the edgeij appears with probabilitypij and the indicators Iij := 1[edge ij appears], 1 i < j n, are independent...
- ...We extend the denition of G(n; p) to the case when p is a random vector (with entries in [0,1]) by conditioning on p, i.e., given p =fpijg, the edge indicators Iij are independent random variables with Iij Be(pij)...
- ...We dene a function : [0; 1]2! [0;1) in Denition 2.1, where we also give some equivalent (within constant factors) alternative formulas that often are more convenient...
- ...Theorem 2.9. Let 1 N(n) 1 and suppose that pn = fpnig and p0n = fp0nig are random vectors in [0; 1] N(n)...
- ...Example 3.4. A related case uses the sameS = (0; 1], = Lebesgue measure and xi = i=n, i = 1;:::;n, as Example 3.3, now with the homogeneous (x;y) = c= p xy yielding ^ pij = c= p ij; this case is a mean-eld version of the preferential attachment model by Barab asi and Albert [1], see Bollob as, Janson and Riordan [4], 16.2 and Riordan [17] and the references given there...
- ...with elements in [0; 1], if the random variables Ii are independent indicator variables with Ii Be(pi)...
- ...More generally, if p =fpigN i=1 is a random vector with elements in [0; 1], with N1 , we say that random vectors of indicator variables X = (Ii)N i=1...
Svante Janson. Asymptotic equivalence and contiguity of some random graphs
- ...OpenR is scale-free [2], i.e., the distribution of the number of edges is a power law as illustrated in Figure 5. A scale-free network suggests that OpenR is able to build a complete picture of the social network of stakeholders...
Soo Ling Lim, et al. StakeNet: using social networks to analyse the stakeholders of large-s...
- ...In the original PA model proposed by Barab´ asi and Albert [2], new vertices join a graph one by one, and each new vertex chooses a pre-determined number of neighbours at random, so that the probability that a vertex is chosen as a neighbour (its link probability) is proportional to its degree...
- ...Analysis shows that this model indeed generates power law graphs with high probability, where the exponent of the power law equals 3 [2, 5]. More general PA models, such as the ones proposed and analyzed in [1] and [6] allow for the creation of edges between existing vertices and the deletion of edges and vertices...
Jeannette Janssen, et al. Rank-Based Attachment Leads to Power Law Graphs
- ...Social networks have extended tails in their degree distributions, often well-described by power laws [8]...
Tad Hogg. Inferring preference correlations from social networks