Network 'small-world-ness': a quantitative method for determining canonical network equivalence.
Network 'small-world-ness': a quantitative method for determining canonical network equivalence.
复制标题
DOI：
10.1371/journal.pone.0002051
复制
发表时间：
2008-04-30
期刊：
影响因子：
3.7
通讯作者：
Gurney K
中科院分区：
文献类型：
--
作者：
Humphries MD;Gurney K
许多技术、生物、社会和信息网络都属于“小世界”网络的大类：它们具有紧密互连的节点簇，以及类似于匹配随机图（相同数量的节点和边）的最短平均路径长度。这种半定量的定义导致了一个分类的区别（“小/不小”），而不是一个定量的，连续的网络分级，并可能导致网络的小世界状态的不确定性。此外，由小世界网络描述的系统通常使用等效的规范网络模型-瓦特-斯托加茨（WS）模型来研究。然而，建立一个等效的WS模型的过程是不精确的，迫切需要发现这种等效性可以量化的方法。我们定义了一个精确的衡量'小世界'的基础上权衡高本地集群和短路径长度。如果S>1，网络现在被认为是一个“小世界”，这是一个可以进行统计测试的断言。然后，我们研究了S在真实世界系统的大型数据集上的行为。我们发现，所有这些系统都是由它们的S值和网络大小n之间的线性关系联系在一起的。此外，我们展示了一种方法，用于将唯一的Watts-Strogatz（WS）模型分配给任何现实世界的网络，并分析表明，与我们的网络样本相关的WS模型也显示出S和n之间的线性关系。然而，S和n之间的线性并不是不可避免的，对于给定大小的任意网络，S也不是最大的。然而，线性可以用一个共同的限制增长过程来解释。我们已经展示了如何量化小世界网络的概念。描述了度量的几个关键属性，并将WS规范模型的使用置于更安全的基础上。
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. 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. 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.
登录
查看更多内容
影响因子：
5.3
作者：
Achard, S;Salvador, R;Bullmore, ET
通讯作者：
Bullmore, ET
影响因子：
2.4
作者：
Ebel, H;Mielsch, LI;Bornholdt, S
通讯作者：
Bornholdt, S
影响因子：
64.8
作者：
Jeong, H;Mason, SP;Oltvai, ZN
通讯作者：
Oltvai, ZN
影响因子：
64.8
作者：
Albert, R;Jeong, H;Barabási, AL
通讯作者：
Barabási, AL
影响因子：
4.3
作者：
Kaiser, Marcus;Hilgetag, Claus C
通讯作者：
Hilgetag, Claus C