The Diameter of a Scale-Free Random Graph

By Béla Bollobás, Oliver Riordan. Comb., 2004

657 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/3635fe52038a5a06c405163332ce525310f1e8ce

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

The Economic Consequences of Social Network Structure (2017, unknown): “For example, in cases in which there are strong complementarities in behaviors such as in crime or education, Katz-Bonacich centrality has proven useful in describing the activity of each agent (Ballester, Calvó-Armengol, Zenou (2006)).”
Asymptotic behavior and distributional limits of preferential attachment graphs (2014, methodology): “It should be noted that the α= 0 case of the sequential model defined here differs slightly from the model of Bollobás and Riordan [7] in that they allow (self-)loops, while we do not.”
A Brief History of Generative Models for Power Law and Lognormal Distributions (2004, background): “It follows that the produ t of lognormal distributions is again lognormal.”
Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (2005, unknown): “As pointed out in [23, 24], despite the popularity of the SF network paradigm in the complex systems literature, the definition of “scale-free” in the context of network graph models has never been made precise, and the results on SF graphs are largely heuristic and experimental studies with “rather”
X-Stream: edge-centric graph processing using streaming partitions (2013, background): “There is evidence that the diameter of real world graphs often grows only sub-logarithmically (O( log(V ) loglog(V ) )) with the number of vertices [22] or even”
Graph theory and networks in Biology. (2006, unknown): “In this subsection, we shall discuss four classical concepts of centrality which have recently been applied to biological interaction networks: (i) Degree centrality; (ii) Closeness centrality; (iii) Betweenness centrality; (iv) Eigenvector centrality.”
Extremal Properties of Random Structures (2003, unknown): “om v to w. The diameter ∆ and the average vertex-vertex distance Λ are deﬁned by ∆ = max v,w d graph(v,w), Λ = avev,wd graph(v,w). In the context of a simple proportional attachment model it is known [8] that E∆n, EΛn = (1+o(1))logn loglogn as n → ∞. It is natural to conjecture, but hard to prove, t”
The phase transition in inhomogeneous random graphs (2005, methodology): “Extensive surveys of the mostly experimental or heuristic work have been written by Barabási and Albert [2] and Dorogovtsev and Mendes [30]; for a partial survey of the much smaller body of rigorous work see Bollobás and Riordan [18].”
A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment (2005, methodology): “Other specific models are the LCD graph of [ 5 ], or the Barab´ asi-Albert model”
Distances in Random Graphs with Finite Mean and Infinite Variance Degrees (2005, methodology): “For this model, it is shown that the number of nodes with degree k decays proportionally to k−3 [11], the diameter is of order log N log log N when m ≥ 2 [8], and couplings to a classical random graph G(N, p) are given for an appropriately chosen p in [10].”
Directed scale-free graphs (2003, background): “Microsoft Research, One Microsoft Way, Redmond, WA 98122. borgs~microsoft, com SMicrosoft Research, One Microsoft Way, Redmond, WA 98122. j chayes~microsoft, com §Trinity College, Cambridge CB2 1TQ, UK.”
On a conditionally Poissonian graph process (2006, background): “In this section we show that the three parameter regions τ ∈ (1, 2), τ ∈ (2, 3), and τ > 3 correspond to three qualitatively different asymptotic connectivity structures, or architectures, of the graphsGN (we have not considered the boundary cases τ = 2 and τ = 3; however, Bollobás and Riordan [6] a”