Parallel structures in multidimensional networks

The method of parallel representation of networks is used to determine the restrictions imposed by the space dimension on the variety of multidimensional regular networks. The method makes it possible to establish an analytic relation between the network dimension and the connectivity of vertices and the perimeter of elementary contours. It is proved that an infinite-dimensional network is equivalent to an infinite tree. In addition, the problem of closed regular polytopes inside networks is discussed.     

Kernel-Kohonen networks

We investigate the combination of the Kohonen networks with the kernel methods in the context of classification. We use the idea of kernel functions to handle products of vectors of arbitrary dimension. We indicate how to build Kohonen networks with robust classification performance by transformation of the original data vectors into a possibly infinite dimensional space. The resulting Kohonen networks preserve a non-Euclidean neighborhood structure of the input space that fits the properties of the data. We show how to optimize the transformation of the data vectors in order to obtain higher classification performance. We compare the kernel-Kohonen networks with the regular Kohonen networks in the context of a classification task.     

Traveling and Pinned Fronts in Bistable Reaction-Diffusion Systems on Networks

Traveling fronts and stationary localized patterns in bistable reaction-diffusion systems have been broadly studied for classical continuous media and regular lattices. Analogs of such non-equilibrium patterns are also possible in networks. Here, we consider traveling and stationary patterns in bistable one-component systems on random Erdös-Rényi, scale-free and hierarchical tree networks. As revealed through numerical simulations, traveling fronts exist in network-organized systems. They represent waves of transition from one stable state into another, spreading over the entire network. The fronts can furthermore be pinned, thus forming stationary structures. While pinning of fronts has previously been considered for chains of diffusively coupled bistable elements, the network architecture brings about significant differences. An important role is played by the degree (the number of connections) of a node. For regular trees with a fixed branching factor, the pinning conditions are analytically determined. For large Erdös-Rényi and scale-free networks, the mean-field theory for stationary patterns is constructed.     

Visual exploration of isotope labeling networks in 3D

Isotope labeling networks (ILNs) are graphs explaining the flow of isotope labeled molecules in a metabolic network. Moreover, they are the structural backbone of metabolic flux analysis (MFA) by isotopic tracers which has been established as a standard experimental tool in fluxomics. To configure an isotope labeling experiment (ILE) for MFA, the structure of the corresponding ILN must be understood to a certain extent even by a practitioner. Graph algorithms help to analyze the network structure but produce rather abstract results. Here, the major obstruction is the high dimension of these networks and the large number of network components which, consequently, are hard to figure out manually. At the interface between theory and experiment, the three-dimensional interactive visualization tool CumoVis has been developed for exploring the network structure in a step by step manner. Navigation and orientation within ILNs are supported by exploiting the natural 3D structure of an underlying metabolite network with stacked labeled particles on top of each metabolite node. Network exploration is facilitated by rotating, zooming, forward and backward path tracing and, most important, network component reduction. All features of CumoVis are explained with an educational example and a realistic network describing carbon flow in the citric acid cycle.     

An integrate-and-fire model for synchronized bursting in a network of cultured cortical neurons

It has been suggested that spontaneous synchronous neuronal activity is an essential step in the formation of functional networks in the central nervous system. The key features of this type of activity consist of bursts of action potentials with associated spikes of elevated cytoplasmic calcium. These features are also observed in networks of rat cortical neurons that have been formed in culture. Experimental studies of these cultured networks have led to several hypotheses for the mechanisms underlying the observed synchronized oscillations. In this paper, bursting integrate-and-fire type mathematical models for regular spiking (RS) and intrinsic bursting (IB) neurons are introduced and incorporated through a small-world connection scheme into a two-dimensional excitatory network similar to those in the cultured network. This computer model exhibits spontaneous synchronous activity through mechanisms similar to those hypothesized for the cultured experimental networks. Traces of the membrane potential and cytoplasmic calcium from the model closely match those obtained from experiments. We also consider the impact on network behavior of the IB neurons, the geometry and the small world connection scheme. Action Editor: David Golomb     

The impacts of network topology on disease spread

