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.

Corrections to scaling for watersheds, optimal path cracks, and bridge lines.

We study the corrections to scaling for the mass of the watershed, the bridge line, and the optimal path crack in two and three dimensions (2D and 3D). We disclose that these models have numerically equivalent fractal dimensions and leading correction-to-scaling exponents. We conjecture all three models to possess the same fractal dimension, namely, d(f) =1.2168 ± 0.0005 in 2D and d(f) = 2.487 ± 0.003 in 3D, and the same exponent of the leading correction, Ω = 0.9 ± 0.1 and Ω=1.0 ± 0.1, respectively. The close relations between watersheds, optimal path cracks in the strong disorder limit, and bridge lines are further supported by either heuristic or exact arguments.

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}.

Dimensional crossover of heat conduction in low dimensions.

The dimensional crossover phenomena of heat conduction is studied by a two-dimensional (2D) Fermi-Pasta-Ulam lattice. The 2D divergence law of the thermal conductivity is confirmed by the simulations results. The divergence law of the thermal conductivity will change from the 2D class to 1D class as delta=N{y}N{x} decreases, here N{y} is the size in transverse direction and Nx in longitude direction. The simulation's results suggest that the dimensional crossover happens in delta{*}-->0 as N{x}-->infinity .

Event synchronization: a simple and fast method to measure synchronicity and time delay patterns.

We propose a simple method to measure synchronization and time-delay patterns between signals. It is based on the relative timings of events in the time series, defined, e.g., as local maxima. The degree of synchronization is obtained from the number of quasisimultaneous appearances of events, and the delay is calculated from the precedence of events in one signal with respect to the other. Moreover, we can easily visualize the time evolution of the delay and synchronization level with an excellent resolution. We apply the algorithm to short rat electroencephalogram (EEG) signals, some of them containing spikes. We also apply it to an intracranial human EEG recording containing an epileptic seizure, and we propose that the method might be useful for the detection of epileptic foci. It can be easily extended to other types of data and it is very simple and fast, thus being suitable for on-line implementations.

Performance of different synchronization measures in real data: a case study on electroencephalographic signals.

We study the synchronization between left and right hemisphere rat electroencephalographic (EEG) channels by using various synchronization measures, namely nonlinear interdependences, phase synchronizations, mutual information, cross correlation, and the coherence function. In passing we show a close relation between two recently proposed phase synchronization measures and we extend the definition of one of them. In three typical examples we observe that except mutual information, all these measures give a useful quantification that is hard to be guessed beforehand from the raw data. Despite their differences, results are qualitatively the same. Therefore, we claim that the applied measures are valuable for the study of synchronization in real data. Moreover, in the particular case of EEG signals their use as complementary variables could be of clinical relevance.

Exactness of the annealed and the replica symmetric approximations for random heteropolymers.

We study a heteropolymer model with random contact interactions introduced some time ago as a simplified model for proteins. The model consists of self-avoiding walks on the simple cubic lattice, with contact interactions between nearest-neighbor pairs. For each pair, the interaction energy is an independent Gaussian variable with mean value B and variance Delta(2). For this model the annealed approximation is expected to become exact for low disorder, at sufficiently high dimension and in the thermodynamic limit. We show that corrections to the annealed approximation in the three-dimensional high-temperature phase are small, but do not vanish in the thermodynamic limit, and are in good agreement with our replica symmetric calculations. Such corrections derive from the fact that the overlap between two typical chains is nonzero. We explain why previous authors had come to the opposite conclusion, and discuss consequences for the thermodynamics of the model. Numerical results were obtained by simulating chains of length N

Coarsening in the presence of kinetic disorders: analogy to granular compaction.

We study the zero temperature dynamics in an Ising chain in the presence of a dynamically induced field that favors locally the " -" phase compared to the " +" phase. At late times, while the " +" domains coarsen as t(1/2), the " -" domains coarsen as t(1/2)log(t). Hence, at late times, the magnetization decays slowly as m(t) = -1+const/log(t). We establish this behavior both analytically within an independent interval approximation and numerically. Our model can be viewed as a simple model for granular compaction, where the system decays into a fully compact state (with all spins " -") in a slow logarithmic manner as seen in recent experiments on granular systems.

