Search

We consider an infinite spatial inhomogeneous random graph model with an integrable connection kernel that interpolates nicely between existing spatial random graph models. Key examples are versions of the weight-dependent random connection model, the infinite geometric inhomogeneous random graph, and the age-based random connection model. These infinite models arise as the local limit of the corresponding finite models. For these models we identify the asymptotics of the local clustering as a function of the degree of the root in different regimes in a unified way. We show that the scaling exhibits phase transitions as the interpolation parameter moves across different regimes. This allows us to draw conclusions on the geometry of a typical triangle contributing to the clustering in the different regimes. [ABSTRACT FROM AUTHOR]

We introduce a metric space of clusterings, where clusterings are described by a binary vector indexed by the vertex-pairs. We extend this geometry to a hypersphere and prove that maximizing modularity is equivalent to minimizing the angular distance to some modularity vector over the set of clustering vectors. In that sense, modularity-based community detection methods can be seen as a subclass of a more general class of projection methods, which we define as the community detection methods that adhere to the following two-step procedure: first, mapping the network to a point on the hypersphere; second, projecting this point to the set of clustering vectors. We show that this class of projection methods contains many interesting community detection methods. Many of these new methods cannot be described in terms of null models and resolution parameters, as is customary for modularity-based methods. We provide a new characterization of such methods in terms of meridians and latitudes of the hypersphere. In addition, by relating the modularity resolution parameter to the latitude of the corresponding modularity vector, we obtain a new interpretation of the resolution limit that modularity maximization is known to suffer from. [ABSTRACT FROM AUTHOR]

We investigate how the complexity of Euclidean TSP for point sets P inside the strip (- ∞ , + ∞) × [ 0 , δ ] depends on the strip width δ . We obtain two main results. For the case where the points have distinct integer x-coordinates, we prove that a shortest bitonic tour (which can be computed in O (n log 2 n) time using an existing algorithm) is guaranteed to be a shortest tour overall when δ ⩽ 2 2 , a bound which is best possible. We present an algorithm that is fixed-parameter tractable with respect to δ . Our algorithm has running time 2 O (δ) n + O (δ 2 n 2) for sparse point sets, where each 1 × δ rectangle inside the strip contains O(1) points. For random point sets, where the points are chosen uniformly at random from the rectangle [ 0 , n ] × [ 0 , δ ] , it has an expected running time of 2 O (δ) n . These results generalise to point sets P inside a hypercylinder of width δ . In this case, the factors 2 O (δ) become 2 O (δ 1 - 1 / d) . [ABSTRACT FROM AUTHOR]

In this paper, we study the critical behavior of percolation on a configuration model with degree distribution satisfying an infinite second-moment condition, which includes power-law degrees with exponent τ ∈ (2 , 3) . It is well known that, in this regime, many canonical random graph models, such as the configuration model, are robust in the sense that the giant component is not destroyed when the percolation probability stays bounded away from zero. Thus, the critical behavior is observed when the percolation probability tends to zero with the network size, despite of the fact that the average degree remains bounded. In this paper, we initiate the study of critical random graphs in the infinite second-moment regime by identifying the critical window for the configuration model. We prove scaling limits for component sizes and surplus edges, and show that the maximum diameter the critical components is of order log n , which contrasts with the previous universality classes arising in the literature. This introduces a third and novel universality class for the critical behavior of percolation on random networks, that is not covered by the multiplicative coalescent framework due to Aldous and Limic (Electron J Probab 3(3):1–59, 1998). We also prove concentration of the component sizes outside the critical window, and that a unique, complex giant component emerges after the critical window. This completes the picture for the percolation phase transition on the configuration model. [ABSTRACT FROM AUTHOR]

Consider random d-regular graphs, i.e., random graphs such that there are exactly d edges from each vertex for some d≥3. We study both the configuration model version of this graph, which has occasional multi-edges and self-loops, as well as the simple version of it, which is a d-regular graph chosen uniformly at random from the collection of all d-regular graphs. In this paper, we discuss mixing times of Glauber dynamics for the Ising model with an external magnetic field on a random d-regular graph, both in the quenched as well as the annealed settings. Let β be the inverse temperature, βc be the critical temperature and B be the external magnetic field. Concerning the annealed measure, we show that for β>βc there exists ... such that the model is metastable (i.e., the mixing time is exponential in the graph size n) when β>βc and ..., whereas it exhibits the cut-off phenomenon at c*nlogn with a window of order n when β<βc or β>βc and ... Interestingly, ... coincides with the critical external field of the Ising model on the d-ary tree (namely, above which the model has a unique Gibbs measure). Concerning the quenched measure, we show that there exists Bc(β) with ... such that for β>βc, the mixing time is at least exponential along some subsequence (nk)k≥1 when 0≤B

Let T be a supercritical Galton–Watson tree with a bounded offspring distribution that has mean μ > 1 , conditioned to survive. Let φ T be a random embedding of T into Z d according to a simple random walk step distribution. Let T p be percolation on T with parameter p, and let p c = μ - 1 be the critical percolation parameter. We consider a random walk (X n) n ≥ 1 on T p and investigate the behavior of the embedded process φ T p (X n) as n → ∞ and simultaneously, T p becomes critical, that is, p = p n ↘ p c . We show that when we scale time by n / (p n - p c) 3 and space by (p n - p c) / n , the process (φ T p (X n)) n ≥ 1 converges to a d-dimensional Brownian motion. We argue that this scaling can be seen as an interpolation between the scaling of random walk on a static random tree and the anomalous scaling of processes in critical random environments. [ABSTRACT FROM AUTHOR]

