NETWORK SECURITY IN MODELS OF COMPLEX

NETWORKS
ANTHONY BONATO, PAWE L PRA LAT, AND CHANGPING WANG
Abstract. Vertex pursuit games, such as the game of Cops and
Robber, are a simplied model for network security. In these
games, cops try to capture a robber loose on the vertices of the
network. The minimum number of cops required to win on a graph
G is the cop number of G. We present asymptotic results for the
game of Cops and Robber played in various stochastic network
models, such as in G(n, p) with non-constant p, and in random
power law graphs. We nd bounds for the cop number of G(n, p)
for a large range of p as a function of n. We prove that the cop
number of random power law graphs with n vertices is asymptot-
ically almost surely (n). The cop number of the core of random
power law graphs is investigated, and is proved to be of smaller
order than the order of the core.
1. Introduction
Suppose that an intruder is loose on the vertices of a network, and
travels between adjacent vertices. The intruder could represent a virus
or hacker, or some other malicious agent intent on avoiding capture.
A set of searchers are attempting to capture the intruder. Although
placing a searcher on each vertex guarantees the capture of the in-
truder, it is a more interesting (and more dicult) problem to nd
the minimum number of searchers required to capture the intruder. A
motivation for minimizing the number of searcher comes from the fact
that fewer searchers require fewer resources. Networks that require a
smaller number of searchers may be viewed as more secure than those
where many searchers are needed.
Vertex pursuit games, such as Cops and Robber, may be viewed of
as a simplied model for such network security problems. The game of
Cops and Robber, introduced independently by Nowakowski and Win-
kler [12] and Quilliot [13] over twenty years ago, is played on a xed
1991 Mathematics Subject Classication. 05C80, 68R10, 94C15.
Key words and phrases. random graphs, complex networks, vertex-pursuit
games, Cops and Robber, domination, adjacency property.
The authors gratefully acknowledge support from NSERC and MITACS.
1
2 ANTHONY BONATO, PAWE L PRA LAT, AND CHANGPING WANG
graph G, and is our focus in this study. We will always assume that
G is undirected, simple, and nite. There are two players, a set of k
cops (or searchers), where k > 0 is a xed integer, and the robber. The
cops begin the game by occupying a set of k vertices. The robber then
chooses a vertex, and the cops and robber move in alternate rounds.
The players use edges to move from vertex to vertex. More than one
cop is allowed to occupy a vertex, and the players may remain on their
current vertex. The players know each others current locations and
can remember all the previous moves. The cops win and the game
ends if at least one of the cops can eventually occupy the same vertex
as the robber; otherwise, the robber wins. As placing a cop on each
vertex guarantees that the cops win, we may dene the cop number,
written c(G), which is the minimum number of cops needed to win on
G. The cop number was introduced by Aigner and Fromme [1] who
proved (among other things) that if G is planar, then c(G) 3. For
a survey of results on vertex pursuit games such as Cops and Robber,
the reader is directed to the survey [2].
Over the last few years there was an explosion of mathematical re-
search related to stochastic models of real-world networks, especially
for models of the web graph. Many technological, social, biological net-
works have properties similar to those present in the web, such as power
law degree distributions and the small world property. Following [8],
we refer to these networks as complex. For example, power laws have
been observed in protein-protein interaction networks, and social net-
works such as the one formed by scientic collaborators. While much
of the earlier mathematical work on complex networks focused on de-
signing models satisfying certain properties such as power law degree
distributions, new approaches are constantly emerging.
In this paper, which is the full version of [6], we study vertex pur-
suit games in random graph models, including models for complex net-
works. While Cops and Robber have been extensively studied in highly
structured deterministic graphs such as graph products (see [11]), to
our best knowledge, our work is the rst to consider such games in
stochastic network models.
All asymptotics throughout are as n . We say that an event
in a probability space holds asymptotically almost surely (a.a.s.) if the
probability that it holds tends to 1 as n goes to innity. For p (0, 1)
or p = p(n) tending to 0 with n, dene Ln = log 1
1p
n. We denote the
incomplete gamma function by (, ).
NETWORK SECURITY IN MODELS OF COMPLEX NETWORKS 3
We consider Erdos, Renyi G(n, p) random graphs and their general-
izations used to model complex networks. The cop number of G(n, p)
was studied in [5], where the following result was proved.
Theorem 1.1. Let 0 < p < 1 be xed. For every real > 0 a.a.s. for
G G(n, p)
(1 )Ln c(G) (1 + )Ln.
The problem of determining the cop number of G(n, p) where p =
p(n) is a function of n was left open in [5]. We consider the general
case of a non-constant p in this work (the ranges of p that we study
are described in the next subsection).
Recent work of Chung and Lu [7, 8] supplies an extension of the
G(n, p) random graphs to random graphs G(w) with given expected
degree sequence w. For example, if w follows a power law distribu-
tion, then G(w) supplies a model for complex networks. We determine
bounds on the cop number of random power law graphs as discussed
in the next subsection.
1.1. Results. We consider the cop number in classical random graphs
and for random power law graphs. The proofs of the results in this
subsection may be found in Section 2. We consider the cop number of
G(n, p(n)) when p(n) is a function of n. We will abuse notation and
refer to p rather than p(n). For G(n, p) our main results are summarized
in the following theorem.
Theorem 1.2.
(1) Suppose that p p
0
where p
0
is the smallest p for which
p
2
/40
log
_
(log
2
n)/p
_
log n
holds. Then a.a.s. G G(n, p) satises
Ln L
_
(p
1
Ln)(log n)
_
c(G) Ln L
_
(Ln)(log n)
_
+ 2.
(2) If (2 log n)/

