Network 'Small-World-Ness': A Quantitative Method for Determining Canonical Network Equivalence

被引:1006
作者
Humphries, Mark D. [1 ]
Gurney, Kevin [1 ]
机构
[1] Univ Sheffield, Dept Psychol, Adapt Behav Res Grp, Sheffield S10 2TN, S Yorkshire, England
来源
PLOS ONE | 2008年 / 3卷 / 04期
基金
英国工程与自然科学研究理事会;
关键词
D O I
10.1371/journal.pone.0002051
中图分类号
O [数理科学和化学]; P [天文学、地球科学]; Q [生物科学]; N [自然科学总论];
学科分类号
07 ; 0710 ; 09 ;
摘要
Background: Many technological, biological, social, and information networks fall into the broad class of 'small-world' networks: they have tightly interconnected clusters of nodes, and a shortest mean path length that is similar to a matched random graph (same number of nodes and edges). This semi-quantitative definition leads to a categorical distinction ('small/not-small') rather than a quantitative, continuous grading of networks, and can lead to uncertainty about a network's small-world status. Moreover, systems described by small-world networks are often studied using an equivalent canonical network model-the Watts-Strogatz (WS) model. However, the process of establishing an equivalent WS model is imprecise and there is a pressing need to discover ways in which this equivalence may be quantified. Methodology/Principal Findings: We defined a precise measure of 'small-world-ness' S based on the trade off between high local clustering and short path length. A network is now deemed a 'small-world' if S. 1-an assertion which may be tested statistically. We then examined the behavior of S on a large data-set of real-world systems. We found that all these systems were linked by a linear relationship between their S values and the network size n. Moreover, we show a method for assigning a unique Watts-Strogatz (WS) model to any real-world network, and show analytically that the WS models associated with our sample of networks also show linearity between S and n. Linearity between S and n is not, however, inevitable, and neither is S maximal for an arbitrary network of given size. Linearity may, however, be explained by a common limiting growth process. Conclusions/Significance: We have shown how the notion of a small-world network may be quantified. Several key properties of the metric are described and the use of WS canonical models is placed on a more secure footing.
引用
收藏
页数:10
相关论文
共 60 条
[1]   A resilient, low-frequency, small-world human brain functional network with highly connected association cortical hubs [J].
Achard, S ;
Salvador, R ;
Whitcher, B ;
Suckling, J ;
Bullmore, ET .
JOURNAL OF NEUROSCIENCE, 2006, 26 (01) :63-72
[2]   Search in power-law networks [J].
Adamic, L.A. ;
Lukose, R.M. ;
Puniyani, A.R. ;
Huberman, B.A. .
Physical Review E - Statistical, Nonlinear, and Soft Matter Physics, 2001, 64 (4 II) :461351-461358
[3]   Internet -: Diameter of the World-Wide Web [J].
Albert, R ;
Jeong, H ;
Barabási, AL .
NATURE, 1999, 401 (6749) :130-131
[4]   Classes of small-world networks [J].
Amaral, LAN ;
Scala, A ;
Barthélémy, M ;
Stanley, HE .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2000, 97 (21) :11149-11152
[5]  
[Anonymous], RANDOM GRAPHS
[6]   Emergence of scaling in random networks [J].
Barabási, AL ;
Albert, R .
SCIENCE, 1999, 286 (5439) :509-512
[7]   Synchronization in small-world systems [J].
Barahona, M ;
Pecora, LM .
PHYSICAL REVIEW LETTERS, 2002, 89 (05) :054101/1-054101/4
[8]   On the properties of small-world network models [J].
Barrat, A ;
Weigt, M .
EUROPEAN PHYSICAL JOURNAL B, 2000, 13 (03) :547-560
[9]   Adaptive reconfiguration of fractal small-world human brain functional networks [J].
Bassettt, Danielle S. ;
Meyer-Lindenberg, Andreas ;
Achard, Sophie ;
Duke, Thomas ;
Bullmore, Edward T. .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2006, 103 (51) :19518-19523
[10]   Chains of affection: The structure of adolescent romantic and sexual networks [J].
Bearman, PS ;
Moody, J ;
Stovel, K .
AMERICAN JOURNAL OF SOCIOLOGY, 2004, 110 (01) :44-91