Dataset Information

Finding and testing network communities by lumped Markov chains.

ABSTRACT: Identifying communities (or clusters), namely groups of nodes with comparatively strong internal connectivity, is a fundamental task for deeply understanding the structure and function of a network. Yet, there is a lack of formal criteria for defining communities and for testing their significance. We propose a sharp definition that is based on a quality threshold. By means of a lumped Markov chain model of a random walker, a quality measure called "persistence probability" is associated to a cluster, which is then defined as an "?-community" if such a probability is not smaller than ?. Consistently, a partition composed of ?-communities is an "?-partition." These definitions turn out to be very effective for finding and testing communities. If a set of candidate partitions is available, setting the desired ?-level allows one to immediately select the ?-partition with the finest decomposition. Simultaneously, the persistence probabilities quantify the quality of each single community. Given its ability in individually assessing each single cluster, this approach can also disclose single well-defined communities even in networks that overall do not possess a definite clusterized structure.

SUBMITTER: Piccardi C

PROVIDER: S-EPMC3207820 | biostudies-literature | 2011

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Finding and testing network communities by lumped Markov chains.

Piccardi Carlo C

PloS one 20111103 11

Identifying communities (or clusters), namely groups of nodes with comparatively strong internal connectivity, is a fundamental task for deeply understanding the structure and function of a network. Yet, there is a lack of formal criteria for defining communities and for testing their significance. We propose a sharp definition that is based on a quality threshold. By means of a lumped Markov chain model of a random walker, a quality measure called "persistence probability" is associated to a cl ...[more]

PMID: 22073245

Similar Datasets

Project description:Nerve cells produce electrical impulses ("spikes") through the coordinated opening and closing of ion channels. Markov processes with voltage-dependent transition rates capture the stochasticity of spike generation at the cost of complex, time-consuming simulations. Schmandt and Galán introduced a novel method, based on the stochastic shielding approximation, as a fast, accurate method for generating approximate sample paths with excellent first and second moment agreement to exact stochastic simulations. We previously analyzed the mathematical basis for the method's remarkable accuracy, and showed that for models with a Gaussian noise approximation, the stationary variance of the occupancy at each vertex in the ion channel state graph could be written as a sum of distinct contributions from each edge in the graph. We extend this analysis to arbitrary discrete population models with first-order kinetics. The resulting decomposition allows us to rank the "importance" of each edge's contribution to the variance of the current under stationary conditions. In most cases, transitions between open (conducting) and closed (non-conducting) states make the greatest contributions to the variance, but there are exceptions. In a 5-state model of the nicotinic acetylcholine receptor, at low agonist concentration, a pair of "hidden" transitions (between two closed states) makes a greater contribution to the variance than any of the open-closed transitions. We exhaustively investigate this "edge importance reversal" phenomenon in simplified 3-state models, and obtain an exact formula for the contribution of each edge to the variance of the open state. Two conditions contribute to reversals: the opening rate should be faster than all other rates in the system, and the closed state leading to the opening rate should be sparsely occupied. When edge importance reversal occurs, current fluctuations are dominated by a slow noise component arising from the hidden transitions.

Dataset Information

Finding and testing network communities by lumped Markov chains.

Publications

Finding and testing network communities by lumped Markov chains.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets