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
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ć.