iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/978-3-540-77004-6_18
Giant Component and Connectivity in Geographical Threshold Graphs | SpringerLink
Skip to main content
Springer Nature Link
Log in

Giant Component and Connectivity in Geographical Threshold Graphs

  • Conference paper
Algorithms and Models for the Web-Graph (WAW 2007)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4863))

Included in the following conference series:

Abstract

The geographical threshold graph model is a random graph model with nodes distributed in a Euclidean space and edges assigned through a function of distance and node weights. We study this model and give conditions for the absence and existence of the giant component, as well as for connectivity.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Bonato, A.: A survey of models of the web graph. In: López-Ortiz, A., Hamel, A.M. (eds.) CAAN 2004. LNCS, vol. 3405, pp. 159–172. Springer, Heidelberg (2005)

    Google Scholar 

  2. Abello, J., Pardalos, P.M., Resende, M.G.C. (eds.): Handbook of massive data sets. Kluwer Academic Publishers, Norwell, MA (2002)

    MATH  Google Scholar 

  3. Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the internet topology. In: SIGCOMM 1999: Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, pp. 251–262. ACM Press, New York (1999)

    Chapter  Google Scholar 

  4. Kleinberg, J.M., Kumar, R., Raghavan, P., Rajagopalan, S., Tomkins, A.S.: The web as a graph: Measurements, models, and methods. In: Asano, T., Imai, H., Lee, D.T., Nakano, S.-i., Tokuyama, T. (eds.) COCOON 1999. LNCS, vol. 1627, pp. 1–17. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  5. Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., Upfal, E.: Stochastic models for the web graph. In: FOCS 2000: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, Washington, DC, USA, p. 57. IEEE Computer Society, Los Alamitos (2000)

    Chapter  Google Scholar 

  6. Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286, 509–512 (1999)

    Article  MathSciNet  Google Scholar 

  7. Aiello, W., Chung, F., Lu, L.: A random graph model for massive graphs. In: STOC 2000: Proceedings of the thirty-second annual ACM symposium on Theory of computing, pp. 171–180. ACM Press, New York (2000)

    Chapter  Google Scholar 

  8. Bollobás, B., Riordan, O., Spencer, J., Tusnády, G.: The degree sequence of a scale-free random graph process. Random Struct. Algorithms 18, 279–290 (2001)

    Article  MATH  Google Scholar 

  9. Cooper, C., Frieze, A.M.: A general model of undirected Web graphs. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 500–511. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  10. Bradonjić, M., Kong, J.: Wireless Ad Hoc Networks with Tunable Topology. To appear in Proceedings of the 45th Annual Allerton Conference on Communication, Control and Computing (2007)

    Google Scholar 

  11. Erdős, P., Rényi, A.: On random graphs. Publ. Math. Inst. Hungar. Acad. Sci. (1959)

    Google Scholar 

  12. Erdős, P., Rényi, A.: On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. (1960)

    Google Scholar 

  13. Penrose, M.D.: Random Geometric Graphs. Oxford University Press, Oxford (2003)

    MATH  Google Scholar 

  14. Mahadev, N.V.R., Peled, U.N.: Threshold graphs and related topics. Annals of discrete mathematics, vol. 56. Elsevier, New York (1995)

    MATH  Google Scholar 

  15. Hagberg, A., Swart, P.J., Schult, D.A.: Designing threshold networks with given structural and dynamical properties. Phys. Rev. E 74, 056116 (2006)

    Google Scholar 

  16. Masuda, N., Miwa, H., Konno, N.: Geographical threshold graphs with small-world and scale-free properties. Physical Review E 71, 036108 (2005)

    Google Scholar 

  17. Alon, N., Spencer, J.H.: The probabilistic method, 2nd edn. John Wiley & Sons, Inc., New York (2000)

    MATH  Google Scholar 

  18. Gupta, P., Kumar, P.R.: Critical power for asymptotic connectivity. In: Proceedings of the 37th IEEE Conference on Decision and Control, vol. 1, pp. 1106–1110 (1998)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electrical Engineering, UCLA, Los Angeles, CA 90095,  

    Milan Bradonjić

  2. Mathematical Modeling and Analysis, Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM 87545,  

    Aric Hagberg

  3. Department of Mathematics, UCLA, Los Angeles, CA 90095,  

    Allon G. Percus

  4. Information Sciences Group, Los Alamos National Laboratory, Los Alamos, NM 87545,  

    Allon G. Percus

Authors
  1. Milan Bradonjić
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Aric Hagberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Allon G. Percus
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Anthony Bonato Fan R. K. Chung

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bradonjić, M., Hagberg, A., Percus, A.G. (2007). Giant Component and Connectivity in Geographical Threshold Graphs. In: Bonato, A., Chung, F.R.K. (eds) Algorithms and Models for the Web-Graph. WAW 2007. Lecture Notes in Computer Science, vol 4863. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77004-6_18

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-77004-6_18

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-77003-9

  • Online ISBN: 978-3-540-77004-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation