Skip to main content Accessibility help
×
×
Home

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
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. 171180. Google Scholar
[2] Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286, 509512. Google Scholar | PubMed
[3] Barabási, A.-L. and Albert, R. (2002). Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 4797. Google Scholar
[4] Bingham, N. H., Goldie, C. M. and Teugels, J. L. (1987). Regular Variation. Cambridge University Press. CrossRef | Google Scholar
[5] Bollobás, B. and Riordan, O. (2003). Coupling scale-free and classical random graphs. Internet Math. 1, 215225. CrossRef | Google Scholar
[6] Bollobás, B. and Riordan, O. (2004). The diameter of a scale-free random graph. Combinatorica 4, 534. CrossRef | 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, 91114. CrossRef | Google Scholar
[8] Erdös, P. and Rényi, A. (1960). On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5, 1761. Google Scholar
[9] Hooghiemstra, G. and van Mieghem, P. (2005). On the mean distance in scale-free graphs. Method. Comput. Appl. Prob. 7, 285306. CrossRef | Google Scholar
[10] Janson, S., Łuczak, T. and Ruciński, A. (2000). Random Graphs. John Wiley, New York. CrossRef | Google Scholar
[11] Kallenberg, O. (1997). Foundations of Modern Probability. Springer, New York. Google Scholar
[12] Molloy, M. and Reed, B. (1995). A critical point for random graphs with a given degree sequence. Random Structures Algorithms 6, 161179. CrossRef | 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, 295305. CrossRef | 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, 167256. CrossRef | 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 | 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. 26242628. Google Scholar
[17] Reittu, H. and Norros, I. (2004). On the power law random graph model of massive data networks. Performance Evaluation 55, 323. CrossRef | 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. Google Scholar
[19] Van der Hofstad, R., Hooghiemstra, G. and van Mieghem, P. (2005). Random graphs with finite variance degrees. Random Structures Algorithms 27, 76123. CrossRef | 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. Google Scholar
Recommend this journal

Email your librarian or administrator to recommend adding this journal to your organisation's collection.

Advances in Applied Probability
  • ISSN: 0001-8678
  • EISSN: 1475-6064
  • URL: /core/journals/advances-in-applied-probability
Please enter your name
Please enter a valid email address
Who would you like to send this to? *

CAPTCHA *

Skip to the audio challenge
Type below the answer to what you hear. Numbers or words:

Click or touch the Printer

Refresh/reload the challenge
Accessibility: Request an audio challenge instead of visual
×

Keywords

MSC classification

Citation Tools

Copy and paste a formatted citation or use one of the options to export in your chosen format

Loading citation...
×
Share content

Anyone you share the following link with will be able to freely read this content. Copy and paste the link or use the option below to share it via email. Alternatively you can download a PDF containing the link which can be freely shared online. For more information, please view our content sharing policy.

Sharing content...
×