Non-hyperbolicity in random regular graphs and their traffic characteristics

• Autorzy: Gabriel Tucci
• Języki publikacji: EN

Abstrakty

EN

In this paper we prove that random d-regular graphs with d ≥ 3 have traffic congestion of the order O(n logd−13 n) where n is the number of nodes and geodesic routing is used. We also show that these graphs are not asymptotically δ-hyperbolic for any non-negative δ almost surely as n → ∞.

Słowa kluczowe

EN

Random regular graph; Hyperbolic spaces; Traffic flow

Kategorie tematyczne

• 05C80: Random graphs
• 20F67: Hyperbolic groups and nonpositively curved groups
• 05C82: Small world graphs, complex networks
• 05C75: Structural characterization of families of graphs

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2013
• Tom: 11
• Numer: 9
• Strony: 1593-1597

Daty

wydano

2013-09-01

online

2013-06-28

Twórcy

autor

Gabriel Tucci

• Alcatel-Lucent

Bibliografia

• [1] Baryshnikov Yu., Tucci G.H., Asymptotic traffic flow in a hyperbolic network: definition and properties of the core, preprint available at http://arxiv.org/abs/1010.3304
• [2] Baryshnikov Yu., Tucci G.H., Asymptotic traffic flow in a hyperbolic network: non-uniform traffic, preprint available at http://arxiv.org/abs/1010.3305
• [3] Benjamini I., Expanders are not hyperbolic, Israel J. Math., 1998, 108, 33–36 http://dx.doi.org/10.1007/BF02783040
• [4] Benjamini I., Hoppen C., Ofek E., Prałat P., Wormald N., Geodesics and almost geodesic cycles in random regular graphs, J. Graph Theory, 2011, 66(2), 115–136 http://dx.doi.org/10.1002/jgt.20496
• [5] Bollobás B., Fernandez de la Vega W., The diameter of random regular graphs, Combinatorica, 1982, 2(2), 125–134 http://dx.doi.org/10.1007/BF02579310
• [6] Brisdon M.R., Haefliger A., Metric Spaces of Non-Positive Curvature, Grundlehren Math. Wiss., 319, Springer, Berlin, 1999
• [7] 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
• [8] Jonckheere E.A., Lohsoonthorn P., A hyperbolic geometry approach to multi-path routing, In: Proceedings of the 10th Mediterranean Conference on Control and Automation, Lisbon, July 9-12, 2002, available at http://med.ee.nd.edu/MED10/pdf/373.pdf
• [9] Jonckheere E., Lohsoonthorn P., Geometry of network security, In: Proceedings of the 2004 American Control Conference, 6, 2004, available at http://eudoxus2.usc.edu/CHAOS/paper4.pdf
• [10] Jonckheere E.A., Lou M., Hespanha J., Barooah P., Effective resistance of Gromov-hyperbolic graphs: application to asymptotic sensor network problems, In: Proceedings of the 46th IEEE Conference on Decision and Control, New Orleans, 2007, 1453–1458
• [11] Krioukov D., Papadopoulos F., Kitsak M., Vahdat A., Boguñá M., Hyperbolic geometry of complex networks, Phys. Rev. E, 2010, 82(3), #036106
• [12] Narayan O., Saniee I., Large-scale curvature of networks, Phys. Rev. E, 2011, 84, #066108
• [13] Shang Y., Lack of Gromov-hyperbolicity in small-world networks, Cent. Eur. J. Math., 2012, 10(3), 1152–1158 http://dx.doi.org/10.2478/s11533-012-0032-8

Identyfikatory

DOI

10.2478/s11533-013-0268-y