key: cord-0036391-gz1uln2r
authors: Abdullah, Mohammed; Cooper, Colin; Draief, Moez
title: Viral Processes by Random Walks on Random Regular Graphs
date: 2011
journal: Approximation, Randomization, and Combinatorial Optimization
DOI: 10.1007/978-3-642-22935-0_30
sha: 3dd35457abd539e4b629874e6b1fa12613f8982a
doc_id: 36391
cord_uid: gz1uln2r

We study the SIR epidemic model with infections carried by k particles making independent random walks on a random regular graph. We give a edge-weighted graph reduction of the dynamics of the process that allows us to apply standard results of Erdős–Renyi random graphs on the particle set. In particular, we show how the parameters of the model produce two phase transitions: In the subcritical regime, O(ln k) particles are infected. In the supercritical regime, for a constant C determined by the parameters of the model, Ck get infected with probability C, and O(ln k) get infected with probability (1 − C). Finally, there is a regime in which all k particles are infected. Furthermore, the edge weights give information about when a particle becomes infected. We demonstrate how this can be exploited to determine the completion time of the process by applying a result of Janson on randomly edge weighted graphs.

The spread of an infection throughout a population, often referred to loosely as an epidemic, has come to be modelled in various ways in the literature, spurred by the richness of the domains in which the abstract notion of a virus has gone beyond the traditional biological phenomenon. Electronic viruses over computer networks are not the only extension, others include rumour spreading [20] or broadcasting [3] and viral marketing [13, ch. 9 ]. Models may vary over domains, but the underlying principle is one of spread of some unit of information or change of state through interaction between individuals.

In much of the literature on the spread of epidemics as well as the dissemination of information, individuals reside at fixed locations connected by a graph and the evolution of the state of an individual depends on the state of its neighbours in the graph. In particular if the graph is complete, mean-field (homogeneous mixing) models have been exploited to study the outcome of the diffusion process [9] . More recently, there has been an increasing interest in understanding the impact of the network topology on the spread of epidemics in networks with fixed nodes, see [13] for a review of such results. There has however been little analytical work to date on models where the possible interactions between the nodes are dynamic, i.e., evolves in time.

We explore a particular instance of dynamicity in interaction by assuming that individuals are mobile particles and can only infect each other if they are in sufficiently close proximity. The model is motivated both by certain kinds of biological epidemics, whose transmission may be dominated by sites at which individuals gather in close proximity (e.g., workplaces or public transport for a disease like SARS, cattle markets for foot-and-mouth disease, etc.) and by malware. Furthermore, it is relevant to studying the dissemination of information in opportunistic networks [5] where the information is transmitted between users who happen to be in each others range. As in the case of static networks [20] one may be interested in the time it takes for the rumour to be known to all users.

In our model (elaborated upon below) the virus can be carried by k particles making independent random walks on an n-vertex r-regular random graph G which represents the environment. Each particle is in one of three states: susceptible (S), infected (I), recovered (R). An infected particle can infect a susceptible particle, which remains infected for a fixed infectious period ξ before recovering permanently. This is a known as the SIR epidemic model and is extensively studied in the literature. When ξ = ∞ (the SI model ) particles never go from I to R. Two questions can be asked: (1) When ξ < ∞, how many particles ever get infected? (2) How long does the process take to complete? We address both of these questions by reducing the dynamics of the process to what we term an interaction graph. This is an Erdős-Renyi (E-R) random graph G k,q on the set of particles, where the edge probabilityq is a function of the parameters of the model. Infected particles are connected components in G k,q , and so well known results from the literature on E-R random graphs can be directly applied using our reduction to answer question (1) . In particular, we show how the parameters of the model produce two phase transitions: In the subcritical regime, O(ln k) particles are infected. In the supercritical regime, for a constant C determined by the parameters of the model, Ck get infected with probability C, and O(ln k) get infected with probability (1 − C). Finally, there is a regime in which all k particles are infected. Statements are with high probability (whp), that is, with probability tending to 1 as n → ∞. Furthermore, the graph reduction assigns weights on the edges that give information about when a particle becomes infected. This information can be used for addressing question (2) . As an example, in the case of ξ = ∞, we apply a result of Janson [16] on randomly-weighted graphs to deduce that completion time converges in probability to 2θrn k ln k, where θ r = r−1 r−2 . This matches the expectation determined in [8] for the same example.

