A Complex Network Approach to Distributional Semantic Models

A number of studies on network analysis have focused on language networks based on free word association, which reflects human lexical knowledge, and have demonstrated the small-world and scale-free properties in the word association network. Nevertheless, there have been very few attempts at applying network analysis to distributional semantic models, despite the fact that these models have been studied extensively as computational or cognitive models of human lexical knowledge. In this paper, we analyze three network properties, namely, small-world, scale-free, and hierarchical properties, of semantic networks created by distributional semantic models. We demonstrate that the created networks generally exhibit the same properties as word association networks. In particular, we show that the distribution of the number of connections in these networks follows the truncated power law, which is also observed in an association network. This indicates that distributional semantic models can provide a plausible model of lexical knowledge. Additionally, the observed differences in the network properties of various implementations of distributional semantic models are consistently explained or predicted by considering the intrinsic semantic features of a word-context matrix and the functions of matrix weighting and smoothing. Furthermore, to simulate a semantic network with the observed network properties, we propose a new growing network model based on the model of Steyvers and Tenenbaum. The idea underlying the proposed model is that both preferential and random attachments are required to reflect different types of semantic relations in network growth process. We demonstrate that this model provides a better explanation of network behaviors generated by distributional semantic models.     

On the evolution of scale-free topologies with a gene regulatory network model

A novel approach to generating scale-free network topologies is introduced, based on an existing artificial gene regulatory network model. From this model, different interaction networks can be extracted, based on an activation threshold. By using an evolutionary computation approach, the model is allowed to evolve, in order to reach specific network statistical measures. The results obtained show that, when the model uses a duplication and divergence initialisation, such as seen in nature, the resulting regulation networks not only are closer in topology to scale-free networks, but also require only a few evolutionary cycles to achieve a satisfactory error value.     

Statistical analyses support power law distributions found in neuronal avalanches

The size distribution of neuronal avalanches in cortical networks has been reported to follow a power law distribution with exponent close to -1.5, which is a reflection of long-range spatial correlations in spontaneous neuronal activity. However, identifying power law scaling in empirical data can be difficult and sometimes controversial. In the present study, we tested the power law hypothesis for neuronal avalanches by using more stringent statistical analyses. In particular, we performed the following steps: (i) analysis of finite-size scaling to identify scale-free dynamics in neuronal avalanches, (ii) model parameter estimation to determine the specific exponent of the power law, and (iii) comparison of the power law to alternative model distributions. Consistent with critical state dynamics, avalanche size distributions exhibited robust scaling behavior in which the maximum avalanche size was limited only by the spatial extent of sampling ("finite size" effect). This scale-free dynamics suggests the power law as a model for the distribution of avalanche sizes. Using both the Kolmogorov-Smirnov statistic and a maximum likelihood approach, we found the slope to be close to -1.5, which is in line with previous reports. Finally, the power law model for neuronal avalanches was compared to the exponential and to various heavy-tail distributions based on the Kolmogorov-Smirnov distance and by using a log-likelihood ratio test. Both the power law distribution without and with exponential cut-off provided significantly better fits to the cluster size distributions in neuronal avalanches than the exponential, the lognormal and the gamma distribution. In summary, our findings strongly support the power law scaling in neuronal avalanches, providing further evidence for critical state dynamics in superficial layers of cortex.     

Emergence of scale-free distribution in protein–protein interaction networks based on random selection of interacting domain pairs

Recent analyses of biological and artificial networks have revealed a common network architecture, called scale-free topology. The origin of the scale-free topology has been explained by using growth and preferential attachment mechanisms. In a cell, proteins are the most important carriers of function, and are composed of domains as elemental units responsible for the physical interaction between protein pairs. Here, we propose a model for protein–protein interaction networks that reveals the emergence of two possible topologies. We show that depending on the number of randomly selected interacting domain pairs, the connectivity distribution follows either a scale-free distribution, even in the absence of the preferential attachment, or a normal distribution. This new approach only requires an evolutionary model of proteins (nodes) but not for the interactions (edges). The edges are added by means of random interaction of domain pairs. As a result, this model offers a new mechanistic explanation for understanding complex networks with a direct biological interpretation because only protein structures and their functions evolved through genetic modifications of amino acid sequences. These findings are supported by numerical simulations as well as experimental data.     

Is the intrinsic disorder of proteins the cause of the scale-free architecture of protein-protein interaction networks?

In protein-protein interaction (PPI) networks certain topological properties appear to be recurrent: network maps are considered scale-free. It is possible that this topology is reflected in the protein structure. In this paper, we investigate the role of protein disorder in the network topology. We find that the disorder of a protein (or of its neighbors) is independent of its number of PPIs. This result suggests that protein disorder does not play a role in the scale-free architecture of protein networks.     

The role of log-normal dynamics in the evolution of biochemical pathways

The study of the scale-free topology in non-biological and biological networks and the dynamics that can explain this fascinating property of complex systems have captured the attention of the scientific community in the last years. Here, we analyze the biochemical pathways of three organisms (Methanococcus jannaschii, Escherichia coli, Saccharomyces cerevisiae) which are representatives of the main kingdoms Archaea, Bacteria and Eukaryotes during the course of the biological evolution. We can consider two complementary representations of the biochemical pathways: the enzymes network and the chemical compounds network. In this article, we propose a stochastic model that explains that the scale-free topology with exponent in the vicinity of gamma approximately 3/2 found across these three organisms is governed by the log-normal dynamics in the evolution of the enzymes network. Precisely, the fluctuations of the connectivity degree of enzymes in the biochemical pathways between evolutionary distant organisms follow the same conserved dynamical principle, which in the end is the origin of the stationary scale-free distribution observed among species, from Archaea to Eukaryotes. In particular, the log-normal dynamics guarantees the conservation of the scale-free distribution in evolving networks. Furthermore, the log-normal dynamics also gives a possible explanation for the restricted range of observed exponents gamma in the scale-free networks (i.e., gamma > or = 3/2). Finally, our model is also applied to the chemical compounds network of biochemical pathways and the Internet network.     

Molecular basis for evolving modularity in the yeast protein interaction network

Scale-free networks are generically defined by a power-law distribution of node connectivities. Vastly different graph topologies fit this law, ranging from the assortative, with frequent similar-degree node connections, to a modular structure. Using a metric to determine the extent of modularity, we examined the yeast protein network and found it to be significantly self-dissimilar. By orthologous node categorization, we established the evolutionary trend in the network, from an “emerging” assortative network to a present-day modular topology. The evolving topology fits a generic connectivity distribution but with a progressive enrichment in intramodule hubs that avoid each other. Primeval tolerance to random node failure is shown to evolve toward resilience to hub failure, thus removing the fragility often ascribed to scale-free networks. This trend is algorithmically reproduced by adopting a connectivity accretion law that disfavors like-degree connections for large-degree nodes. The selective advantage of this trend relates to the need to prevent a failed hub from inducing failure in an adjacent hub. The molecular basis for the evolutionary trend is likely rooted in the high-entropy penalty entailed in the association of two intramodular hubs.     

Intrinsic properties of Boolean dynamics in complex networks

We study intrinsic properties of attractor in Boolean dynamics of complex networks with scale-free topology, comparing with those of the so-called Kauffman's random Boolean networks. We numerically study both frozen and relevant nodes in each attractor in the dynamics of relatively small networks (20?N?200). We investigate numerically robustness of an attractor to a perturbation. An attractor with cycle length of ?_c in a network of size N consists of ?_c states in the state space of 2^N states; each attractor has the arrangement of N nodes, where the cycle of attractor sweeps ?_c states. We define a perturbation as a flip of the state on a single node in the attractor state at a given time step. We show that the rate between unfrozen and relevant nodes in the dynamics of a complex network with scale-free topology is larger than that in Kauffman's random Boolean network model. Furthermore, we find that in a complex scale-free network with fluctuation of the in-degree number, attractors are more sensitive to a state flip for a highly connected node (i.e. input-hub node) than to that for a less connected node. By some numerical examples, we show that the number of relevant nodes increases, when an input-hub node is coincident with and/or connected with an output-hub node (i.e. a node with large output-degree) one another.     