n p = o(1) and (n) is any function tending to

innity, then a.a.s. G G(n, p) satises
Ln L
_
(p
1
Ln)(log n)
_
c(G) Ln +L((n)).
The proof may be found in Subsection 2.1 below. By Theorem 1.2,
we have the following corollary.
Corollary 1.3. If p = n
o(1)
and p < 1, then a.a.s. G G(n, p)
satises
c(G) = (1 + o(1))Ln.
4 ANTHONY BONATO, PAWE L PRA LAT, AND CHANGPING WANG
Indeed, from part (1) it follows that if p is a constant, then
c(G) = Ln 2Llog n + (1) = (1 + o(1))Ln.
From part (2), for p = n
o(1)
tending to zero with n, the lower bound
is
Ln L
_
(p
1
Ln)(log n)
_
= Ln 2L
_
(1 + o(1))p
1
log n
_
= Ln 2L
_
n
o(1)
_
= (1 + o(1))Ln.
Note also that for p = n
a(1+o(1))
(0 < a < 1/2) we do not have a
concentration for c(G) but the following bounds hold
(1 + o(1))(1 2a)Ln c(G) (1 + o(1))Ln.
We now describe results for the cop number of random power law
graphs. Let
w = (w
1
, . . . , w
n
)
be a sequence of n real nonnegative real numbers. We dene a random
graph model, written G(w), as follows. Typically, vertices are integers
in [n]. Each potential edge between i and j is chosen independently
with probability p
ij
= w
i
w
j
, where
=
1

n
i=1
w
i
.
We will always assume that
max
i
w
2
i
<
n

i=1
w
i
,
which implies that p
ij
[0, 1). The model G(w) is referred to as
random graphs with given expected degree sequence w. Observe that
G(n, p) may be viewed as a special case of G(w) by taking w to be
equal the constant n-sequence (pn, pn, . . . , pn).
Given > 2, d > 0, and a function M = M(n) = o(

n) (with M
tending to innity with n), we consider the random graph with given
expected degrees w
i
> 0, where
w
i
= ci