We establish sharp tail asymptotics for componentwise extreme values of bivariate Gaussian random vectors with arbitrary correlation between the components. We consider two scaling regimes for the tail event in which we demonstrate the existence of a restricted large deviations principle and identify the unique rate function associated with these asymptotics. Our results identify when the maxima of both coordinates are typically attained by two different versus the same index, and how this depends on the correlation between the coordinates of the bivariate Gaussian random vectors. Our results complement a growing body of work on the extremes of Gaussian processes. The results are also relevant for steady-state performance and simulation analysis of networks of infinite server queues. [ABSTRACT FROM AUTHOR]

We prove results for first-passage percolation on the configuration model with degrees having asymptotic finite mean, infinite variance and i.i.d. edge-weights with strictly positive support of the form Y=a+X, where a is a positive constant and the excess edge-weight X is a non-negative random variable with zero as the infimum of its support. We prove that the weight of the optimal path between two uniformly chosen vertices has tight fluctuations around the asymptotic mean of the graph-distance if and only if the following condition holds: the random variable X is such that the age-dependent branching process describing first-passage percolation exploration in the same graph with edge-weights from distribution X has a positive probability to reach infinitely many individuals in a finite time. This shows that almost-shortest paths in the graph-distance proliferate, in the sense that there even exist paths having tight total excess edge-weight for appropriate edge-weight distributions. Our proof makes use of a degree-dependent percolation model that we believe is interesting in its own right, as well as tightness results for distances in scale-free configuration models that we prove to hold under rather weak conditions on the degrees. [ABSTRACT FROM AUTHOR]

Abstract To understand mesoscopic scaling in networks, we study the hierarchical configuration model (HCM), a random graph model with community structure. Connections between communities are formed as in a configuration model. We study the component sizes of HCM at criticality, and we study critical bond percolation. We find the conditions on the community sizes such that the critical component sizes of HCM behave similarly as in the configuration model. We show that the ordered components of a critical HCM on N vertices are O (N 2 ∕ 3). More specifically, the rescaled component sizes converge to the excursions of a Brownian motion with parabolic drift. [ABSTRACT FROM AUTHOR]

The configuration model generates random graphs with any given degree distribution, and thus serves as a null model for scale-free networks with power-law degrees and unbounded degree fluctuations. For this setting, we study the local clustering c(k), i.e., the probability that two neighbors of a degree-k node are neighbors themselves. We show that c(k) progressively falls off with k and the graph size n and eventually for k=Ω(n) settles on a power law c(k)∼n5-2τk-2(3-τ) with τ∈(2,3) the power-law exponent of the degree distribution. This fall-off has been observed in the majority of real-world networks and signals the presence of modular or hierarchical structure. Our results agree with recent results for the hidden-variable model and also give the expected number of triangles in the configuration model when counting triangles only once despite the presence of multi-edges. We show that only triangles consisting of triplets with uniquely specified degrees contribute to the triangle counting. [ABSTRACT FROM AUTHOR]

In [3, Theorem 1.2], we claim that the maximal cluster for critical percolation on the high-dimensional torus is non-concentrated. This proof contains an error. In this note, we replace this statement by a conditional statement instead. [ABSTRACT FROM AUTHOR]

Recently, the scaling limit of cluster sizes for critical inhomogeneous random graphs of rank-1 type having finite variance but infinite third moment degrees was obtained in Bhamidi et al. (Ann Probab 40:2299-2361, 2012). It was proved that when the degrees obey a power law with exponent τ∈(3,4), the sequence of clusters ordered in decreasing size and multiplied through by n-(τ-2)/(τ-1) converges as n→∞ to a sequence of decreasing non-degenerate random variables. Here, we study the tails of the limit of the rescaled largest cluster, i.e., the probability that the scaling limit of the largest cluster takes a large value u, as a function of u. This extends a related result of Pittel (J Combin Theory Ser B 82(2):237-269, 2001) for the Erdős-Rényi random graph to the setting of rank-1 inhomogeneous random graphs with infinite third moment degrees. We make use of delicate large deviations and weak convergence arguments. [ABSTRACT FROM AUTHOR]

One major open conjecture in the area of critical random graphs, formulated by statistical physicists, and supported by a large amount of numerical evidence over the last decade (Braunstein et al. in Phys Rev Lett 91(16):168701, 2003; Wu et al. in Phys Rev Lett 96(14):148702, 2006; Braunstein et al. Int J Bifurc Chaos 17(07):2215-2255, 2007; Chen et al. in Phys Rev Lett 96(6):068702, 2006) is as follows: for a wide array of random graph models with degree exponent $$\tau \in (3,4)$$ , distances between typical points both within maximal components in the critical regime as well as on the minimal spanning tree on the giant component in the supercritical regime scale like $$n^{(\tau -3)/(\tau -1)}$$ . In this paper we study the metric space structure of maximal components of the multiplicative coalescent, in the regime where the sizes converge to excursions of Lévy processes 'without replacement' (Aldous and Limic Electron in J Probab 3(3):59, 1998), yielding a completely new class of limiting random metric spaces. A by-product of the analysis yields the continuum scaling limit of one fundamental class of random graph models with degree exponent $$\tau \in (3,4)$$ where edges are rescaled by $$n^{-(\tau -3)/(\tau -1)}$$ yielding the first rigorous proof of the above conjecture. The limits in this case are compact 'tree-like' random fractals with a dense collection of hubs (infinite degree vertices), a finite number of which are identified with leaves to form shortcuts. In a special case, we show that the Minkowski dimension of the limiting spaces equal $$(\tau -2)/(\tau -3)$$ a.s., in stark contrast to the Erdős-Rényi scaling limit whose Minkowski dimension is 2 a.s. It is generally believed that dynamic versions of a number of fundamental random graph models, as one moves from the barely subcritical to the critical regime can be approximated by the multiplicative coalescent. In work in progress, the general theory developed in this paper is used to prove analogous limit results for other random graph models with degree exponent $$\tau \in (3,4)$$ . Our proof makes crucial use of inhomogeneous continuum random trees (ICRT), which have previously arisen in the study of the entrance boundary of the additive coalescent. We show that tilted versions of the same objects using the associated mass measure, describe connectivity properties of the multiplicative coalescent. Since convergence of height processes of corresponding approximating $$\mathbf {p}$$ -trees is not known, we use general methodology in Athreya et al. (2014) and develop novel techniques relying on first showing convergence in the Gromov-weak topology and then extending this to Gromov-Hausdorff-Prokhorov convergence by proving a global lower mass-bound. [ABSTRACT FROM AUTHOR]

We show Green's function asymptotic upper bound for the two-point function of weakly self-avoiding walk in d >4, revisiting a classic problem. Our proof relies on Banach algebras to analyse the lace-expansion fixed point equation and is simpler than previous approaches in that it avoids Fourier transforms. [ABSTRACT FROM AUTHOR]

We study bond percolation on the Hamming hypercube {0,1}m around the critical probability pc. It is known that if p=pc(1+O(2−m/3)), then with high probability the largest connected component C1 is of size Θ(22m/3). Here we show that for any sequence ϵ(m) such that ϵ(m)=o(1) but ϵ(m)≫2−m/3 percolation on the hypercube at pc(1+ϵ(m)) has |C1|=(2+o(1))ϵ(m)2mand|C2|=o(ϵ(m)2m), with high probability, where C2 is the second largest component. This resolves a conjecture of Borgs, Chayes, the first author, Slade and Spencer [18]. [ABSTRACT FROM AUTHOR]

Numerous properties of random graphs are highly predictable. Even by exploring a small part reliable observations are possible regarding their structure and size. An unfortunate observation is that standard models for random graphs, such as the Erdös–Rényi model, do not reflect the structure of the graphs that describe distributed systems and protocols. In this paper we propose to use the parallel composition of such random graphs to model ‘real’ state spaces. We show how we can use this structure to predict the size of state spaces, and we can use it to explain that software bugs are in practice far easier to find than predicted by the standard random graph models. By practical experiments we show that our new probabilistic model is an improvement over the standard model in predicting properties of transition systems representing realistic systems. [ABSTRACT FROM AUTHOR]

We study lattice trees (LTs) and animals (LAs) on the nearest-neighbor lattice Z d in high dimensions. We prove that LTs and LAs display mean-field behavior above dimension 16 and 17 , respectively. Such results have previously been obtained by Hara and Slade in sufficiently high dimensions. The dimension above which their results apply was not yet specified. We rely on the non-backtracking lace expansion (NoBLE) method that we have recently developed. The NoBLE makes use of an alternative lace expansion for LAs and LTs that perturbs around non-backtracking random walk rather than around simple random walk, leading to smaller corrections. The NoBLE method then provides a careful computational analysis that improves the dimension above which the result applies. Universality arguments predict that the upper critical dimension, above which our results apply, is equal to d c = 8 for both models, as is known for sufficiently spread-out models by the results of Hara and Slade mentioned earlier. The main ingredients in this paper are (a) a derivation of a non-backtracking lace expansion for the LT and LA two-point functions; (b) bounds on the non-backtracking lace-expansion coefficients, thus showing that our general NoBLE methodology can be applied; and (c) sharp numerical bounds on the coefficients. Our proof is complemented by a computer-assisted numerical analysis that verifies that the necessary bounds used in the NoBLE are satisfied. [ABSTRACT FROM AUTHOR]

This paper deals with the large deviations behavior of a stochastic process called a thinned Lévy process. This process appeared recently as a stochastic-process limit in the context of critical inhomogeneous random graphs (Bhamidi et al. (2012)). The process has a strong negative drift, while we are interested in the rare event of the process being positive at large times. To characterize this rare event, we identify a tilted measure. This presents some challenges inherent to the power-law nature of the thinned Lévy process. General principles prescribe that the tilt should follow from a variational problem, but in the case of the thinned Lévy process this involves a Riemann sum that is hard to control. We choose to approximate the Riemann sum by its limiting integral, derive the first-order correction term, and prove that the tilt that follows from the corresponding approximate variational problem is sufficient to establish the large deviations results. [ABSTRACT FROM AUTHOR]

In the past years, many properties of the largest connected components of critical percolation on the high-dimensional torus, such as their sizes and diameter, have been established. The order of magnitude of these quantities equals the one for percolation on the complete graph or Erdos-Rényi random graph, raising the question whether the scaling limits of the largest connected components, as identified by Aldous (1997), are also equal. In this paper, we investigate the cycle structure of the largest critical components for high-dimensional percolation on the torus {-⌊r/2⌋,...,⌈r/2⌉-1}d. While percolation clusters naturally have many short cycles, we show that the long cycles, i.e., cycles that pass through the boundary of the cube of width r/4 centered around each of their vertices, have length of order rd/3, as on the critical Erdos-Rényi random graph. On the Erdos-Rényi random graph, cycles play an essential role in the scaling limit of the large critical clusters, as identified by Addario-Berry, Broutin and Goldschmidt (2010). Our proofs crucially rely on various new estimates of probabilities of the existence of open paths in critical Bernoulli percolation on ℤd with constraints on their lengths. We believe these estimates are interesting in their own right. [ABSTRACT FROM AUTHOR]

We formulate and study a model for inhomogeneous long-range percolation on ℤd. Each vertex x ϵ ℤd is assigned a non-negative weight Wx, where (Wx)xϵℤd are i.i.d. random variables. Conditionally on the weights, and given two parameters a, A > 0, the edges are independent and the probability that there is an edge between x and y is given by Pxy = 1 - exp{ -λWx Wy / ∣x - y ∣α}. The parameter λ is the percolation parameter, while a describes the long-range nature of the model. We focus on the degree distribution in the resulting graph, on whether there exists an infinite component and on graph distance between remote pairs of vertices. First, we show that the tail behavior of the degree distribution is related to the tail behavior of the weight distribution. When the tail of the distribution of Wx is regularly varying with exponent τ - 1, then the tail of the degree distribution is regularly varying with exponent γ = α(τ - l)/d. The parameter γ turns out to be crucial for the behavior of the model. Conditions on the weight distribution and γ are formulated for the existence of a critical value λ c ϵ(0, ∞) such that the graph contains an infinite component when λ > λc and no infinite component when λ < λc. Furthermore, a phase transition is established for the graph distances between vertices in the infinite component at the point γ = 2, that is, at the point where the degrees switch from having finite to infinite second moment. The model can be viewed as an interpolation between long-range percolation and models for inhomogeneous random graphs, and we show that the behavior shares the interesting features of both these models. [ABSTRACT FROM AUTHOR]

Mixing patterns in large self-organizing networks, such as the Internet, the World Wide Web, and social and biological networks, are often characterized by degree-degree dependencies between neighboring nodes. In this paper, we propose a new way of measuring degree-degree dependencies. One of the problems with the commonly used assortativity coefficient is that in disassortative networks its magnitude decreases with the network size. We mathematically explain this phenomenon and validate the results on synthetic graphs and real-world network data. As an alternative, we suggest to use rank correlation measures such as Spearman's ρ. Our experiments convincingly show that Spearman's ρ produces consistent values in graphs of different sizes but similar structure, and it is able to reveal strong (positive or negative) dependencies in large graphs. In particular, we discover much stronger negative degree-degree dependencies in Web graphs than was previously thought. Rank correlations allow us to compare the assortativity of networks of different sizes, which is impossible with the assortativity coefficient due to its genuine dependence on the network size. We conclude that rank correlations provide a suitable and informative method for uncovering network mixing patterns. [ABSTRACT FROM AUTHOR]

In this paper, which is a culmination of our previous research efforts, we provide a general framework for studying mixing profiles of non-backtracking random walks on dynamic random graphs generated according to the configuration model. The quantity of interest is the scaling of the mixing time of the random walk as the number of vertices of the random graph tends to infinity. Subject to mild general conditions, we link two mixing times: one for a static version of the random graph, the other for a class of dynamic versions of the random graph in which the edges are randomly rewired but the degrees are preserved. With the help of coupling arguments we show that the link is provided by the probability that the random walk has not yet stepped along a previously rewired edge. To demonstrate the utility of our framework, we rederive our earlier results on mixing profiles for global edge rewiring under weaker assumptions, and extend these results to an entire class of rewiring dynamics parametrised by the range of the rewiring relative to the position of the random walk. Along the way we establish that all the graph dynamics in this class exhibit the trichotomy we found earlier, namely, no cut-off, one-sided cut-off or two-sided cut-off. For interpolations between global edge rewiring, the only Markovian graph dynamics considered here, and local edge rewiring (i.e., only those edges that are incident to the random walk can be rewired), we show that the trichotomy splits further into a hexachotomy, namely, three different mixing profiles with no cut-off, two with one-sided cutoff, and one with two-sided cut-off. Proofs are built on a new and flexible coupling scheme, in combination with sharp estimates on the degrees encountered by the random walk in the static and the dynamic version of the random graph. Some of these estimates require sharp control on possible short-cuts in the graph between the edges that are traversed by the random walk. • We give a framework to study mixing of non-backtracking random walks on dynamic graphs. • We describe mixing profiles for a class of graph dynamics parametrised by their range. • For a class of graph dynamics we observe a hexachotomy in their mixing profiles. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the diameter in preferential attachment (PA-) models, thus quantifying the statement that these models are small worlds. The models studied here are such that edges are attached to older vertices proportional to the degree plus a constant, i.e., we consider affine PA-models. There is a substantial amount of literature proving that, quite generally, PA-graphs possess power-law degree sequences with a power-law exponent τ>2. We prove that the diameter of the PA-model is bounded above by a constant times log t, where t is the size of the graph. When the power-law exponent τ exceeds 3, then we prove that log t is the right order, by proving a lower bound of this order, both for the diameter as well as for the typical distance. This shows that, for τ>3, distances are of the order log t. For τ∈(2,3), we improve the upper bound to a constant times log log t, and prove a lower bound of the same order for the diameter. Unfortunately, this proof does not extend to typical distances. These results do show that the diameter is of order log log t. These bounds partially prove predictions by physicists that the typical distance in PA-graphs are similar to the ones in other scale-free random graphs, such as the configuration model and various inhomogeneous random graph models, where typical distances have been shown to be of order log log t when τ∈(2,3), and of order log t when τ>3. [ABSTRACT FROM AUTHOR]

We survey the recent work on phase transition and distances in various random graph models with general degree sequences. We focus on inhomogeneous random graphs, the configuration model, and affine preferential attachment models, and pay special attention to the setting where these random graphs have a power-law degree sequence. This means that the proportion of vertices with degree k in large graphs is approximately proportional to k-τ for some τ>1. Since many real networks have been empirically shown to have power-law degree sequences, these random graphs can be seen as more realistic models for real complex networks than classical random graphs such as the Erdős–Rényi random graph. It is often suggested that the behavior of random graphs should have a large amount of universality, meaning, in this case, that random graphs with similar degree sequences share similar behavior. We survey the available results on graph distances in power-law random graphs that are consistent with this prediction. [ABSTRACT FROM AUTHOR]

We generalize the asymptotic behavior of the graph distance between two uniformly chosen nodes in the configuration model to a wide class of random graphs. Among others, this class contains the Poissonian random graph, the expected degree random graph and the generalized random graph (including the classical Erdős-Rényi graph). In the paper we assign to each node a deterministic capacity and the probability that there exists an edge between a pair of nodes is equal to a function of the product of the capacities of the pair divided by the total capacity of all the nodes. We consider capacities which are such that the degrees of a node have uniformly bounded moments of order strictly larger than two, so that, in particular, the degrees have finite variance. We prove that the graph distance grows like log ν N, where the ν depends on the capacities and N denotes the size of the graph. In addition, the random fluctuations around this asymptotic mean log ν N are shown to be tight. We also consider the case where the capacities are independent copies of a positive random Λ with $\mathbb{P}\left (\Lambda>x\right )\leq cx^{1-\tau}$ , for some constant c and τ>3, again resulting in graphs where the degrees have finite variance. The method of proof of these results is to couple each member of the class to the Poissonian random graph, for which we then give the complete proof by adapting the arguments of van der Hofstad et al. (Random Struct. Algorithms 27(2):76–123, ). [ABSTRACT FROM AUTHOR]

The article presents an elementary proof of the random walk hitting time theorem. This theorem states that a left-continuous random walk on (Z) that start at a nonnegative integer (k) wherein the probability that hits the origin (n) is equal to k/n. It discusses the hitting time theorem which is equivalent to the ballot theorem that dates back to Whitford and Bertrand. It presents equations and solutions to prove these theorems. It also presents minor modification or assumptions in the hitting time theorem.

We study occurrences of patterns on clusters of size n in random fields on ℤ d . We prove that for a given pattern, there is a constant a>0 such that the probability that this pattern occurs at most na times on a cluster of size n is exponentially small. Moreover, for random fields obeying a certain Markov property, we show that the ratio between the numbers of occurrences of two distinct patterns on a cluster is concentrated around a constant value. This leads to an elegant and simple proof of the ratio limit theorem for these random fields, which states that the ratio of the probabilities that the cluster of the origin has sizes n+1 and n converges as n→∞. Implications for the maximal cluster in a finite box are discussed. [ABSTRACT FROM AUTHOR]

Abstract: We derive a lace expansion for the survival probability for critical spread-out oriented percolation above dimensions, i.e., the probability that the origin is connected to the hyperplane at time n, at the critical threshold . Our lace expansion leads to a non-linear recursion relation for , with coefficients that we bound via diagrammatic estimates. This lace expansion is for point-to-plane connections and differs substantially from previous lace expansions for point-to-point connections. In particular, to be able to deduce the asymptotics of for large n, we need to derive the recursion relation up to quadratic order. The present paper is Part II in a series of two papers. In Part I, we use the recursion relation and the diagrammatic estimates to prove that , and also deduce consequences of this asymptotics for the geometry of large critical clusters and for the incipient infinite cluster. [Copyright &y& Elsevier]

We consider critical spread-out oriented percolation above 4 + 1 dimensions. Our main result is that the extinction probability at time n (i.e., the probability for the origin to be connected to the hyperplane at time n but not to the hyperplane at time n + 1) decays like 1/ Bn 2 as $$n\to\infty$$ , where B is a finite positive constant. This in turn implies that the survival probability at time n (i.e., the probability that the origin is connected to the hyperplane at time n) decays like 1/ Bn as $$n\to\infty$$ . The latter has been shown in an earlier paper to have consequences for the geometry of large critical clusters and for the incipient infinite cluster. The present paper is Part I in a series of two papers. In Part II, we derive a lace expansion for the survival probability, adapted so as to deal with point-to-plane connections. This lace expansion leads to a nonlinear recursion relation for the survival probability. In Part I, we use this recursion relation to deduce the asymptotics via induction. [ABSTRACT FROM AUTHOR]

Abstract: We find the asymptotic number of connected graphs with vertices and edges when approach infinity, re-proving a result of Bender, Canfield and McKay. We use the probabilistic method, analyzing breadth-first search on the random graph for an appropriate edge probability . Central is the analysis of a random walk with fixed beginning and end which is tilted to the left. [Copyright &y& Elsevier]

In this correpsondence, we study a lightly loaded code-division multiple-access (CDMA) system with and without multistage hard- and soft-decision parallel interference cancelation (HO-PlC and SD-PlC). Throughout this paper we will only consider the situation of a noiseless channel, equal powers and random spreading codes. For the system with no or a fixed number of steps of interference cancelation, we give a lower bound on the maximum number of users such that the probability for the system to have no bit-errors converges to one. Moreover, we investigate when the matched filter system, where parallel interference cancelation is absent, has bit errors with probability converging to one. This implies that the use of HD-PIC and SD-PlC significantly enhances the number of users the system can serve. [ABSTRACT FROM AUTHOR]

We discuss the long time behaviour of the parabolic Anderson model, the Cauchy problem for the heat equation with random potential on $$\mathbb{Z}^{d}$$ . We consider general i.i.d. potentials and show that exactly four qualitatively different types of intermittent behaviour can occur. These four universality classes depend on the upper tail of the potential distribution: (1) tails at ∞ that are thicker than the double-exponential tails, (2) double-exponential tails at ∞ studied by Gärtner and Molchanov, (3) a new class called almost bounded potentials, and (4) potentials bounded from above studied by Biskup and König. The new class (3), which contains both unbounded and bounded potentials, is studied in both the annealed and the quenched setting. We show that intermittency occurs on unboundedly increasing islands whose diameter is slowly varying in time. The characteristic variational formulas describing the optimal profiles of the potential and of the solution are solved explicitly by parabolas, respectively, Gaussian densities. Our analysis of class (3) relies on two large deviation results for the local times of continuous-time simple random walk. One of these results is proved by Brydges and the first two authors in [BHK04], and is also used here to correct a proof in [BK01]. [ABSTRACT FROM AUTHOR]

We construct a measure valued Markov process which we call infinite canonical super-Brownian motion, and which corresponds to the canonical measure of super-Brownian motion conditioned on non-extinction. Infinite canonical super-Brownian motion is a natural candidate for the scaling limit of various random branching objects on $$\mathbb{Z}^d$$ when these objects are critical, mean-field and infinite. We prove that ICSBM is the scaling limit of the spread-out oriented percolation incipient infinite cluster above 4 dimensions and of incipient infinite branching random walk in any dimension. We conjecture that it also arises as the scaling limit in various other models above the upper-critical dimension, such as the incipient infinite lattice tree above 8 dimensions, the incipient infinite cluster for unoriented percolation above 6 dimensions, uniform spanning trees above 4 dimensions, and invasion percolation above 6 dimensions. [ABSTRACT FROM AUTHOR]

Abstract: Let be a d-dimensional random walk in random scenery, i.e., with a random walk in and an i.i.d. scenery, independent of the walk. We assume that the random variables have a stretched exponential tail. In particular, they do not possess exponential moments. We identify the speed and the rate of the logarithmic decay of for all sequences satisfying a certain lower bound. This complements results of Gantert et al. [Annealed deviations of random walk in random scenery, preprint, 2005], where it was assumed that has exponential moments of all orders. In contrast to the situation (Gantert et al., 2005), the event is not realized by a homogeneous behavior of the walk''s local times and the scenery, but by many visits of the walker to a particular site and a large value of the scenery at that site. This reflects a well-known extreme behavior typical for random variables having no exponential moments. [Copyright &y& Elsevier]

We consider bond percolation on $\{\backslash Bbb\; Z\}^d$ at the critical occupation density pc for d>6 in two different models. The first is the nearest-neighbor model in dimension d≫6. The second model is a “spread-out” model having long range parameterized by L in dimension d>6. In the spread-out case, we show that the cluster of the origin conditioned to contain the site x weakly converges to an infinite cluster as |x|→∞ when d>6 and L is sufficiently large. We also give a general criterion for this convergence to hold, which is satisfied in the case d≫6 in the nearest-neighbor model by work of Hara.(12) We further give a second construction, by taking p{\Bbb Q}^p and taking its limit as p↗p-c. The limiting object is the high-dimensional analogue of Kesten's incipient infinite cluster (IIC) in d=2. We also investigate properties of the IIC such as bounds on the growth rate of the cluster that show its four-dimensional nature. The proofs of both the existence and of the claimed properties of the IIC use the lace expansion. Finally, we give heuristics connecting the incipient infinite cluster to invasion percolation, and use this connection to support the well-known conjecture that for d>6 the probability for invasion percolation to reach a site x is asymptotic to c|x|-(d-4) as |x|→∞. [ABSTRACT FROM AUTHOR]

We study a multiuser detection system for code-division multiple access (CDMA). We show that applying multistage hard-decision parallel interference cancellation (HD-PIC) significantly improves performance compared to the matched filter system. In (multistage) HD-PIC, estimates of the interfering signals are used iteratively to improve knowledge of the desired signal. We use large deviation theory to show that the bit-error probability (REP) is exponentially small when the number of users is fixed and the processing gain increases. We investigate the exponential rate of the REP after several stages of HD-PIC. We propose to use the exponential rate of the REP as a measure of performance, rather than the signal-to-noise ratio (SNR), which is often not reliable in multiuser detection models when the system is lightly loaded. We show that the exponential rate of the REP remains fixed after a finite number of stages, resulting in an optimal hard-decision system. When the number of users becomes large, the exponential rate of the REP converges to (log 2)/2 - 1/4. We provide guidelines for the number of stages necessary to obtain this asymptotic exponential rate. We also give Chemoff bounds on the REPs. These estimates show that the REPs are quite small as long as k = o(m/ log n) when the number of stages of HO-PlC is fixed, and even exponentially small when k = O(n) for the optimal HD-PlC system, and where k is the number of users in the system and n is the processing gain. Finally, we extend the results to the case where the number of stages depends on k in a certain manner. The above results are proved for a noiseless channel, and we argue that we expect similar results in a noisy channel as long as the two-sided spectrum of the noise decreases proportionally to n. [ABSTRACT FROM AUTHOR]

We consider oriented bond percolation on Zd×N, at the critical occupation density pc, for d>4. The model is a “spread-out” model having long range parameterised by L. We consider configurations in which the cluster of the origin survives to time n, and scale space by n1/2. We prove that for L sufficiently large all the moment measures converge, as n→∞, to those of the canonical measure of super-Brownian motion. This extends a previous result of Nguyen and Yang, who proved Gaussian behaviour for the critical two-point function, to all r-point functions (r&ges;2). We use lace expansion methods for the two-point function, and prove convergence of the expansion using a general inductive method that we developed in a previous paper. For the r-point functions with r&ges;3, we use a new expansion method. [Copyright &y& Elsevier]

The lace expansion has been used successfully to study the critical behaviour in high dimensions of self-avoiding walks, lattice trees and lattice animals, and percolation. In each case, the lace expansion has been an expansion along a time interval. In this paper, we introduce the lace expansion on a tree, in which ‘time’ is generalised from an interval to a tree. We develop the expansion in the context of networks of mutually-avoiding self-avoiding walks joined together with the topology of a tree, in dimensions d>4, and prove Gaussian behaviour for sufficiently spread-out networks consisting of long self-avoiding walks. [Copyright &y& Elsevier]

The lace expansion is a powerful tool for analysing the critical behaviour of self-avoiding walks and percolation. It gives rise to a recursion relation which we abstract and study using an adaptation of the inductive method introduced by den Hollander and the authors. We give conditions under which the solution to the recursion relation behaves as a Gaussian, both in Fourier space and in terms of a local central limit theorem. These conditions are shown elsewhere to hold for sufficiently spread-out models of networks of self-avoiding walks in dimensions d > 4, and for sufficiently spread-out models of critical oriented percolation in dimensions d + 1 > 5, providing a unified approach and an essential ingredient for a detailed analysis of the branching behaviour of these models. [ABSTRACT FROM AUTHOR]

We derive approximations for the probability of a bit error for a code division multiple access (CDMA) system with one-stage soft decision parallel interference cancellation. More precisely, we derive the exponential rates, J[SUBk] with cancellation and I[SUBk] without cancellation, of a CDMA system with k users and processing gain equal to n as n →∞. Whereas the rates I[SUBk] follow explicitly from Craméer's theorem, the rates J[SUBk] are given in terms of an optimization problem that can be evaluated numerically. We prove that J[SUBk]>I[SUBk] for k≥3, which shows that interference cancellation is e4ective. For the case without interference cancellation, we investigate the second order (Bahadur-Rao) asymptotics. For the case with interference cancellation, we can obtain second order asymptotics only for k = 3. Together the limits provide excellent approximations for the probability of a bit error in a wide range of interest. [ABSTRACT FROM AUTHOR]

Abstract. We prove ballistic behaviour in dimension one for a model of weakly self-avoiding walks where loops of length m are penalized by a factor e[sup -beta/m[sup p]] with p is an element of [0, 1] and beta sufficiently large. Furthermore, we prove that the fluctuations around the linear drift satisfy a central limit theorem. The proof uses a variant of the lace expansion, together with an inductive analysis of the arising recursion relation. In particular, we derive the law of large numbers, first obtained by Greven and den Hollander, and the central limit theorem, first obtained by Konig, for the weakly self-avoiding walk (p = 0 and beta > 0). Their proofs use large deviation theory for the Markov description of the local times of one-dimensional simple random walk. It is the first time that the lace expansion is used to prove behaviour that is not diffusive. It has previously been used by van der Hofstad, den Hollander and Slade to prove diffusive behaviour in dimension d for p is greater than or equal to 0 such that p > 4-d/2 and beta > 0 sufficiently small. The lace expansion presented here compares the above weakly self-avoiding walk to strictly self-avoiding walk in dimension one, obtained when beta = Infinity, and shows that the difference in behaviour is small when beta is large. [ABSTRACT FROM AUTHOR]

