Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2012 | 10 | 3 | 1152-1158
Tytuł artykułu

Lack of Gromov-hyperbolicity in small-world networks

Treść / Zawartość
Warianty tytułu
Języki publikacji
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
Opis fizyczny
  • University of Texas at San Antonio
  • [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
  • [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
  • [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
  • [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
  • [8] Gromov M., Hyperbolic groups, In: Essays in Group Theory, Math. Sci. Res. Inst. Publ., 8, Springer, New York, 1987, 75–263
  • [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
  • [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
  • [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
  • [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
  • [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
  • [18] Newman M.E.J., Models of the small world, J. Stat. Phys., 2000, 101(3–4), 819–841
  • [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
  • [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
Typ dokumentu
Identyfikator YADDA
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ć.