# Lack of Gromov-hyperbolicity in small-world networks

Open Mathematics (2012)

- Volume: 10, Issue: 3, page 1152-1158
- ISSN: 2391-5455

## Access Full Article

top## Abstract

top## How to cite

topYilun Shang. "Lack of Gromov-hyperbolicity in small-world networks." Open Mathematics 10.3 (2012): 1152-1158. <http://eudml.org/doc/269148>.

@article{YilunShang2012,

abstract = {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.},

author = {Yilun Shang},

journal = {Open Mathematics},

keywords = {Graph hyperbolicity; Small world; Complex networks; graph hyperbolicity; small world; complex networks},

language = {eng},

number = {3},

pages = {1152-1158},

title = {Lack of Gromov-hyperbolicity in small-world networks},

url = {http://eudml.org/doc/269148},

volume = {10},

year = {2012},

}

TY - JOUR

AU - Yilun Shang

TI - Lack of Gromov-hyperbolicity in small-world networks

JO - Open Mathematics

PY - 2012

VL - 10

IS - 3

SP - 1152

EP - 1158

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

LA - eng

KW - Graph hyperbolicity; Small world; Complex networks; graph hyperbolicity; small world; complex networks

UR - http://eudml.org/doc/269148

ER -

## References

top- [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 Zbl1056.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 Zbl1110.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 Zbl1296.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 Zbl0969.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 Zbl1049.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 Zbl1230.05264
- [21] Shang Y., Multi-type directed scale-free percolation, Commun. Theor. Phys. (in press) Zbl1247.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

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.