Several studies predicting Functional Connectivity (FC) from Structural Connectivity (SC) at individual level have been published in recent years, each promising increased performance and utility. We investigated three of these studies, analyzing whether the results truly represent a meaningful individual-level mapping from SC to FC. Using data from the Human Connectome Project shared accross the three studies, we constructed a predictor by averaging FC of training data and analyzed its performance in the same way. In each case, we found that group average FC is an equivalent or better predictor of individual FC than the predictive models in terms of raw prediction performance. Furthermore, we showed that additional analyses performed by the authors of the three studies, in which they attempt to show that their predicted FC has value beyond raw prediction performance, could also be reproduced using the group average FC predictor. This makes it unclear whether any of the three methods represent a meaningful individual-level predictive model. We conclude that either the methods are not appropriate for the data, that the sample size is too small, or that the data does not contain sufficient information to learn a mapping from SC to FC. We advise future individual-level studies to explicitly report results in comparison to the performance of the group average, and carefully demonstrate that their predictions contain meaningful individual-level information. Finally, we believe that investigating alternatives for the construction of SC and FC may improve the chances of developing a meaningful individual-level mapping from SC to FC. [ABSTRACT FROM AUTHOR]

Summary. We introduce a new inductive approach to the lace expansion, and apply it to prove Gaussian behaviour for the weakly self-avoiding walk on Z[sup d] where loops of length m are penalised by a factor e[sup -beta/m[sup p]] (0 < beta much less than 1) when: (1) d > 4, p is greater than or equal to 0; (2) d less than or equal to 4, p > 4 - d/2. In particular, we derive results first obtained by Brydges and Spencer (and revisited by other authors) for the case d > 4, p = 0. In addition, we prove a local central limit theorem, with the exception of the case d > 4, p = 0. [ABSTRACT FROM AUTHOR]

Real-world networks often have power-law degrees and scale-free properties, such as ultrasmall distances and ultrafast information spreading. In this paper, we study a third universal property: three-point correlations that suppress the creation of triangles and signal the presence of hierarchy. We quantify this property in terms of c(k), the probability that two neighbors of a degree-k node are neighbors themselves. We investigate how the clustering spectrum k ↦ c(k) scales with k in the hidden-variable model and show that c(k) follows a universal curve that consists of three k ranges where c(k) remains flat, starts declining, and eventually settles on a power-law c(k) ~ k-α with α depending on the power law of the degree distribution. We test these results against ten contemporary real-world networks and explain analytically why the universal curve properties only reveal themselves in large networks. [ABSTRACT FROM AUTHOR]

We study the random geometry of first passage percolation on the complete graph equipped with independent and identically distributed positive edge weights. We consider the case where the lower extreme values of the edge weights are highly separated. This model exhibits strong disorder and a crossover between local and global scales. Local neighborhoods are related to invasion percolation that display self-organised criticality. Globally, the edges with relevant edge weights form a barely supercritical Erdős–Rényi random graph that can be described by branching processes. This near-critical behaviour gives rise to optimal paths that are considerably longer than logarithmic in the number of vertices, interpolating between random graph and minimal spanning tree path lengths. Crucial to our approach is the quantification of the extreme-value behavior of small edge weights in terms of a sequence of parameters (s n) n ≥ 1 that characterises the different universality classes for first passage percolation on the complete graph. We investigate the case where s n → ∞ with s n = o (n 1 / 3) , which corresponds to the barely supercritical setting. We identify the scaling limit of the weight of the optimal path between two vertices, and we prove that the number of edges in this path obeys a central limit theorem with mean approximately s n log (n / s n 3) and variance s n 2 log (n / s n 3) . Remarkably, our proof also applies to n-dependent edge weights of the form E s n , where E is an exponential random variable with mean 1, thus settling a conjecture of Bhamidi et al. (Weak disorder asymptotics in the stochastic meanfield model of distance. Ann Appl Probab 22(1):29–69, 2012). The proof relies on a decomposition of the smallest-weight tree into an initial part following invasion percolation dynamics, and a main part following branching process dynamics. The initial part has been studied in Eckhoff et al. (Long paths in first passage percolation on the complete graph I. Local PWIT dynamics. Electron. J. Probab. 25:1–45, 2020. 10.1214/20-EJP484); the current paper focuses on the global branching dynamics. [ABSTRACT FROM AUTHOR]

We investigate the presence of triangles in a class of correlated random graphs in which hidden variables determine the pairwise connections between vertices. The class rules out self-loops and multiple edges. We focus on the regime where the hidden variables follow a power law with exponent τ∈(2,3), so that the degrees have infinite variance. The natural cutoff hc characterizes the largest degrees in the hidden variable models, and a structural cutoff hs introduces negative degree correlations (disassortative mixing) due to the infinite-variance degrees. We show that local clustering decreases with the hidden variable (or degree). We also determine how the average clustering coefficient C scales with the network size N, as a function of hs and hc. For scale-free networks with exponent 2 <τ<3 and the default choices hs~N1/2 and hc~N1/(τ-1) this gives C~N2-τlnN for the universality class at hand. We characterize the extremely slow decay of C when τ≈2 and show that for τ=2.1, say, clustering starts to vanish only for networks as large as N=109. [ABSTRACT FROM AUTHOR]

Most random graph models are locally tree-like--do not contain short cycles--rendering them unfit for modeling networks with a community structure. We introduce the hierarchical configuration model (HCM), a generalization of the configuration model that includes community structures, while properties such as the size of the giant component, and the size of the giant percolating cluster under bond percolation can still be derived analytically. Viewing real-world networks as realizations of HCM, we observe two previously undiscovered power-law relations: between the number of edges inside a community and the community sizes, and between the number of edges going out of a community and the community sizes. We also relate the power-law exponent τ of the degree distribution with the power-law exponent of the community-size distribution γ. In the case of extremely dense communities (e.g., complete graphs), this relation takes the simple form τ=γ−1. [ABSTRACT FROM AUTHOR]