Whilst the metaphor of an epidemic is a motivating and illustrative one, this work is part of the more general scope of interacting particle systems (see, e.g., [2, ch. 14] ).

Note, due to space restrictions, we refer to [1] for a more detailed exposition and proofs of lemmas and theorems not presented in this paper.

Let r ≥ 3 be fixed. Let G r denote the set of r-regular graphs with vertex set V = {1, 2, . . . , n} and the uniform measure. Let G = (V G , E G ) be chosen uniformly at random (uar) from G r . The results in this paper are always asymptotic in n = |V G |. The notation A n ∼ B n means that lim n→∞ A n /B n = 1.

At step t, let S(t), I(t), R(t) be the set of susceptible, infected and recovered particles respectively. These form a partition of the particle set P. Thus, |P| = k.

When two particles x and y meet at some vertex v at time step t, an interaction takes place between them at that time step with probability ρ ∈ (0, 1], which is a fixed constant parameter of the model. We term such an event an xy interaction and call ρ the interaction probability. If one of the particles is infected and the other is susceptible, the infection takes place upon interaction. We define the completion time of the process to be the time step at which the last infection takes place. Consider that the counter has just changed from time step t − 1 to t. The sequence of actions is as follows: (i)Every particle makes an independent move in its random walk. (ii)A particle x ∈ I(t − 1) that had reached the end of its infectious period by time t changes from state I to state R, so x / ∈ I(t) and x ∈ R(t). Otherwise, it remains in state I, i.e., x ∈ I(t). (iii)Each pair of particles x, y at the same vertex v interact with probability ρ; the particle-pair interactions are independent of each other. If one of x or y is in I(t), and the other was in S(t − 1), the latter becomes infected, and it becomes a member of I(t). New infections are considered to have started at time t; we say a particle is infected at step t, and step t counts as one unit in the infectious period. (iv) The counter changes from t to t + 1, and the sequence is repeated.

A note on notation and terminology: When we refer to a 'period' [t 1 , t 2 ], we mean the set of time steps {t 1 , t 1 + 1, t 1 + 2 . . . , t 2 }. When we refer to "time t" we are referring to step t on the counter -this is a discrete time process. The first time step is t = 1, and t = 0 is not a time step, just a useful convention to express the state of the system before the first time step.

Observe the pair-wise independence of the interactions: If x, y, z meet at a vertex v at time step t, there is an interaction between each pair ({xy, yz, xz}) with probability ρ, independently of the other interactions. From the sequence of actions, it can be seen that it is also the case that an infection is not transitive in a single time step. For example, say they meet at the same vertex at time step t, x is infected but y and z are not. If x interacts with y but not z, then y does not pass on the infection to z at that time step, even if they interact at that time step. Let M k be the total number of particles that ever get infected in the course of the process, and let T k be the completion time.

Theorem 1. Suppose ρ = 1 and k → ∞ as n → ∞. Define

all the particles get infected).

Theorem 1 is for finite ξ, but observe that taking the convention that x ∞ = 0 for |x| < 1 means that part (iii) is consistent with the SI model, for which all particles get infected almost surely. The theorem effectively gives conditions for transitions between different possible "regimes" of behaviour. The most interesting is the regime of part (ii), which is entered as φ transitions from φ < 1 to φ > 1. When I 0 = 1, roughly speaking, in this transition the number of infected particles goes from very few (O(ln k)) whp, to a constant fraction Ck with probability C, or O(ln k) with probability 1 − C. Hence, it's "all or nothing", with a constant probability C of being "all".

k . This is unsurprising since it can be seen from the tools we use in our analysis that the hitting time of one particle to any of the k others is distributed approximately Geom( k θrn ), and hence has expected value θrn k . Concerning the completion times, we will demonstrate in Sect. 7.2 that for ξ = ∞, (that is, the SI model) and ρ = 1, how the edge weightings can be exploited by a fairly straightforward application of a theorem of [16] to get

where T k is the completion time for k particles. This is not a new result since it is implied by the matching expectation result from [8] , however, our weighting sheme generalises to ρ < 1 and/or ξ < ∞ and in principle can be exploited in the same manner. In fact, for ξ = ∞, ρ < 1 we claim that (2) holds as T k ln k/k p − → 2 θrn ψ . For ρ < 1, we claim that Theorem 1 holds when the term 1

See [1] .

In this section, we briefly describe some of the relevant related work on diffusion processes like epidemic spreading and the dissemination of information in mobile environments.

There has been a growing body of work in the interacting particle systems community analysing epidemic models with mobile particles. In [10] the authors provide a review of the results, techniques and conjectures when the graph is an infinite lattice. In [21] , the authors explore by means of mean-field approximations the evolution of the number of infected individuals when individuals perform random motions on the plane. Recent papers by Peres et al [19] and Pettarin et al [22] both analyse mobile networks modeled as multiple random walks; the former as Brownian motion on R d and the latter as walks on the grid. In each case, there is a parameter r within which distance a pair of walks can communicate, producing a communication graph (which is disconnected below a certain threshold r c ). [19] studies various aspects of the communication graph, such as how long it takes a particular point to become part of the giant component. [22] studies the broadcast time T B of a piece of information and originating in one agent in relation to r. Setting r = 0 means information is passed only when particles are coincident. In this case, T B is equivalent to our completion time and [22] give T B =Θ(n/ √ k). Of closer relevance to this work are [12] and [11] . Both of these papers study infections carried by random walks on graphs. In particular [11] analyses an SI model similar to ours; multiple random walks on a graph G that carry a virus, and the quantity of interest is the completion time. They give a general upper bound E[T k ] = O(m * ln k) for any graph G, where m * is the expected meeting time of a pair of random walks maximised over all pairs of starting vertices. Special cases are analysed too, in particular, they give an upperbound of E[T k ] = O( nr k ln k ln n) for random r-regular graphs. This is a factor ln n larger than the precise value of the process considered in this paper.

Finally, we mention [3] , which studies flooding on dynamic random networks. A fixed set of n vertices is part of a dynamic random graph process where each edge is an independent two-state Markov chain, either existing or not existing. A single initial vertex initially holds a message and any vertex which receives this message broadcasts it on existing edges for the next k steps. Although flooding is a different process to multiple random walks, the authors develop a reduction to a weighted random graph with some similarity to the interaction graphs we present. It allows them to derive relations between the edge-Markov probabilities and state asymptotic bounds on the number of vertices that receive the message, as well as the broadcast (equivalently, completion) time.

If each particle is distance at least ω(k, n) ≡ Ω(ln ln n + ln k) from every other then we say the particles are in general position (g.p.). We assume the following: A typical graph (formally defined in the appendix) is one that has a number of specific properties. It is connected and non-bipartite, which implies that a random walk will converge to a stationary distribution π on the vertex set. Because the graph is regular, π will be the uniform distribution. A typical graph also has good expansion properties, meaning that a random walk will converge quickly to the stationary distribution; it will be rapidly mixing. In fact, for all the graph we consider, O(k ln n) steps is sufficient for our results. A typical graph also has most of its vertices treelike. A vertex v is treelike if there is no cycle in the subgraph G[v, L 1 ] induced by the set of vertices within distance L 1 = 1 log r n of v, where 1 > 0 is a sufficiently small constant. The near-uniformity and treelike structure throughout the graph allows us to make precise calculations for the behaviour of a random walk from a treelike vertex within the period of the mixing time. This helps us separete the analysis of the period within the mixing time from the period after it. The rapid mixing means that the dynamics of the process is dominated by the long-term behaviour very quickly, and that essentially, short-term behaviour is restricted to groups of local interactions that don't interfere with each other. This provides a degree of homogeneity to the process.

Assumptions (ii) and (iii) are not unreasonable: G is typical whp (Lemma 10 in appendix), and it is straightforward to verify that if the positions of each of the k particles are chosen uar from the vertices of G, then whp they will be in g.p. with respect to each other if is small enough. We will require additional assumptions beyond those stated in this section and previous ones, and they will be shown to hold whp too. Assumption (iv) implies |S(0)| = k − I 0 .

The analysis of multiple random walks can be reduced to a single random walk, in a way we informally describe here based on techniques developed in [8] and extended in [1] . We refer to the latter for details and rigorous justification for this section.

We We can calculate the times for a pair of particles (or one particle and a set of others, or any pair from a set of pairs, or whatever) to meet by calculating the time for the single random walk W H u (t) to visit the relevant set of vertices S ⊆ V H . This is turn is done by the contraction described above, and calculating the time for the walk W Γ u (t) on Γ to visit γ(S). These two times asymptotically equal.

