Coarse-grain reconstruction of genetic networks from expression levels

In the postgenome era many efforts have been dedicated to systematically elucidate the complex web of interacting genes and proteins. These efforts include experimental and computational methods. Microarray technology offers an opportunity for monitoring gene expression level at the genome scale. By recourse to information theory, this study proposes a mathematical approach to reconstruct gene regulatory networks at a coarse-grain level from high throughput gene expression data. The method provides the a posteriori probability that a given gene regulates positively, negatively or does not regulate each one of the network genes. This approach also allows the introduction of prior knowledge and the quantification of the information gain from experimental data used in the inference procedure. This information gain can be used to choose those genes that will be perturbed in subsequent experiments in order to refine our knowledge about the architecture of an underlying gene regulatory network. The performance of the proposed approach has been studied by in numero experiments. Our results suggest that the approach is suitable for focusing on size-limited problems, such as recovering a small subnetwork of interest by performing perturbation over selected genes.     

Influence of a network structure on the network effect in the communication service market

In this study, we analyze the network effect in a model of a personal communication market, by using a multi-agent based simulation approach. We introduce into the simulation model complex network structures as the interaction patterns of agents. With complex network models, we investigate the dynamics of a market in which two providers are competing. We also examine the structure of networks that affect the complex behavior of the market. By a series of simulations, we show that the structural properties of complex networks, such as the clustering coefficient and degree correlation, have a major influence on the dynamics of the market. We find that the network effect is increased if the interaction pattern of agents is characterized by a high clustering coefficient, or a positive degree correlation. We also discuss a suitable model of the interaction pattern for reproducing market dynamics in the real world, by performing simulations using real data of a social network.     

A validity index approach for network partitions

The validity index has been used to evaluate the fitness of partitions produced by clustering algorithms for points in Euclidean space. In this paper, we propose a new validity index for network partitions, which can provide a measure of goodness for the community structure of networks. It is defined as a product of two factors, and involves the compactness and separation for each partition. The simulated annealing strategy is used to minimize such a validity index function in coordination with our previous k-means algorithm based on the optimal reduction of a random walker Markovian dynamics on the network. It is demonstrated that the algorithm can efficiently find the community structure during the cooling process. The number of communities can be automatically determined without any prior knowledge of the community structure. Moreover, the algorithm is successfully applied to three real-world networks.     

Impact of initial lattice structures on networks generated by traces of random walks

We show that the platform stage of network evolution plays a principal role in the topology of resulting networks generated by short-cuts stimulated by the movements of a random walker, the mechanism of which tends to produce power-law degree distributions. To examine the numerical results, we have developed a statistical method which relates the power-law exponent γ to random properties of the subgraph developed in the platform stage. As a result, we find that an important exponent in the network evolution is α, which characterizes the size of the subgraph in the form V∼t^α, where V and t denote the number of vertices in the subgraph and the time variable, respectively. 2D lattices can impose specific limitations on the walker’s diffusion, which keeps the value of α within a moderate range and provides typical properties of complex networks. 1D and 3D cases correspond to different ends of the spectrum for α, with 2D cases in between. Especially for 2D square lattices, a discontinuous change of the network structure is observed, which varies according to whether γ is greater or less than 2. For 1D cases, we show that emergence of nearly complete subgraphs is guaranteed by α<1/2, although the transient power-law is permitted at low increase rates of edges. Additionally, the model exhibits a spontaneous emergence of highly clustered structures regardless of its initial structure.     

Navigation in large subway networks: An informational approach

The structural properties of the subway network are crucial in effective transportation in cities. This paper presents an information perspective of navigation in four different subway networks: New York City, Paris, Barcelona and Moscow. We addressed our study to investigate what is that makes it complicated to navigate in these kinds of networks and we carried out a comparison between them and their intrinsic constraints. Our methodological approach is based on a set of cost/efficiency indicators which are defined in the complex networks literature. We find that the overall complexity in finding stations measured by the average search information S linearly increases as a function of the network size N. The direct implication of this finding is that from these basic levels of required information, the average value H(k) can be represented as a function of the node degree k. Finally, through analyzing subway networks in space P, we reveal the existing service modularity among subway routes using a rescaled expression of S.     

Information theoretical methods to deconvolute genetic regulatory networks applied to thyroid neoplasms

