Sampling properties of directed networks.

For many real-world networks only a small "sampled" version of the original network may be investigated; those results are then used to draw conclusions about the actual system. Variants of breadth-first search (BFS) sampling, which are based on epidemic processes, are widely used. Although it is well established that BFS sampling fails, in most cases, to capture the IN component(s) of directed networks, a description of the effects of BFS sampling on other topological properties is all but absent from the literature. To systematically study the effects of sampling biases on directed networks, we compare BFS sampling to random sampling on complete large-scale directed networks. We present new results and a thorough analysis of the topological properties of seven complete directed networks (prior to sampling), including three versions of Wikipedia, three different sources of sampled World Wide Web data, and an Internet-based social network. We detail the differences that sampling method and coverage can make to the structural properties of sampled versions of these seven networks. Most notably, we find that sampling method and coverage affect both the bow-tie structure and the number and structure of strongly connected components in sampled networks. In addition, at a low sampling coverage (i.e., less than 40%), the values of average degree, variance of out-degree, degree autocorrelation, and link reciprocity are overestimated by 30% or more in BFS-sampled networks and only attain values within 10% of the corresponding values in the complete networks when sampling coverage is in excess of 65%. These results may cause us to rethink what we know about the structure, function, and evolution of real-world directed networks.

PageRank and rank-reversal dependence on the damping factor.

PageRank (PR) is an algorithm originally developed by Google to evaluate the importance of web pages. Considering how deeply rooted Google's PR algorithm is to gathering relevant information or to the success of modern businesses, the question of rank stability and choice of the damping factor (a parameter in the algorithm) is clearly important. We investigate PR as a function of the damping factor d on a network obtained from a domain of the World Wide Web, finding that rank reversal happens frequently over a broad range of PR (and of d). We use three different correlation measures, Pearson, Spearman, and Kendall, to study rank reversal as d changes, and we show that the correlation of PR vectors drops rapidly as d changes from its frequently cited value, d_{0}=0.85. Rank reversal is also observed by measuring the Spearman and Kendall rank correlation, which evaluate relative ranks rather than absolute PR. Rank reversal happens not only in directed networks containing rank sinks but also in a single strongly connected component, which by definition does not contain any sinks. We relate rank reversals to rank pockets and bottlenecks in the directed network structure. For the network studied, the relative rank is more stable by our measures around d=0.65 than at d=d_{0}.

Solar flares as cascades of reconnecting magnetic loops.

A model for the solar coronal magnetic field is proposed where multiple directed loops evolve in space and time. Loops injected at small scales are anchored by footpoints of opposite polarity moving randomly on a surface. Nearby footpoints of the same polarity aggregate, and loops can reconnect when they collide. This may trigger a cascade of further reconnection, representing a solar flare. Numerical simulations show that a power law distribution of flare energies emerges, associated with a scale-free network of loops, indicating self-organized criticality.

Scaling in a nonconservative earthquake model of self-organized criticality.

We numerically investigate the Olami-Feder-Christensen model for earthquakes in order to characterize its scaling behavior. We show that ordinary finite size scaling in the model is violated due to global, system wide events. Nevertheless we find that subsystems of linear dimension small compared to the overall system size obey finite (subsystem) size scaling, with universal critical coefficients, for the earthquake events localized within the subsystem. We provide evidence, moreover, that large earthquakes responsible for breaking finite-size scaling are initiated predominantly near the boundary.

Self-organized criticality and universality in a nonconservative earthquake model.

We make an extensive numerical study of a two-dimensional nonconservative model proposed by Olami, Feder, and Christensen to describe earthquake behavior [Phys. Rev. Lett. 68, 1244 (1992)]. By analyzing the distribution of earthquake sizes using a multiscaling method, we find evidence that the model is critical, with no characteristic length scale other than the system size, in agreement with previous results. However, in contrast to previous claims, we find a convergence to universal behavior as the system size increases, over a range of values of the dissipation parameter alpha. We also find that both "free" and "open" boundary conditions tend to the same result. Our analysis indicates that, as L increases, the behavior slowly converges toward a power law distribution of earthquake sizes P(s) approximately equal s(-tau) with an exponent tau approximately equal 1.8. The universal value of tau we find numerically agrees quantitatively with the empirical value (tau=B+1) associated with the Gutenberg-Richter law.

Solitons in the one-dimensional forest fire model.

Fires in the one-dimensional Bak-Chen-Tang forest fire model propagate as solitons, resembling shocks in Burgers turbulence. The branching of solitons, creating new fires, is balanced by the pairwise annihilation of oppositely moving solitons. Two distinct, diverging length scales appear in the limit where the growth rate of trees, p, vanishes. The width of the solitons, w, diverges as a power law, 1/p, while the average distance between solitons diverges much faster as d approximately exp(pi2/12p).

Theoretical results for sandpile models of self-organized criticality with multiple topplings

We study a directed stochastic sandpile model of self-organized criticality, which exhibits multiple topplings, putting it in a separate universality class from the exactly solved model of Dhar and Ramaswamy. We show that in the steady-state all stable states are equally likely. Using this fact, we explicitly derive a discrete dynamical equation for avalanches on the lattice. By coarse graining we arrive at a continuous Langevin equation for the propagation of avalanches and calculate all the critical exponents characterizing avalanches. The avalanche equation is similar to the Edwards-Wilkinson equation, but with a noise amplitude that is a threshold function of the local avalanche activity, or interface height, leading to a stable absorbing state when the avalanche dies.

Self-organized networks of competing boolean agents

A model of Boolean agents competing in a market is presented where each agent bases his action on information obtained from a small group of other agents. The agents play a competitive game that rewards those in the minority. After a long time interval, the poorest player's strategy is changed randomly, and the process is repeated. Eventually the network evolves to a stationary but intermittent state where random mutation of the worst strategy can change the behavior of the entire network, often causing a switch in the dynamics between attractors of vastly different lengths.

dc = 4 is the upper critical dimension for the Bak-Sneppen model.

Numerical results are presented indicating d(c) = 4 as the upper critical dimension for the Bak-Sneppen evolution model. This finding agrees with previous theoretical arguments, but contradicts a recent Letter [Phys. Rev. Lett. 80, 5746 (1998)] that placed d(c) as high as d = 8. In particular, we find that avalanches are compact for all dimensions d< or =4 and are fractal for d>4. Under those conditions, scaling arguments predict a d(c) = 4, where hyperscaling relations hold for d< or =4. Other properties of avalanches, studied for 1< or =d< or =6, corroborate this result. To this end, an improved numerical algorithm is presented that is based on the equivalent branching process.

Complexity, contingency, and criticality.

Complexity originates from the tendency of large dynamical systems to organize themselves into a critical state, with avalanches or "punctuations" of all sizes. In the critical state, events which would otherwise be uncoupled become correlated. The apparent, historical contingency in many sciences, including geology, biology, and economics, finds a natural interpretation as a self-organized critical phenomenon. These ideas are discussed in the context of simple mathematical models of sandpiles and biological evolution. Insights are gained not only from numerical simulations but also from rigorous mathematical analysis.