Dataset Information

Stability of graph communities across time scales.

ABSTRACT: The complexity of biological, social, and engineering networks makes it desirable to find natural partitions into clusters (or communities) that can provide insight into the structure of the overall system and even act as simplified functional descriptions. Although methods for community detection abound, there is a lack of consensus on how to quantify and rank the quality of partitions. We introduce here the stability of a partition, a measure of its quality as a community structure based on the clustered autocovariance of a dynamic Markov process taking place on the network. Because the stability has an intrinsic dependence on time scales of the graph, it allows us to compare and rank partitions at each time and also to establish the time spans over which partitions are optimal. Hence the Markov time acts effectively as an intrinsic resolution parameter that establishes a hierarchy of increasingly coarser communities. Our dynamical definition provides a unifying framework for several standard partitioning measures: modularity and normalized cut size can be interpreted as one-step time measures, whereas Fiedler's spectral clustering emerges at long times. We apply our method to characterize the relevance of partitions over time for constructive and real networks, including hierarchical graphs and social networks, and use it to obtain reduced descriptions for atomic-level protein structures over different time scales.

SUBMITTER: Delvenne JC

PROVIDER: S-EPMC2919907 | biostudies-other | 2010 Jul

REPOSITORIES: biostudies-other

ACCESS DATA

Publications

Stability of graph communities across time scales.

Delvenne J-C JC Yaliraki S N SN Barahona M M

Proceedings of the National Academy of Sciences of the United States of America 20100630 29

The complexity of biological, social, and engineering networks makes it desirable to find natural partitions into clusters (or communities) that can provide insight into the structure of the overall system and even act as simplified functional descriptions. Although methods for community detection abound, there is a lack of consensus on how to quantify and rank the quality of partitions. We introduce here the stability of a partition, a measure of its quality as a community structure based on th ...[more]

PMID: 20615936

Similar Datasets

Project description:The ventriloquism aftereffect (VAE) refers to a shift in auditory spatial perception following exposure to a spatial disparity between auditory and visual stimuli. The VAE has been previously measured on two distinct time scales. Hundreds or thousands of exposures to a an audio-visual spatial disparity produces enduring VAE that persists after exposure ceases. Exposure to a single audio-visual spatial disparity produces immediate VAE that decays over seconds. To determine if these phenomena are two extremes of a continuum or represent distinct processes, we conducted an experiment with normal hearing listeners that measured VAE in response to a repeated, constant audio-visual disparity sequence, both immediately after exposure to each audio-visual disparity and after the end of the sequence. In each experimental session, subjects were exposed to sequences of auditory and visual targets that were constantly offset by +8° or -8° in azimuth from one another, then localized auditory targets presented in isolation following each sequence. Eye position was controlled throughout the experiment, to avoid the effects of gaze on auditory localization. In contrast to other studies that did not control eye position, we found both a large shift in auditory perception that decayed rapidly after each AV disparity exposure, along with a gradual shift in auditory perception that grew over time and persisted after exposure to the AV disparity ceased. We modeled the temporal and spatial properties of the measured auditory shifts using grey box nonlinear system identification, and found that two models could explain the data equally well. In the power model, the temporal decay of the ventriloquism aftereffect was modeled with a power law relationship. This causes an initial rapid drop in auditory shift, followed by a long tail which accumulates with repeated exposure to audio-visual disparity. In the double exponential model, two separate processes were required to explain the data, one which accumulated and decayed exponentially and the other which slowly integrated over time. Both models fit the data best when the spatial spread of the ventriloquism aftereffect was limited to a window around the location of the audio-visual disparity. We directly compare the predictions made by each model, and suggest additional measurements that could help distinguish which model best describes the mechanisms underlying the VAE.

Dataset Information

Stability of graph communities across time scales.

Publications

Stability of graph communities across time scales.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets