Complex cooperative networks from evolutionary preferential attachment

In spite of its relevance to the origin of complex networks, the interplay between form and function and its role during network formation remains largely unexplored. While recent studies introduce dynamics by considering rewiring processes of a pre-existent network, we study network growth and formation by proposing an evolutionary preferential attachment model, its main feature being that the capacity of a node to attract new links depends on a dynamical variable governed in turn by the node interactions. As a specific example, we focus on the problem of the emergence of cooperation by analyzing the formation of a social network with interactions given by the Prisoner's Dilemma. The resulting networks show many features of real systems, such as scale-free degree distributions, cooperative behavior and hierarchical clustering. Interestingly, results such as the cooperators being located mostly on nodes of intermediate degree are very different from the observations of cooperative behavior on static networks. The evolutionary preferential attachment mechanism points to an evolutionary origin of scale-free networks and may help understand similar feedback problems in the dynamics of complex networks by appropriately choosing the game describing the interaction of nodes.     

An Adaptive Complex Network Model for Brain Functional Networks

Brain functional networks are graph representations of activity in the brain, where the vertices represent anatomical regions and the edges their functional connectivity. These networks present a robust small world topological structure, characterized by highly integrated modules connected sparsely by long range links. Recent studies showed that other topological properties such as the degree distribution and the presence (or absence) of a hierarchical structure are not robust, and show different intriguing behaviors. In order to understand the basic ingredients necessary for the emergence of these complex network structures we present an adaptive complex network model for human brain functional networks. The microscopic units of the model are dynamical nodes that represent active regions of the brain, whose interaction gives rise to complex network structures. The links between the nodes are chosen following an adaptive algorithm that establishes connections between dynamical elements with similar internal states. We show that the model is able to describe topological characteristics of human brain networks obtained from functional magnetic resonance imaging studies. In particular, when the dynamical rules of the model allow for integrated processing over the entire network scale-free non-hierarchical networks with well defined communities emerge. On the other hand, when the dynamical rules restrict the information to a local neighborhood, communities cluster together into larger ones, giving rise to a hierarchical structure, with a truncated power law degree distribution.     

Biological network comparison using graphlet degree distribution

MOTIVATION: Analogous to biological sequence comparison, comparing cellular networks is an important problem that could provide insight into biological understanding and therapeutics. For technical reasons, comparing large networks is computationally infeasible, and thus heuristics, such as the degree distribution, clustering coefficient, diameter, and relative graphlet frequency distribution have been sought. It is easy to demonstrate that two networks are different by simply showing a short list of properties in which they differ. It is much harder to show that two networks are similar, as it requires demonstrating their similarity in all of their exponentially many properties. Clearly, it is computationally prohibitive to analyze all network properties, but the larger the number of constraints we impose in determining network similarity, the more likely it is that the networks will truly be similar. RESULTS: We introduce a new systematic measure of a network's local structure that imposes a large number of similarity constraints on networks being compared. In particular, we generalize the degree distribution, which measures the number of nodes 'touching' k edges, into distributions measuring the number of nodes 'touching' k graphlets, where graphlets are small connected non-isomorphic subgraphs of a large network. Our new measure of network local structure consists of 73 graphlet degree distributions of graphlets with 2-5 nodes, but it is easily extendible to a greater number of constraints (i.e. graphlets), if necessary, and the extensions are limited only by the available CPU. Furthermore, we show a way to combine the 73 graphlet degree distributions into a network 'agreement' measure which is a number between 0 and 1, where 1 means that networks have identical distributions and 0 means that they are far apart. Based on this new network agreement measure, we show that almost all of the 14 eukaryotic PPI networks, including human, resulting from various high-throughput experimental techniques, as well as from curated databases, are better modeled by geometric random graphs than by Erd?s-Rény, random scale-free, or Barabási-Albert scale-free networks. AVAILABILITY: Software executables are available upon request.     

Networks as constrained thermodynamic systems

We show how a network of interconnections between nodes can be constructed to have a specified distribution of nodal degrees. This is achieved by treating the network as a thermodynamic system subject to constraints and then rewiring the system to maintain the constraints while increasing the entropy. The general construction is given and illustrated by the simple example of an exponential network. By considering the constraints as a cost function analogous to an internal energy, we obtain a characterisation of the correspondence between the intensive and extensive variables of the network. Applied to networks in living organisms, this approach may lead to macroscopic variables useful in characterising living systems.     

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.     

Effectiveness of realistic vaccination strategies for contact networks of various degree distributions

A "contact network" that models infection transmission comprises nodes (or individuals) that are linked when they are in contact and can potentially transmit an infection. Through analysis and simulation, we studied the influence of the distribution of the number of contacts per node, defined as degree, on infection spreading and its control by vaccination. Three random contact networks of various degree distributions were examined. In a scale-free network, the frequency of high-degree nodes decreases as the power of the degree (the case of the third power is studied here); the decrease is exponential in an exponential network, whereas all nodes have the same degree in a constant network. Aiming for containment at a very early stage of an epidemic, we measured the sustainability of a specific network under a vaccination strategy by employing the critical transmissibility larger than which the epidemic would occur. We examined three vaccination strategies: mass, ring, and acquaintance. Irrespective of the networks, mass preventive vaccination increased the critical transmissibility inversely proportional to the unvaccinated rate of the population. Ring post-outbreak vaccination increased the critical transmissibility inversely proportional to the unvaccinated rate, which is the rate confined to the targeted ring comprising the neighbors of an infected node; however, the total number of vaccinated nodes could mostly be fewer than 100 nodes at the critical transmissibility. In combination, mass and ring vaccinations decreased the pathogen's "effective" transmissibility each by the factor of the unvaccinated rate. The amount of vaccination used in acquaintance preventive vaccination was lesser than the mass vaccination, particularly under a highly heterogeneous degree distribution; however, it was not as less as that used in ring vaccination. Consequently, our results yielded a quantitative assessment of the amount of vaccination necessary for infection containment, which is universally applicable to contact networks of various degree distributions.     

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.     

Boolean dynamics of Kauffman models with a scale-free network

We studied the Boolean dynamics of the "quenched" Kauffman models with a directed scale-free network, comparing with that of the original directed random Kauffman networks and that of the directed exponential-fluctuation networks. We have numerically investigated the distributions of the state cycle lengths and its changes as the network size N and the average degree k of nodes increase. In the relatively small network (N approximately 150), the median, the mean value and the standard deviation grow exponentially with N in the directed scale-free and the directed exponential-fluctuation networks with k=2, where the function forms of the distributions are given as an almost exponential. We have found that for the relatively large N approximately 10(3) the growth of the median of the distribution over the attractor lengths asymptotically changes from algebraic type to exponential one as the average degree k goes to k=2. The result supports the existence of the transition at k(c)=2 derived in the annealed model.     

Some protein interaction data do not exhibit power law statistics

It has been claimed that protein-protein interaction (PPI) networks are scale-free, and that identifying high-degree "hub" proteins reveals important features of PPI networks. In this paper, we evaluate the claims that PPI node degree sequences follow a power law, a necessary condition for networks to be scale-free. We provide two PPI network examples which clearly do not have power laws when analyzed correctly, and thus at least these PPI networks are not scale-free. We also show that these PPI networks do appear to have power laws according to methods that have become standard in the existing literature. We explain the source of this error using numerically generated data from analytic formulas, where there are no sampling or noise ambiguities.     

Congruent epidemic models for unstructured and structured populations: analytical reconstruction of a 2003 SARS outbreak

Both the threat of bioterrorism and the natural emergence of contagious diseases underscore the importance of quantitatively understanding disease transmission in structured human populations. Over the last few years, researchers have advanced the mathematical theory of scale-free networks and used such theoretical advancements in pilot epidemic models. Scale-free contact networks are particularly interesting in the realm of mathematical epidemiology, primarily because these networks may allow meaningfully structured populations to be incorporated in epidemic models at moderate or intermediate levels of complexity. Moreover, a scale-free contact network with node degree correlation is in accord with the well-known preferred mixing concept. The present author describes a semi-empirical and deterministic epidemic modeling approach that (a) focuses on time-varying rates of disease transmission in both unstructured and structured populations and (b) employs probability density functions to characterize disease progression and outbreak controls. Given an epidemic curve for a historical outbreak, this modeling approach calls for Monte Carlo calculations (that define the average new infection rate) and solutions to integro-differential equations (that describe outbreak dynamics in an aggregate population or across all network connectivity classes). Numerical results are obtained for the 2003 SARS outbreak in Taiwan and the dynamical implications of time-varying transmission rates and scale-free contact networks are discussed in some detail.     

An evolving model of undirected networks based on microscopic biological interaction systems

With protein or gene interaction systems as the background, this paper proposes an evolving model of biological undirected networks, which are consistent with some plausible mechanisms in biology. Through introducing a rule of preferential duplication of a node inversely proportional to the degree of existing nodes and an attribute of the age of the node (the older, the more influence), by which the probability of a node receiving re-wiring links is chosen, the model networks generated in certain parameter conditions could reproduce series of statistic topological characteristics of real biological graphs, including the scale-free feature, small world effect, hierarchical modularity, limited structural robustness, and disassortativity of degree–degree correlation.     

Ongoing Processes in a Fitness Network Model under Restricted Resources

In real networks, the resources that make up the nodes and edges are finite. This constraint poses a serious problem for network modeling, namely, the compatibility between robustness and efficiency. However, these concepts are generally in conflict with each other. In this study, we propose a new fitness-driven network model for finite resources. In our model, each individual has its own fitness, which it tries to increase. The main assumption in fitness-driven networks is that incomplete estimation of fitness results in a dynamical growing network. By taking into account these internal dynamics, nodes and edges emerge as a result of exchanges between finite resources. We show that our network model exhibits exponential distributions in the in- and out-degree distributions and a power law distribution of edge weights. Furthermore, our network model resolves the trade-off relationship between robustness and efficiency. Our result suggests that growing and anti-growing networks are the result of resolving the trade-off problem itself.     

Hub-centered gene network reconstruction using automatic relevance determination

Network inference deals with the reconstruction of biological networks from experimental data. A variety of different reverse engineering techniques are available; they differ in the underlying assumptions and mathematical models used. One common problem for all approaches stems from the complexity of the task, due to the combinatorial explosion of different network topologies for increasing network size. To handle this problem, constraints are frequently used, for example on the node degree, number of edges, or constraints on regulation functions between network components. We propose to exploit topological considerations in the inference of gene regulatory networks. Such systems are often controlled by a small number of hub genes, while most other genes have only limited influence on the network's dynamic. We model gene regulation using a Bayesian network with discrete, Boolean nodes. A hierarchical prior is employed to identify hub genes. The first layer of the prior is used to regularize weights on edges emanating from one specific node. A second prior on hyperparameters controls the magnitude of the former regularization for different nodes. The net effect is that central nodes tend to form in reconstructed networks. Network reconstruction is then performed by maximization of or sampling from the posterior distribution. We evaluate our approach on simulated and real experimental data, indicating that we can reconstruct main regulatory interactions from the data. We furthermore compare our approach to other state-of-the art methods, showing superior performance in identifying hubs. Using a large publicly available dataset of over 800 cell cycle regulated genes, we are able to identify several main hub genes. Our method may thus provide a valuable tool to identify interesting candidate genes for further study. Furthermore, the approach presented may stimulate further developments in regularization methods for network reconstruction from data.     

Epidemic threshold and network structure: The interplay of probability of transmission and of persistence in small-size directed networks

A growing number of studies are investigating the effect of contact structure on the dynamics of epidemics in large-scale complex networks. Whether findings thus obtained apply also to networks of small size, and thus to many real-world biological applications, is still an open question. We use numerical simulations of disease spread in directed networks of 100 individual nodes with a constant number of links. We show that, no matter the type of network structure (local, small-world, random and scale-free), there is a linear threshold determined by the probability of infection transmission between connected nodes and the probability of infection persistence in an infected node. The threshold is significantly lower for scale-free networks compared to local, random and small-world ones only if super-connected nodes have a higher number of links both to and from other nodes. The starting point, the node at which the epidemic starts, does not affect the threshold conditions, but has a marked influence on the final size of the epidemic in all kinds of network. There is evidence that contact structure has an influence on the average final size of an epidemic across all starting nodes, with significantly lower values in scale-free networks at equilibrium. Simulations in scale-free networks show a distinctive time-series pattern, which, if found in a real epidemic, can be used to infer the underlying network structure. The findings have relevance also for meta-population ecology and species conservation.     

Visualization and analysis of the complexome network of Saccharomyces cerevisiae

Most processes in the cell are delivered by protein complexes, rather than individual proteins. While the association of proteins has been studied extensively in protein-protein interaction networks (the interactome), an intuitive and effective representation of complex-complex connections (the complexome) is not yet available. Here, we describe a new representation of the complexome of Saccharomyces cerevisiae. Using the core-module-attachment data of Gavin et al. ( Nature 2006 , 440 , 631 - 6 ), protein complexes in the network are represented as nodes; these are connected by edges that represent shared core and/or module protein subunits. To validate this network, we examined the network topology and its distribution of biological processes. The complexome network showed scale-free characteristics, with a power law-like node degree distribution and clustering coefficient independent of node degree. Connected complexes in the network showed similarities in biological process that were nonrandom. Furthermore, clusters of interacting complexes reflected a higher-level organization of many cellular functions. The strong functional relationships seen in these clusters, along with literature evidence, allowed 44 uncharacterized complexes to be assigned putative functions using guilt-by-association. We demonstrate our network model using the GEOMI visualization platform, on which we have developed capabilities to integrate and visualize complexome data.     

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.     

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.     

油菜基因流网络的结构特性与小团体分析

为从系统角度掌握转基因油菜(Brassica campestris)基因流规律, 基于常规油菜与十字花科植物杂交的有关文献,构建了油菜基因流网络拓扑图实例并分析其网络结构特性。研究结果表明, 该网络节点度服从幂律分布, 具有无标度特性。从随机攻击和恶性攻击两个方面对标准结构熵和网络效率2个指标的网络稳健性进行分析, 结果显示在随机移除不到10%的顶点时网络表现较好的鲁棒性, 但在受到选择性移除10%的顶点时, 网络具有极弱的抗攻击性。基于软件UCINET对网络进行了小团体和结构同型性分析, 可将网络中298个节点22类十字花科植物划分为2个小团体和5类结构角色, 其中甘蓝型油菜在基因流网络小团体中具有关键性作用。这些研究结果可为揭示转基因油菜基因流规律提供新思路, 同时也可对转基因油菜商业化种植采取合理的农业生产栽培管理措施提供参考。     

Degree Correlations in Directed Scale-Free Networks

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.