Modes of Interaction between Individuals Dominate the Topologies of Real World Networks

We find that the topologies of real world networks, such as those formed within human societies, by the Internet, or among cellular proteins, are dominated by the mode of the interactions considered among the individuals. Specifically, a major dichotomy in previously studied networks arises from modeling networks in terms of pairwise versus group tasks. The former often intrinsically give rise to scale-free, disassortative, hierarchical networks, whereas the latter often give rise to single- or broad-scale, assortative, nonhierarchical networks. These dependencies explain contrasting observations among previous topological analyses of real world complex systems. We also observe this trend in systems with natural hierarchies, in which alternate representations of the same networks, but which capture different levels of the hierarchy, manifest these signature topological differences. For example, in both the Internet and cellular proteomes, networks of lower-level system components (routers within domains or proteins within biological processes) are assortative and nonhierarchical, whereas networks of upper-level system components (internet domains or biological processes) are disassortative and hierarchical. Our results demonstrate that network topologies of complex systems must be interpreted in light of their hierarchical natures and interaction types.     

Visualizing global properties of large complex networks

For complex biological networks, graphical representations are highly desired for understanding some design principles, but few drawing methods are available that capture topological features of a large and highly heterogeneous network, such as a protein interaction network. Here we propose the circular perspective drawing (CPD) method to visualize global structures of large complex networks. The presented CPD combines the quasi-continuous search (QCS) analogous to the steepest descent method with a random node swapping strategy for an enhanced calculation speed. The CPD depicts a network in an aesthetic manner by showing connection patterns between different parts of the network instead of detailed links between nodes. Global structural features of networks exhibited by CPD provide clues toward a comprehensive understanding of the network organizations. Availability: Software is freely available at http://www.cadlive.jp.     

Identification of a Topological Characteristic Responsible for the Biological Robustness of Regulatory Networks

Attribution of biological robustness to the specific structural properties of a regulatory network is an important yet unsolved problem in systems biology. It is widely believed that the topological characteristics of a biological control network largely determine its dynamic behavior, yet the actual mechanism is still poorly understood. Here, we define a novel structural feature of biological networks, termed ‘regulation entropy’, to quantitatively assess the influence of network topology on the robustness of the systems. Using the cell-cycle control networks of the budding yeast (Saccharomyces cerevisiae) and the fission yeast (Schizosaccharomyces pombe) as examples, we first demonstrate the correlation of this quantity with the dynamic stability of biological control networks, and then we establish a significant association between this quantity and the structural stability of the networks. And we further substantiate the generality of this approach with a broad spectrum of biological and random networks. We conclude that the regulation entropy is an effective order parameter in evaluating the robustness of biological control networks. Our work suggests a novel connection between the topological feature and the dynamic property of biological regulatory networks.     

Control Centrality and Hierarchical Structure in Complex Networks

We introduce the concept of control centrality to quantify the ability of a single node to control a directed weighted network. We calculate the distribution of control centrality for several real networks and find that it is mainly determined by the network’s degree distribution. We show that in a directed network without loops the control centrality of a node is uniquely determined by its layer index or topological position in the underlying hierarchical structure of the network. Inspired by the deep relation between control centrality and hierarchical structure in a general directed network, we design an efficient attack strategy against the controllability of malicious networks.     

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.     

Revisiting the variation of clustering coefficient of biological networks suggests new modular structure

ABSTRACT: A central idea in biology is the hierarchical organization of cellular processes. A commonly used method to identify the hierarchical modular organization of network relies on detecting a global signature known as variation of clustering coefficient (so-called modularity scaling). Although several studies have suggested other possible origins of this signature, it is still widely used nowadays to identify hierarchical modularity, especially in the analysis of biological networks. Therefore, a further and systematical investigation of this signature for different types of biological networks is necessary. RESULTS: We analyzed a variety of biological networks and found that the commonly used signature of hierarchical modularity is actually the reflection of spoke-like topology, suggesting a different view of network architecture. We proved that the existence of super-hubs is the origin that the clustering coefficient of a node follows a particular scaling law with degree k in metabolic networks. To study the modularity of biological networks, we systematically investigated the relationship between repulsion of hubs and variation of clustering coefficient. We provided direct evidences for repulsion between hubs being the underlying origin of the variation of clustering coefficient, and found that for biological networks having no anti-correlation between hubs, such as gene co-expression network, the clustering coefficient doesn't show dependence of degree. CONCLUSIONS: Here we have shown that the variation of clustering coefficient is neither sufficient nor exclusive for a network to be hierarchical. Our results suggest the existence of spoke-like modules as opposed to "deterministic model" of hierarchical modularity, and suggest the need to reconsider the organizational principle of biological hierarchy.     

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.     