Individuals in a population susceptible to a disease may be represented as vertices in a network, with the edges that connect vertices representing social and/or spatial contact between individuals. Networks, which explicitly included six different patterns of connection between vertices, were created. Both scale-free networks and random graphs showed a different response in path level to increasing levels of clustering than regular lattices. Clustering promoted short path lengths in all network types, but randomly assembled networks displayed a logarithmic relationship between degree and path length; whereas this response was linear in regular lattices. In all cases, small-world models, generated by rewiring the connections of a regular lattice, displayed properties, which spanned the gap between random and regular networks.Simulation of a disease in these networks showed a strong response to connectance pattern, even when the number of edges and vertices were approximately equal. Epidemic spread was fastest, and reached the largest size, in scale-free networks, then in random graphs. Regular lattices were the slowest to be infected, and rewired lattices were intermediate between these two extremes. Scale-free networks displayed the capacity to produce an epidemic even at a likelihood of infection, which was too low to produce an epidemic for the other network types. The interaction between the statistical properties of the network and the results of epidemic spread provides a useful tool for assessing the risk of disease spread in more realistic networks.     

The effect of negative feedback loops on the dynamics of boolean networks

Feedback loops play an important role in determining the dynamics of biological networks. To study the role of negative feedback loops, this article introduces the notion of distance-to-positive-feedback which, in essence, captures the number of independent negative feedback loops in the network, a property inherent in the network topology. Through a computational study using Boolean networks, it is shown that distance-to-positive-feedback has a strong influence on network dynamics and correlates very well with the number and length of limit cycles in the phase space of the network. To be precise, it is shown that, as the number of independent negative feedback loops increases, the number (length) of limit cycles tends to decrease (increase). These conclusions are consistent with the fact that certain natural biological networks exhibit generally regular behavior and have fewer negative feedback loops than randomized networks with the same number of nodes and same connectivity.     

A condition for cooperation in a game on complex networks

We study a condition of favoring cooperation in Prisoner's Dilemma game on complex networks. There are two kinds of players: cooperators and defectors. Cooperators pay a benefit b to their neighbors at a cost c, whereas defectors only receive a benefit. The game is a death-birth process with weak selection. Although it has been widely thought that b/c>〈k〉 is a condition of favoring cooperation (Ohtsuki et al., 2006), we find that b/c>〈k_nn〉 is the condition. We also show that among three representative networks, namely, regular, random, and scale-free, a regular network favors cooperation the most, whereas a scale-free network favors cooperation the least. In an ideal scale-free network, cooperation is never realized. Whether or not the scale-free network and network heterogeneity favor cooperation depends on the details of the game, although it is occasionally believed that these favor cooperation irrespective of the game structure.     

A general mathematical performance model for wormhole-switched irregular networks

Irregular topologies are desirable network structures for building scalable cluster systems and very recently they have also been employed in SoC (system-on-chip) design. Many analytical models have been proposed in the literature to evaluate the performance of networks with different topologies such as hypercube, torus, mesh, hypermesh, Cartesian product networks, star graph, and k-ary n-cube; however, to the best of our knowledge, no mathematical model has been presented for irregular networks. Therefore, as an effort to fill this gap, this paper presents a comprehensive mathematical model for fully adaptive routing in wormhole-switched irregular networks. Moreover, since our approach holds no assumption for the network topology, the proposed analytical model covers all the aforementioned models (i.e. it covers both regular and irregular topologies). Furthermore, the model makes no preliminary assumption about the deadlock-free routing algorithm applied to the network. Finally, besides the generality of the model regarding the topology and routing algorithm, our analysis shows that the analytical model exhibits high accuracy which enables it to be used for almost all topologies with all traffic loads.     

Comparison of Tree-Child Phylogenetic Networks

Phylogenetic networks are a generalization of phylogenetic trees that allow for the representation of nontreelike evolutionary events, like recombination, hybridization, or lateral gene transfer. While much progress has been made to find practical algorithms for reconstructing a phylogenetic network from a set of sequences, all attempts to endorse a class of phylogenetic networks (strictly extending the class of phylogenetic trees) with a well-founded distance measure have, to the best of our knowledge and with the only exception of the bipartition distance on regular networks, failed so far. In this paper, we present and study a new meaningful class of phylogenetic networks, called tree-child phylogenetic networks, and we provide an injective representation of these networks as multisets of vectors of natural numbers, their path multiplicity vectors. We then use this representation to define a distance on this class that extends the well-known Robinson-Foulds distance for phylogenetic trees and to give an alignment method for pairs of networks in this class. Simple polynomial algorithms for reconstructing a tree-child phylogenetic network from its path multiplicity vectors, for computing the distance between two tree-child phylogenetic networks and for aligning a pair of tree-child phylogenetic networks, are provided. They have been implemented as a Perl package and a Java applet, which can be found at http://bioinfo.uib.es/~recerca/phylonetworks/mudistance/.     

Oscillations and waves in the models of interactive neural populations

The dynamics of activity in interactive neural populations is simulated by the networks of Wilson–Cowan oscillators. Two extreme cases of connection architectures in the networks are considered: (1) 1D and 2D regular and homogeneous grids with local connections and (2) sparse random coupling. Propagating waves in the network have been found under the stationary external input and the regime of partial synchronization has been obtained for the periodic input. It has been shown that in the case of random coupling about 60% of neural populations demonstrate oscillatory activity and some of these oscillations are synchronous. The role of different types of dynamics in information processing is discussed. In particular, we discuss the regime of partial synchronization in the context of cortical microcircuits.     

Oscillations and waves in the models of interactive neural populations

The dynamics of activity in interactive neural populations is simulated by the networks of Wilson-Cowan oscillators. Two extreme cases of connection architectures in the networks are considered: (1) 1D and 2D regular and homogeneous grids with local connections and (2) sparse random coupling. Propagating waves in the network have been found under the stationary external input and the regime of partial synchronization has been obtained for the periodic input. It has been shown that in the case of random coupling about 60% of neural populations demonstrate oscillatory activity and some of these oscillations are synchronous. The role of different types of dynamics in information processing is discussed. In particular, we discuss the regime of partial synchronization in the context of cortical microcircuits.     

A Full Bayesian Approach for Boolean Genetic Network Inference

Boolean networks are a simple but efficient model for describing gene regulatory systems. A number of algorithms have been proposed to infer Boolean networks. However, these methods do not take full consideration of the effects of noise and model uncertainty. In this paper, we propose a full Bayesian approach to infer Boolean genetic networks. Markov chain Monte Carlo algorithms are used to obtain the posterior samples of both the network structure and the related parameters. In addition to regular link addition and removal moves, which can guarantee the irreducibility of the Markov chain for traversing the whole network space, carefully constructed mixture proposals are used to improve the Markov chain Monte Carlo convergence. Both simulations and a real application on cell-cycle data show that our method is more powerful than existing methods for the inference of both the topology and logic relations of the Boolean network from observed data.     

Small-world networks decrease the speed of Muller's ratchet

Muller's ratchet is an evolutionary process that has been implicated in the extinction of asexual species, the evolution of non-recombining genomes, such as the mitochondria, the degeneration of the Y chromosome, and the evolution of sex and recombination. Here we study the speed of Muller's ratchet in a spatially structured population which is subdivided into many small populations (demes) connected by migration, and distributed on a graph. We studied different types of networks: regular networks (similar to the stepping-stone model), small-world networks and completely random graphs. We show that at the onset of the small-world network - which is characterized by high local connectivity among the demes but low average path length - the speed of the ratchet starts to decrease dramatically. This result is independent of the number of demes considered, but is more pronounced the larger the network and the stronger the deleterious effect of mutations. Furthermore, although the ratchet slows down with increasing migration between demes, the observed decrease in speed is smaller in the stepping-stone model than in small-world networks. As migration rate increases, the structured populations approach, but never reach, the result in the corresponding panmictic population with the same number of individuals. Since small-world networks have been shown to describe well the real contact networks among people, we discuss our results in the light of the evolution of microbes and disease epidemics.     

Spiking regularity in a noisy small-world neuronal network

The regularity of spiking oscillations is studied in the networks with different topological structures. The network is composed of coupled Fitz-Hugh-Nagumo neurons driven by colored noise. The investigation illustrates that the spike train in both the regular and the Watts-Strogatz small-world neuronal networks can show the best regularity at a moderate noise intensity, indicating the existence of coherence resonance. Moreover, the temporal coherence of the spike train in the small-world network is superior to that in a regular network due to the increase of the randomness of the network topology. Besides the noise intensity, the spiking regularity can be optimized by tuning the randomness of the network topological structure or by tuning the correlation time of the colored noise. In particular, under the cooperation of the small-world topology and the correlation time, the spike train with good regularity could sustain a large magnitude of the local noise.     

The effect of recombination on the neutral evolution of genetic robustness

Conventional population genetics considers the evolution of a limited number of genotypes corresponding to phenotypes with different fitness. As model phenotypes, in particular RNA secondary structure, have become computationally tractable, however, it has become apparent that the context dependent effect of mutations and the many-to-one nature inherent in these genotype-phenotype maps can have fundamental evolutionary consequences. It has previously been demonstrated that populations of genotypes evolving on the neutral networks corresponding to all genotypes with the same secondary structure only through neutral mutations can evolve mutational robustness [E. van Nimwegen, J.P. Crutchfield, M. Huynen, Neutral evolution of mutational robustness, Proc. Natl. Acad. Sci. USA 96(17), 9716-9720 (1999)], by concentrating the population on regions of high neutrality. Introducing recombination we demonstrate, through numerically calculating the stationary distribution of an infinite population on ensembles of random neutral networks that mutational robustness is significantly enhanced and further that the magnitude of this enhancement is sensitive to details of the neutral network topology. Through the simulation of finite populations of genotypes evolving on random neutral networks and a scaled down microRNA neutral network, we show that even in finite populations recombination will still act to focus the population on regions of locally high neutrality.     

Modeling adaptive biological systems

During the evolution of many systems found in nature, both the system composition and the interactions between components will vary. Equating the dimension with the number of different components, a system which adds or deletes components belongs to a class of dynamical systems with a finite dimensional phase space of variable dimension. We present two models of biochemical systems with a variable phase space, a model of autocatalytic reaction networks in the prebiotic soup and a model of the idiotypic network of the immune system. Each model contains characteristic meta-dynamical rules for constructing equations of motion from component properties. The simulation of each model occurs on two levels. On one level, the equations of motion are integrated to determine the state of each component. On a second level, algorithms which approximate physical processes in the real system are employed to change the equations of motion. Models with meta-dynamical rules possess several advantages for the study of evolving systems. First, there are no explicit fitness functions to determine how the components of the model rank in terms of survivability. The success of any component is a function of its relationship to the rest of the system. A second advantage is that since the phase space representation of the system is always finite but continually changing, we can explore a potentially infinite phase space which would otherwise be inaccessible with finite computer resources. Third, the enlarged capacity of systems with meta-dynamics for variation allows us to conduct true evolution experiments. The modeling methods presented here can be applied to many real biological systems. In the two studies we present, we are investigating two apparent properties of adaptive networks. With the simulation of the prebiotic soup, we are most interested in how a chemical reaction network might emerge from an initial state of relative disorder. With the study of the immune system, we study the self-regulation of the network including its ability to distinguish between species which are part of the network and those which are not.     

Variability v.s. synchronicity of neuronal activity in local cortical network models with different wiring topologies

Dynamical behavior of a biological neuronal network depends significantly on the spatial pattern of synaptic connections among neurons. While neuronal network dynamics has extensively been studied with simple wiring patterns, such as all-to-all or random synaptic connections, not much is known about the activity of networks with more complicated wiring topologies. Here, we examined how different wiring topologies may influence the response properties of neuronal networks, paying attention to irregular spike firing, which is known as a characteristic of in vivo cortical neurons, and spike synchronicity. We constructed a recurrent network model of realistic neurons and systematically rewired the recurrent synapses to change the network topology, from a localized regular and a “small-world” network topology to a distributed random network topology. Regular and small-world wiring patterns greatly increased the irregularity or the coefficient of variation (Cv) of output spike trains, whereas such an increase was small in random connectivity patterns. For given strength of recurrent synapses, the firing irregularity exhibited monotonous decreases from the regular to the random network topology. By contrast, the spike coherence between an arbitrary neuron pair exhibited a non-monotonous dependence on the topological wiring pattern. More precisely, the wiring pattern to maximize the spike coherence varied with the strength of recurrent synapses. In a certain range of the synaptic strength, the spike coherence was maximal in the small-world network topology, and the long-range connections introduced in this wiring changed the dependence of spike synchrony on the synaptic strength moderately. However, the effects of this network topology were not really special in other properties of network activity. Action Editor: Xiao-Jing Wang     

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.     

Dimensionality of Social Networks Using Motifs and Eigenvalues

We consider the dimensionality of social networks, and develop experiments aimed at predicting that dimension. We find that a social network model with nodes and links sampled from an m-dimensional metric space with power-law distributed influence regions best fits samples from real-world networks when m scales logarithmically with the number of nodes of the network. This supports a logarithmic dimension hypothesis, and we provide evidence with two different social networks, Facebook and LinkedIn. Further, we employ two different methods for confirming the hypothesis: the first uses the distribution of motif counts, and the second exploits the eigenvalue distribution.