1
1
(1)
for i satisfying i
0
i < n +i
0
. The term c depends on and d, and i
0
depends also on M; namely,
c =
_
2
1
_
dn
1
1
, i
0
= n
_
d
M
_
2
1
__
1
. (2)
NETWORK SECURITY IN MODELS OF COMPLEX NETWORKS 5
It is not hard to show (see [7, 8]) that a.a.s. the random graphs with
the expected degrees satisfying (1) and (2) follow a power law degree
distribution with exponent , average degree d(1+o(1)), and maximum
degree M(1 + o(1)).
Our next theorem demonstrates that the cop number of random
power law graphs is a.a.s. (n), and so is of much larger order than
the logarithmic cop number of G(n, p) random graphs. Hence, these
results are suggestive that in power law graphs, on average a large
number of cops are needed to secure the network.
Theorem 1.4. For a random power law graph G G(w) with exponent
> 2 and average degree d, a.a.s. the following hold.
(1) If X is the random variable denoting the number of isolated
vertices in G(w), then
c(G) X
= (1 + o(1))n
_
1
0
exp
_
d
2
1
x
1/(1)
_
dx
= (1 + o(1))(d( 2))
1
( 1)
2
n
_
1 , d
2
1
_
.
(2) For a (0, 1), dene
f(a) = a +
_
1
a
exp
_
d
2
1
a
(2)/(1)
x
1/(1)
_
dx.
Then
c(G) (1 + o(1))n min
0<a<1
f(a).
The proof of Theorem 1.4 may be found in Subsection 2.3. We note
that integrals in the statement of Theorem 1.4 do not possess closed-
form solutions in general. We supply numerical values for lower/upper
bounds of the cop number of G(w) when d = 10, 20 and = 2.1, 2.7
(note that the values of d = 10 and = 2.1 coincide with earlier
experimental results found in the web graph; see for example the survey
[3]).
Table 1. Upper and lower bounds for the cop number
of G(w) for various values of d (top row) and (left
column).
10 20
2.1 0.1806/0.2940 0.5112 10
1
/0.1265
2.7 0.4270 10
2
/0.1895 0.4205 10
4
/0.8261 10
1
6 ANTHONY BONATO, PAWE L PRA LAT, AND CHANGPING WANG
While Theorem 1.4 suggests a large number of cops are needed to
secure complex networks against intruders, by item (1) it is the abun-
dance of isolated vertices that makes the cop number equal to (n).
To overcome the issue with isolated vertices, we consider restricting
the movements of the cops and robber to the subgraph induced by
suciently high degree vertices.
Fix (2, 3). Dene the core of a graph G, written

G, as the
subgraph induced by the set of vertices of degree at least n
1/ log log n
.
Random power law graphs with (2, 3) are referred to as octopus
graphs in [8], since the core is dense with small diameter O(log log n)
and the overall diameter is O(log n). For G G(w), since the expected
degree of vertex i in G is
w
i
=
2
1
dn
1/(1)
i
1/(1)
,
vertices with expected degree at least n
1/ log log n
have labels at most
i
N
=
_
2
1
d
_
1
n
1(1)/ log log n
.
The order of the core is written N. By the Chernos bound,
N = (1 + o(1))i
N
i
0
= (1 + o(1))i
N
= (n
1(1)/ log log n
) ,
provided that log M (log n)/ log log n. Thus,
n = N
1+(1)/ log log N+(1)/ log
2
log N
. (3)
We consider the cop number of the core of random power law graphs
(so the cop and robber are restricted to movements within the core).
As vertices in the core informally represent the hubs of the network,
one would suspect that the cop number of the core is of smaller order
than the core itself. This intuition is made precise by the following
theorem, which provides a sublinear upper bound for the cop number
of the core. The proof is deferred to Subsection 2.4.
Theorem 1.5. For a random power law graph G G(w) with power
law exponent (2, 3) a.a.s. the cop number of the core

