Spectra of weighted scale-free networks.
Ontology highlight
ABSTRACT:
SUBMITTER: Zhang Z
PROVIDER: S-EPMC4669447 | biostudies-other | 2015
REPOSITORIES: biostudies-other
Similar Datasets
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
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
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
Project description:Scale-free networks, in which the distribution of the degrees obeys a power-law, are ubiquitous in the study of complex systems. One basic network property that relates to the structure of the links found is the degree assortativity, which is a measure of the correlation between the degrees of the nodes at the end of the links. Degree correlations are known to affect both the structure of a network and the dynamics of the processes supported thereon, including the resilience to damage, the spread of information and epidemics, and the efficiency of defence mechanisms. Nonetheless, while many studies focus on undirected scale-free networks, the interactions in real-world systems often have a directionality. Here, we investigate the dependence of the degree correlations on the power-law exponents in directed scale-free networks. To perform our study, we consider the problem of building directed networks with a prescribed degree distribution, providing a method for proper generation of power-law-distributed directed degree sequences. Applying this new method, we perform extensive numerical simulations, generating ensembles of directed scale-free networks with exponents between 2 and 3, and measuring ensemble averages of the Pearson correlation coefficients. Our results show that scale-free networks are on average uncorrelated across directed links for three of the four possible degree-degree correlations, namely in-degree to in-degree, in-degree to out-degree, and out-degree to out-degree. However, they exhibit anticorrelation between the number of outgoing connections and the number of incoming ones. The findings are consistent with an entropic origin for the observed disassortativity in biological and technological networks.
| S-EPMC4195702 | biostudies-literature
Project description:A general class of dynamic models on scale-free networks is studied by analytical methods and computer simulations. Each network consists of N vertices and is characterized by its degree distribution, P(k), which represents the probability that a randomly chosen vertex is connected to k nearest neighbors. Each vertex can attain two internal states described by binary variables or Ising-like spins that evolve in time according to local majority rules. Scale-free networks, for which the degree distribution has a power law tail P(k) approximately k(-gamma), are shown to exhibit qualitatively different dynamic behavior for gamma < 5/2 and gamma > 5/2, shedding light on the empirical observation that many real-world networks are scale-free with 2 < gamma < 5/2. For 2 < gamma < 5/2, strongly disordered patterns decay within a finite decay time even in the limit of infinite networks. For gamma > 5/2, on the other hand, this decay time diverges as ln(N) with the network size N. An analogous distinction is found for a variety of more complex models including Hopfield models for associative memory networks. In the latter case, the storage capacity is found, within mean field theory, to be independent of N in the limit of large N for gamma > 5/2 but to grow as N(alpha) with alpha = (5 - 2gamma)/(gamma - 1) for 2 < gamma < 5/2.
| S-EPMC1174918 | biostudies-literature
Project description:Many complex random networks have been found to be scale-free. Existing literature on scale-free networks has rarely considered potential false positive and false negative links in the observed networks, especially in biological networks inferred from high-throughput experiments. Therefore, it is important to study the impact of these measurement errors on the topology of the observed networks.This article addresses the impact of erroneous links on network topological inference and explores possible error mechanisms for scale-free networks with an emphasis on Saccharomyces cerevisiae protein interaction networks. We study this issue by both theoretical derivations and simulations. We show that the ignorance of erroneous links in network analysis may lead to biased estimates of the scale parameter and recommend robust estimators in such scenarios. Possible error mechanisms of yeast protein interaction networks are explored by comparisons between real data and simulated data.Our studies show that, in the presence of erroneous links, the connectivity distribution of scale-free networks is still scale-free for the middle range connectivities, but can be greatly distorted for low and high connecitivities. It is more appropriate to use robust estimators such as the least trimmed mean squares estimator to estimate the scale parameter gamma under such circumstances. Moreover, we show by simulation studies that the scale-free property is robust to some error mechanisms but untenable to others. The simulation results also suggest that different error mechanisms may be operating in the yeast protein interaction networks produced from different data sources. In the MIPS gold standard protein interaction data, there appears to be a high rate of false negative links, and the false negative and false positive rates are more or less constant across proteins with different connectivities. However, the error mechanism of yeast two-hybrid data may be very different, where the overall false negative rate is low and the false negative rates tend to be higher for links involving proteins with more interacting partners.
| S-EPMC1156868 | biostudies-other
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:Biological neuronal networks are the computing engines of the mammalian brain. These networks exhibit structural characteristics such as hierarchical architectures, small-world attributes, and scale-free topologies, providing the basis for the emergence of rich temporal characteristics such as scale-free dynamics and long-range temporal correlations. Devices that have both the topological and the temporal features of a neuronal network would be a significant step toward constructing a neuromorphic system that can emulate the computational ability and energy efficiency of the human brain. Here we use numerical simulations to show that percolating networks of nanoparticles exhibit structural properties that are reminiscent of biological neuronal networks, and then show experimentally that stimulation of percolating networks by an external voltage stimulus produces temporal dynamics that are self-similar, follow power-law scaling, and exhibit long-range temporal correlations. These results are expected to have important implications for the development of neuromorphic devices, especially for those based on the concept of reservoir computing.
| S-EPMC7286302 | biostudies-literature
Project description:The evolution of cooperation in social dilemmas in structured populations has been studied extensively in recent years. Whereas many theoretical studies have found that a heterogeneous network of contacts favors cooperation, the impact of spatial effects in scale-free networks is still not well understood. In addition to being heterogeneous, real contact networks exhibit a high mean local clustering coefficient, which implies the existence of an underlying metric space. Here we show that evolutionary dynamics in scale-free networks self-organize into spatial patterns in the underlying metric space. The resulting metric clusters of cooperators are able to survive in social dilemmas as their spatial organization shields them from surrounding defectors, similar to spatial selection in Euclidean space. We show that under certain conditions these metric clusters are more efficient than the most connected nodes at sustaining cooperation and that heterogeneity does not always favor-but can even hinder-cooperation in social dilemmas.
| S-EPMC5709505 | biostudies-literature
Project description:Failing to consider the strong correlations between weights and topological properties in capacity-weighted networks renders test results on the scale-free property unreliable. According to the preferential attachment mechanism, existing high-degree nodes normally attract new nodes. However, in capacity-weighted networks, the weights of existing edges increase as the network grows. We propose an optimized simplification method and apply it to international trade networks. Our study covers more than 1200 product categories annually from 1995 to 2018. We find that, on average, 38%, 38% and 69% of product networks in export, import and total trade are scale-free. Furthermore, the scale-free characteristics differ depending on the technology. Counter to expectations, the exports of high-technology products are distributed worldwide rather than concentrated in a few developed countries. Our research extends the scale-free exploration of capacity-weighted networks and demonstrates that choosing appropriate filtering methods can clarify the properties of complex networks.
| S-EPMC8233329 | biostudies-literature