Browse
Submit Data
Databases
API
Help

Dataset Information

0 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Dominating scale-free networks using generalized probabilistic methods.

ABSTRACT: 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.

SUBMITTER: Molnar F

PROVIDER: S-EPMC4158322 | biostudies-literature | 2014 Sep

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

Dominating scale-free networks using generalized probabilistic methods.

Molnár F F Derzsy N N Czabarka É É Székely L L Szymanski B K BK Korniss G G

Scientific reports 20140909

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

PMID: 25200937

Similar Datasets

Minimum Dominating Sets in Scale-Free Network Ensembles

Project description:We study the scaling behavior of the size of minimum dominating set (MDS) in scale-free networks, with respect to network size N and power-law exponent ?, while keeping the average degree fixed. We study ensembles generated by three different network construction methods, and we use a greedy algorithm to approximate the MDS. With a structural cutoff imposed on the maximal degree

| S-EPMC3636516 | biostudies-literature

Subnets of scale-free networks are not scale-free: sampling properties of networks.

Project description:Most studies of networks have only looked at small subsets of the true network. Here, we discuss the sampling properties of a network's degree distribution under the most parsimonious sampling scheme. Only if the degree distributions of the network and randomly sampled subnets belong to the same family of probability distributions is it possible to extrapolate from subnet data to properties of the global network. We show that this condition is indeed satisfied for some important classes of networks, notably classical random graphs and exponential random graphs. For scale-free degree distributions, however, this is not the case. Thus, inferences about the scale-free nature of a network may have to be treated with some caution. The work presented here has important implications for the analysis of molecular networks as well as for graph theory and the theory of networks in general.

| S-EPMC555505 | biostudies-literature

Representing dynamic biological networks with multi-scale probabilistic models.

Project description:Dynamic models analyzing gene regulation and metabolism face challenges when adapted to modeling signal transduction networks. During signal transduction, molecular reactions and mechanisms occur in different spatial and temporal frames and involve feedbacks. This impedes the straight-forward use of methods based on Boolean networks, Bayesian approaches, and differential equations. We propose a new approach, ProbRules, that combines probabilities and logical rules to represent the dynamics of a system across multiple scales. We demonstrate that ProbRules models can represent various network motifs of biological systems. As an example of a comprehensive model of signal transduction, we provide a Wnt network that shows remarkable robustness under a range of phenotypical and pathological conditions. Its simulation allows the clarification of controversially discussed molecular mechanisms of Wnt signaling by predicting wet-lab measurements. ProbRules provides an avenue in current computational modeling by enabling systems biologists to integrate vast amounts of available data on different scales.

| S-EPMC6336720 | biostudies-literature

Behavioral Studies Using Large-Scale Brain Networks - Methods and Validations.

Project description:Mapping human behaviors to brain activity has become a key focus in modern cognitive neuroscience. As methods such as functional MRI (fMRI) advance cognitive scientists show an increasing interest in investigating neural activity in terms of functional connectivity and brain networks, rather than activation in a single brain region. Due to the noisy nature of neural activity, determining how behaviors are associated with specific neural signals is not well-established. Previous research has suggested graph theory techniques as a solution. Graph theory provides an opportunity to interpret human behaviors in terms of the topological organization of brain network architecture. Graph theory-based approaches, however, only scratch the surface of what neural connections relate to human behavior. Recently, the development of data-driven methods, e.g., machine learning and deep learning approaches, provide a new perspective to study the relationship between brain networks and human behaviors across the whole brain, expanding upon past literatures. In this review, we sought to revisit these data-driven approaches to facilitate our understanding of neural mechanisms and build models of human behaviors. We start with the popular graph theory approach and then discuss other data-driven approaches such as connectome-based predictive modeling, multivariate pattern analysis, network dynamic modeling, and deep learning techniques that quantify meaningful networks and connectivity related to cognition and behaviors. Importantly, for each topic, we discuss the pros and cons of the methods in addition to providing examples using our own data for each technique to describe how these methods can be applied to real-world neuroimaging data.

| S-EPMC9244405 | biostudies-literature

A novel probabilistic generator for large-scale gene association networks.