The dynamics of the system, is as follows. The random walks have a mixing time T = O(k ln n), and the distribution of a particle at some timet ≥ T is almost the stationary distribution. In this case, because the graph is regular, the stationary distribution is uniform across the vertices of G.

Consider a set A of particle pairs. For a particle pair (x, y) ∈ A, let B (x,y) (t) be the event {no pair in A meet in the period [T, t−1] and x and y meet at time t}. Note, (x, y) is unordered. Subject to some restrictions (which are satisfied by the type of interactions relevant to this paper), it is established in [1] that

where

During the mixing time, we cannot be precise in general. However, if the particles begin in general position with respect to each other then whp, the particles don't meet in the mixing time. This is a consequence of Lemma 5. We say a visit to vertex v, or a particle-pair meeting is T -distinct if it occurs at least T steps after a previous T -distinct visit/meeting, or the start of the walk. As suggested by the above, we can view the dynamics within the mixing time separately to the dynamics after the mixing time, up until the visit to a vertex or a particle-pair meeting.

In this section, we discuss how the system behaves when k = 2. Let s and x be the two particles, with s being the initial infective. Suppose that the assumptions stated above hold. We allow ξ < ∞ and/or ρ < 1. The former conditions means that x may never get infected, the latter condition means that it may take more than one meeting between s and x before an interaction takes place. Note, that if s and x were at the same vertex at time t, and happen to move to the same neighbouring vertex in the next step, then this counts as another meeting.

By (4) 

The RHS of (6) is the probability of a Geom(p) random variable taking value t. Now, suppose s and x have just stepped to the same vertex v. With probability ρ there will be an interaction. After this, they will move again, either to the same neighbour of v with probability 1/r or to different neighbours with probability (r − 1)/r. Let φ = Pr(No sx interaction before they move apart)

The following lemma is from [8] : G be a typical r-regular graph, and let v be a vertex Using this lemma, let φ T = Pr(No sx interaction before being apart more than T time steps) (9)

Now, assuming s and x start at the same vertex, Pr(sx interaction occurs within T time steps) (11) ∼ Pr(sx interaction occurs before s and x have been apart more than T steps)(12)

Recall ψ was defined in (3), and observe that ρ ≤ ψ ≤ 1 with ψ = 1 iff ρ = 1. Clearly, the number of T -distinct meetings in [0, t] is at most t/T . Subject to slightly more stringent restrictions, it can be shown (see [1] ) that we have

i.e., it is approximately distributed Bin(t, p) . The probability that there are no interactions in any of the i intervals [t j , t j + T ] where t j is the time of the j'th T -distinct meeting is (1 − ψ) i . Thus

Hence,

When ρ = ψ = 1, (15) looks similar to the bracketed terms in (1). This is, of course, not a coincidence since the bracketed term in (1) is essentially the probability that an infection is passed between a pair of particles if one of them had been infected, and therefore, φ is effectively the expected number of other particles that are infected by a particular particle.

We remind the reader that proofs of lemmas and theorems not present in what follows are given in [1] . We can study the SI model (the case ξ = ∞) by analysing the edge weights of the interaction graph Υ = (V Υ , E Υ ). This is a complete graph on the particle set P, thus V Υ = P and E Υ = {(x, y) : x, y ∈ P, x = y}. For a particle x, let t(x) be the time at which x got infected, or ∞ if it never gets infected. For an interaction edge e = (x, y) ∈ E Υ , let t(e) = min{t(x), t(y)}. Then the weight w Υ (e) of the edge is a random variable defined as w Υ (e) = min{t − t(e) : t > t(e) and there was an xy interaction at step t}.

If the other particle was susceptible at the time of interaction, it becomes infected at the point of interaction. Υ , therefore, is a space of randomly-weighted complete graphs, and the distribution on Υ is the joint distribution of the edge weight random variables w Υ (e). A member Z of this space -an instance of Υ -is a specific set of values for each random variable w Υ (e). We may write Z Υ ∈ Υ to denote a particular instance drawn from the space Υ with probability Pr(Z Υ ).

We claim that the joint distribution of edge weights, is well approximated by the joint distribution of random edge weights of another complete graph on P, Λ = (V Λ , E Λ ). The weight w Λ (e) of each edge e ∈ E Λ is an independent random variable with distribution Geom(q), where q = ψ θr n . Labelling the edges in Λ as e i with 1 ≤ i ≤ k 2 , observe

Observe that with probability one, neither graph has an edge of infinite weight.

