Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-24T03:11:36.839Z Has data issue: false hasContentIssue false
  • English
  • Français

On a conditionally Poissonian graph process

Part of: Graph theory

Published online by Cambridge University Press:  01 July 2016

Ilkka Norros  and
Hannu Reittu
Ilkka Norros*
Affiliation:
VTT Technical Research Centre of Finland
Hannu Reittu*
Affiliation:
VTT Technical Research Centre of Finland
*
∗ Postal address: VTT Technical Research Centre of Finland, PO Box 10000, FIN-02044 VTT, Finland.
∗ Postal address: VTT Technical Research Centre of Finland, PO Box 10000, FIN-02044 VTT, Finland.
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.

Random (pseudo)graphs GN with the following structure are studied: first, independent and identically distributed capacities Λi are drawn for vertices i = 1, …, N; then, each pair of vertices (i, j) is connected, independently of the other pairs, with E(i, j) edges, where E(i, j) has distribution Poisson(Λi Λj / ∑k=1N Λk). The main result of the paper is that when P(Λ1 > x) ≥ x−τ+1, where τ ∈ (2, 3), then, asymptotically almost surely, GN has a giant component, and the distance between two randomly selected vertices of the giant component is less than (2 + o(N))(log log N)/(-log (τ − 2)). It is also shown that the cases τ > 3, τ ∈ (2, 3), and τ ∈ (1, 2) present three qualitatively different connectivity architectures.

Keywords

Random graphbranching processgiant componentpower law

MSC classification

Primary: 05C80: Random graphs
Secondary: 05C12: Distance in graphs
Type
Stochastic Geometry and Statistical Applications
Information
Advances in Applied Probability , Volume 38 , Issue 1 , March 2006 , pp. 59 - 75
Copyright
Copyright © Applied Probability Trust 2006 

Footnotes

Presented at the ICMS Workshop on Spatial Stochastic Modelling with Applications to Communications Networks (Edinburgh, June 2004).

References

Aiello, W., Chung, F. and Lu, L. (2000). A random graph model for massive graphs. In Proc. 32nd Annual ACM Symp. Theory Comput., ACM, New York, pp. 171–180.Google Scholar
Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286, 509–512.Google Scholar
Barabási, A.-L. and Albert, R. (2002). Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47–97.Google Scholar
Bingham, N. H., Goldie, C. M. and Teugels, J. L. (1987). Regular Variation. Cambridge University Press.Google Scholar
Bollobás, B. and Riordan, O. (2003). Coupling scale-free and classical random graphs. Internet Math. 1, 215–225.Google Scholar
Bollobás, B. and Riordan, O. (2004). The diameter of a scale-free random graph. Combinatorica 4, 5–34.Google Scholar
Chung, F. and Lu, L. (2003). The average distance in a random graph with given expected degrees (full version). Internet Math. 1, 91–114.CrossRefGoogle Scholar
Erdös, P. and Rényi, A. (1960). On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5, 17–61.Google Scholar
Hooghiemstra, G. and van Mieghem, P. (2005). On the mean distance in scale-free graphs. Method. Comput. Appl. Prob. 7, 285–306.CrossRefGoogle Scholar
Janson, S., Łuczak, T. and Ruciński, A. (2000). Random Graphs. John Wiley, New York.CrossRefGoogle Scholar
Kallenberg, O. (1997). Foundations of Modern Probability. Springer, New York.Google Scholar
Molloy, M. and Reed, B. (1995). A critical point for random graphs with a given degree sequence. Random Structures Algorithms 6, 161–179.Google Scholar
Molloy, M. and Reed, B. (1998). The size of the giant component of a random graph with a given degree sequence. Combin. Prob. Comput. 7, 295–305.Google Scholar
Newman, M. E. J. (2003). The size of the giant component of a random graph with a given degree sequence. SIAM Rev. 45, 167–256.CrossRefGoogle Scholar
Newman, M. E. J., Strogatz, S. H. and Watts, D. J. (2001). Random graphs with arbitrary degree distribution and their applications. Phys. Rev. E 64, 026118, 17 pp.CrossRefGoogle ScholarPubMed
Reittu, H. and Norros, I. (2002). On the effect of very large nodes in Internet graphs. In Globecom'02, Vol. III (Proc. Global Telecommunications Conf., Taipei, 2002), IEEE, pp. 2624–2628.Google Scholar
Reittu, H. and Norros, I. (2004). On the power law random graph model of massive data networks. Performance Evaluation 55, 3–23.CrossRefGoogle Scholar
Van der Esker, H., van der Hofstad, R., Hooghiemstra, G. and Znamenski, D. (2004). Distances in random graphs with infinite mean degrees. To appear in Extremes.Google Scholar
Van der Hofstad, R., Hooghiemstra, G. and van Mieghem, P. (2005). Random graphs with finite variance degrees. Random Structures Algorithms 27, 76–123.Google Scholar
Van der Hofstad, R., Hooghiemstra, G. and Znamenski, D. (2005). Distances in random graphs with finite mean and infinite variance degrees. Submitted.Google Scholar