Project description:MotivationGene expression data provide an opportunity for reverse-engineering gene-gene associations using network inference methods. However, it is difficult to assess the performance of these methods because the true underlying network is unknown in real data. Current benchmarks address this problem by subsampling a known regulatory network to conduct simulations. But the topology of regulatory networks can vary greatly across organisms or tissues, and reference-based generators-such as GeneNetWeaver-are not designed to capture this heterogeneity. This means, for example, benchmark results from the E. coli regulatory network will not carry over to other organisms or tissues. In contrast, probabilistic generators do not require a reference network, and they have the potential to capture a rich distribution of topologies. This makes probabilistic generators an ideal approach for obtaining a robust benchmarking of network inference methods.ResultsWe propose a novel probabilistic network generator that (1) provides an alternative to address the inherent limitation of reference-based generators and (2) is able to create realistic gene association networks, and (3) captures the heterogeneity found across gold-standard networks better than existing generators used in practice. Eight organism-specific and 12 human tissue-specific gold-standard association networks are considered. Several measures of global topology are used to determine the similarity of generated networks to the gold-standards. Along with demonstrating the variability of network structure across organisms and tissues, we show that the commonly used "scale-free" model is insufficient for replicating these structures.AvailabilityThis generator is implemented in the R package "SeqNet" and is available on CRAN (https://cran.r-project.org/web/packages/SeqNet/index.html).

| S-EPMC8589155 | biostudies-literature

Are RNA networks scale-free?

Project description:A network is scale-free if its connectivity density function is proportional to a power-law distribution. It has been suggested that scale-free networks may provide an explanation for the robustness observed in certain physical and biological phenomena, since the presence of a few highly connected hub nodes and a large number of small-degree nodes may provide alternate paths between any two nodes on average-such robustness has been suggested in studies of metabolic networks, gene interaction networks and protein folding. A theoretical justification for why many networks appear to be scale-free has been provided by Barabási and Albert, who argue that expanding networks, in which new nodes are preferentially attached to highly connected nodes, tend to be scale-free. In this paper, we provide the first efficient algorithm to compute the connectivity density function for the ensemble of all homopolymer secondary structures of a user-specified length-a highly nontrivial result, since the exponential size of such networks precludes their enumeration. Since existent power-law fitting software, such as powerlaw, cannot be used to determine a power-law fit for our exponentially large RNA connectivity data, we also implement efficient code to compute the maximum likelihood estimate for the power-law scaling factor and associated Kolmogorov-Smirnov p value. Hypothesis tests strongly indicate that homopolymer RNA secondary structure networks are not scale-free; moreover, this appears to be the case for real (non-homopolymer) RNA networks.

| S-EPMC7052049 | biostudies-literature

Scale-free networks are rare.

Project description:Real-world networks are often claimed to be scale free, meaning that the fraction of nodes with degree k follows a power law k-α, a pattern with broad implications for the structure and dynamics of complex systems. However, the universality of scale-free networks remains controversial. Here, we organize different definitions of scale-free networks and construct a severe test of their empirical prevalence using state-of-the-art statistical tools applied to nearly 1000 social, biological, technological, transportation, and information networks. Across these networks, we find robust evidence that strongly scale-free structure is empirically rare, while for most networks, log-normal distributions fit the data as well or better than power laws. Furthermore, social networks are at best weakly scale free, while a handful of technological and biological networks appear strongly scale free. These findings highlight the structural diversity of real-world networks and the need for new theoretical explanations of these non-scale-free patterns.

| S-EPMC6399239 | biostudies-literature

Spectra of weighted scale-free networks.

Project description:Much information about the structure and dynamics of a network is encoded in the eigenvalues of its transition matrix. In this paper, we present a first study on the transition matrix of a family of weight driven networks, whose degree, strength, and edge weight obey power-law distributions, as observed in diverse real networks. We analytically obtain all the eigenvalues, as well as their multiplicities. We then apply the obtained eigenvalues to derive a closed-form expression for the random target access time for biased random walks occurring on the studied weighted networks. Moreover, using the connection between the eigenvalues of the transition matrix of a network and its weighted spanning trees, we validate the obtained eigenvalues and their multiplicities. We show that the power-law weight distribution has a strong effect on the behavior of random walks.

| S-EPMC4669447 | biostudies-other

Infectious disease control using contact tracing in random and scale-free networks.

Project description:Contact tracing aims to identify and isolate individuals that have been in contact with infectious individuals. The efficacy of contact tracing and the hierarchy of traced nodes-nodes with higher degree traced first-is investigated and compared on random and scale-free (SF) networks with the same number of nodes N and average connection K. For values of the transmission rate larger than a threshold, the final epidemic size on SF networks is smaller than that on corresponding random networks. While in random networks new infectious and traced nodes from all classes have similar average degrees, in SF networks the average degree of nodes that are in more advanced stages of the disease is higher at any given time. On SF networks tracing removes possible sources of infection with high average degree. However a higher tracing effort is required to control the epidemic than on corresponding random networks due to the high initial velocity of spread towards the highly connected nodes. An increased latency period fails to significantly improve contact tracing efficacy. Contact tracing has a limited effect if the removal rate of susceptible nodes is relatively high, due to the fast local depletion of susceptible nodes.

| S-EPMC1618487 | biostudies-literature

Probabilistic modeling methods for cell-free DNA methylation based cancer classification.

Project description:BackgroundcfMeDIP-seq is a low-cost method for determining the DNA methylation status of cell-free DNA and it has been successfully combined with statistical methods for accurate cancer diagnostics. We investigate the diagnostic classification aspect by applying statistical tests and dimension reduction techniques for feature selection and probabilistic modeling for the cancer type classification, and we also study the effect of sequencing depth.MethodsWe experiment with a variety of statistical methods that use different feature selection and feature extraction methods as well as probabilistic classifiers for diagnostic decision making. We test the (moderated) t-tests and the Fisher's exact test for feature selection, principal component analysis (PCA) as well as iterative supervised PCA (ISPCA) for feature generation, and GLMnet and logistic regression methods with sparsity promoting priors for classification. Probabilistic programming language Stan is used to implement Bayesian inference for the probabilistic models.Results and conclusionsWe compare overlaps of differentially methylated genomic regions as chosen by different feature selection methods, and evaluate probabilistic classifiers by evaluating the area under the receiver operating characteristic scores on discovery and validation cohorts. While we observe that many methods perform equally well as, and occasionally considerably better than, GLMnet that was originally proposed for cfMeDIP-seq based cancer classification, we also observed that performance of different methods vary across sequencing depths, cancer types and study cohorts. Overall, methods that seem robust and promising include Fisher's exact test and ISPCA for feature selection as well as a simple logistic regression model with the number of hyper and hypo-methylated regions as features.

| S-EPMC8978416 | biostudies-literature

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

Tweets

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data