In what follows we give a proof of the following theorem for the special case in which ρ = 1 (implying ψ = 1). We claim that it holds when ρ < 1 as well.

where F ∈ {Υ, Λ}. Then

Edge weightings in the interaction graph are pair-wise independent by virtue of the independence of the random walks. However there is a correlation when more than two edges are considered. For example, if particles x and y interacted at some time t and x and z interacted at some time close to t, then y and z are more likely to have interacted at some time close to t.

We 

Let A 0 be the set of active edges at time τ 0 = 0. For example, in the case

for some R, denote the times at which the set of active edges changes. Let A i be the set of edges active in the period [τ i , τ i+1 − 1]. We call the τ i 's epochs. A particular edge e i = (x, y) will become active at some epoch τ = d Υ (e i ) and remain so until τ − 1 (inclusive), where τ = d Υ (e i ) + z i is some epoch after τ . Its period of activation may, therefore, cross a number of epochs, in which case it will be a member of a number of edge sets A j .

We analyse each period [τ j + 1, τ j+1 ] individually through application of (4). In the product graph H, we identify the set of vertices S(A j ) ⊆ V H such that v ∈ S(A j ) iff for some (x, y) ∈ A j v represents x and y being at the same vertex in G. Thus, if v = (v 1 , v 2 , . . . , v k ), then v r = v s where r and s are the vector indices for x and y respectively. Since each pair is not to interact in the period [τ j + 1, τ j+1 − 1], and since we assume ρ = 1, the walk W on H must avoid the set S(A j ) until τ j+1 − 1 (inclusive). Then, at τ j+1 it must visit S j ⊆ S(A j ). v ∈ S j iff it represents any of the (x, y) ∈ A j that interact at time τ j+1 being at the same vertex in G. We deal with (non-)visits to S(A j ) and S j by applying (4) to their contractions γ(S(A j )) and γ(S j ).

W do not prove (19) for all possible Z Υ , only those that are termed good. Let T = O(k ln n) be a mixing time and let L = T 3 , and let = 2(T + L).

Call Z Υ good if it satisfies these criteria: (a) k 3 ln n ( k 2 ) i=1 z i = o(n 2 ) (b) None of the k 2 interactions that form the edges of Υ take place within steps of each other.

We shall assume the Z Υ that is drawn is good. Note part (b) implies R = k 2 and so we only need to consider cases of Z Υ where, for each j, S j is a single particle pair. It also implies that during the period [τ j + 1, τ j + ], we do not need to account for interactions. The following lemma applies (4) sequentially for each period [τ j + 1, τ j+1 ]. By the Markov property, we can multiply the probabilities for each period. Theorem 3 follows from this.

In (21) we have included correction factors which we left out in (4) for clarity.

In [8] an expectation of 2θr n k ln k was determined for the completion time of a broadcasting model on k particles that is equivalent to the SI model with I 0 = 1 and ρ = 1. We apply a theorem from [16] to get a convergence in probability to the same value. Assign each edge (i, j) of a complete graph on n vertices a random weight Y ij . The weights are assumed to be independent and identically distributed, non-negative and satisfying Pr(Y ij ≤ t) = t + o(t) as t → 0. Let X ij be the minimal total weight of a path between a given pair of vertices i, j. The theorem states max j≤n Xij ln n/n p − → 2. By scaling, we can apply the result to an exponential analogue of the edge probabilities of Λ, and show that the distribution is well approximated, thereby giving (2) . See [1] for details.

To analyse the SIR model, we build an interaction graph but we modify the process by considering two phases. Phase 1 assigns edge weights as before: an edge e = (x, y) is weighted by the time it takes for an xy interaction after one of them has become infected. It is possible, of course, that neither ever get infected when ξ is finite, in which case the edge (x, y) does not become active (and is not given a weight) in this phase. Phase 1 ends at τ end when there are no more active edges. At this point, there remains a set of susceptible particles S(τ end ) that were never infected in phase 1. Phase 2 begins with an arbitrary z ∈ S(τ end ) being given a pseudo-infection with an infinite infectious period, and we proceed with an SI process on the particle set S(τ end ), giving them edge weights, as per the normal SI process. A pseudo-infection is the same process as an infection but we do not count pseudo-infected particles as infected; only particles infected in phase 1 are counted as infect. Phase 2 exists to maintain the same probability space as in the SI model.