Most common pathologies in humans are not caused by the mutation of a single gene, rather they are complex diseases that arise due to the dynamic interaction of many genes and environmental factors. This plethora of interacting genes generates a complexity landscape that masks the real effects associated with the disease. To construct dynamic maps of gene interactions (also called genetic regulatory networks) we need to understand the interplay between thousands of genes. Several issues arise in the analysis of experimental data related to gene function: on the one hand, the nature of measurement processes generates highly noisy signals; on the other hand, there are far more variables involved (number of genes and interactions among them) than experimental samples. Another source of complexity is the highly nonlinear character of the underlying biochemical dynamics. To overcome some of these limitations, we generated an optimized method based on the implementation of a Maximum Entropy Formalism (MaxEnt) to deconvolute a genetic regulatory network based on the most probable meta-distribution of gene-gene interactions. We tested the methodology using experimental data for Papillary Thyroid Cancer (PTC) and Thyroid Goiter tissue samples. The optimal MaxEnt regulatory network was obtained from a pool of 25,593,993 different probability distributions. The group of observed interactions was validated by several (mostly in silico) means and sources. For the associated Papillary Thyroid Cancer Gene Regulatory Network (PTC-GRN) the majority of the nodes (genes) have very few links (interactions) whereas a small number of nodes are highly connected. PTC-GRN is also characterized by high clustering coefficients and network heterogeneity. These properties have been recognized as characteristic of topological robustness, and they have been largely described in relation to biological networks. A number of biological validity outcomes are discussed with regard to both the inferred model and the PTC.     

Enhancing robustness and synchronizability of networks homogenizing their degree distribution

A new family of networks, called entangled, has recently been proposed in the literature. These networks have optimal properties in terms of synchronization, robustness against errors and attacks, and efficient communication. They are built with an algorithm which uses modified simulated annealing to enhance a well-known measure of networks’ ability to reach synchronization among nodes. In this work, we suggest that a class of networks similar to entangled networks can be produced by changing some of the connections in a given network, or by just adding a few connections. We call this class of networks weak-entangled. Although entangled networks can be considered as a subset of weak-entangled networks, we show that both classes share similar properties, especially with respect to synchronization and robustness, and that they have similar structural properties.     

Regulatory networks and connected components of the neutral space

The functioning of a living cell is largely determined by the structure of its regulatory network, comprising non-linear interactions between regulatory genes. An important factor for the stability and evolvability of such regulatory systems is neutrality – typically a large number of alternative network structures give rise to the necessary dynamics. Here we study the discretized regulatory dynamics of the yeast cell cycle [Li et al., PNAS, 2004] and the set of networks capable of reproducing it, which we call functional. Among these, the empirical yeast wildtype network is close to optimal with respect to sparse wiring. Under point mutations, which establish or delete single interactions, the neutral space of functional networks is fragmented into ≈ 4.7 × 10⁸ components. One of the smaller ones contains the wildtype network. On average, functional networks reachable from the wildtype by mutations are sparser, have higher noise resilience and fewer fixed point attractors as compared with networks outside of this wildtype component.     

A survey on 5G: The next generation of mobile communication

The rapidly increasing number of mobile devices, voluminous data, and higher data rate are pushing to rethink the current generation of the cellular mobile communication. The next or fifth generation (5G) cellular networks are expected to meet high-end requirements. The 5G networks are broadly characterized by three unique features: ubiquitous connectivity, extremely low latency, and very high-speed data transfer. The 5G networks would provide novel architectures and technologies beyond state-of-the-art architectures and technologies. In this paper, our intent is to find an answer to the question: “what will be done by 5G and how?” We investigate and discuss serious limitations of the fourth generation (4G) cellular networks and corresponding new features of 5G networks. We identify challenges in 5G networks, new technologies for 5G networks, and present a comparative study of the proposed architectures that can be categorized on the basis of energy-efficiency, network hierarchy, and network types. Interestingly, the implementation issues, e.g., interference, QoS, handoff, security–privacy, channel access, and load balancing, hugely effect the realization of 5G networks. Furthermore, our illustrations highlight the feasibility of these models through an evaluation of existing real-experiments and testbeds.     

Pruned optical banyan networks on vertical stacking scheme for faster connection establishment

In this paper, we address the issue of faster connection establishment in a large vertically stacked optical Banyan (VSOB) network. The best known global routing algorithm, which turns an N × N crosstalk-free VSOB network into a rearrangeably non-blocking one, has time complexity O (NlogN). This is quite large compared to O (NlogN) time complexity of a single plane banyan network, which is a self-routing network with very high blocking probability. For a large size of switching network this O (NlogN) time complexity may result unacceptably long delay. Therefore, an optical network with very low blocking probability and O (NlogN) time complexity will be useful. Previously proposed Plane Fixed Routing (PFR) algorithm has O (logN) time complexity but results in higher than 2% blocking probability with zero-crosstalk constraint for a network as large as 4096 × 4096 at full load. In this paper, first we propose the pruning of VSOB networks that reduces the hardware cost by almost 30%. The networks can still use the PFR algorithm and results in the same blocking probability. However, we show that the blocking probability can be reduced dramatically while keeping the optimum time complexity O (logN) by allowing only a small amount of crosstalk. Then, we propose a new kind of switching networks in which extra regular banyan planes have been added with the pruned VBOS (P-VSOB) networks. Necessary routing algorithms, namely, PFR_RS and PFR_LS show that this new switching network can reduce the blocking probability to very low value even with zero-crosstalk constraint while keeping the hardware cost 3almost the same as for P-VSOB networks. Both these algorithms also have time complexity O (NlogN).     

An evolving model of online bipartite networks

Understanding the structure and evolution of online bipartite networks is a significant task since they play a crucial role in various e-commerce services nowadays. Recently, various attempts have been tried to propose different models, resulting in either power-law or exponential degree distributions. However, many empirical results show that the user degree distribution actually follows a shifted power-law distribution, the so-called Mandelbrot’s law, which cannot be fully described by previous models. In this paper, we propose an evolving model, considering two different user behaviors: random and preferential attachment. Extensive empirical results on two real bipartite networks, Delicious and CiteULike  , show that the theoretical model can well characterize the structure of real networks for both user and object degree distributions. In addition, we introduce a structural parameter p$p$, to demonstrate that the hybrid user behavior leads to the shifted power-law degree distribution, and the region of power-law tail will increase with the increment of p$p$. The proposed model might shed some lights in understanding the underlying laws governing the structure of real online bipartite networks.     

Exploring the random genesis of co-occurrence networks

Using the network random generation models from Gustedt (2009) [23], we simulate and analyze several characteristics (such as the number of components, the degree distribution and the clustering coefficient) of the generated networks. This is done for a variety of distributions (fixed value, Bernoulli, Poisson, binomial) that are used to control the parameters of the generation process. These parameters are in particular the size of newly appearing sets of objects, the number of contexts in which new elements appear initially, the number of objects that are shared with ‘parent’ contexts, and, the time period inside which a context may serve as a parent context (aging). The results show that these models allow to fine-tune the generation process such that the graphs adopt properties as can be found in real world graphs.     

Duplication： a Mechanism Producing Disassortative Mixing Networks in Biology

Assortative/disassortative mixing is an important topological property of a network. A network is called assortative mixing if the nodes in the network tend to connect to their connectivity peers, or disassortative mixing if nodes with low degrees are more likely to connect with high-degree nodes. We have known that biological networks such as protein-protein interaction networks （PPI）, gene regulatory networks, and metabolic networks tend to be disassortative. On the other hand, in biological evolution, duplication and divergence are two fundamental processes. In order to make the relationship between the property of disassortative mixing and the two basic biological principles clear and to study the cause of the disassortative mixing property in biological networks, we present a random duplication model and an anti-preference duplication model. Our results show that disassortative mixing networks can be obtained by both kinds of models from uncorrelated initial networks. Moreover, with the growth of the network size, the disassortative mixing property becomes more obvious.     

Preferential survival in models of complex ad hoc networks

There has been a rich interplay in recent years between (i) empirical investigations of real-world dynamic networks, (ii) analytical modeling of the microscopic mechanisms that drive the emergence of such networks, and (iii) harnessing of these mechanisms to either manipulate existing networks, or engineer new networks for specific tasks. We continue in this vein, and study the deletion phenomenon in the web by the following two different sets of websites (each comprising more than 150,000 pages) over a one-year period. Empirical data show that there is a significant deletion component in the underlying web networks, but the deletion process is not uniform. This motivates us to introduce a new mechanism of preferential survival (PS), where nodes are removed according to the degree-dependent deletion kernel, D(k)∝k^−α, with α≥0. We use the mean-field rate equation approach to study a general dynamic model driven by Preferential Attachment (PA), Double PA (DPA), and a tunable PS (i.e., with any α>0), where c nodes (c<1) are deleted per node added to the network, and verify our predictions via large-scale simulations. One of our results shows that, unlike in the case of uniform deletion (i.e., where α=0), the PS kernel when coupled with the standard PA mechanism, can lead to heavy-tailed power-law networks even in the presence of extreme turnover in the network. Moreover, a weak DPA mechanism, coupled with PS, can help to make the network even more heavy-tailed, especially in the limit when deletion and insertion rates are almost equal, and the overall network growth is minimal. The dynamics reported in this work can be used to design and engineer stable ad hoc networks and explain the stability of the power-law exponents observed in real-world networks.     

A new measure of network efficiency

We address the issue of the dynamical origin of scale-free link distributions. We study a two-dimensional lattice of cooperatively interacting units. Although the units interact only with the four nearest neighbors, a sufficiently large cooperation strength generates dynamically a scale-free network with the power law index ν approaching 1. We explain this result by using a new definition of network efficiency determined by the Euclidean distance between correlated units. According to this definition the link distribution favoring long-range connections makes efficiency increase. We embed an ad hoc scale-free network with power index ν≥1 into a Euclidean two-dimensional space and show that the network efficiency becomes maximal as ν approaches 1. We therefore conclude that ν=1 emerging from the cooperative interaction of units may be a consequence of the principle of network maximal efficiency.     

Detecting community structure in complex networks based on a measure of information discrepancy

Properties of complex networks, such as small-world property, power-law degree distribution, network transitivity, and network- community structure which seem to be common to many real-world networks have attracted great interest among researchers. In this study, global information of the networks is considered by defining the profile of any node based on the shortest paths between it and all the other nodes in the network; then a useful iterative procedure for community detection based on a measure of information discrepancy and the popular modular function Q is presented. The new iterative method does not need any prior knowledge about the community structure and can detect an appropriate number of communities, which can be hub communities or non-hub communities. The computational results of the method on real networks confirm its capability.     

Motif structure and cooperation in real-world complex networks

Networks of dynamical nodes serve as generic models for real-world systems in many branches of science ranging from mathematics to physics, technology, sociology and biology. Collective behavior of agents interacting over complex networks is important in many applications. The cooperation between selfish individuals is one of the most interesting collective phenomena. In this paper we address the interplay between the motifs’ cooperation properties and their abundance in a number of real-world networks including yeast protein-protein interaction, human brain, protein structure, email communication, dolphins’ social interaction, Zachary karate club and Net-science coauthorship networks. First, the amount of cooperativity for all possible undirected subgraphs with three to six nodes is calculated. To this end, the evolutionary dynamics of the Prisoner’s Dilemma game is considered and the cooperativity of each subgraph is calculated as the percentage of cooperating agents at the end of the simulation time. Then, the three- to six-node motifs are extracted for each network. The significance of the abundance of a motif, represented by a Z-value, is obtained by comparing them with some properly randomized versions of the original network. We found that there is always a group of motifs showing a significant inverse correlation between their cooperativity amount and Z-value, i.e. the more the Z-value the less the amount of cooperativity. This suggests that networks composed of well-structured units do not have good cooperativity properties.     

Network evolution by nonlinear preferential rewiring of edges

The mathematical framework for small-world networks proposed in a seminal paper by Watts and Strogatz sparked a widespread interest in modeling complex networks in the past decade. However, most of research contributing to static models is in contrast to real-world dynamic networks, such as social and biological networks, which are characterized by rearrangements of connections among agents. In this paper, we study dynamic networks evolved by nonlinear preferential rewiring of edges. The total numbers of vertices and edges of the network are conserved, but edges are continuously rewired according to the nonlinear preference. Assuming power-law kernels with exponents α and β, the network structures in stationary states display a distinct behavior, depending only on β. For β>1, the network is highly heterogeneous with the emergence of starlike structures. For β<1, the network is widely homogeneous with a typical connectivity. At β=1, the network is scale free with an exponential cutoff.