Modeling for evolving biological networks with scale-free connectivity, hierarchical modularity, and disassortativity

We propose a growing network model that consists of two tunable mechanisms: growth by merging modules which are represented as complete graphs and a fitness-driven preferential attachment. Our model exhibits the three prominent statistical properties are widely shared in real biological networks, for example gene regulatory, protein-protein interaction, and metabolic networks. They retain three power law relationships, such as the power laws of degree distribution, clustering spectrum, and degree-degree correlation corresponding to scale-free connectivity, hierarchical modularity, and disassortativity, respectively. After making comparisons of these properties between model networks and biological networks, we confirmed that our model has inference potential for evolutionary processes of biological networks.     

A more efficient search strategy for aging genes based on connectivity

MOTIVATION: Many aging genes have been found from unbiased screens in model organisms. Genetic interventions promoting longevity are usually quantitative, while in many other biological fields (e.g. development) null mutations alone have been very informative. Therefore, in the case of aging the task is larger and the need for a more efficient genetic search strategy is especially strong. RESULTS: The topology of genetic and metabolic networks is organized according to a scale-free distribution, in which hubs with large numbers of links are present. We have developed a computational model of aging genes as the hubs of biological networks. The computational model shows that, after generalized damage, the function of a network with scale-free topology can be significantly restored by a limited intervention on the hubs. Analyses of data on aging genes and biological networks support the applicability of the model to biological aging. The model also might explain several of the properties of aging genes, including the high degree of conservation across different species. The model suggests that aging genes tend to have a higher number of connections and therefore supports a strategy, based on connectivity, for prioritizing what might otherwise be a random search for aging genes.     

The emergence of scaling in sequence-based physical models of protein evolution

It has recently been discovered that many biological systems, when represented as graphs, exhibit a scale-free topology. One such system is the set of structural relationships among protein domains. The scale-free nature of this and other systems has previously been explained using network growth models that, although motivated by biological processes, do not explicitly consider the underlying physics or biology. In this work we explore a sequence-based model for the evolution protein structures and demonstrate that this model is able to recapitulate the scale-free nature observed in graphs of real protein structures. We find that this model also reproduces other statistical feature of the protein domain graph. This represents, to our knowledge, the first such microscopic, physics-based evolutionary model for a scale-free network of biological importance and as such has strong implications for our understanding of the evolution of protein structures and of other biological networks.     

Evolution of cooperation on dynamical graphs

There are two key characteristic of animal and human societies: (1) degree heterogeneity, meaning that not all individual have the same number of associates; and (2) the interaction topology is not static, i.e. either individuals interact with different set of individuals at different times of their life, or at least they have different associations than their parents. Earlier works have shown that population structure is one of the mechanisms promoting cooperation. However, most studies had assumed that the interaction network can be described by a regular graph (homogeneous degree distribution). Recently there are an increasing number of studies employing degree heterogeneous graphs to model interaction topology. But mostly the interaction topology was assumed to be static. Here we investigate the fixation probability of the cooperator strategy in the prisoner's dilemma, when interaction network is a random regular graph, a random graph or a scale-free graph and the interaction network is allowed to change.     

The emergent properties of a dolphin social network

