Search

We develop a matrix-based approach to predict and verify indirect interactions in gene and protein regulatory networks. It is based on the approximate transitivity of indirect regulations (e.g. A regulates B and B regulates C often implies that A regulates C) and optimally takes into account the length of a cascade and signs of intermediate interactions. Our method is at its most powerful when applied to large and densely interconnected networks. It successfully predicts both the yet unknown indirect regulations, as well as the sign (activation or repression) of already known ones. The reliability of sign predictions was calibrated using the gold-standard sets of positive and negative interactions. We fine-tuned the parameters of our algorithm by maximizing the area under the Receiver Operating Characteristic (ROC) curve. We then applied the optimized algorithm to large literature-derived networks of all direct and indirect regulatory interactions in several model organisms (Homo sapiens, Saccharomyces cerevisiae, Arabidopsis thaliana and Drosophila melanogaster)., Comment: revised version, 19 pages, 6 figures, including supplementary materials

We study how the dynamic equilibrium of the reversible protein-protein binding network in yeast Saccharomyces cerevisiae responds to large changes in abundances of individual proteins. The magnitude of shifts between free and bound concentrations of their immediate and more distant neighbors in the network is influenced by such factors as the network topology, the distribution of protein concentrations among its nodes, and the average binding strength. Our primary conclusion is that, on average, the effects of a perturbation are strongly localized and exponentially decay with the network distance away from the perturbed node, which explains why, despite globally connected topology, individual functional modules in such networks are able to operate fairly independently. We also found that under specific favorable conditions, realized in a significant number of paths in the yeast network, concentration perturbations can selectively propagate over considerable network distances (up to four steps). Such "action-at-a-distance" requires high concentrations of heterodimers along the path as well as low free (unbound) concentration of intermediate proteins., Comment: 5 pages, 7 figures

Finding the dominant direction of flow of information in densely interconnected regulatory or signaling networks is required in many applications in computational biology and neuroscience. This is achieved by first identifying and removing links which close up feedback loops in the original network and hierarchically arranging nodes in the remaining network. In mathematical language this corresponds to a problem of making a graph acyclic by removing as few links as possible and thus altering the original graph in the least possible way. Practically in all applications the exact solution of this problem requires an enumeration of all combinations of removed links, which is computationally intractable. We introduce and compare two algorithms: the deterministic, 'greedy' algorithm that preferentially cuts the links that participate in the largest number of feedback cycles, and the probabilistic one based on a simulated annealing of a hierarchical layout of the network which minimizes the number of ``backward'' links going from lower to higher hierarchical levels. We find that the annealing algorithm outperforms the deterministic one in terms of speed, memory requirement, and the actual number of removed links. Implications for system biology and directions for further research are discussed., Comment: 4 pages, 5 figures

Escherichia coli bacteria respond to DNA damage by a highly orchestrated series of events known as the SOS response, regulated by transcription factors, protein-protein binding and active protein degradation. We present a dynamical model of the UV-induced SOS response, incorporating mutagenesis by the error-prone polymerase, Pol V. In our model, mutagenesis depends on a combination of two key processes: damage counting by the replication forks and a long term memory associated with the accumulation of UmuD'. Together, these provide a tight regulation of mutagenesis resulting, we show, in a "digital" turn-on and turn-off of Pol V. Our model provides a compact view of the topology and design of the SOS network, pinpointing the specific functional role of each of the regulatory processes. In particular, we suggest that the recently observed second peak in the activity of promoters in the SOS regulon (Friedman et al., 2005, PLoS Biol. 3, e238) is the result of a positive feedback from Pol V to RecA filaments., Comment: 21 pages, 10 figures

To account for strong aging characteristics of citation networks, we modify Google's PageRank algorithm by initially distributing random surfers exponentially with age, in favor of more recent publications. The output of this algorithm, which we call CiteRank, is interpreted as approximate traffic to individual publications in a simple model of how researchers find new information. We develop an analytical understanding of traffic flow in terms of an RPA-like model and optimize parameters of our algorithm to achieve the best performance. The results are compared for two rather different citation networks: all American Physical Society publications and the set of high-energy physics theory (hep-th) preprints. Despite major differences between these two networks, we find that their optimal parameters for the CiteRank algorithm are remarkably similar., Comment: 4 pages, 3 figures

