Network 'small-world-ness': a quantitative method for determining canonical network equivalence.

<h4>Background</h4>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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Mark D Humphries, Kevin Gurney
Formato:	article
Lenguaje:	EN
Publicado:	Public Library of Science (PLoS) 2008
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/84e58dfb878b42829d9b816353d8a0f7
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:84e58dfb878b42829d9b816353d8a0f7
record_format	dspace
spelling	oai:doaj.org-article:84e58dfb878b42829d9b816353d8a0f72021-11-25T06:12:40ZNetwork 'small-world-ness': a quantitative method for determining canonical network equivalence.1932-620310.1371/journal.pone.0002051https://doaj.org/article/84e58dfb878b42829d9b816353d8a0f72008-04-01T00:00:00Zhttps://www.ncbi.nlm.nih.gov/pmc/articles/pmid/18446219/pdf/?tool=EBIhttps://doaj.org/toc/1932-6203<h4>Background</h4>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.<h4>Methodology/principal findings</h4>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.<h4>Conclusions/significance</h4>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.Mark D HumphriesKevin GurneyPublic Library of Science (PLoS)articleMedicineRScienceQENPLoS ONE, Vol 3, Iss 4, p e0002051 (2008)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Mark D Humphries Kevin Gurney Network 'small-world-ness': a quantitative method for determining canonical network equivalence.
description	<h4>Background</h4>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.<h4>Methodology/principal findings</h4>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.<h4>Conclusions/significance</h4>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.
format	article
author	Mark D Humphries Kevin Gurney
author_facet	Mark D Humphries Kevin Gurney
author_sort	Mark D Humphries
title	Network 'small-world-ness': a quantitative method for determining canonical network equivalence.
title_short	Network 'small-world-ness': a quantitative method for determining canonical network equivalence.
title_full	Network 'small-world-ness': a quantitative method for determining canonical network equivalence.
title_fullStr	Network 'small-world-ness': a quantitative method for determining canonical network equivalence.
title_full_unstemmed	Network 'small-world-ness': a quantitative method for determining canonical network equivalence.
title_sort	network 'small-world-ness': a quantitative method for determining canonical network equivalence.
publisher	Public Library of Science (PLoS)
publishDate	2008
url	https://doaj.org/article/84e58dfb878b42829d9b816353d8a0f7
work_keys_str_mv	AT markdhumphries networksmallworldnessaquantitativemethodfordeterminingcanonicalnetworkequivalence AT kevingurney networksmallworldnessaquantitativemethodfordeterminingcanonicalnetworkequivalence
_version_	1718414053199577088

Network 'small-world-ness': a quantitative method for determining canonical network equivalence.

Ejemplares similares