Aftermath epidemics: Percolation on the sites visited by generalized random walks.

We study percolation on the sites of a finite lattice visited by a generalized random walk of finite length with periodic boundary conditions. More precisely, consider Levy flights and walks with finite jumps of length >1 [like Knight's move random walks (RWs) in two dimensions and generalized Knight's move RWs in 3D]. In these walks, the visited sites do not form (as in ordinary RWs) a single connected cluster, and thus percolation on them is nontrivial. The model essentially mimics the spreading of an epidemic in a population weakened by the passage of some devastating agent-like diseases in the wake of a passing army or of a hurricane. Using the density of visited sites (or the number of steps in the walk) as a control parameter, we find a true continuous percolation transition in all cases except for the 2D Knight's move RWs and Levy flights with Levy parameter σ≥2. For 3D generalized Knight's move RWs, the model is in the universality class of pacman percolation, and all critical exponents seem to be simple rationals, in particular, ß=1. For 2D Levy flights with 0<σ<2, scale invariance is broken even at the critical point, which leads at least to very large corrections in finite-size scaling, and even very large simulations were unable to unambiguously determine the critical exponents.

Many universality classes in an interface model restricted to non-negative heights.

We present a simple one-dimensional stochastic model with three control parameters and a surprisingly rich zoo of phase transitions. At each (discrete) site x and time t, an integer n(x,t) satisfies a linear interface equation with added random noise. Depending on the control parameters, this noise may or may not satisfy the detailed balance condition, so that the growing interfaces are in the Edwards-Wilkinson or in the Kardar-Parisi-Zhang universality class. In addition, there is also a constraint n(x,t)≥0. Points x where n>0 on one side and n=0 on the other are called "fronts." These fronts can be "pushed" or "pulled," depending on the control parameters. For pulled fronts, the lateral spreading is in the directed percolation (DP) universality class, while it is in a different universality class for pushed fronts, and another universality class in between. In the DP case, the activity at each active site can in general be arbitrarily large, in contrast to previous realizations of DP. Finally, we find two different types of transitions when the interface detaches from the line n=0 (with 〈n(x,t)〉→const on one side, and →∞ on the other), again with new universality classes. We also discuss a mapping of this model to the avalanche propagation in a directed Oslo rice pile model in specially prepared backgrounds.

On Generalized Schürmann Entropy Estimators.

We present a new class of estimators of Shannon entropy for severely undersampled discrete distributions. It is based on a generalization of an estimator proposed by T. Schürmann, which itself is a generalization of an estimator proposed by myself.For a special set of parameters, they are completely free of bias and have a finite variance, something which is widely believed to be impossible. We present also detailed numerical tests, where we compare them with other recent estimators and with exact results, and point out a clash with Bayesian estimators for mutual information.

Universality of Critically Pinned Interfaces in Two-Dimensional Isotropic Random Media.

Based on extensive simulations, we conjecture that critically pinned interfaces in two-dimensional isotropic random media with short-range correlations are always in the universality class of ordinary percolation. Thus, in contrast to interfaces in >2 dimensions, there is no distinction between fractal (i.e., percolative) and rough but nonfractal interfaces. Our claim includes interfaces in zero-temperature random field Ising models (both with and without spontaneous nucleation), in heterogeneous bootstrap percolation, and in susceptible-weakened-infected-removed epidemics. It does not include models with long-range correlations in the randomness and models where overhangs are explicitly forbidden (which would imply nonisotropy of the medium).

Self-Trapping Self-Repelling Random Walks.

Although the title seems self-contradictory, it does not contain a misprint. The model we study is a seemingly minor modification of the "true self-avoiding walk" model of Amit, Parisi, and Peliti in two dimensions. The walks in it are self-repelling up to a characteristic time T^{*} (which depends on various parameters), but spontaneously (i.e., without changing any control parameter) become self-trapping after that. For free walks, T^{*} is astronomically large, but on finite lattices the transition is easily observable. In the self-trapped regime, walks are subdiffusive and intermittent, spending longer and longer times in small areas until they escape and move rapidly to a new area. In spite of this, these walks are extremely efficient in covering finite lattices, as measured by average cover times.

Critical phenomena on k-booklets.

We define a "k-booklet" to be a set of k semi-infinite planes with -∞

Universality and asymptotic scaling in drilling percolation.

We present simulations of a three-dimensional percolation model studied recently by K. J. Schrenk et al. [Phys. Rev. Lett. 116, 055701 (2016)PRLTAO0031-900710.1103/PhysRevLett.116.055701], obtained with a new and more efficient algorithm. They confirm most of their results in spite of larger systems and higher statistics used in the present Rapid Communication, but we also find indications that the results do not yet represent the true asymptotic behavior. The model is obtained by replacing the isotropic holes in ordinary Bernoulli percolation by randomly placed and oriented cylinders, with the constraint that the cylinders are parallel to one of the three coordinate axes. We also speculate on possible generalizations.

How fast does a random walk cover a torus?

We present high statistics simulation data for the average time 〈T_{cover}(L)〉 that a random walk needs to cover completely a two-dimensional torus of size L×L. They confirm the mathematical prediction that 〈T_{cover}(L)〉∼(LlnL)^{2} for large L, but the prefactor seems to deviate significantly from the supposedly exact result 4/π derived by Dembo et al. [Ann. Math. 160, 433 (2004)ANMAAH0003-486X10.4007/annals.2004.160.433], if the most straightforward extrapolation is used. On the other hand, we find that this scaling does hold for the time T_{N(t)=1}(L) at which the average number of yet unvisited sites is 1, as also predicted previously. This might suggest (wrongly) that 〈T_{cover}(L)〉 and T_{N(t)=1}(L) scale differently, although the distribution of rescaled cover times becomes sharp in the limit L→∞. But our results can be reconciled with those of Dembo et al. by a very slow and nonmonotonic convergence of 〈T_{cover}(L)〉/(LlnL)^{2}, as had been indeed proven by Belius et al. [Probab. Theory Relat. Fields 167, 461 (2017)10.1007/s00440-015-0689-6] for Brownian walks, and was conjectured by them to hold also for lattice walks.

Oslo model, hyperuniformity, and the quenched Edwards-Wilkinson model.

We present simulations of the one-dimensional Oslo rice pile model in which the critical height at each site is randomly reset after each toppling. We use the fact that the stationary state of this sand-pile model is hyperuniform to reach system of sizes >10^{7}. Most previous simulations were seriously flawed by important finite-size corrections. We find that all critical exponents have values consistent with simple rationals: ν=4/3 for the correlation length exponent, D=9/4 for the fractal dimension of avalanche clusters, and z=10/7 for the dynamical exponent. In addition, we relate the hyperuniformity exponent to the correlation length exponent ν. Finally, we discuss the relationship with the quenched Edwards-Wilkinson model, where we find in particular that the local roughness exponent is α_{loc}=1.

Immunization and Targeted Destruction of Networks using Explosive Percolation.

A new method ("explosive immunization") is proposed for immunization and targeted destruction of networks. It combines the explosive percolation (EP) paradigm with the idea of maintaining a fragmented distribution of clusters. The ability of each node to block the spread of an infection (or to prevent the existence of a large cluster of connected nodes) is estimated by a score. The algorithm proceeds by first identifying low score nodes that should not be vaccinated or destroyed, analogously to the links selected in EP if they do not lead to large clusters. As in EP, this is done by selecting the worst node (weakest blocker) from a finite set of randomly chosen "candidates." Tests on several real-world and model networks suggest that the method is more efficient and faster than any existing immunization strategy. Because of the latter property it can deal with very large networks.

Phase transitions in cooperative coinfections: Simulation results for networks and lattices.

We study the spreading of two mutually cooperative diseases on different network topologies, and with two microscopic realizations, both of which are stochastic versions of a susceptible-infected-removed type model studied by us recently in mean field approximation. There it had been found that cooperativity can lead to first order transitions from spreading to extinction. However, due to the rapid mixing implied by the mean field assumption, first order transitions required nonzero initial densities of sick individuals. For the stochastic model studied here the results depend strongly on the underlying network. First order transitions are found when there are few short but many long loops: (i) No first order transitions exist on trees and on 2-d lattices with local contacts. (ii) They do exist on Erdos-Rényi (ER) networks, on d-dimensional lattices with d≥4, and on 2-d lattices with sufficiently long-ranged contacts. (iii) On 3-d lattices with local contacts the results depend on the microscopic details of the implementation. (iv) While single infected seeds can always lead to infinite epidemics on regular lattices, on ER networks one sometimes needs finite initial densities of infected nodes. (v) In all cases the first order transitions are actually "hybrid"; i.e., they display also power law scaling usually associated with second order transitions. On regular lattices, our model can also be interpreted as the growth of an interface due to cooperative attachment of two species of particles. Critically pinned interfaces in this model seem to be in different universality classes than standard critically pinned interfaces in models with forbidden overhangs. Finally, the detailed results mentioned above hold only when both diseases propagate along the same network of links. If they use different links, results can be rather different in detail, but are similar overall.

Percolation transitions in the survival of interdependent agents on multiplex networks, catastrophic cascades, and solid-on-solid surface growth.

We present an efficient algorithm for simulating percolation transitions of mutually supporting viable clusters on multiplex networks (also known as "catastrophic cascades on interdependent networks"). This algorithm maps the problem onto a solid-on-solid-type model. We use this algorithm to study interdependent agents on duplex Erdös-Rényi (ER) networks and on lattices with dimensions 2, 3, 4, and 5. We obtain surprising results in all these cases, and we correct statements in the literature for ER networks and for two-dimensional lattices. In particular, we find that d=4 is the upper critical dimension and that the percolation transition is continuous for d≤4 but-at least for d≠3-not in the universality class of ordinary percolation. For ER networks we verify that the cluster statistics is exactly described by mean-field theory but find evidence that the cascade process is not. For d=5 we find a first-order transition as for ER networks, but we find also that small clusters have a nontrivial mass distribution that scales at the transition point. Finally, for d=2 with intermediate-range dependency links we propose a scenario that differs from that proposed in W. Li et al. [Phys. Rev. Lett. 108, 228702 (2012)].

Information theoretic aspects of the two-dimensional Ising model.

We present numerical results for various information theoretic properties of the square lattice Ising model. First, using a bond propagation algorithm, we find the difference 2H(L)(w)-H(2L)(w) between entropies on cylinders of finite lengths L and 2L with open end cap boundaries, in the limit L→∞. This essentially quantifies how the finite length correction for the entropy scales with the cylinder circumference w. Secondly, using the transfer matrix, we obtain precise estimates for the information needed to specify the spin state on a ring encircling an infinitely long cylinder. Combining both results, we obtain the mutual information between the two halves of a cylinder (the "excess entropy" for the cylinder), where we confirm with higher precision but for smaller systems the results recently obtained by Wilms et al., and we show that the mutual information between the two halves of the ring diverges at the critical point logarithmically with w. Finally, we use the second result together with Monte Carlo simulations to show that also the excess entropy of a straight line of n spins in an infinite lattice diverges at criticality logarithmically with n. We conjecture that such logarithmic divergence happens generically for any one-dimensional subset of sites at any two-dimensional second-order phase transition. Comparing straight lines on square and triangular lattices with square loops and with lines of thickness 2, we discuss questions of universality.

Agglomerative percolation on bipartite networks: nonuniversal behavior due to spontaneous symmetry breaking at the percolation threshold.

Ordinary bond percolation (OP) can be viewed as a process where clusters grow by joining them pairwise, adding links chosen randomly one by one from a set of predefined virtual links. In contrast, in agglomerative percolation (AP) clusters grow by choosing randomly a target cluster and joining it with all its neighbors, as defined by the same set of virtual links. Previous studies showed that AP is in different universality classes from OP for several types of (virtual) networks (linear chains, trees, Erdös-Rényi networks), but most surprising were the results for two-dimensional (2D) lattices: While AP on the triangular lattice was found to be in the OP universality class, it behaved completely differently on the square lattice. In the present paper we explain this striking violation of universality by invoking bipartivity. While the square lattice is a bipartite graph, the triangular lattice is not. In conformity with this we show that AP on the honeycomb and simple cubic (3D) lattices--both of which are bipartite--are also not in the OP universality classes. More precisely, we claim that this violation of universality is basically due to a Z(2) symmetry that is spontaneously broken at the percolation threshold. We also discuss AP on bipartite random networks and suitable generalizations of AP on k-partite graphs.

Discontinuous percolation transitions in epidemic processes, surface depinning in random media, and Hamiltonian random graphs.

Discontinuous percolation transitions and the associated tricritical points are manifest in a wide range of both equilibrium and nonequilibrium cooperative phenomena. To demonstrate this, we present and relate the continuous and first-order behaviors in two different classes of models: The first are generalized epidemic processes that describe in their spatially embedded version--either on or off a regular lattice--compact or fractal cluster growth in random media at zero temperature. A random graph version of these processes is mapped onto a model previously proposed for complex social contagion. We compute detailed phase diagrams and compare our numerical results at the tricritical point in d = 3 with field theory predictions of Janssen et al. [Phys. Rev. E 70, 026114 (2004)]. The second class consists of exponential ("Hamiltonian," i.e., formally equilibrium) random graph models and includes the Strauss and the two-star model, where "chemical potentials" control the densities of links, triangles, or two-stars. When the chemical potentials in either graph model are O(logN), the percolation transition can coincide with a first-order phase transition in the density of links, making the former also discontinuous. Hysteresis loops can then be of mixed order, with second-order behavior for decreasing link fugacity, and a jump (first order) when it increases.

Exact solutions for mass-dependent irreversible aggregations.

We consider the mass-dependent aggregation process (k+1)X→X, given a fixed number of unit mass particles in the initial state. One cluster is chosen proportional to its mass and is merged into one, either with k neighbors in one dimension, or--in the well-mixed case--with k other clusters picked randomly. We find the same combinatorial exact solutions for the probability to find any given configuration of particles on a ring or line, and in the well-mixed case. The mass distribution of a single cluster exhibits scaling laws and the finite-size scaling form is given. The relation to the classical sum kernel of irreversible aggregation is discussed.

Percolation transitions are not always sharpened by making networks interdependent.

We study a model for coupled networks introduced recently by Buldyrev et al., [Nature (London) 464, 1025 (2010)], where each node has to be connected to others via two types of links to be viable. Removing a critical fraction of nodes leads to a percolation transition that has been claimed to be more abrupt than that for uncoupled networks. Indeed, it was found to be discontinuous in all cases studied. Using an efficient new algorithm we verify that the transition is discontinuous for coupled Erdös-Rényi networks, but find it to be continuous for fully interdependent diluted lattices. In 2 and 3 dimensions, the order parameter exponent ß is larger than in ordinary percolation, showing that the transition is less sharp, i.e., further from discontinuity, than for isolated networks. Possible consequences for spatially embedded networks are discussed.

Explosive percolation is continuous, but with unusual finite size behavior.

We study four Achlioptas-type processes with "explosive" percolation transitions. All transitions are clearly continuous, but their finite size scaling functions are not entirely holomorphic. The distributions of the order parameter, i.e., the relative size s(max)/N of the largest cluster, are double humped. But-in contrast to first-order phase transitions-the distance between the two peaks decreases with system size N as N(-η) with η>0. We find different positive values of ß (defined via (s(max)/N)∼(p-p(c))ß for infinite systems) for each model, showing that they are all in different universality classes. In contrast, the exponent Θ (defined such that observables are homogeneous functions of (p-p(c))N(Θ)) is close to-or even equal to-1/2 for all models.