Lack of Gromov-hyperbolicity in small-world networks

被引：44

作者：

Shang, Yilun ^{[1
]}

机构：

[1] Univ Texas San Antonio, Inst Cyber Secur, San Antonio, TX 78249 USA

来源：

CENTRAL EUROPEAN JOURNAL OF MATHEMATICS | 2012年 / 10卷 / 03期

关键词：

Graph hyperbolicity; Small world; Complex networks;

D O I：

10.2478/s11533-012-0032-8

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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 Erdos-Renyi 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.

引用

页码：1152 / 1158

页数：7

共 22 条

[1]

[Anonymous], 1999, Metric structures for Riemannian and nonRiemannian spaces

[2]

[Anonymous], 2001, CAMBRIDGE STUD ADV M

[3] Synchronization in small-world systems [J].

Barahona, M ;

Pecora, LM .

PHYSICAL REVIEW LETTERS, 2002, 89 (05) :054101/1-054101/4

[4]

Bermudo S, 2010, AIP CONF PROC, V1281, P575

[5]

Brisdon M.R., 1999, GRUNDLEHREN MATH WIS, V319

[6] Hierarchical structure and the prediction of missing links in networks [J].

Clauset, Aaron ;

Moore, Cristopher ;

Newman, M. E. J. .

NATURE, 2008, 453 (7191) :98-101

[7] Some uses of the Farris transform in mathematics and phylogenetics - A review [J].

Dress, A. ;

Huber, K. T. ;

Moulton, V. .

ANNALS OF COMBINATORICS, 2007, 11 (01) :1-37

[8] Δ additive and Δ ultra-additive maps, Gromov's trees, and the Farris transform [J].

Dress, A ;

Holland, B ;

Huber, KT ;

Koolen, JH ;

Moulton, V ;

Weyer-Menkhoff, J .

DISCRETE APPLIED MATHEMATICS, 2005, 146 (01) :51-73

[9]

Gromov M., 1987, ESSAYS GROUP THEORY, P75, DOI 10.1007/978-1-4613-9586-7_3

[10]

Jonckheere E, 2004, P AMER CONTR CONF, P976

← 1 2 3 →