Call the resulting (complete) graph Ψ . We remove an edge e in Ψ if w Ψ (e) > ξ and call the resulting graph Ψ .

Let C(x) be the component of Ψ containing a particle x. LetD Ψ (x, y) be the weighted distance between particles x and y if y ∈ C(x), otherwise let D Ψ (x, y) = ∞. Let d Ψ (y) = min{D Ψ (x, y) : x ∈ I(0)}. Theorem 7. In Ψ , (i) A particle y is infected if and only if y ∈ C(x) for some initial infective x ∈ I(0), (ii) If a particle y gets infected, the infection time is t(y) = d Ψ (y).

We show that Theorem 3 holds for Ψ . Let Λ and Z F for some graph space F be as before.

Pr(Z Ψ ) = (1 + o(1))Pr(Z Λ ).

As with Ψ , Ψ is a space of weighted graphs. Furthermore, we can define an equivalence relation ∼ on Ψ such that for Y, Z ∈ Ψ , we have Y ∼ Z iff E(Y ) = E(Z), that is, they have the same edge set. Let Ψ /∼ be the graph space induced by Ψ and the equivalence relation ∼. Thus, the probability a graph G is drawn from Ψ /∼ , that is, Pr(G ∈ Ψ /∼ ) = Pr(some Z is drawn from Ψ such that E(Z) = E(G)). We show Ψ /∼ is approximated by G k,q , the space of Erdős-Renyi random graphs with edge probabilitŷ q = 1 − (1 − q) ξ , where q = ψ θrn for the special case ρ = ψ = 1. Lemma 9. Let G be a graph on the particle set P.

Pr(G ∈ Ψ /∼ ) = (1 + o(1))Pr(G ∈ G k,q ).

(24)

Proof of Theorem 1. For an Erdős-Renyi random graph space G n,p on n vertices and edge probability p, the connectivity results are well known (see, e.g., [13] ). By Lemma 9, the whp statements carry through to Ψ /∼ . Since Theorem 1 deals with the case of one initial infective s, the infected particles will be those in C(s). Cases (i) and (iii) of Theorem 1 are straightforward to see from the above. For case (ii), there is a unique giant component g of size C 1 in G ∈ Ψ /∼ . By the symmetry of the model, the probability any particular particle x being in g is |g|/k = (1 + o(1))C. Thus, the giant component is infected with this probability. Otherwise, s will be placed in a component of size at most O(ln k). 2

Viral Processes by Random Walks on Random Regular Graphs

Reversible Markov Chains and Random Walks on Graphs

Parsimonious Flooding in Dynamic Graphs

Disease Spreading in Populations of Moving Agents

Impact of Human Mobility on Opportunistic Forwarding Algorithms

The Cover Time of Random Regular Graphs

The Cover Time of the Giant Component of a Random graph

Multiple Random Walks in Random Regular Graphs

Epidemic Modelling: An Introduction

Activated Random Walkers: Facts, Conjectures and Challenges

The Infection Time of Graphs

A random Walk Model for Infection on Graphs: Spread of Epidemics and Rumours with Mobile Agents

Epidemics and Rumours in Complex Networks

An Introduction to Probability Theory

A Proof of Alon's Second Eigenvalue Conjecture and Related Problems

One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights

Limit Theorems for an Epidemic Model on the Complete Graph

Random Walks on Graphs: A Survey

Mobile Geometric Graphs: Detection, Coverage and Percolation

On spreading a rumor

The Opportunistic Transmission of Wireless Worms Between Mobile Devices

Tight Bounds on Information Dissemination in Sparse Mobile Networks

Epidemic Spreading in Communities with Mobile Agents

We say an r-regular graph G is typical if it satisfies the properties P1-P4 listed below. We first give some definitions.LetP1. G is connected and not bipartite. P2. The second eigenvalue of the adjacency matrix of G is at most 2 √ r − 1 + , where > 0 is an arbitrarily small constant. P3. There are at most n 2 1 vertices on small cycles. P4. No pair of cycles C 1 , C 2 with |C 1 |, |C 2 | ≤ 100L 1 are within distance 100L 1 of each other.Note that P3 implies that at most n C vertices of a typical r-regular graph are not treelike, whereLemma 10. Let G r ⊆ G r be the set of typical r-regular graphs. Then |G r |∼ |G r |.For Lemma 10, that P2 holds whp is a very difficult result of Friedman [15] . The other properties are straightforward to establish; see, e.g., [6] .