Correction to: Probability Theory and Related Fieldshttps://doi.org/10.1007/s00440-025-01417-1. The received and accepted dates are incorrect due to an error from the publisher and should be disregarded. The original article has been corrected.

In this paper we study degree-penalized contact processes on Galton-Watson (GW) trees and the configuration model. The model we consider is a modification of the usual contact process on a graph. In particular, each vertex can be either infected or healthy. When infected, each vertex heals at rate one. Also, when infected, a vertex u with degree du infects its neighboring vertex v with degree d _v with rate λ/ f (d _u, d _v ) for some positive function f. In the case F (d _u, d _v = max(d _u, d _v ) ^u for some u ≥ 0, the infection is slowed down to and from high-degree vertices. This is in line with arguments used in social network science: people with many contacts do not have the time to infect their neighbors at the same rate as people with fewer contacts. We show that new phase transitions occur in terms of the parameter u (at 1/2) and the degree distribution D of the GW tree. ◦ When u ≥ 1, the process goes extinct for all distributions D for all sufficiently small λ > 0; ◦ When u E [1/2, 1), and the tail of D weakly follows a power law with tail-exponent less than 1 − u, the process survives globally but not locally for all λ small enough; ◦ When u E [1/2, 1), and E[D ^1−u] < ∞, the process goes extinct almost surely, for all λ small enough; ◦ When u < 1/2, and D is heavier than stretched exponential with stretch-exponent 1 − 2u, the process survives (locally) with positive probability for all λ > 0. We also study the product case, where f (d _u, d _v ) = (d _ud _v ) ^u. In that case, the situation for u < 1/2 is the same as the one described above, but u ≥ 1/2 always leads to a subcritical contact process for small enough λ > 0 on all graphs. Furthermore, for finite random graphs with prescribed degree sequences, we establish the corresponding phase transitions in terms of the length of survival.

We consider a large class of spatially-embedded random graphs that includes among others long-range percolation, continuum scale-free percolation and the age-dependent random connection model. We assume that the model is supercritical: there is an infinite component. We identify the stretch-exponent ζ ∈ (0, 1) of the decay of the cluster-size distribution. That is, with (Formula presented) denoting the number of vertices in the component of the vertex at (Formula presented), we prove (Formula presented) The value of ζ undergoes several phase transitions with respect to three main model parameters: the Euclidean dimension d, the power-law tail exponent τ of the degree distribution and a long-range parameter α governing the presence of long edges in Euclidean space. In this paper we present the proof for the region in the phase diagram where the model is a generalization of continuum scale-free percolation and/or hyperbolic random graphs: ζ in this regime depends both on τ, α. We also prove that the second-largest component in a box of volume n is of size (Formula presented) with high probability. We develop a deterministic algorithm, the cover expansion, as new methodology. This algorithm enables us to prevent too large components that may be de-localized or locally dense in space.

We study cluster sizes in supercritical d-dimensional inhomogeneous percolation models with long-range edges —such as long-range percolation— and/or heavy-tailed degree distributions —such as geometric inhomogeneous random graphs and the age-dependent random connection model. Our focus is on large deviations of the size of the largest cluster in the graph restricted to a finite box as its volume tends to infinity. Compared to nearest neighbor Bernoulli bond percolation on Zd, we show that long edges can increase the exponent of the polynomial speed of the lower tail from (d-1)/d to any ζ⋆∈((d-1)/d,1). We prove that this exponent ζ⋆ also governs the size of the second-largest cluster, and the distribution of the size of the cluster containing the origin C(0). For the upper tail of large deviations, we prove that its speed is logarithmic for models with power-law degree distributions. We express the rate function via the generating function of |C(0)|. The upper tail in degree-homogeneous models decays much faster: the speed in long-range percolation is linear.

We study the cluster-size distribution of supercritical long-range percolation on Z^d, where two vertices x, y ϵ Z^d are connected by an edge with probability p(‖x − y‖):= p min(1, β‖x − y‖)^−dα for parameters p ϵ (0, 1], α > 1, and β > 0. We show that when α > 1 + 1/d, and either β or p is sufficiently large, the probability that the origin is in a finite cluster of size at least k decays as exp( − Θ(k^(d−1)/d)). This corresponds to classical results for nearest-neighbor Bernoulli percolation on Z^d, but is in contrast to long-range percolation with α < 1 + 1/d, when the exponent of the stretched exponential decay changes to 2 − α. This result, together with our accompanying paper, establishes the phase diagram of long-range percolation with respect to cluster-size decay. Our proofs rely on combinatorial methods that show that large delocalized components are unlikely to occur. As a side result we determine the asymptotic growth of the second-largest connected component when the graph is restricted to a finite box.

A k-truncated resolving set of a graph is a subset S⊆V of its vertex set such that the vector (d_k(s,v))_s∈S is distinct for each vertex v∈V where d_k(x,y)=min⁡{d(x,y),k+1} is the graph distance truncated at k+1. We think of elements of a k-truncated resolving set as sensors that can measure up to distance k. The k-truncated metric dimension (Tmd_k) of a graph G is the minimum cardinality of a k-truncated resolving set of G. We give a sharp lower bound on Tmd_k for any tree T in terms of its number of vertices |T| and the measuring radius k. Our result is that Tmd_k(T)≥|T|⋅3/(k²+4k+3+1{k≡1(mod3)})+c_k, disproving earlier conjectures by Frongillo et al. that suspected |T|/(⌊k²/4⌋+2k)+c_k^′ as general lower bound, where c_k, c_k^′ are k-dependent constants. We provide a construction for trees with the largest number of vertices with a given Tmd_k value. The proof that our optimal construction cannot be improved relies on edge-rewiring procedures of arbitrary (suboptimal) trees with arbitrary resolving sets, which reveal the structure of how small subsets of sensors measure and resolve certain areas in the tree that we call the attraction of those sensors. The notion of ‘attraction of sensors’ might be useful in other contexts beyond trees to solve related problems. We also provide an improved lower bound on Tmd_k of arbitrary trees that takes into account the structural properties of the tree, in particular, the number and length of simple paths of degree-two vertices terminating in leaf vertices. This bound complements the result of the above-mentioned work of Frongillo et al., where only trees without degree-two vertices were considered, except the simple case of a single path.

We study the evolution of the graph distance and weighted distance between two fixed vertices in dynamically growing random graph models. More precisely, we consider preferential attachment models with powerlaw exponent τ ϵ (2, 3), sample two vertices ut , vt uniformly at random when the graph has t vertices and study the evolution of the graph distance between these two fixed vertices as the surrounding graph grows. This yields a discrete-time stochastic process in t ' ≥ t , called the distance evolution. We show that there is a tight strip around the function 4 log log(t)-log(log(t'/t)ν1) | log(τ-2)| ν 2 that the distance evolution never leaves with high probability as t tends to infinity. We extend our results to weighted distances, where every edge is equipped with an i.i.d. copy of a nonnegative random variable L.

The “random intersection graph with communities” (RIGC) models networks with communities, assuming an underlying bipartite structure of groups and individuals. Each group has its own internal structure described by a (small) graph, while groups may overlap. The group memberships are generated by a bipartite configuration model. The model generalizes the classical random intersection graph model, a special case where each community is a complete graph. The RIGC model is analytically tractable. We prove a phase transition in the size of the largest connected component in terms of the model parameters. We prove that percolation on RIGC produces a graph within the RIGC family, also undergoing a phase transition with respect to size of the largest component. Our proofs rely on the connection to the bipartite configuration model. Our related results on the bipartite configuration model are of independent interest, since they shed light on interesting differences from the unipartite case.

Random intersection graphs model networks with communities, assuming an underlying bipartite structure of communities and individuals, where these communities may overlap. We generalize the model, allowing for arbitrary community structures within the communities. In our new model, communities may overlap, and they have their own internal structure described by arbitrary finite community graphs. Our model turns out to be tractable. We analyze the overlapping structure of the communities, show local weak convergence (including convergence of subgraph counts), and derive the asymptotic degree distribution and the local clustering coefficient.