Using an example of physical interactions between proteins, we study how perturbations propagate in interconnected networks whose equilibrium state is governed by the law of mass action. We introduce a comprehensive matrix formalism which predicts the response of this equilibrium to small changes in total concentrations of individual molecules, and explain it using a heuristic analogy to a current flow in a network of resistors. Our main conclusion is that on average changes in free concentrations exponentially decay with the distance from the source of perturbation. We then study how this decay is influenced by such factors as the topology of a network, binding strength, and correlations between concentrations of neighboring nodes. An exact analytic expression for the decay constant is obtained for the case of uniform interactions on the Bethe lattice. Our general findings are illustrated using a real biological network of protein-protein interactions in baker's yeast with experimentally determined protein concentrations., Comment: 4 pages; 2 figures

We develop a simple statistical method to find affinity relations in a large opinion network which is represented by a very sparse matrix. These relations allow us to predict missing matrix elements. We test our method on the Eachmovie data of thousands of movies and viewers. We found that significant prediction precision can be achieved and it is rather stable. There is an intrinsic limit to further improve the prediction precision by collecting more data, implying perfect prediction can never obtain via statistical means., Comment: 9 pages, 4 figures

The World-Wide Web (WWW) is characterized by a strong community structure in which groups of webpages (e.g. those devoted to a common topic or belonging to the same organization) are densely interconnected by hyperlinks. We study how such network architecture affects the average Google rank of individual communities. Using a mean-field approximation, we quantify how the average Google rank of community webpages depends on the degree to which it is isolated from the rest of the world in both incoming and outgoing directions, and $\alpha$ -- the only intrinsic parameter of Google's PageRank algorithm. Based on this expression we introduce a concept of a web-community being decoupled or conversely coupled to the rest of the network. We proceed with empirical study of several internal web-communities within two US universities. The predictions of our mean-field treatment were qualitatively verified in those real-life networks. Furthermore, the value $\alpha=0.15$ used by Google seems to be optimized for the degree of isolation of communities as they exist in the actual WWW.

The evolution of the full repertoire of proteins encoded in a given genome is mostly driven by gene duplications, deletions, and sequence modifications of existing proteins. Indirect information about relative rates and other intrinsic parameters of these three basic processes is contained in the proteome-wide distribution of sequence identities of pairs of paralogous proteins. We introduce a simple mathematical framework based on a stochastic birth-and-death model that allows one to extract some of this information and apply it to the set of all pairs of paralogous proteins in seven model organisms. It was found that the histogram of sequence identities p generated by an all-to-all alignment of all protein sequences encoded in a genome is well fitted with a power-law form ~p^(-gamma) with the value of the exponent gamma around 4 for the majority of organisms used in this study. This implies that the intra-protein variability of substitution rates is best described by the Gamma-distribution with the exponent alpha ~ 0.33. We separately measure the short-term (``raw'') duplication and deletion rates r*_dup, r*_del which include gene copies that will be removed soon after the duplication event and their dramatically reduced long-term counterparts r_dup, r_del. Systematic trends of each of the four duplication/deletion rates with the total number of genes in the genome were analyzed. All but the deletion rate of recent duplicates r*_del were shown to systematically increase with N_genes. Abnormally flat shapes of sequence identity histograms observed for yeast and human are consistent with lineages leading to these organisms undergoing one or more whole-genome duplications., Comment: 42 pages, 6 figures, 2 supplementary figure

We demonstrate that Protein-Protein Interaction (PPI) networks in several eucaryotic organisms contain significantly more self-interacting proteins than expected if such homodimers randomly appeared in the course of the evolution. We also show that on average homodimers have twice as many interaction partners than non-self-interacting proteins. More specifically the likelihood of a protein to physically interact with itself was found to be proportional to the total number of its binding partners. These properties of dimers are are in agreement with a phenomenological model in which individual proteins differ from each other by the degree of their ``stickiness'' or general propensity towards interaction with other proteins including oneself. A duplication of self-interacting proteins creates a pair of paralogous proteins interacting with each other. We show that such pairs occur more frequently than could be explained by pure chance alone. Similar to homodimers, proteins involved in heterodimers with their paralogs on average have twice as many interacting partners than the rest of the network. The likelihood of a pair of paralogous proteins to interact with each other was also shown to decrease with their sequence similarity. This all points to the conclusion that most of interactions between paralogs are inherited from ancestral homodimeric proteins, rather than established de novo after the duplication. We finally discuss possible implications of our empirical observations from functional and evolutionary standpoints., Comment: 16 pages, 3 figures

The World-Wide Web (WWW) is characterized by a strong community structure in which communities of webpages (e.g. those sharing a common keyword) are densely interconnected by hyperlinks. We study how such network architecture affects the average Google ranking of individual webpages in the comunity. It is shown that the Google rank of community webpages could either increase or decrease with the density of inter-community links depending on the exact balance between average in- and out-degrees in the community. The magnitude of this effect is described by a simple analytical formula and subsequently verified by numerical simulations of random scale-free networks with a desired level of the community structure. A new algorithm allowing for generation of such networks is proposed and studied. The number of inter-community links in such networks is controlled by a temperature-like parameter with the strongest community structure realized in "low-temperature" networks., Comment: 5 pages, 4 figures

A diffusion process on complex networks is introduced in order to uncover their large scale topological structures. This is achieved by focusing on the slowest decaying diffusive modes of the network. The proposed procedure is applied to real-world networks like a friendship network of known modular structure, and an Internet routing network. For the friendship network, its known structure is well reproduced. In case of the Internet, where the structure is far less well-known, one indeed finds a modular structure, and modules can roughly be associated with individual countries. Quantitatively the modular structure of the Internet manifests itself in an approximately 10 times larger participation ratio of its slowest decaying modes as compared to the null model -- a random scale-free network. The extreme edges of the Internet are found to correspond to Russian and US military sites., Comment: Latex, 13 pages, 4 figures (To appear Physica A)

The price multiplier effect provides precious insight into the behavior of investors during episodes of speculative trading. It tells us that the higher the price of an asset is (within a set of similar assets) the more its price is likely to increase during the upgoing phase of a speculative price peak. In short, instead of being risk averse, as is often assumed, investors rather seem to be ``risk prone''. While this effect is known to hold for several sorts of assets, it has not yet been possible to test it for stocks because the price of one share has no intrinsic significance which means that one cannot say that a stock $ A $ is more expensive than a stock $ B $ on the basis of its price. In this paper we show that the price-dividend ratio gives a good basis for assessing the price of stocks in an intrinsic way. When this alternative measure is used instead, it turns out that the price multiplier effect also holds for stocks, at least if one concentrates on samples of companies which are sufficiently homogeneous., Comment: 11 pages, 5 figures, 1 table To appear in the "International Journal of Modern Physics C"

In a general way, stock and bond prices do not display any significant correlation. Yet, if we concentrate our attention on specific episodes marked by a crash followed by a rebound, then we observe that stock prices have a strong connection with interest rates on the one hand, and with bond yield spreads on the other hand. That second relationship is particularly stable in the course of time having been observed for over 140 years. Throughout the paper we use a quasi-experimental approach. By observing how markets respond to well-defined exogenous shocks (such as the shock of September 11, 2001) we are able to determine how investors organize their ``flight to safety'': which safe haven they select, how long their collective panic lasts, and so on. As rebounds come to an end the correlation of stock and bond prices fades away, a clear sign that the collective behavior of investors loses some of its coherence; this observation can be used as an objective criterion for assessing the end of a market rebound. Based on the behavior of investors, we introduce a distinction between ``genuine stock market rallies'', as opposed to spurious rallies such as those brought about by the buyback programs implemented by large companies. The paper ends with a discussion of testable predictions., Comment: 19 pages, 8 figures, 3 tables. To appear in "Physica A"

Evolving biomolecular networks have to combine the stability against perturbations with flexibility allowing their constituents to assume new roles in the cell. Gene duplication followed by functional divergence of associated proteins is a major force shaping molecular networks in living organisms. Recent availability of system-wide data for yeast S. Cerevisiae allow us to access the effects of gene duplication on robustness and plasticity of molecular networks. We demonstrate that the upstream transcriptional regulation of duplicated genes diverges fast, losing on average 4% of their common transcription factors for every 1% divergence of their amino acid sequences. In contrast, the set of physical interaction partners of their protein products changes much slower. The relative stability of downstream functions of duplicated genes, is further corroborated by their ability to substitute for each other in gene knockout experiments. We believe that the combination of the upstream plasticity and the downstream robustness is a general feature determining the evolvability of molecular networks., Comment: 10 pages, 4 figures. Submitted to BMC evolutionary biology

Using each node's degree as a proxy for its importance, the topological hierarchy of a complex network is introduced and quantified. We propose a simple dynamical process used to construct networks which are either maximally or minimally hierarchical. Comparison with these extremal cases as well as with random scale-free networks allows us to better understand hierarchical versus modular features in several real-life complex networks. For random scale-free topologies the extent of topological hierarchy is shown to smoothly decline with $\gamma$ -- the exponent of a degree distribution -- reaching its highest possible value for $\gamma \leq 2$ and quickly approaching zero for $\gamma>3$., Comment: 4 pages, 4 figures

We study the spectral properties of a diffusion process taking place on the Internet network focusing on the slowest decaying modes. These modes allow us to identify an underlying modular structure of the Internet roughly corresponding to individual countries. For instance in the slowest decaying mode the diffusion current flows from Russia towards US military sites. These two regions thus constitute the extreme edges of the Internet. Quantitatively the modular structure of the Internet manifests itself in approximately 10 times larger participation ratio of its slow decaying modes compared to the null model - a random scale-free network. We propose to use the fraction of nodes participating in slow decaying modes as a general measure of the modularity of a network. For the 100 slowest decaying modes of the Internet we measured this fraction to be around 30%. Finally we suggest, that the degree of isolation of an individual module can be assessed by comparing its participation in different diffusion modes. Using the proportionality of response as a criterion we find that the independent module approximation works well for the Internet., Comment: 5 pages, 3 figures

Molecular networks guide the biochemistry of a living cell on multiple levels: its metabolic and signalling pathways are shaped by the network of interacting proteins, whose production, in turn, is controlled by the genetic regulatory network. To address topological properties of these two networks we quantify correlations between connectivities of interacting nodes and compare them to a null model of a network, in which al links were randomly rewired. We find that for both interaction and regulatory networks, links between highly connected proteins are systematically suppressed, while those between a highly-connected and low-connected pairs of proteins are favored. This effect decreases the likelihood of cross talk between different functional modules of the cell, and increases the overall robustness of a network by localizing effects of deleterious perturbations., Comment: 17 pages, 7 figures

A general scheme for detecting and analyzing topological patterns in large complex networks is presented. In this scheme the network in question is compared with its properly randomized version that preserves some of its low-level topological properties. Statistically significant deviation of any measurable property of a network from this null model likely reflect its design principles and/or evolutionary history. We illustrate this basic scheme on the example of the correlation profile of the Internet quantifying correlations between connectivities of its neighboring nodes. This profile distinguishes the Internet from previously studied molecular networks with a similar scale-free connectivity distribution. We finally demonstrate that clustering in a network is very sensitive to both the connectivity distribution and its correlation profile and compare the clustering in the Internet to the appropriate null model., Comment: 6 pages, 7 figures

We develop a method allowing us to reconstruct individual tastes of customers from a sparsely connected network of their opinions on products, services, or each other. Two distinct phase transitions occur as the density of edges in this network is increased: above the first - macroscopic prediction of tastes becomes possible, while above the second - all unknown opinions can be uniquely reconstructed. We illustrate our ideas using a simple Gaussian model, which we study using both field-theoretical methods and numerical simulations. We point out a potential relevance of our approach to the field of bioinformatics., Comment: published version, 5 pages, 1 figure

The cross-correlation matrix of daily returns of stock market indices in a diverse set of 37 countries worldwide was analyzed. Comparison of the spectrum of this matrix with predictions of random matrix theory provides an empirical evidence of strong interactions between individual economies, as manifested by three largest eigenvalues and the corresponding set of stable, non-random eigenvectors. The observed correlation structure is robust with respect to changes in the time horizon of returns ranging from 1 to 10 trading days, and to replacing individual returns with just their signs. This last observation confirms that it is mostly correlations in signs and not absolute values of fluctuations, which are responsible for the observed effect. Correlations between different trading days seem to persist for up to 3 days before decaying to the level of the background noise., Comment: Significantly extended version with 2 new figures. Now: 4 pages, 5 figures, 1 table

Statistical properties of an order book and the effect they have on price dynamics were studied using the high-frequency NASDAQ Level II data. It was observed that the size distribution of marketable orders (transaction sizes) has power law tails with an exponent 1+mu_{market}=2.4 \pm 0.1. The distribution of limit order sizes was found to be consistent with a power law with an exponent close to 2. A somewhat better fit to this distribution was obtained by using a log-normal distribution with an effective power law exponent equal to 2 in the middle of the observed range. The depth of the order book measured as a price impact of a hypothetical large market order was observed to be a non-linear function of its size. A large imbalance in the number of limit orders placed at bid and ask sides of the book was shown to lead to a short term deterministic price change, which is in accord with the law of supply and demand., Comment: To appear in proceedings of the NATO Advanced Research Workshop on Application of Physics in Economic Modelling, Prague 2001. 8 figures

We introduce and analytically solve a directed sandpile model with stochastic toppling rules. The model clearly belongs to a different universality class from its counterpart with deterministic toppling rules, previously solved by Dhar and Ramaswamy. The critical exponents are D_||=7/4, \tau=10/7 in two dimensions and D_||=3/2, \tau=4/3 in one dimension. The upper critical dimension of the model is three, at which the exponents apart from logarithmic corrections reach their mean-field values D_||=2, \tau=3/2., Comment: 4 pages, 2 figures. Added numerical data for 3D case (2nd figure)

We introduce and study a simple model of a limit order-driven market. Traders in this model can either trade at the market price or place a limit order, i.e. an instruction to buy (sell) a certain amount of the stock if its price falls below (raises above) a predefined level. The choice between these two options is purely random (there are no strategies involved), and the execution price of a limit order is determined simply by offsetting the most recent market price by a random amount. Numerical simulations of this model revealed that despite such minimalistic rules the price pattern generated by the model has such realistic features as ``fat'' tails of the price fluctuations distribution, characterized by a crossover between two power law exponents, long range correlations of the volatility, and a non-trivial Hurst exponent of the price signal., Comment: 4 pages, 3 fugures

We report our findings of an 1/f power spectrum for the total amount of sand in directed and undirected Bak-Tang-Wiesenfeld models confined on narrow stripes and driven locally. The underlying mechanism for the 1/f noise in these systems is an exponentially long configuration memory giving rise to a very broad distribution of time scales. Both models are solved analytically with the help of an operator algebra to explicitly show the appearance of the long configuration memory., Comment: 7 pages, 5 figures, Hands-on Java applets of sandpile models at http://cmth.phy.bnl.gov/~maslov/applets.htm

We study the risk criterion for investments based on the drawdown from the maximal value of the capital in the past. Depending on investor's risk attitude, thus his risk exposure, we find that the distribution of these drawdowns follows a general power law. In particular, if the risk exposure is Kelly-optimal, the exponent of this power law has the borderline value of 2, i.e. the average drawdown is just about to diverge, Comment: 5 pages, 4 figures (included)

We study the properties of one-dimensional gapped Heisenberg antiferromagnets in the presence of an arbitrary strong staggered magnetic field. For these systems we predict a universal form for the staggered magnetization curve. This function, as well as the effect the staggered field has on the energy gaps in longitudinal and transversal excitation spectra, are determined from the universal form of the effective potential in O(3)-symmetric 1+1--dimensional field theory. Our theoretical findings are in excellent agreement with recent neutron scattering data on R_2 Ba Ni O_5 (R = magnetic rare earth) linear-chain mixed spin antiferromagnets., Comment: 4 pages, 2 figures

We analyze the behavior of spatially anisotropic Bak-Sneppen model. We demonstrate that a nontrivial relation between critical exponents tau and mu=d/D, recently derived for the isotropic Bak-Sneppen model, holds for its anisotropic version as well. For one-dimensional anisotropic Bak-Sneppen model we derive a novel exact equation for the distribution of avalanche spatial sizes, and extract the value gamma=2 for one of the critical exponents of the model. Other critical exponents are then determined from previously known exponent relations. Our results are in excellent agreement with Monte Carlo simulations of the model as well as with direct numerical integration of the new equation., Comment: 8 pages, three figures included with psfig, some rewriting, + extra figure and table of exponents

Comment to D.H. Zanette and S.C. Manrubia, Phys. Rev. Lett. 79, 523 (1997)., Comment: 1 page no figures

We design an optimal strategy for investment in a portfolio of assets subject to a multiplicative Brownian motion. The strategy provides the maximal typical long-term growth rate of investor's capital. We determine the optimal fraction of capital that an investor should keep in risky assets as well as weights of different assets in an optimal portfolio. In this approach both average return and volatility of an asset are relevant indicators determining its optimal weight. Our results are particularly relevant for very risky assets when traditional continuous-time Gaussian portfolio theories are no longer applicable., Comment: 11 pages, 1 figure, submitted to International Journal of Theoretical and Applied Finance

We propose and study a simple model of dynamical redistribution of capital in a diversified portfolio. We consider a hypothetical situation of a portfolio composed of N uncorrelated stocks. Each stock price follows a multiplicative random walk with identical drift and dispersion. The rules of our model naturally give rise to power law tails in the distribution of capital fractions invested in different stocks. The exponent of this scale free distribution is calculated in both discrete and continuous time formalism. It is demonstrated that the dynamical redistribution strategy results in a larger typical growth rate of the capital than a static ``buy-and-hold'' strategy. In the large N limit the typical growth rate is shown to asymptotically approach that of the expectation value of the stock price. The finite dimensional variant of the model is shown to describe the partition function of directed polymers in random media., Comment: 9 pages, 2 figures, accepted for publication in Physica A; Figure captions and PS-files of two figues are added

We study a recently proposed equation for the avalanche distribution in the Bak-Sneppen model. We demonstrate that this equation indirectly relates $\tau$,the exponent for the power law distribution of avalanche sizes, to $D$, the fractal dimension of an avalanche cluster.We compute this relation numerically and approximate it analytically up to the second order of expansion around the mean field exponents. Our results are consistent with Monte Carlo simulations of Bak-Sneppen model in one and two dimensions., Comment: 5 pages, 2 ps-figures icluded

We introduce and study a dynamic transport model exhibiting Self-Organized Criticality. The novel concepts of our model are the probabilistic propagation of activity and unbiased random repartition of energy among the active site and its nearest neighbors. For space dimensionality $d\geq 2$ we argue that the model is related to $d+1$ dimensional directed percolation, with time interpreted as the preferred direction., Comment: 4 two-column pages (revtex), 3 ps figures included with epsf, g-zipped, uuencoded

We derive an infinite hierarchy of exact equations for the Bak-Sneppen model in arbitrary dimensions. These equations relate different moments of temporal duration and spatial size of avalanches. We prove that the exponents of the BS model are the same above and below the critical point and express the universal amplitude ratio of the avalanche spatial size in terms of the critical exponents. The equations uniquely determine the shape of the scaling function of the avalanche distribution. It is suggested that in the BS model there is only one independent critical exponent., Comment: Submitted to PRL, 4 two-column pages (revtex), 1 ps figure included with epsf, g-zipped, uuencoded