G of G satises
N
(1+o(1))(3)/ log log N
c(

G) N
1(1+o(1))(1)(3)/(2) log log n
.
As the asymptotic bounds in Theorem 1.5 are not tight, it is an
interesting open problem to determine the asymptotic value of the cop
number of the core of random power law graphs.
NETWORK SECURITY IN MODELS OF COMPLEX NETWORKS 7
2. Proofs of Main Results
The remainder of the paper is devoted to the proof of our three
main theorems. Each subsequent subsection contains a proof of the
required bounds in each theorem. In all cases, the upper bound for the
cop number is provided by a corresponding bound of the domination
number. In all cases except the proof of Theorem 1.4 (which estimates
the number of isolated vertices), a lower bound for the cop number is
derived by considering an appropriate adjacency property. A minor
detour is made in Subsection 2.2, which gives a concentration result
for the cop number in very sparse G(n, p) random graphs.
2.1. Proof of Theorem 1.2. We rst prove the upper bound in item
(1), and require some background on the domination number of a
graph. A set of vertices S is a dominating set in G if each vertex
not in S is joined to some vertex of S. The domination number of G,
written (G), is the minimum cardinality of a dominating set in G. A
straightforward observation is that
c(G) (G), (4)
(place a cop on each vertex of dominating set with minimum cardi-
nality). However, if n 1, then c(P
n
) = 1 (where P
n
is a path with
n vertices) and (P
n
) =
_
n
3
_
. The bound of (4) while useful, is far
from tight in general. Domination in models of complex networks were
considered by Cooper et al. in [9].
The upper bound in Theorem 1.2 (1) follows by the following result
proved in [14].
Theorem 2.1. Suppose that p p
0
(n) where p
0
is the smallest p for
which
p
2
/40
log
_
(log
2
n)/p
_
log n
holds. Then a.a.s. G G(n, p) satises
Ln L
_
(Ln)(log n)
_
| + 1 (G) Ln L
_
(Ln)(log n)
_
| + 2.
For item (2), the proof follows by the following theorem.
Theorem 2.2. If p = o(1) and (n) is any function tending to innity
with n, then a.a.s. G G(n, p) satises
(G) Ln +L((n))| .
Proof. Since p = o(1) we have that
Ln =
log n
log(1 p)
= (1 + o(1))
log n
p
. (5)
8 ANTHONY BONATO, PAWE L PRA LAT, AND CHANGPING WANG
The probability that the domination number of a random graph is at
most
k = Ln +L((n))|
is bounded from below by the probability that any xed set of k vertices
is a dominating set. But the latter probability is equal to
_
1 (1 p)
k
_
nk
1 (n k)(1 p)
k
1 n(1 p)
k
1 n(1 p)
Ln+L((n))
= 1
1
(n)
= 1 o(1) .

For the proofs of the lower bounds in Theorem 1.2, we employ the
following adjacency property. For a xed k > 0 an integer, we say
that G is (1, k)-existentially closed (or (1, k)-e.c.) if for each k-set S
of vertices of G and vertex u , S, there is a vertex z / S not joined
to a vertex in S and joined to u. If G is (1, k)-e.c., then c(G) k (the
robber may use the property to escape to a vertex not joined to any
vertex occupied by a cop).
The lower bound in Theorem 1.2 will follow once we prove the fol-
lowing theorem.
Theorem 2.3. If p > (2 log n)/

n and
k =
_
Ln L
_
(p
1
Ln)(log n)
__
, (6)
then a.a.s. G G(n, p) is (1, k)-e.c.
Note that we do not use the condition for p in the proof of the
theorem. The condition is introduced in order to get a non-trivial
result; the value of k is negative otherwise.
Proof. Assume that p = o(1). Then
k = Ln L
_
(1 + o(1))
log
2
n
p
2
_
= Ln 2L
_
(1 + o(1))
log n
p
_
.
Fix S a k-subset of vertices and a vertex u not in S. For a vertex
x V (G)(S u), the probability that a vertex x is joined to u and
to no vertex of S is p(1 p)
k
. Since edges are chosen independently,
NETWORK SECURITY IN MODELS OF COMPLEX NETWORKS 9
the probability that no suitable vertex can be found for this particular
S and u is (1 p(1 p)
k
)
nk1
.
Let X be the random variable counting the number of S and u for
which no suitable x can be found. We then have that
E(X) =
_
n
k
_
(n k)
_
1 p(1 p)
k
_
nk1
n
k+1
_
1
(Ln)(log n)
n
_
n(1(Ln)/n)
= n
k+1
exp ((Ln)(log n)(1 (Ln)/n)) (1 + o(1))
= n
k+1
exp
_
(Ln (Ln)
2
/n)(log n)(1 + o(1))
_
n
k+1
exp
_

_
k +
2 log log n
p

2 log
2
n
p
2
n
_
(log n)(1 + o(1))
_
= n
k+1
exp
_

