Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Home
  • Home
Article
  • Access

On a conditionally Poissonian graph process

  • Ilkka Norros (a1) and Hannu Reittu (a1)

Abstract

Random (pseudo)graphs G N 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=1 N Λ k ). The main result of the paper is that when P(Λ1 > x) ≥ x −τ+1, where τ ∈ (2, 3), then, asymptotically almost surely, G N 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.

    •

      • Send article to Kindle

      To send this article to your Kindle, first ensure no-reply@cambridge.org is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about sending to your Kindle. Find out more about sending to your Kindle.

      Note you can select to send to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be sent to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

      Find out more about the Kindle Personal Document Service.

      On a conditionally Poissonian graph process
      Available formats
      ×

      Send article to Dropbox

      To send this article to your Dropbox account, please select one or more formats and confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your <service> account. Find out more about sending content to Dropbox.

      On a conditionally Poissonian graph process
      Available formats
      ×

      Send article to Google Drive

      To send this article to your Google Drive account, please select one or more formats and confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your <service> account. Find out more about sending content to Google Drive.

      On a conditionally Poissonian graph process
      Available formats
      ×

Copyright

COPYRIGHT: © Applied Probability Trust 2006 

Corresponding author

∗ Postal address: VTT Technical Research Centre of Finland, PO Box 10000, FIN-02044 VTT, Finland.
∗∗ Email address: ilkka.norros@vtt.fi
∗∗∗ Email address: hannu.reittu@vtt.fi

Footnotes

Hide All

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

Footnotes

References

Hide All
[1] 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. Library Links | Google Scholar
[2] Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286, 509–512. Library Links | Google Scholar | PubMed
[3] Barabási, A.-L. and Albert, R. (2002). Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47–97. Library Links | Google Scholar
[4] Bingham, N. H., Goldie, C. M. and Teugels, J. L. (1987). Regular Variation. Cambridge University Press. CrossRef | Library Links | Google Scholar
[5] Bollobás, B. and Riordan, O. (2003). Coupling scale-free and classical random graphs. Internet Math. 1, 215–225. CrossRef | Library Links | Google Scholar
[6] Bollobás, B. and Riordan, O. (2004). The diameter of a scale-free random graph. Combinatorica 4, 5–34. CrossRef | Library Links | Google Scholar
[7] Chung, F. and Lu, L. (2003). The average distance in a random graph with given expected degrees (full version). Internet Math. 1, 91–114. CrossRef | Library Links | Google Scholar
[8] Erdös, P. and Rényi, A. (1960). On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5, 17–61. Library Links | Google Scholar
[9] Hooghiemstra, G. and van Mieghem, P. (2005). On the mean distance in scale-free graphs. Method. Comput. Appl. Prob. 7, 285–306. CrossRef | Library Links | Google Scholar
[10] Janson, S., Łuczak, T. and Ruciński, A. (2000). Random Graphs. John Wiley, New York. CrossRef | Library Links | Google Scholar
[11] Kallenberg, O. (1997). Foundations of Modern Probability. Springer, New York. Library Links | Google Scholar
[12] Molloy, M. and Reed, B. (1995). A critical point for random graphs with a given degree sequence. Random Structures Algorithms 6, 161–179. CrossRef | Library Links | Google Scholar
[13] 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. CrossRef | Library Links | Google Scholar
[14] 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. CrossRef | Library Links | Google Scholar
[15] 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. CrossRef | Library Links | Google Scholar
[16] 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. Library Links | Google Scholar
[17] Reittu, H. and Norros, I. (2004). On the power law random graph model of massive data networks. Performance Evaluation 55, 3–23. CrossRef | Library Links | Google Scholar
[18] 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. Library Links | Google Scholar
[19] Van der Hofstad, R., Hooghiemstra, G. and van Mieghem, P. (2005). Random graphs with finite variance degrees. Random Structures Algorithms 27, 76–123. CrossRef | Library Links | Google Scholar
[20] Van der Hofstad, R., Hooghiemstra, G. and Znamenski, D. (2005). Distances in random graphs with finite mean and infinite variance degrees. Submitted. Library Links | Google Scholar

Keywords

MSC classification