Simple model for the DNA denaturation transition.

We study pairs of interacting self-avoiding walks ¿omega(1), omega(2)¿ on the 3d simple cubic lattice. They have a common origin omega(1)(0)=omega 20, and are allowed to overlap only at the same monomer position along the chain: omega(1)(i) not equal omega(2)(j) for i not equal j, while omega(1)(i)=omega(2)(i) is allowed. The latter overlaps are indeed favored by an energetic gain epsilon. This is inspired by a model introduced long ago by Poland and Sheraga [J. Chem. Phys. 45, 1464 (1966)] for the denaturation transition in DNA where, however, self avoidance was not fully taken into account. For both models, there exists a temperature T(m) above which the entropic advantage to open up overcomes the energy gained by forming tightly bound two-stranded structures. Numerical simulations of our model indicate that the transition is of first order (the energy density is discontinuous), but the analog of the surface tension vanishes and the scaling laws near the transition point are exactly those of a second-order transition with crossover exponent straight phi=1. Numerical and exact analytic results show that the transition is second order in modified models where the self-avoidance is partially or completely neglected.

Scaling of waves in the bak-tang-wiesenfeld sandpile model

We study probability distributions of waves of topplings in the Bak-Tang-Wiesenfeld model on hypercubic lattices for dimensions D>/=2. Waves represent relaxation processes which do not contain multiple toppling events. We investigate bulk and boundary waves by means of their correspondence to spanning trees, and by extensive numerical simulations. While the scaling behavior of avalanches is complex and usually not governed by simple scaling laws, we show that the probability distributions for waves display clear power-law asymptotic behavior in perfect agreement with the analytical predictions. Critical exponents are obtained for the distributions of radius, area, and duration of bulk and boundary waves. Relations between them and fractal dimensions of waves are derived. We confirm that the upper critical dimension D(u) of the model is 4, and calculate logarithmic corrections to the scaling behavior of waves in D=4. In addition, we present analytical estimates for bulk avalanches in dimensions D>/=4 and simulation data for avalanches in D

Learning driver-response relationships from synchronization patterns.

We test recent claims that causal (driver-response) relationships can be deduced from interdependencies between simultaneously measured time series. We apply two recently proposed interdependence measures that should give results similar to cross predictabilities used by previous authors. The systems that we study are asymmetrically coupled simple models (Lorenz, Roessler, and Hénon models), the couplings being such that they lead to generalized synchronization. If the data were perfect (noise-free, infinitely long), we should be able to detect, at least in some cases, which of the coupled systems is the driver and which the response. This might no longer be true if the time series has finite length. Instead, estimated interdependencies depend strongly on which of the systems has a higher effective dimension at the typical neighborhood sizes used to estimate them, and causal relationships are more difficult to detect. We also show that slightly different variants of the interdependence measure can have quite different sensitivities.

Kulback-Leibler and renormalized entropies: applications to electroencephalograms of epilepsy patients.

Recently, "renormalized entropy" was proposed as a novel measure of relative entropy [P. Saparin et al., Chaos, Solitons and Fractals 4, 1907 (1994)] and applied to several physiological time sequences, including electroencephalograms (EEGs) of patients with epilepsy. We show here that this measure is just a modified Kullback-Leibler (KL) relative entropy, and it gives similar numerical results to the standard KL entropy. The latter better distinguishes frequency contents of, e.g., seizure and background EEGs than renormalized entropy. We thus propose that renormalized entropy might not be as useful as claimed by its proponents. In passing, we also make some critical remarks about the implementation of these methods.

Testing a new Monte Carlo algorithm for protein folding.

We demonstrate that the recently proposed pruned-enriched Rosenbluth method (PERM) (Grassberger, Phys. Rev. E 56:3682, 1997) leads to extremely efficient algorithms for the folding of simple model proteins. We test it on several models for lattice heteropolymers, and compare it to published Monte Carlo studies of the properties of particular sequences. In all cases our method is faster than the previous ones, and in several cases we find new minimal energy states. In addition to producing more reliable candidates for ground states, our method gives detailed information about the thermal spectrum and thus allows one to analyze thermodynamic aspects of the folding behavior of arbitrary sequences.