Many complex networks, including human societies, the Internet, the World Wide Web and power grids, have surprising properties that allow vertices (individuals, nodes, Web pages, etc.) to be in close contact and information to be transferred quickly between them. Nothing is known of the emerging properties of animal societies, but it would be expected that similar trends would emerge from the topology of animal social networks. Despite its small size (64 individuals), the Doubtful Sound community of bottlenose dolphins has the same characteristics. The connectivity of individuals follows a complex distribution that has a scale-free power-law distribution for large k. In addition, the ability for two individuals to be in contact is unaffected by the random removal of individuals. The removal of individuals with many links to others does affect the length of the 'information' path between two individuals, but, unlike other scale-free networks, it does not fragment the cohesion of the social network. These self-organizing phenomena allow the network to remain united, even in the case of catastrophic death events.     

A scale-free structure prior for graphical models with applications in functional genomics

The problem of reconstructing large-scale, gene regulatory networks from gene expression data has garnered considerable attention in bioinformatics over the past decade with the graphical modeling paradigm having emerged as a popular framework for inference. Analysis in a full Bayesian setting is contingent upon the assignment of a so-called structure prior-a probability distribution on networks, encoding a priori biological knowledge either in the form of supplemental data or high-level topological features. A key topological consideration is that a wide range of cellular networks are approximately scale-free, meaning that the fraction, , of nodes in a network with degree is roughly described by a power-law with exponent between and . The standard practice, however, is to utilize a random structure prior, which favors networks with binomially distributed degree distributions. In this paper, we introduce a scale-free structure prior for graphical models based on the formula for the probability of a network under a simple scale-free network model. Unlike the random structure prior, its scale-free counterpart requires a node labeling as a parameter. In order to use this prior for large-scale network inference, we design a novel Metropolis-Hastings sampler for graphical models that includes a node labeling as a state space variable. In a simulation study, we demonstrate that the scale-free structure prior outperforms the random structure prior at recovering scale-free networks while at the same time retains the ability to recover random networks. We then estimate a gene association network from gene expression data taken from a breast cancer tumor study, showing that scale-free structure prior recovers hubs, including the previously unknown hub SLC39A6, which is a zinc transporter that has been implicated with the spread of breast cancer to the lymph nodes. Our analysis of the breast cancer expression data underscores the value of the scale-free structure prior as an instrument to aid in the identification of candidate hub genes with the potential to direct the hypotheses of molecular biologists, and thus drive future experiments.     

Discriminating Different Classes of Biological Networks by Analyzing the Graphs Spectra Distribution

The brain''s structural and functional systems, protein-protein interaction, and gene networks are examples of biological systems that share some features of complex networks, such as highly connected nodes, modularity, and small-world topology. Recent studies indicate that some pathologies present topological network alterations relative to norms seen in the general population. Therefore, methods to discriminate the processes that generate the different classes of networks (e.g., normal and disease) might be crucial for the diagnosis, prognosis, and treatment of the disease. It is known that several topological properties of a network (graph) can be described by the distribution of the spectrum of its adjacency matrix. Moreover, large networks generated by the same random process have the same spectrum distribution, allowing us to use it as a “fingerprint”. Based on this relationship, we introduce and propose the entropy of a graph spectrum to measure the “uncertainty” of a random graph and the Kullback-Leibler and Jensen-Shannon divergences between graph spectra to compare networks. We also introduce general methods for model selection and network model parameter estimation, as well as a statistical procedure to test the nullity of divergence between two classes of complex networks. Finally, we demonstrate the usefulness of the proposed methods by applying them to (1) protein-protein interaction networks of different species and (2) on networks derived from children diagnosed with Attention Deficit Hyperactivity Disorder (ADHD) and typically developing children. We conclude that scale-free networks best describe all the protein-protein interactions. Also, we show that our proposed measures succeeded in the identification of topological changes in the network while other commonly used measures (number of edges, clustering coefficient, average path length) failed.     

Conservation and coevolution in the scale-free human gene coexpression network