_
k +
2 log log n
p
_
(log n)(1 + o(1))
_
= o(1),
where the second inequality follows by (5). It is also easy to show that
the same argument holds for p a constant. The proof now follow by
Markovs inequality.
2.2. Extreme cases. It is known that if p is tending to one pretty fast,
then the maximum degree of a random graph is very large. Formally,
for a xed non-negative integer k, if n(1p)log nk log log n ,
then the maximum degree is at least n 1 k a.a.s. and clearly k +1
is an upper bound for a cop number (one cop can occupy a vertex with
maximum degree).
We next provide a concentration result for the cop number of the
random graphs G(n, p) for p approaching zero very fast. For example,
if p = o(1/n
2
), a.a.s. G G(n, p) is empty. In this range of p a.a.s.
the cop number of G is n. We now consider the case when p = d/n for
constant d (0, 1). Bollobas [4] proved the following result.
Theorem 2.4. Let 0 < d < 1, p = d/n, and let X be the number of
tree connected components of G(n, p). Then the expectation of X is
E(X) = u(d)n + O(1),
where
u(d) =
1
d

k=1
k
k2
k!
(de
d
)
k
.
10 ANTHONY BONATO, PAWE L PRA LAT, AND CHANGPING WANG
A.a.s. G(n, p) satises
[X[ = u(d)n(1 + o(1)).
We note that u(d) (0, 1). A graph is unicyclic if it contains exactly
one cycle.
Theorem 2.5. Let 0 < d < 1 and p = d/n. Then a.a.s. G G(n, p)
is such that every connected component is a tree or a unicyclic graph,
and there are at most log log n vertices in the unicyclic components.
Trees are cop-win graphs, while unicyclic graphs have cop number at
most 2. Each tree component requires exactly one cop, while there are
at most 2 log log n many cops needed for all the unicyclic components.
Hence, the number of cops on the unicyclic components becomes negli-
gible in contrast to the number of cops on tree components. Therefore,
from Theorems 2.4 and 2.5 we have the following concentration result.
Corollary 2.6. Let 0 < d < 1, p = d/n. Then for the graph G
G(n, p),
E(c(G)) = u(d)n + O(log log n).
A.a.s. G G(n, p) satises
c(G) = u(d)n(1 + o(1)).
Concentration results for the cop number of G(n, p) with p in other
ranges (such as just after the phase transition p c/n with c > 1)
remain open.
2.3. The proof of Theorem 1.4. For the lower bound, we exploit
the fact that the cop number is bounded from below by the number
of isolated vertices: one cop is needed per isolated vertex. In general
power law graphs, there may exist an abundance of isolated vertices,
even as much as (n) many. We show that this is indeed the case for
random power law graphs.
The probability that the vertex i for i
0
i < n + i
0
(that is, the
vertex i corresponds to the weight w
i
) is isolated is equal to
p
i
=

j,j=i
(1 w
i
w
j
)
=

j,j=i
exp (w
i
w
j
(1 + o(1)))
= exp
_
w
i

j,j=i
w
j
(1 + o(1))
_
= exp (w
i
(1 + o(1))) . (7)
NETWORK SECURITY IN MODELS OF COMPLEX NETWORKS 11
Let X
i
be an indicator random variable for the event that the vertex i
is isolated. Then
P(X
i
= 1) = 1 P(X
i
= 0) = p
i
for i
0
i < n + i
0
.
Let X be the number of isolated vertices in G(w). As X =

i
0
i<n+i
0
X
i
,
it follows from (7) that the expected value of X is

i
0
i<n+i
0
p
i
= (1 + o(1))n
_
1
0
exp
_
c(xn)
1/(1)
_
dx
= (1 + o(1))n
_
1
0
exp
_
d
2
1
x
1/(1)
_
dx.
A sum of independent random variables with large enough expected
value is concentrated on its expected value (see, for example, Theo-
rem 2.8 in [10]). Thus, the number of isolated vertices in G(w) is a.a.s.
equal to
X = (1 + o(1))n
_
1
0
exp
_
d
2
1
x
1/(1)
_
dx
= (1 + o(1))(d( 2))
1
( 1)
2
n
_

d
2
1
t

e
t
dt
= (1 + o(1))(d( 2))
1
( 1)
2
n
_
1 , d
2
1
_
.
Hence, item (1) of Theorem 1.4 follows. We note that another asymp-
totic expression of the number of isolated vertices in random power law
graphs is given in [8] (see Theorem 5.20).
For the proof of the upper bound in item (2) of Theorem 1.4, we
give a bound on the domination number. Fix a constant a (0, 1) and
consider the set A V of rst an| i
0
+ 1 = (1 + o(1))an vertices,
that is, A = i
0
, i
0
+ 1, . . . , an|. Let B V A denote the set of
vertices that do not have a neighbour in A. Then D = A B is a
dominating set of G, and we estimate the cardinality of D.
Consider the vertex i, where an < i < n + i
0
. Since i
0
= o(n), there
is b (0, 1] such that i = bn(1 +o(1)). The probability that i does not
12 ANTHONY BONATO, PAWE L PRA LAT, AND CHANGPING WANG
have a neighbour in A is equal to
q
i
=

j<an+i
0
(1 w
i
w
j
)
= exp
_
(1 + o(1))w
i

j<an+i
0
w
j
_
= exp
_
(1 + o(1))c(bn)
1/(1)
(dn)
1
n
_
a
0
c(xn)
1/(1)
dx
_
= exp
_
(1 + o(1))d
_
2
1
_
2
b
1/(1)
_
a
0
x
1/(1)
dx
_
= exp
_
(1 + o(1))d
2
1
b
1/(1)
a
(2)/(1)
_
.
Thus, using Chernos bound, we obtain that a.a.s.
[B[ = (1 + o(1))n
_
1
a
exp
_
d
2
1
a
(2)/(1)
x
1/(1)
_
dx,
and that a.a.s.
[D[ = [A B[
= (1 + o(1))n
_
a +
_
1
a
exp
_
d
2
1
a
(2)/(1)
x
1/(1)
_
dx
_
.
As this holds for every a (0, 1), the proof of item (2) follows.
2.4. The proof of Theorem 1.5. We rst consider an upper bound
for c(

G) by using a dominating set. The probability that there is an

edge between two given vertices in the core is at least
p
min
= w
2
i
N
(1+o(1))

= (n
2/ log log n
/dn)(1 + o(1))
= (N
(3)/ log log N+(1)/ log
2
log n
)/N (8)
= (N
(1+o(1))(3)/ log log N
)/N .
NETWORK SECURITY IN MODELS OF COMPLEX NETWORKS 13
Hence,

G contains a random graph G(N, p
min
). Thus, using Theo-
rem 2.2, any set of cardinality
k
N
=
_
log
1/(1p
min
)
N + log
1/(1p
min
)
(N)
_
= (1 + o(1))
log N
p
min
=
N log N
N
(1+o(1))(3)/ log log N
= N exp ((1 + o(1))(3 )(log N)/ log log N + log log N)
= N exp ((1 + o(1))(3 )(log N)/ log log N)
= N/N
(1+o(1))(3)/ log log N
= o(N)
is a dominating set a.a.s. (where (N) is any function tending to innity
with N). As this holds for any set of cardinality k
N
, we obtain a smaller
dominating set by considering only vertices with the largest expected
degree. Consider the subset of vertices U = i
0
, i
0
+ 1, . . . , k of rst
k i
0
+ 1 vertices, k i
0
. Then
k

i=i
0

i
= c
_
k
i
0
i
1/(1)
di + O(1) = (1 + o(1))c
1
2
k
(2)/(1)
.
Hence, the probability that vertex i does not have a neighbour in U is
equal to
q(i) =
k

j=i
0
(1
i

j
)
= exp
_
(1 + o(1))
i

j=i
0

j
_
= exp
_
(1 + o(1))
2
1
dn
(3)/(1)
i
1/(1)
k
(2)/(1)
_
.
It is straightforward to see that for all vertices i in the core,
q(i) q
_
i
N
(1 + o(1))
_
= exp
_
(1 + o(1))n
(2)/(1)+1/ log log n
k
(2)/(1)
_
. (9)
14 ANTHONY BONATO, PAWE L PRA LAT, AND CHANGPING WANG
Therefore, in order to make the right hand side of (9) equal to o(n
1
),
it is enough to take
k = n
1(1)/(2) log log n
log
2(1)/(2)
n
= n
1(1+o(1))(1)/(2) log log n
= N
1(1+o(1))(1)(3)/(2) log log n
.
Now, the expected number of vertices that are not dominated by U is
o(1), and the assertion follows from Markovs inequality. The upper
bound now follows.
For the lower bound, we can show that the core is a.a.s. (1, k)-e.c.
for k = log N/ log log N. We do not present this argument here, but in-
stead prove a better bound by considering a weaker adjacency property.
We will show that a.a.s. for all subsets S of vertices of cardinality
K = N
(3)/ log log N1/ log
3/2
log N
= N
(1+o(1))(3)/ log log N
and all vertices u , S with N/3 < u < 2N/3, there is a vertex x ,
(Su) with N/3 < x < 2N/3, not joined to a vertex in S and joined
to u. This will yield a lower bound of K for the cop number since the
robber can move only on vertices with labels between N/3 and 2N/3
to avoid being captured.
Note that the probability that there is an edge between vertex in the
core and vertex with label between N/3 and 2N/3 is at most
p
max
= M(n
1/ log log n
)
n
1/2+1/ log log n
= N
1/2+(3)/2 log log N+(1)/ log
2
log N
(using (3) and the fact that M = o(

n)). A lower bound for the edge

probability is given by (8).
Let X be the random variable counting the number of ordered pairs
of K-sets S and vertices u with N/3 < u < 2N/3 for which no suitable
NETWORK SECURITY IN MODELS OF COMPLEX NETWORKS 15
vertex x with N/3 < x < 2N/3 can be found. Then
E(X) N
K+1
_
1 p
min
(1 p
max
)
K
_
(N)K1
= N
K+1
_
1 N
1+(3)/ log log N+(1)/ log
2
log N
(1 N
1/2+(1)/ log log N
)
K
_
(N)
= N
K+1
_
1 N
1+(3)/ log log N+(1)/ log
2
log N
_
(N)
= exp
_
(K + 1) log N N
(3)/ log log N+(1)/ log
2
log N
_
= exp
_
N
(3)/ log log N(1)/ log
3/2
log N
N
(3)/ log log N+(1)/ log
2
log N
_
= exp
_
N
(1+o(1))(3)/ log log N
_
= o(1).
The proof now follows by Markovs inequality.
References
[1] M. Aigner, M. Fromme, A game of cops and robbers, Discrete Applied Math-
ematics 8 (1984) 112.
[2] B. Alspach, Sweeping and searching in graphs: a brief survey, Matematiche 59
(2006) 537.
[3] A. Bonato, A survey of models of the web graph, In: Proceedings of Combi-
natorial and Algorithmic Aspects of Networking, 2004.
[4] B. Bollobas, Random Graphs, Cambridge University Press, Cambridge, 2001.
[5] A. Bonato, G. Hahn, C. Wang, The cop density of a graph, Contributions to
Discrete Mathematics 2 (2007) 133-144.
[6] A. Bonato, P. Pralat, C. Wang, Vertex pursuit games in stochastic network
models, In: Proceedings of the 4th Workshop on Combinatorial and Algorith-
mic Aspects of Networking, 2007.
[7] F.R.K. Chung, L. Lu, The average distance in a random graph with given
expected degrees, Internet Mathematics 1 (2006), 91114.
[8] F.R.K. Chung, L. Lu, Complex graphs and networks, American Mathematical
Society, U.S.A., 2004.
[9] C. Cooper, R. Klasing, M. Zito, Lower bounds and algorithms for dominating
sets in web graphs, Internet Mathematics 2 (2005) 275300.
[10] S. Janson, T. Luczak, A. Ruci nski, Random Graphs, Wiley, New York, 2000.
[11] S. Neufeld, R. Nowakowski, A game of cops and robbers played on products
of graphs, Discrete Math. 186 (1998) 253268.
[12] R. Nowakowski, P. Winkler, Vertex to vertex pursuit in a graph, Discrete
Mathematics 43 (1983) 230239.
[13] A. Quilliot, Jeux et pointes xes sur les graphes, Ph.D. Dissertation, Universite
de Paris VI, 1978.
[14] B. Wieland, A.P. Godbole, On the domination number of a random graph,
The Electronic Journal of Combinatorics 8 (2001), #R37.
16 ANTHONY BONATO, PAWE L PRA LAT, AND CHANGPING WANG
Department of Mathematics, Wilfrid Laurier University, Water-
loo, ON, Canada
E-mail address: [email protected]
Department of Mathematics and Statistics, Dalhousie University,
Halifax NS, Canada
E-mail address: [email protected]
Department of Mathematics, Ryerson University, Toronto, ON, Canada
E-mail address: [email protected]