Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-17T19:10:04.343Z Has data issue: false hasContentIssue false
  • English
  • Français

Ultra-small scale-free geometric networks

Part of: Graph theory Geometric probability and stochastic geometry

Published online by Cambridge University Press:  14 July 2016

J. E. Yukich
J. E. Yukich*
Affiliation:
Lehigh University
*
∗Postal address: Department of Mathematics, Lehigh University, Bethlehem, PA 18015, USA. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We consider a family of long-range percolation models (Gp)p>0 on ℤd that allow dependence between edges and have the following connectivity properties for p ∈ (1/d, ∞): (i) the degree distribution of vertices in Gp has a power-law distribution; (ii) the graph distance between points x and y is bounded by a multiple of logpdlogpd|x - y| with probability 1 - o(1); and (iii) an adversary can delete a relatively small number of nodes from Gp(ℤd ∩ [0, n]d), resulting in two large, disconnected subgraphs.

Keywords

Scale-free graphlong-range percolationchemical distance

MSC classification

Primary: 60D05: Geometric probability and stochastic geometry
Secondary: 05C80: Random graphs
Type
Research Article
Information
Journal of Applied Probability , Volume 43 , Issue 3 , September 2006 , pp. 665 - 677
Copyright
© Applied Probability Trust 2006 

Footnotes

Partially supported by NSF grant DMS-0203720.

References

Albert, R. and Barabási, A.-L. (2002). Statistical mechanics of complex networks. Rev. Modern Physics 74, 47–97.Google Scholar
Barabási, A.-L. (2002). Linked: The New Science of Networks. Perseus, Cambridge, MA.Google Scholar
Barbour, A. D., Holst, L. and Janson, S. (1992). Poisson Approximation. Oxford University Press.CrossRefGoogle Scholar
Benjamini, I., Kesten, H., Peres, Y. and Schramm, O. (2004). The geometry of the uniform spanning forests: transitions in dimensions 4,8,12, …. Ann. Math. 160, 465–491.CrossRefGoogle Scholar
Berger, N. (2004). A lower bound for the chemical distance in sparse long-range percolation models. Preprint 0409021, Department of Mathematics, University of California, Davis. Available at http://front.math. ucdavis.edu.Google Scholar
Berger, N. et al. (2003). Degree distribution of the FKP network model. In Automata, Languages and Programming (Lecture Notes Comput. Sci. 2719), Springer, Heidelberg, pp. 725–738.CrossRefGoogle Scholar
Biskup, M. (2004). Graph diameter in long-range percolation. Submitted.Google Scholar
Biskup, M. (2004). On scaling of the chemical distance in long-range percolation models. Ann. Prob. 32, 2938–2977.Google Scholar
Bollabás, B. and Riordan, O. M. (2003). The diameter of a scale-free random graph. Combinatorica 24, 5–34.CrossRefGoogle Scholar
Chung, F. and Lu, L. (2002). The average distance in a random graph with given expected degrees. Proc. Nat. Acad. Sci. USA 99, 15879–15882.Google Scholar
Chung, F. and Lu, L. (2003). The average distance in a random graph with given expected degrees. Internet Math. 1, 91–113. (This is an expanded version of cite{CL}.)Google Scholar
Cohen, R. and Havlin, S. (2003). Scale-free networks are ultrasmall. Phys. Rev. Lett. 90, 058701.Google Scholar
Coppersmith, D., Gamarnik, D. and Sviridenko, M. (2002). The diameter of a long-range percolation graph. Random Structures Algorithms 21, 1–13.CrossRefGoogle Scholar
Dorogovtsev, S. N. and Mendes, J. F. F. (2003). Evolution of Networks: From Biological Nets to the Internet and World Wide Web. Oxford University Press.CrossRefGoogle Scholar
Dudley, R. M. (1999). Uniform Central Limit Theorems. Cambridge University Press.Google Scholar
Fabrikant, A., Koutsoupias, E. and Papadimitriou, C. H. (2002). Heuristically optimized trade-offs: a new paradigm for power laws in the internet. In Automata, Languages and Programming (Lecture Notes Comput. Sci. 2380), Springer, Berlin, pp. 110–122.Google Scholar
Franceschetti, M. and Meester, R. (2004). Navigation in small world networks, a scale-free continuum model. Tech. Rep. UCB/ERL M03/33, EECS Department, University of California, Berkeley.Google Scholar
Hermann, C., Barthélemy, M. and Provero, P. (2003). Connectivity distribution of spatial networks. Phys. Rev. E 68, 026128.Google Scholar
Kleinberg, J. M. (2000). Navigation in the small world. Nature 406, 845.Google Scholar
Meester, R. and Roy, R. (1996). Continuum Percolation (Camb. Tracts Math. 119). Cambridge University Press.Google Scholar
Newman, M. E. J. (2003). The structure and function of complex networks. SIAM Rev. 45, 167–256.Google Scholar
Penrose, M. D. (2001). A spatial central limit theorem with applications to percolation, epidemics and Boolean models. Ann. Prob. 29, 1515–1546.Google Scholar
Penrose, M. D. (2003). Random Geometric Graphs. Clarendon Press, Oxford.Google Scholar
Watts, D. J. (1999). Small Worlds. Princeton University Press.Google Scholar
Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of ‘small world’ networks. Nature 393, 440–442.CrossRefGoogle ScholarPubMed