The role of natural selection in biology is well appreciated. Recently, however, a critical role for physical principles of network self-organization in biological systems has been revealed. Here, we employ a systems level view of genome-scale sequence and expression data to examine the interplay between these two sources of order, natural selection and physical self-organization, in the evolution of human gene regulation. The topology of a human gene coexpression network, derived from tissue-specific expression profiles, shows scale-free properties that imply evolutionary self-organization via preferential node attachment. Genes with numerous coexpressed partners (the hubs of the coexpression network) evolve more slowly on average than genes with fewer coexpressed partners, and genes that are coexpressed show similar rates of evolution. Thus, the strength of selective constraints on gene sequences is affected by the topology of the gene coexpression network. This connection is strong for the coding regions and 3' untranslated regions (UTRs), but the 5' UTRs appear to evolve under a different regime. Surprisingly, we found no connection between the rate of gene sequence divergence and the extent of gene expression profile divergence between human and mouse. This suggests that distinct modes of natural selection might govern sequence versus expression divergence, and we propose a model, based on rapid, adaptation-driven divergence and convergent evolution of gene expression patterns, for how natural selection could influence gene expression divergence.     

Asymptotic states and topological structure of an activation-deactivation chemical network

The influence of the topology on the asymptotic states of a network of interacting chemical species has been studied by simulating its time evolution. Random and scale-free networks have been designed to support relevant features of activation-deactivation reactions networks (mapping signal transduction networks) and the system of ordinary differential equations associated to the dynamics has been numerically solved. We analysed stationary states of the dynamics as a function of the network's connectivity and of the distribution of the chemical species on the network; we found important differences between the two topologies in the regime of low connectivity. In particular, only for low connected scale-free networks it is possible to find zero activity patterns as stationary states of the dynamics which work as signal off-states. Asymptotic features of random and scale-free networks become similar as the connectivity increases.     

Effect of sampling on topology predictions of protein-protein interaction networks

Currently available protein-protein interaction (PPI) network or 'interactome' maps, obtained with the yeast two-hybrid (Y2H) assay or by co-affinity purification followed by mass spectrometry (co-AP/MS), only cover a fraction of the complete PPI networks. These partial networks display scale-free topologies--most proteins participate in only a few interactions whereas a few proteins have many interaction partners. Here we analyze whether the scale-free topologies of the partial networks obtained from Y2H assays can be used to accurately infer the topology of complete interactomes. We generated four theoretical interaction networks of different topologies (random, exponential, power law, truncated normal). Partial sampling of these networks resulted in sub-networks with topological characteristics that were virtually indistinguishable from those of currently available Y2H-derived partial interactome maps. We conclude that given the current limited coverage levels, the observed scale-free topology of existing interactome maps cannot be confidently extrapolated to complete interactomes.     

How affinity influences tolerance in an idiotypic network

Idiotypic network models give one possible justification for the appearance of tolerance for a certain category of cells while maintaining immunization for the others. In this paper, we provide new evidence that the manner in which affinity is defined in an idiotypic network model imposes a definite topology on the connectivity of the potential idiotypic network that can emerge. The resulting topology is responsible for very different qualitative behaviour of the network. We show that using a 2D shape-space model with affinity based on complementary regions, a cluster-free topology results that clearly divides the space into distinct zones; if antigens fall into a zone in which there are no available antibodies to bind to, they are tolerated. On the other hand, if they fall into a zone in which there are highly concentrated antibodies available for binding, then they will be eliminated. On the contrary, using a 2D shape space with an affinity function based on cell similarity, a highly clustered topology emerges in which there is no separation of the space into isolated tolerant and non-tolerant zones. Using a bit-string shape space, both similar and complementary affinity measures also result in highly clustered networks. In the networks whose topologies exhibit high clustering, the tolerant and intolerant zones are so intertwined that the networks either reject all antigen or tolerate all antigen. We show that the distribution and topology of the antibody network defined by the complete set of nodes and links-an autonomous feature of the system-therefore selects which antigens are tolerated and which are eliminated.