Minimum Dominating Sets in Scale-Free Network Ensembles
Ontology highlight
ABSTRACT:
SUBMITTER: Molnar F
PROVIDER: S-EPMC3636516 | biostudies-literature | 2013 Jan
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:We study ensemble-based graph-theoretical methods aiming to approximate the size of the minimum dominating set (MDS) in scale-free networks. We analyze both analytical upper bounds of dominating sets and numerical realizations for applications. We propose two novel probabilistic dominating set selection strategies that are applicable to heterogeneous networks. One of them obtains the smallest probabilistic dominating set and also outperforms the deterministic degree-ranked method. We show that a degree-dependent probabilistic selection method becomes optimal in its deterministic limit. In addition, we also find the precise limit where selecting high-degree nodes exclusively becomes inefficient for network domination. We validate our results on several real-world networks, and provide highly accurate analytical estimates for our methods.
| S-EPMC4158322 | biostudies-literature
Project description:Network controllability is an important topic in wide-ranging research fields. However, the relationship between controllability and network structure is poorly understood, although degree heterogeneity is known to determine the controllability. We focus on the size of a minimum dominating set (MDS), a measure of network controllability, and investigate the effect of degree-degree correlation, which is universally observed in real-world networks, on the size of an MDS. We show that disassortativity or negative degree-degree correlation reduces the size of an MDS using analytical treatments and numerical simulation, whereas positive correlations hardly affect the size of an MDS. This result suggests that disassortativity enhances network controllability. Furthermore, apart from the controllability issue, the developed techniques provide new ways of analyzing complex networks with degree-degree correlations.
| S-EPMC4915616 | biostudies-literature
Project description:The structure and dynamics of tissue cultures depend strongly on the physical and chemical properties of the underlying substrate. Inspired by previous advances in the context of inorganic materials, the use of patterned culture surfaces has been proposed as an effective way to induce space-dependent properties in cell tissues. However, cells move and diffuse, and the transduction of external stimuli to biological signals is not instantaneous. Here, we show that the fidelity of patterns to demix tissue cells depends on the relation between the diffusion (τD) and adaptation (τ) times. Numerical results for the self-propelled Voronoi model reveal that the fidelity decreases with τ/τD, a result that is reproduced by a continuum reaction-diffusion model. Based on recent experimental results for single cells, we derive a minimal length scale for the patterns in the substrate that depends on τ/τD and can be much larger than the cell size.
| S-EPMC7732815 | biostudies-literature
Project description:We study the vulnerability of dominating sets against random and targeted node removals in complex networks. While small, cost-efficient dominating sets play a significant role in controllability and observability of these networks, a fixed and intact network structure is always implicitly assumed. We find that cost-efficiency of dominating sets optimized for small size alone comes at a price of being vulnerable to damage; domination in the remaining network can be severely disrupted, even if a small fraction of dominator nodes are lost. We develop two new methods for finding flexible dominating sets, allowing either adjustable overall resilience, or dominating set size, while maximizing the dominated fraction of the remaining network after the attack. We analyze the efficiency of each method on synthetic scale-free networks, as well as real complex networks.
| S-EPMC4321165 | biostudies-literature
Project description:RNA structure heterogeneity is a major challenge when querying RNA structures with chemical probing. We introduce DRACO, an algorithm for the deconvolution of coexisting RNA conformations from mutational profiling experiments. Analysis of the SARS-CoV-2 genome using dimethyl sulfate mutational profiling with sequencing (DMS-MaPseq) and DRACO, identifies multiple regions that fold into two mutually exclusive conformations, including a conserved structural switch in the 3′ untranslated region. This work may open the way to dissecting the heterogeneity of the RNA structurome.
2020-12-23 | GSE158052 | GEO
Project description:For scale-free networks with degrees following a power law with an exponent τ ∈ (2, 3), the structures of motifs (small subgraphs) are not yet well understood. We introduce a method designed to identify the dominant structure of any given motif as the solution of an optimization problem. The unique optimizer describes the degrees of the vertices that together span the most likely motif, resulting in explicit asymptotic formulas for the motif count and its fluctuations. We then classify all motifs into two categories: motifs with small and large fluctuations.
| S-EPMC6494877 | biostudies-other
Project description:The field of optimal control typically requires the assumption of perfect knowledge of the system one desires to control, which is an unrealistic assumption for biological systems, or networks, typically affected by high levels of uncertainty. Here, we investigate the minimum energy control of network ensembles, which may take one of a number of possible realizations. We ensure the controller derived can perform the desired control with a tunable amount of accuracy and we study how the control energy and the overall control cost scale with the number of possible realizations. Our focus is in characterizing the solution of the optimal control problem in the limit in which the systems are drawn from a continuous distribution, and in particular, how to properly pose the weighting terms in the objective function. We verify the theory in three examples of interest: a unidirectional chain network with uncertain edge weights and self-loop weights, a network where each edge weight is drawn from a given distribution, and the Jacobian of the dynamics corresponding to the cell signaling network of autophagy in the presence of uncertain parameters.
| S-EPMC7994643 | biostudies-literature
Project description:Uncertainty in the structure and parameters of networks is ubiquitous across computational biology. In constraint-based reconstruction and analysis of metabolic networks, this uncertainty is present both during the reconstruction of networks and in simulations performed with them. Here, we present Medusa, a Python package for the generation and analysis of ensembles of genome-scale metabolic network reconstructions. Medusa builds on the COBRApy package for constraint-based reconstruction and analysis by compressing a set of models into a compact ensemble object, providing functions for the generation of ensembles using experimental data, and extending constraint-based analyses to ensemble scale. We demonstrate how Medusa can be used to generate ensembles and perform ensemble simulations, and how machine learning can be used in conjunction with Medusa to guide the curation of genome-scale metabolic network reconstructions. Medusa is available under the permissive MIT license from the Python Packaging Index (https://pypi.org) and from github (https://github.com/opencobra/Medusa), and comprehensive documentation is available at https://medusa.readthedocs.io/en/latest.
| S-EPMC7213742 | biostudies-literature
Project description:Despite the importance of intracellular signaling networks, there is currently no consensus regarding the fundamental nature of the protein complexes such networks employ. One prominent view involves stable signaling machines with well-defined quaternary structures. The combinatorial complexity of signaling networks has led to an opposing perspective, namely that signaling proceeds via heterogeneous pleiomorphic ensembles of transient complexes. Since many hypotheses regarding network function rely on how we conceptualize signaling complexes, resolving this issue is a central problem in systems biology. Unfortunately, direct experimental characterization of these complexes has proven technologically difficult, while combinatorial complexity has prevented traditional modeling methods from approaching this question. Here we employ rule-based modeling, a technique that overcomes these limitations, to construct a model of the yeast pheromone signaling network. We found that this model exhibits significant ensemble character while generating reliable responses that match experimental observations. To contrast the ensemble behavior, we constructed a model that employs hierarchical assembly pathways to produce scaffold-based signaling machines. We found that this machine model could not replicate the experimentally observed combinatorial inhibition that arises when the scaffold is overexpressed. This finding provides evidence against the hierarchical assembly of machines in the pheromone signaling network and suggests that machines and ensembles may serve distinct purposes in vivo. In some cases, e.g. core enzymatic activities like protein synthesis and degradation, machines assembled via hierarchical energy landscapes may provide functional stability for the cell. In other cases, such as signaling, ensembles may represent a form of weak linkage, facilitating variation and plasticity in network evolution. The capacity of ensembles to signal effectively will ultimately shape how we conceptualize the function, evolution and engineering of signaling networks.
| S-EPMC3794900 | biostudies-literature
Project description:Stimulus information is encoded in the spatial-temporal structures of external inputs to the neural system. The ability to extract the temporal information of inputs is fundamental to brain function. It has been found that the neural system can memorize temporal intervals of visual inputs in the order of seconds. Here we investigate whether the intrinsic dynamics of a large-size neural circuit alone can achieve this goal. The network models we consider have scale-free topology and the property that hub neurons are difficult to be activated. The latter is implemented by either including abundant electrical synapses between neurons or considering chemical synapses whose efficacy decreases with the connectivity of the postsynaptic neuron. We find that hub neurons trigger synchronous firing across the network, loops formed by low-degree neurons determine the rhythm of synchronous firing, and the hardness of exciting hub neurons avoids epileptic firing of the network. Our model successfully reproduces the experimentally observed rhythmic synchronous firing with long periods and supports the notion that the neural system can process temporal information through the dynamics of local circuits in a distributed way.
| S-EPMC3864271 | biostudies-literature