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.
@article{bwmeta1.element.doi-10_2478_s11533-012-0032-8,
author = {Yilun Shang},
title = {Lack of Gromov-hyperbolicity in small-world networks},
journal = {Open Mathematics},
volume = {10},
year = {2012},
pages = {1152-1158},
zbl = {1242.05257},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-012-0032-8}
}
Yilun Shang. Lack of Gromov-hyperbolicity in small-world networks. Open Mathematics, Tome 10 (2012) pp. 1152-1158. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-012-0032-8/
[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 | Zbl 1056.92042
[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 | Zbl 1110.92026
[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 | Zbl 1296.05181
[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 | Zbl 0969.81047
[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 | Zbl 1049.82520
[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 | Zbl 1230.05264
[21] Shang Y., Multi-type directed scale-free percolation, Commun. Theor. Phys. (in press) | Zbl 1247.05229
[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