Dataset Information

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

ABSTRACT:

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.

SUBMITTER: Humphries MD

PROVIDER: S-EPMC2323569 | biostudies-literature | 2008 Apr

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

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

Humphries Mark D MD Gurney Kevin K

PloS one 20080430 4

<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-wo ...[more]

PMID: 18446219

Similar Datasets

Project description:BackgroundDTI is sensitive to white matter (WM) microstructural damage and has been suggested as a surrogate marker for phase 2 clinical trials in cerebral small vessel disease (SVD). The study's objective is to establish the best way to analyse the diffusion-weighted imaging data in SVD for this purpose. The ideal method would be sensitive to change and predict dementia conversion, but also straightforward to implement and ideally automated. As part of the OPTIMAL collaboration, we evaluated five different DTI analysis strategies across six different cohorts with differing SVD severity.MethodsThose 5 strategies were: (1) conventional mean diffusivity WM histogram measure (MD median), (2) a principal component-derived measure based on conventional WM histogram measures (PC1), (3) peak width skeletonized mean diffusivity (PSMD), (4) diffusion tensor image segmentation θ (DSEG θ) and (5) a WM measure of global network efficiency (Geff). The association between each measure and cognitive function was tested using a linear regression model adjusted by clinical markers. Changes in the imaging measures over time were determined. In three cohort studies, repeated imaging data together with data on incident dementia were available. The association between the baseline measure, change measure and incident dementia conversion was examined using Cox proportional-hazard regression or logistic regression models. Sample size estimates for a hypothetical clinical trial were furthermore computed for each DTI analysis strategy.ResultsThere was a consistent cross-sectional association between the imaging measures and impaired cognitive function across all cohorts. All baseline measures predicted dementia conversion in severe SVD. In mild SVD, PC1, PSMD and Geff predicted dementia conversion. In MCI, all markers except Geff predicted dementia conversion. Baseline DTI was significantly different in patients converting to vascular dementia than to Alzheimer' s disease. Significant change in all measures was associated with dementia conversion in severe but not in mild SVD. The automatic and semi-automatic measures PSMD and DSEG θ required the lowest minimum sample sizes for a hypothetical clinical trial in single-centre sporadic SVD cohorts.ConclusionDTI parameters obtained from all analysis methods predicted dementia, and there was no clear winner amongst the different analysis strategies. The fully automated analysis provided by PSMD offers advantages particularly for large datasets.

Dataset Information

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

Background

Methodology/principal findings

Conclusions/significance

Publications

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

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets