Search

The complexity of chess matches has attracted broad interest since its invention. This complexity and the availability of large number of recorded matches make chess an ideal model systems for the study of population-level learning of a complex system. We systematically investigate the move-by-move dynamics of the white player's advantage from over seventy thousand high level chess matches spanning over 150 years. We find that the average advantage of the white player is positive and that it has been increasing over time. Currently, the average advantage of the white player is ~0.17 pawns but it is exponentially approaching a value of 0.23 pawns with a characteristic time scale of 67 years. We also study the diffusion of the move dependence of the white player's advantage and find that it is non-Gaussian, has long-ranged anti-correlations and that after an initial period with no diffusion it becomes super-diffusive. We find that the duration of the non-diffusive period, corresponding to the opening stage of a match, is increasing in length and exponentially approaching a value of 15.6 moves with a characteristic time scale of 130 years. We interpret these two trends as a resulting from learning of the features of the game. Additionally, we find that the exponent {\alpha} characterizing the super-diffusive regime is increasing toward a value of 1.9, close to the ballistic regime. We suggest that this trend is due to the increased broadening of the range of abilities of chess players participating in major tournaments., Comment: Accepted for publication in PLoS ONE

We use agent-based modeling to investigate the effect of conservatism and partisanship on the efficiency with which large populations solve the density classification task--a paradigmatic problem for information aggregation and consensus building. We find that conservative agents enhance the populations' ability to efficiently solve the density classification task despite large levels of noise in the system. In contrast, we find that the presence of even a small fraction of partisans holding the minority position will result in deadlock or a consensus on an incorrect answer. Our results provide a possible explanation for the emergence of conservatism and suggest that even low levels of partisanship can lead to significant social costs., Comment: 11 pages, 5 figures

Interactions between units in phyical, biological, technological, and social systems usually give rise to intrincate networks with non-trivial structure, which critically affects the dynamics and properties of the system. The focus of most current research on complex networks is on global network properties. A caveat of this approach is that the relevance of global properties hinges on the premise that networks are homogeneous, whereas most real-world networks have a markedly modular structure. Here, we report that networks with different functions, including the Internet, metabolic, air transportation, and protein interaction networks, have distinct patterns of connections among nodes with different roles, and that, as a consequence, complex networks can be classified into two distinct functional classes based on their link type frequency. Importantly, we demonstrate that the above structural features cannot be captured by means of often studied global properties.

Modularity is one of the most prominent properties of real-world complex networks. Here, we address the issue of module identification in two important classes of networks: bipartite networks and directed unipartite networks. Nodes in bipartite networks are divided into two non-overlapping sets, and the links must have one end node from each set. Directed unipartite networks only have one type of nodes, but links have an origin and an end. We show that directed unipartite networks can be conviniently represented as bipartite networks for module identification purposes. We report a novel approach especially suited for module detection in bipartite networks, and define a set of random networks that enable us to validate the new approach.

To gain a deeper insight into cellular processes such as transcription and translation, one needs to uncover the mechanisms controlling the configurational changes of nucleic acids. As a step toward this aim, we present here a novel mesoscopic-level computational model that provides a new window into nucleic acid dynamics. We model a single-stranded nucleic as a polymer chain whose monomers are the nucleosides. Each monomer comprises a bead representing the sugar molecule and a pin representing the base. The bead-pin complex can rotate about the backbone of the chain. We consider pairwise stacking and hydrogen-bonding interactions. We use a modified Monte Carlo dynamics that splits the dynamics into translational bead motion and rotational pin motion. By performing a number of tests we first show that our model is physically sound. We then focus on the study of a the kinetics of a DNA hairpin--a single-stranded molecule comprising two complementary segments joined by a non-complementary loop--studied experimentally. We find that results from our simulations agree with experimental observations, demonstrating that our model is a suitable tool for the investigation of the hybridization of single strands., Comment: 27 pages, 13 figures

We analyze the properties of model food webs and of fifteen community food webs from a variety of environments. We first perform a theoretical analysis of the niche model of Williams and Martinez. We derive analytical expressions for the distributions of species' number of prey, number of predators, and total number of trophic links and find that they follow universal functional forms. We also derive expressions for a number of other biologically relevant parameters, including the fraction of top, intermediate, basal, and cannibal species, the standard deviations of generality and vulnerability, the correlation coefficient between species' number of prey and number of predators, and assortativity. We show that our findings are robust under rather general conditions. We then use our analytical predictions as a guide to the analysis of fifteen of the most complete empirical food webs available. We uncover quantitative unifying patterns that describe the properties of the model food webs and most of the trophic webs considered. Our results support a strong new hypothesis that the empirical distributions of number of prey and number of predators follow universal functional forms that, without free parameters, match our analytical predictions. Further, we find that the empirically observed correlation coefficient, assortativity, and fraction of cannibal species are consistent with our analytical expressions and simulations of the niche model. Finally, we show that the average distance between nodes and the average clustering coefficient show a high degree of regularity for both the empirical data and simulations of the niche model. Our findings suggest that statistical physics concepts such as scaling and universality may be useful in the description of natural ecosystems., Comment: 39 pages, 20 figures

We analyze the global structure of the world-wide air transportation network, a critical infrastructure with an enormous impact on local, national, and international economies. We find that the world-wide air transportation network is a scale-free small-world network. In contrast to the prediction of scale-free network models, however, we find that the most connected cities are not necessarily the most central, resulting in anomalous values of the centrality. We demonstrate that these anomalies arise because of the multi-community structure of the network. We identify the communities in the air transportation network and show that the community structure cannot be explained solely based on geographical constraints, and that geo-political considerations have to be taken into account. We identify each city's global role based on its pattern of inter- and intra-community connections, which enables us to obtain scale-specific representations of the network., Comment: Revised version

A challenging problem in the social sciences is the characterization of the formation of ``social capital''. It is believed that societies with more social capital are more democratic and economically developed than societies with little social capital. However, social capital is a concept hard to quantify and measure in a ``real-word'' context. Here, we take advantage of an existing "web of trust'' between users of the "Pretty-Good-Privacy" (PGP) encryption algorithm, which is used in digital communication to ``sign'' documents so that the recipient knows for sure who the author is. Our analysis reveals the coexistence in the web of trust of a macro scale-free structure with micro strongly-connected cells in a complex network. We also show that when this network is intentionally attacked the scale-free structure rapidly disintegrates and that the resulting network is partitioned into a large number of small strongly-connected cells that are resilient to the intentional attack.

We analyze cross-correlations between price fluctuations of different stocks using methods of random matrix theory (RMT). Using two large databases, we calculate cross-correlation matrices C of returns constructed from (i) 30-min returns of 1000 US stocks for the 2-yr period 1994--95 (ii) 30-min returns of 881 US stocks for the 2-yr period 1996--97, and (iii) 1-day returns of 422 US stocks for the 35-yr period 1962--96. We test the statistics of the eigenvalues $\lambda_i$ of C against a ``null hypothesis'' --- a random correlation matrix constructed from mutually uncorrelated time series. We find that a majority of the eigenvalues of C fall within the RMT bounds $[\lambda_-, \lambda_+]$ for the eigenvalues of random correlation matrices. We test the eigenvalues of C within the RMT bound for universal properties of random matrices and find good agreement with the results for the Gaussian orthogonal ensemble of random matrices --- implying a large degree of randomness in the measured cross-correlation coefficients. Further, we find that the distribution of eigenvector components for the eigenvectors corresponding to the eigenvalues outside the RMT bound display systematic deviations from the RMT prediction. In addition, we find that these ``deviating eigenvectors'' are stable in time. We analyze the components of the deviating eigenvectors and find that the largest eigenvalue corresponds to an influence common to all stocks. Our analysis of the remaining deviating eigenvectors shows distinct groups, whose identities correspond to conventionally-identified business sectors. Finally, we discuss applications to the construction of portfolios of stocks that have a stable ratio of risk to return., Comment: 20 pages (2 column format, revtex)

We analyze the properties of seven community food webs from a variety of environments--including freshwater, marine-freshwater interfaces and terrestrial environments. We uncover quantitative unifying patterns that describe the properties of the diverse trophic webs considered and suggest that statistical physics concepts such as scaling and universality may be useful in the description of ecosystems. Specifically, we find that several quantities characterizing these diverse food webs obey functional forms that are universal across the different environments considered. The empirical results are in remarkable agreement with the analytical solution of a recently proposed model for food webs., Comment: 4 pages. Final version to appear in PRL

We map the conformation space of a simple lattice polymer chain to a network, where (i) the vertices of the network have a one-to-one correspondence to the conformations of the chain, and (ii) a link between two vertices indicates the possibility of switching from one conformation to the other by a single Monte Carlo move of the chain. We find that the geometric properties of this network are similar to those of small-world networks, namely, the diameter of conformation space increases, for large networks, as the logarithm of the number of conformations, while locally the network appears to have low dimensionality., Comment: 5 pages and 7 eps figures using Latex (and revtex)

We present a phenomenological study of stock price fluctuations of individual companies. We systematically analyze two different databases covering securities from the three major US stock markets: (a) the New York Stock Exchange, (b) the American Stock Exchange, and (c) the National Association of Securities Dealers Automated Quotation stock market. Specifically, we consider (i) the trades and quotes database, for which we analyze 40 million records for 1000 US companies for the 2-year period 1994--95, and (ii) the Center for Research and Security Prices database, for which we analyze 35 million daily records for approximately 16,000 companies in the 35-year period 1962--96. We study the probability distribution of returns over varying time scales $\Delta t$, where $\Delta t$ varies by a factor of $\approx 10^5$---from 5 min up to $\approx$ 4 years. For time scales from 5~min up to approximately 16~days, we find that the tails of the distributions can be well described by a power-law decay, characterized by an exponent $\alpha \approx 3$ ---well outside the stable L\'evy regime $0 < \alpha < 2$. For time scales $\Delta t \gg (\Delta t)_{\times} \approx 16 $days, we observe results consistent with a slow convergence to Gaussian behavior. We also analyze the role of cross correlations between the returns of different companies and relate these correlations to the distribution of returns for market indices., Comment: 10pages 2 column format with 11 eps figures. LaTeX file requiring epsf, multicol,revtex. Submitted to PRE

We study the dynamics of a system composed of interacting units each with a complex internal structure comprising many subunits. We consider the case in which each subunit grows in a multiplicative manner. We propose a model for such systems in which the interaction among the units is treated in a mean field approximation and the interaction among subunits is nonlinear. To test the model, we identify a large data base spanning 20 years, and find that the model correctly predicts a variety of empirical results., Comment: 4 pages with 4 postscript figures (uses Revtex 3.1, Latex2e, multicol.sty, epsf.sty and rotate.sty). Submitted to PRL

We investigate sandpile models where the updating of unstable columns is done according to a stochastic rule. We examine the effect of introducing nonlocal relaxation mechanisms. We find that the models self-organize into critical states that belong to three different universality classes. The models with local relaxation rules belong to a known universality class that is characterized by an avalanche exponent $\tau \approx 1.55$, whereas the models with nonlocal relaxation rules belong to new universality classes characterized by exponents $\tau \approx 1.35$ and $\tau \approx 1.63$. We discuss the values of the exponents in terms of scaling relations and a mapping of the sandpile models to interface models., Comment: 4 pages, including 3 figures

In the preceding paper we presented empirical results describing the growth of publicly-traded United States manufacturing firms within the years 1974--1993. Our results suggest that the data can be described by a scaling approach. Here, we propose models that may lead to some insight into these phenomena. First, we study a model in which the growth rate of a company is affected by a tendency to retain an ``optimal'' size. That model leads to an exponential distribution of the logarithm of the growth rate in agreement with the empirical results. Then, we study a hierarchical tree-like model of a company that enables us to relate the two parameters of the model to the exponent $\beta$, which describes the dependence of the standard deviation of the distribution of growth rates on size. We find that $\beta = -\ln \Pi / \ln z$, where $z$ defines the mean branching ratio of the hierarchical tree and $\Pi$ is the probability that the lower levels follow the policy of higher levels in the hierarchy. We also study the distribution of growth rates of this hierarchical model. We find that the distribution is consistent with the exponential form found empirically., Comment: 19 pages LateX, RevTeX 3, 6 figures, to appear J. Phys. I France (April 1997)

We address the question of the growth of firm size. To this end, we analyze the Compustat data base comprising all publicly-traded United States manufacturing firms within the years 1974-1993. We find that the distribution of firm sizes remains stable for the 20 years we study, i.e., the mean value and standard deviation remain approximately constant. We study the distribution of sizes of the ``new'' companies in each year and find it to be well approximated by a log-normal. We find (i) the distribution of the logarithm of the growth rates, for a fixed growth period of one year, and for companies with approximately the same size $S$ displays an exponential form, and (ii) the fluctuations in the growth rates -- measured by the width of this distribution $\sigma_1$ -- scale as a power law with $S$, $\sigma_1\sim S^{-\beta}$. We find that the exponent $\beta$ takes the same value, within the error bars, for several measures of the size of a company. In particular, we obtain: $\beta=0.20\pm0.03$ for sales, $\beta=0.18\pm0.03$ for number of employees, $\beta=0.18\pm0.03$ for assets, $\beta=0.18\pm0.03$ for cost of goods sold, and $\beta=0.20\pm0.03$ for property, plant, & equipment., Comment: 16 pages LateX, RevTeX 3, 10 figures, to appear J. Phys. I France (April 1997)

We perform a systematic study of several models that have been proposed for the purpose of understanding the motion of driven interfaces in disordered media. We identify two distinct universality classes: (i) One of these, referred to as directed percolation depinning (DPD), can be described by a Langevin equation similar to the Kardar-Parisi-Zhang equation, but with quenched disorder. (ii) The other, referred to as quenched Edwards-Wilkinson (QEW), can be described by a Langevin equation similar to the Edwards-Wilkinson equation but with quenched disorder. We find that for the DPD universality class the coefficient $\lambda$ of the nonlinear term diverges at the depinning transition, while for the QEW universality class either $\lambda = 0$ or $\lambda \to 0$ as the depinning transition is approached. The identification of the two universality classes allows us to better understand many of the results previously obtained experimentally and numerically. However, we find that some results cannot be understood in terms of the exponents obtained for the two universality classes {\it at\/} the depinning transition. In order to understand these remaining disagreements, we investigate the scaling properties of models in each of the two universality classes {\it above\/} the depinning transition. For the DPD universality class, we find for the roughness exponent $\alpha_P = 0.63 \pm 0.03$ for the pinned phase, and $\alpha_M = 0.75 \pm 0.05$ for the moving phase. For the growth exponent, we find $\beta_P = 0.67 \pm 0.05$ for the pinned phase, and $\beta_M = 0.74 \pm 0.06$ for the moving phase. Furthermore, we find an anomalous scaling of the prefactor of the width on the driving force. A new exponent $\varphi_M = -0.12 \pm 0.06$, characterizing the scaling of this prefactor, is shown to relate the values of the roughness, Comment: Latex manuscript, Revtex 3.0, 15 pages, and 15 figures also available via anonymous ftp from ftp://jhilad.bu.edu/pub/abms/ (128.197.42.52)

We study the recently-introduced directed percolation depinning (DPD) model for interface roughening with quenched disorder for which the interface becomes pinned by a directed percolation (DP) cluster for $d = 1$, or a directed surface (DS) for $d > 1$. The mapping to DP enables us to predict some of the critical exponents of the growth process. For the case of $(1+1)$ dimensions, the theory predicts that the roughness exponent $\alpha$ is given by $\alpha = \nu_{\perp} / \nu_{\parallel}$, where $\nu_{\perp}$ and $\nu_{\parallel}$ are the exponents governing the divergence of perpendicular and parallel correlation lengths of the DP incipient infinite cluster. The theory also predicts that the dynamical exponent $z$ equals the exponent $d_{\rm min}$ characterizing the scaling of the shortest path on a isotropic percolation cluster. The exponent $\alpha$ decreases monotonically with $d$ but does not seem to approach zero for any dimension calculated ($d \le 6$), suggesting that the DPD model has no upper critical dimension for the static exponents. On the other hand, $z$ appears to approach $2$ as $d \rightarrow 6$, as expected by the result $z = d_{\rm min}$, suggesting that $d_c = 6$ for the dynamics. We also perform a set of imbibition experiments, in both $(1+1)$ and $(2+1)$ dimensions, that can be used to test the DPD model. We find good agreement between experimental, theoretical and numerical approaches. Further, we study the properties of avalanches in the context of the DPD model. We relate the scaling properties of the avalanches in the DPD model to the scaling properties for the self-organized depinning (SOD) model, a variant of the DPD model. We calculate the exponent characterizing the avalanches distribution $\tau_{\rm aval}$ for $d = 1$ to $d = 6$, and compare our results with recent theoretical, Comment: RevTex manuscript 17 pages, 69 references and 19 figures (obtained upon request via email sth@iris.bu.edu)

We study the dynamical exponent $z$ for the directed percolation depinning (DPD) class of models for surface roughening in the presence of quenched disorder. We argue that $z$ for $(d+1)$ dimensions is equal to the exponent $d_{\rm min}$ characterizing the shortest path between two sites in an isotropic percolation cluster in $d$ dimensions. To test the argument, we perform simulations and calculate $z$ for DPD, and $d_{\rm min}$ for percolation, from $d = 1$ to $d = 6$., Comment: RevTex manuscript 3 pages + 6 figures (obtained upon request via email sth@iris.bu.edu)