Controllability in Cancer Metabolic Networks According to Drug Targets as Driver Nodes

Networks are employed to represent many nonlinear complex systems in the real world. The topological aspects and relationships between the structure and function of biological networks have been widely studied in the past few decades. However dynamic and control features of complex networks have not been widely researched, in comparison to topological network features. In this study, we explore the relationship between network controllability, topological parameters, and network medicine (metabolic drug targets). Considering the assumption that targets of approved anticancer metabolic drugs are driver nodes (which control cancer metabolic networks), we have applied topological analysis to genome-scale metabolic models of 15 normal and corresponding cancer cell types. The results show that besides primary network parameters, more complex network metrics such as motifs and clusters may also be appropriate for controlling the systems providing the controllability relationship between topological parameters and drug targets. Consequently, this study reveals the possibilities of following a set of driver nodes in network clusters instead of considering them individually according to their centralities. This outcome suggests considering distributed control systems instead of nodal control for cancer metabolic networks, leading to a new strategy in the field of network medicine.     

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.     

Resilience of protein-protein interaction networks as determined by their large-scale topological features

The relationship between the structure and function of biological networks constitutes a fundamental issue in systems biology. Particularly, the structure of protein-protein interaction networks is related to important biological functions. In this work, we investigated how such a resilience is determined by the large scale features of the respective networks. Four species are taken into account, namely yeast Saccharomyces cerevisiae, worm Caenorhabditis elegans, fly Drosophila melanogaster and Homo sapiens. We adopted two entropy-related measurements (degree entropy and dynamic entropy) in order to quantify the overall degree of robustness of these networks. We verified that while they exhibit similar structural variations under random node removal, they differ significantly when subjected to intentional attacks (hub removal). As a matter of fact, more complex species tended to exhibit more robust networks. More specifically, we quantified how six important measurements of the networks topology (namely clustering coefficient, average degree of neighbors, average shortest path length, diameter, assortativity coefficient, and slope of the power law degree distribution) correlated with the two entropy measurements. Our results revealed that the fraction of hubs and the average neighbor degree contribute significantly for the resilience of networks. In addition, the topological analysis of the removed hubs indicated that the presence of alternative paths between the proteins connected to hubs tend to reinforce resilience. The performed analysis helps to understand how resilience is underlain in networks and can be applied to the development of protein network models.     

Evolving Robust Gene Regulatory Networks

Design and implementation of robust network modules is essential for construction of complex biological systems through hierarchical assembly of ‘parts’ and ‘devices’. The robustness of gene regulatory networks (GRNs) is ascribed chiefly to the underlying topology. The automatic designing capability of GRN topology that can exhibit robust behavior can dramatically change the current practice in synthetic biology. A recent study shows that Darwinian evolution can gradually develop higher topological robustness. Subsequently, this work presents an evolutionary algorithm that simulates natural evolution in silico, for identifying network topologies that are robust to perturbations. We present a Monte Carlo based method for quantifying topological robustness and designed a fitness approximation approach for efficient calculation of topological robustness which is computationally very intensive. The proposed framework was verified using two classic GRN behaviors: oscillation and bistability, although the framework is generalized for evolving other types of responses. The algorithm identified robust GRN architectures which were verified using different analysis and comparison. Analysis of the results also shed light on the relationship among robustness, cooperativity and complexity. This study also shows that nature has already evolved very robust architectures for its crucial systems; hence simulation of this natural process can be very valuable for designing robust biological systems.     

Clustering under the line graph transformation: application to reaction network

Background  

Many real networks can be understood as two complementary networks with two kind of nodes. This is the case of metabolic networks where the first network has chemical compounds as nodes and the second one has nodes as reactions. In general, the second network may be related to the first one by a technique called line graph transformation (i.e., edges in an initial network are transformed into nodes). Recently, the main topological properties of the metabolic networks have been properly described by means of a hierarchical model. While the chemical compound network has been classified as hierarchical network, a detailed study of the chemical reaction network had not been carried out.     

Perspective: network-guided pattern formation of neural dynamics

The understanding of neural activity patterns is fundamentally linked to an understanding of how the brain''s network architecture shapes dynamical processes. Established approaches rely mostly on deviations of a given network from certain classes of random graphs. Hypotheses about the supposed role of prominent topological features (for instance, the roles of modularity, network motifs or hierarchical network organization) are derived from these deviations. An alternative strategy could be to study deviations of network architectures from regular graphs (rings and lattices) and consider the implications of such deviations for self-organized dynamic patterns on the network. Following this strategy, we draw on the theory of spatio-temporal pattern formation and propose a novel perspective for analysing dynamics on networks, by evaluating how the self-organized dynamics are confined by network architecture to a small set of permissible collective states. In particular, we discuss the role of prominent topological features of brain connectivity, such as hubs, modules and hierarchy, in shaping activity patterns. We illustrate the notion of network-guided pattern formation with numerical simulations and outline how it can facilitate the understanding of neural dynamics.     

Comparing the plant–herbivore network topology of different insect guilds in Neotropical savannas

1. Herbivorous insects can be classified into several trophic guilds with different levels of specialisation on their host plants, which may influence the topological structure of their trophic networks. The present study tested the hypothesis that the structure of plant–herbivore networks differs between guilds of galling, sucking, and chewing insects. 2. Six areas of Neotropical savannas were studied in two localities in the North of the state of Minas Gerais, Brazil. In each area, interactions between plant and insect species were used to build networks for different guilds. 3. In total, 18 plant–herbivore networks were built, comprising 317 insect morphospecies, 50 plant species, and 489 distinct interactions. The networks were characterised using species richness and different network topological measures (connectance, modularity, nestedness, and specialisation). 4. The results obtained showed no difference in species richness, network size, and connectance between distinct insect herbivore guilds. However, it was found that modularity was higher for exophagous than galling insect networks and nestedness was higher for chewers than for other guilds. On the other hand, galling insect networks showed higher specialisation than exophagous insect networks, and sucking insect networks were more specialised than chewing insect networks. 5. The findings of the present study indicate that, although species richness did not differ between insect guilds of herbivores in Neotropical savannas, the topological structure of networks is sensitive to biological and ecological differences between these herbivore groups. The present study stands out as the first to systematically compare the network structure of different herbivore guilds in Neotropical savannas.     

RedeR: R/Bioconductor package for representing modular structures, nested networks and multiple levels of hierarchical associations

Visualization and analysis of molecular networks are both central to systems biology. However, there still exists a large technological gap between them, especially when assessing multiple network levels or hierarchies. Here we present RedeR, an R/Bioconductor package combined with a Java core engine for representing modular networks. The functionality of RedeR is demonstrated in two different scenarios: hierarchical and modular organization in gene co-expression networks and nested structures in time-course gene expression subnetworks. Our results demonstrate RedeR as a new framework to deal with the multiple network levels that are inherent to complex biological systems. RedeR is available from http://bioconductor.org/packages/release/bioc/html/RedeR.html.     

Do motifs reflect evolved function?--No convergent evolution of genetic regulatory network subgraph topologies

Methods that analyse the topological structure of networks have recently become quite popular. Whether motifs (subgraph patterns that occur more often than in randomized networks) have specific functions as elementary computational circuits has been cause for debate. As the question is difficult to resolve with currently available biological data, we approach the issue using networks that abstractly model natural genetic regulatory networks (GRNs) which are evolved to show dynamical behaviors. Specifically one group of networks was evolved to be capable of exhibiting two different behaviors ("differentiation") in contrast to a group with a single target behavior. In both groups we find motif distribution differences within the groups to be larger than differences between them, indicating that evolutionary niches (target functions) do not necessarily mold network structure uniquely. These results show that variability operators can have a stronger influence on network topologies than selection pressures, especially when many topologies can create similar dynamics. Moreover, analysis of motif functional relevance by lesioning did not suggest that motifs were of greater importance to the functioning of the network than arbitrary subgraph patterns. Only when drastically restricting network size, so that one motif corresponds to a whole functionally evolved network, was preference for particular connection patterns found. This suggests that in non-restricted, bigger networks, entanglement with the rest of the network hinders topological subgraph analysis.     

FunMod: A Cytoscape Plugin for Identifying Functional Modules in Undirected Protein–Protein Networks

The characterization of the interacting behaviors of complex biological systems is a primary objective in protein–protein network analysis and computational biology. In this paper we present FunMod, an innovative Cytoscape version 2.8 plugin that is able to mine undirected protein–protein networks and to infer sub-networks of interacting proteins intimately correlated with relevant biological pathways. This plugin may enable the discovery of new pathways involved in diseases. In order to describe the role of each protein within the relevant biological pathways, FunMod computes and scores three topological features of the identified sub-networks. By integrating the results from biological pathway clustering and topological network analysis, FunMod proved to be useful for the data interpretation and the generation of new hypotheses in two case studies.     

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.