Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl

PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników

Czasopismo

2012 | 10 | 3 | 1152-1158

Tytuł artykułu

Lack of Gromov-hyperbolicity in small-world networks

Autorzy

Treść / Zawartość

Warianty tytułu

Języki publikacji

EN

Abstrakty

EN
The geometry of complex networks is closely related with their structure and function. In this paper, we investigate the Gromov-hyperbolicity of the Newman-Watts model of small-world networks. It is known that asymptotic Erdős-Rényi random graphs are not hyperbolic. We show that the Newman-Watts ones built on top of them by adding lattice-induced clustering are not hyperbolic as the network size goes to infinity. Numerical simulations are provided to illustrate the effects of various parameters on hyperbolicity in this model.

Słowa kluczowe

Wydawca

Czasopismo

Rocznik

Tom

10

Numer

3

Strony

1152-1158

Opis fizyczny

Daty

wydano
2012-06-01
online
2012-03-24

Twórcy

autor
  • University of Texas at San Antonio

Bibliografia

  • [1] Barahona M., Pecora L.M., Synchronization in small-world systems, Phys. Rev. Lett., 2002, 89(5), #054101
  • [2] Bermudo S., Rodríguez J.M., Sigarreta J.M., Vilaire J.-M., Mathematical properties of Gromov hyperbolic graphs, In: International Conference of Numerical Analysis and Applied Mathematics, Rhodes, September 19–25, 2010, AIP Conf. Proc., 1281, American Institute of Physics, Melville, 2010, 575–578
  • [3] Bollobás B., Random Graphs, Cambridge Stud. Adv. Math., 73, Cambridge University Press, Cambridge, 2001 http://dx.doi.org/10.1017/CBO9780511814068
  • [4] Brisdon M.R., Haefliger A., Metric Spaces of Non-positive Curvature, Grundlehren Math. Wiss., 319, Springer, Berlin, 1999
  • [5] Clauset A., Moore C., Newman M.E.J., Hierarchical structure and the prediction of missing links in networks, Nature, 2008, 453, 98–101 http://dx.doi.org/10.1038/nature06830
  • [6] Dress A., Holland B., Huber K.T., Koolen J.H., Moulton V., Weyer-Menkhoff J., δ additive and δ ultra-additive maps, Gromov’s trees, and the Farris transform, Discrete Appl. Math., 2005, 146(1), 51–73 http://dx.doi.org/10.1016/j.dam.2003.01.003
  • [7] Dress A., Huber K.T., Moulton V., Some uses of the Farris transform in mathematics and phylogenetics - a review, Ann. Comb., 2007, 11(1), 1–37 http://dx.doi.org/10.1007/s00026-007-0302-5
  • [8] Gromov M., Hyperbolic groups, In: Essays in Group Theory, Math. Sci. Res. Inst. Publ., 8, Springer, New York, 1987, 75–263 http://dx.doi.org/10.1007/978-1-4613-9586-7_3
  • [9] Gromov M., Metric Structures for Riemannian and Non-Riemannian Spaces, Progr. Math., 152, Birkhäuser, Boston, 1999
  • [10] Jonckheere E., Lohsoonthorn P., Geometry of network security, In: American Control Conference, vol. 2, Boston, June 30–July 2, 2004, 976–981, available at http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1386698
  • [11] Jonckheere E.A., Lohsoonthorn P., A hyperbolic geometry approach to multipath routing, In: 10th Mediterranean Conference on Control and Automation, Lisbon, July 9–12, 2002, available at http://med.ee.nd.edu/MED10/pdf/373.pdf
  • [12] Jonckheere E.A., Lou M., Hespanha J., Barooah P., Effective resistance of Gromov-hyperbolic graphs: application to asymptotic sensor network problems, In: 46th IEEE Conference on Decision and Control, New Orleans, December 12–14, 2007, 1453–1458, DOI: 10.1109/CDC.2007.4434878
  • [13] Kleinberg J.M., Navigation in a small world, Nature, 2000, 406, 845 http://dx.doi.org/10.1038/35022643
  • [14] Krioukov D., Papadopoulos F., Kitsak M., Vahdat A., Boguñá M., Hyperbolic geometry of complex networks, Phys. Rev. E, 2010, 82(3), #036106
  • [15] Maldacena J., The large-N limit of superconformal field theories and supergravity, Internat. J. Theoret. Phys., 1999, 38(4), 1113–1133 http://dx.doi.org/10.1023/A:1026654312961
  • [16] Narayan O., Saniee I., Large-scale curvature of networks, Phys. Rev. E, 2011, 84, #066108
  • [17] Narayan O., Saniee I., Tucci G.H., Lack of spectral gap and hyperbolicity in asymptotic Erdős-Rényi random graphs, preprint available at http://arxiv.org/abs/1009.5700
  • [18] Newman M.E.J., Models of the small world, J. Stat. Phys., 2000, 101(3–4), 819–841 http://dx.doi.org/10.1023/A:1026485807148
  • [19] Newman M.E.J., Moore C., Watts D.J., Mean-field solution of the small-world network model, Phys. Rev. Lett., 2000, 84(14), 3201–3204 http://dx.doi.org/10.1103/PhysRevLett.84.3201
  • [20] Shang Y., Lack of Gromov-hyperbolicity in colored random networks, Panamer. Math. J., 2011, 21(1), 27–36
  • [21] Shang Y., Multi-type directed scale-free percolation, Commun. Theor. Phys. (in press)
  • [22] Watts D.J., Strogatz S.H., Collective dynamics of ’small-world’ networks, Nature, 1998, 393, 440–442 http://dx.doi.org/10.1038/30918

Typ dokumentu

Bibliografia

Identyfikatory

Identyfikator YADDA

bwmeta1.element.doi-10_2478_s11533-012-0032-8
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.