On Detection and Structural Reconstruction of Small-World
Random Networks
T. Tony Cai1 , Tengyuan Liang1 and Alexander Rakhlin1

arXiv:1604.06474v1 [math.ST] 21 Apr 2016

1

Department of Statistics, The Wharton School, University of Pennsylvania

Abstract
In this paper, we study detection and fast reconstruction of the celebrated Watts-Strogatz (WS)
small-world random graph model (Watts and Strogatz, 1998) which aims to describe real-world complex networks that exhibit both high clustering and short average length properties. The WS model
with neighborhood size k and rewiring probability probability β can be viewed as a continuous interpolation between a deterministic ring lattice graph and the Erdős-Rényi random graph. We study
both the computational and statistical aspects of detecting the deterministic ring lattice structure
(or local geographical links, strong ties) in the presence of random connections (or long range links,
weak ties), and for its recovery. The phase diagram in terms of (k, β) is partitioned into several regions
according to the difficulty of the problem. We propose distinct methods for the various regions.

1 Introduction
The “small-world” phenomenon aims to describe real-world complex networks that exhibit both high
clustering and short average length properties. While most of the pairs of nodes are not friends, any node
can be reached from another in a small number of hops. The Watts-Strogatz (WS) model, introduced in
(Watts and Strogatz, 1998; Newman and Watts, 1999), is a popular generative model for networks that
exhibit the small-world phenomenon. The WS model interpolates between the two extremes—the regular lattice graph on the one hand, and the random graph on the other. Considerable effort has been
spent on studying the asymptotic statistical behavior (degree distribution, average path length, clustering coefficient, etc.) and the empirical performance of the WS model (Watts, 1999; Amaral et al., 2000;
Barrat and Weigt, 2000; Latora and Marchiori, 2001; Van Der Hofstad, 2009). Successful applications of
the WS model have been found in a range of disciplines, such as psychology (Milgram, 1967), epidemiology (Moore and Newman, 2000), medicine and health (Stam et al., 2007), to name a few. In one of the first
algorithmic studies of the small-world networks, Kleinberg (2000) investigated the theoretical difficulty
of finding the shortest path between any two nodes when one is restricted to use local algorithms, and
further related the small-world notion to long range percolation on graphs (Benjamini and Berger, 2000;
Coppersmith et al., 2002). The focus of the present paper is on statistical and computational aspects of
the detection and recovery problems.
Given a network, the first statistical and computational challenge is to detect whether it enjoys the
small world property, or whether the observation may be explained by the Erdős-Rényi random graph
(the null hypothesis). The second question is concerned with the reconstruction of the neighborhood
structure if the network does exhibit the small world phenomenon. In the language of social network
analysis, the detection problem corresponds to detecting the existence of local geographical links (or
1

close friend connections, strong ties) in the presence of long range links (or random connections, weak
ties). The reconstruction problem corresponds to distinguishing between these local links and long
range links. The problem is statistically and computationally difficult due to the high-dimensional unobserved latent variable—the permutation matrix— which blurs the natural ordering of the ring structure.
Let us parametrize the WS model in the following way: the number of nodes is denoted by n, the
neighborhood size by k, and the rewiring probability by β. Provided the adjacency matrix A ∈ Rn×n , we
are interested in identifying the choices of (n, k, β) when detection and reconstruction of the small world
random graph is possible. Specifically, we focus on the following two questions.
Detection Given the adjacency matrix A up to a permutation, when (in terms of n, k, β) and how (in
terms of procedures) can one statistically distinguish whether it is a small world graph (β < 1), or a usual
random graph with matching degree (β = 1). What if we restrict our attention to computationally efficient procedures?
Reconstruction Once the presence of the neighborhood structure is confirmed, when (in terms of
n, k, β) and how (in terms of procedures) can one estimate the deterministic neighborhood structure?
If one only aims to estimate the structure consistently (asymptotically correct), are there computationally efficient procedures, and what are their limitations?
We address the above questions by presenting a phase diagram in Figure 1. The phase diagram divides the parameter space into four disjoint regions according to the difficulty of the problem. We propose distinct methods for the regions where solutions are possible.

1.1 Why Small World Graph?
Finding and analyzing the appropriate statistical models for real-world complex networks is one of the
main themes in network science. Many real empirical networks—for example, internet architecture, social networks, and biochemical pathways—exhibit two features simultaneously: high clustering among
individual nodes and short distance between any two nodes. Consider the local tree rooted at a person. The high clustering property suggests prevalent existence of triadic closure, which significantly reduces the number of reachable people within a certain depth (in contrast to the regular tree case where
this number grows exponentially with the depth), contradicting the short average length property. In a
pathbreaking paper, Watts and Strogatz (1998) provided a mathematical model that resolves the above
seemingly contradictory notions. The solution is surprisingly simple — interpolating between structural
ring lattice graph and a random graph. The ring lattice provides the strong ties (i.e., homophily, connection to people who are similar to us) and triadic closure, while the random graph generates the weak
ties (connection to people who are otherwise far-away), preserving the local-regular-branching-tree-like
structure that induces short paths between pairs.
Given the small world model, it is natural to ask the statistical question of distinguishing the local
links (geographical) and long range links (non-geographical) based on the observed graph.

1.2 Rewiring Model
Let us now define the WS model. Consider a ring lattice with n nodes, where each node is connected
with its k nearest neighbors (k/2 on the left and k/2 on the right, k even for convenience). The rewiring
process contains two procedures: erase and reconnect. First, erase each currently connected edge with
k
probability β, independently. Next, reconnect each edge pair with probability β n−1
, allowing multiplic-

2

ity.1 The observed symmetric adjacency matrix A ∈ {0, 1}n×n has the following structure under some
unobserved permutation matrix P π ∈ {0, 1}n×n . For 1 ≤ i < j ≤ n,
½
k
), if 0 < |i − j | ≤ k2 mod n − 1 − k2
w.p. 1 − β(1 − β n−1
T
[P π AP π ]i j = 1
k
w.p. β n−1 ,
otherwise
and entries are independent of each other. Equivalently, we have for 1 ≤ i < j ≤ n
¡
¢
A i j = κ [P π B P πT ]i j ,

(1)

where κ(·) is the entry-wise i.i.d. Markov channel,
¶
k
κ(0) ∼ Bernoulli β
,
n −1
¶
µ
k
) ,
κ(1) ∼ Bernoulli 1 − β(1 − β
n −1
µ

and B ∈ {0, 1}n×n indicates the support of the structural ring lattice
½
1, if 0 < |i − j | ≤ k2 mod n − 1 − k2
.
Bi j =
0, otherwise

(2)

We denote by WS(n, k, β) the distribution of the random graph generated from the rewiring model,
k
and denote by ER(n, n−1
) the Erdős-Rényi random graph distribution (with matching average degree k).
k
), with no neighborhood
Remark that if β = 1, the small world graph WS(n, k, β) reduces to ER(n, n−1
structure. In contrast, if β = 0, the small world graph WS(n, k, β) corresponds to the deterministic ring
lattice, without random connections. We focus on the dependence of the gap 1 − β = o(1) on n and k,
k
such that distinguishing between WS(n, k, β) and ER(n, n−1
) or reconstructing the ring lattice structure
is statistically and computationally possible.

1.3 Summary of Results
The main theoretical and algorithmic results are summarized in this section. We first introduce several
regions in terms of (n, k, β), according to the difficulty of the problem instance, and then we present the
results using the phase diagram in Figure 1. Except for the impossible region, we will introduce different
algorithms with distinct computational properties.
q
log n
log n
Impossible region: 1 − β ≺
n ∨ k . Inside this region no multiple testing procedure (regardless
of computational budget) can succeed in distinguishing among the class of models including all of
k
) with vanishing error.
WS(n, k, β) and ER(n, n−1
p
q
q
log n
log n log n
1
k
Hard region:
. It is possible to detect between WS(n, k, β) and ER(n, n−1
)
n ∨ k ¹ 1−β ≺
k∨ k
statistically with vanishing error; however the evaluation of the test statistic (5) (below) requires exponential time complexity (to the best of our knowledge).
rq
p
q
log n
log n
log n
1
Easy region: k ∨ k ¹ 1 − β ¹
n ∨ k . There exists an efficient spectral test that can distink
guish between the small world random graph WS(n, k, β) and the Erdős-Rényi graph ER(n, n−1
) in near
linear time (in the matrix size).
1 The original rewiring process in Watts and Strogatz (1998) does not allow multiplicity; however, for the simplicity of techni-

cal analysis, we focus on reconnection allowing multiplicity. These two rewiring processes are asymptotically equivalent.

3

Reconstructable region:

rq

log n
n

∨

log n
k

≺ 1 − β ¹ 1. In this region, not only is it possible to detect the

existence of the lattice structure in a small-world graph, but it is also possible computationally to consistently estimate/reconstruct the neighborhood structure via a novel correlation thresholding procedure.
The following phase diagram provides an intuitive illustration of the above theoretical results. If
we parametrize k ³ n x , 0 < x < 1 and 1 − β ³ n −y , 0 < y < 1, each point (x, y) ∈ [0, 1]2 corresponds to a
particular problem instance with parameter bundle (n, k = n x , β = 1 − n −y ). According to the location of
(x, y), the difficulty of the problem changes; for instance, the larger the x and the smaller the y is, the
easier the problem becomes. The various above regions (plotted in [0, 1]2 ) are: impossible region (red
region I), hard region (blue region II), easy region (green region III), reconstructable region (cyan region
IV).
1

=n

y

,0 < y < 1

y

I

1/2
II

III

1/4
IV
1/2

x
k = nx , 0 < x < 1

Figure 1: Phase diagram for small-world network: impossible region (red region I), hard region (blue
region II), easy region (green region III), and reconstructable region (cyan region IV).

1.4 Notation
A, B, Z ∈ Rn×n denote symmetric matrices: A is the adjacency matrix, B is the structural signal matrix
as in Equation (2), and Z = A − E A is the noise matrix. We denote the matrix of all ones by J . Notations
a(n)
≤ c, with some constant
¹, º, ≺, Â denote the asymptotic order: a(n) ¹ b(n) if and only if lim sup b(n)
n→∞

a(n)
c > 0, a(n) ≺ b(n) if and only if lim sup b(n)
= 0. C ,C 0 > 0 are universal constants that may change from
n→∞

line to line. For a symmetric matrix A, λi (A), 1 ≤ i ≤ n denotes the ranked eigenvalues, in a decreasing order. The inner-product 〈A, B 〉 = tr(A T B ) overloads the usual Euclidian inner-product and matrix
inner-product. For any integer n, [n] := {0, 1, . . . , n − 1} denotes the index set. Denote the permutation in
symmetric group π ∈ S n and its associated matrix form as P π .
For a graph G(V, E ) generated from the Watts-Strogatz model WS(n, k, β) with associated permuta-

4

tion π, for each node v i ∈ V, 1 ≤ i ≤ |V |, we denote
½
k
N (v i ) := v j : 0 < |π−1 (i ) − π−1 ( j )| ≤
2

mod n − 1 −

k
2

¾

as the ring neighborhood nodes with respect to node v i , before the permutation π applied.

1.5 Organization of the Paper
The following sections are dedicated to the theoretical justification of the various regions in Section 1.3.
Specifically, Section 2 establishes the boundary for the impossible region I, where the problem is impossible to solve information theoretically. We contrast the hard region II with the regions III and IV in
Section 3; here, the difference arises in statistical and computational aspects of detecting the strong tie
structure inside random graph. Section 4 studies a correlation thresholding algorithm that reconstructs
the neighborhood structure consistently when the parameters lie within the reconstructable region IV.
We also study a spectral ordering algorithm which succeeds in reconstruction in a part of region III.
Whether the remaining part of region III admits a recovery procedure is an open problem. Additional
further directions are listed in Section 5.

2 The Impossible Region: Lower Bounds
We start with an information theoretic result that describes the difficulty of distinguishing among a class
of models. The following Theorem 1 characterizes the impossible region, as in Section 1.3, in the language of minimax multiple testing error. The proof is postponed to Section 6.
Theorem 1 (Impossible Region). Consider the following statistical models: P 0 denotes the probability
k
measure of the Erdős-Rényi random graph ER(n, n−1
), and P π , π ∈ S n−1 denote the probability measures
of the Watts-Strogatz small-world graph WS(n, k, β) as in Equation (1) with different permutations π.
Consider any selector φ : {0, 1}n×n → S n−1 ∪ {0} that maps from the adjacency matrix A ∈ {0, 1}n×n to a
decision in S n−1 ∪ {0}. Then for any fixed 0 < α < 1/8, the following lower bound on multiple testing error
holds:
(
)
X
1
lim min max P 0 (φ 6= 0),
P π (φ 6= π) ≥ 1 − 2α,
(n − 1)! π∈S n−1
n→∞ φ
when the parameters satisfy
s

1 − β ≤ Cα ·

log n
n

or 1 − β ≤ C α0 ·

log n
1
·
,
n log n
k
log k 2

with constants C α ,C α0 that only depend on α. In other words, if
s

1−β ≺

log n log n
∨
,
n
k

no multiple testing procedure can succeed in distinguishing, with vanishing error, the class of models conk
).
taining all of WS(n, k, β) and ER(n, n−1
5

The missing latent random variable, the permutation matrix P π , is the object we are interested in
recovering. A permutation matrix P π induces a certain distribution on the adjacency matrix A. Thus the
k
), is of cardinality (n − 1)! + 1.
parameter space of interest, including models WS(n, k, β) and ER(n, n−1
Based on the observed adjacency matrix, distinguishing among the models including all of WS(n, k, β)
k
and ER(n, n−1
) is equivalent to a multiple testing problem. The impossible region characterizes the information theoretic difficulty of this reconstruction problem by establishing the condition when minimax
testing error does not vanish as n, k(n) → ∞.
The “high dimensional” nature of this problem is mainly driven by the unknown permutation matrix,
and this latent structure introduces difficulty both statistically and computationally. Statistically, via Le
Cam’s method, one can build a distance metric on permutation matrices using the distance between
the corresponding measures (measures on adjacency matrices induced by the permutation structure).
In order to characterize the intrinsic difficulty of estimating the permutation structure, one needs to
understand the richness of the set of permutation matrices within certain distance to one particular
element, a combinatorial task. Computationally, the combinatorial nature of the problem makes the
“naive” approach computationally intensive.

3 Hard v.s. Easy Regions: Detection Statistics
This section studies the hard and easy regions in Section 1.3. First, we propose a near optimal test, the
maximum likelihood test, that detects the ring structure above the information boundary derived in
Theorem 1. However, the evaluation of the maximum likelihood test requires O (n n ) time complexity.
The maximum likelihood test succeeds outside of region I, and, in particular, succeeds (statistically) in
the hard region II. We then propose another efficient test, the spectral test, that detects the ring structure
in time O ∗ (n 2 ) via the power method. The method succeeds in regions III and IV.
Theorem 2 below combines the results of Lemma 1 and Lemma 2.
Theorem 2 (Detection: Easy and Hard Boundaries). Consider the following statistical models: P 0 denotes
k
the distribution of the Erdős-Rényi random graph ER(n, n−1
), and P π , π ∈ S n−1 denote distributions of
the Watts-Strogatz small-world graph WS(n, k, β) with hidden permutation π. Consider any selector φ :
{0, 1}n×n → {0, 1} that maps an adjacency matrix to a binary decision (detection decision).
We say that minimax detection for the small-world random model is possible when
(
)
X
1
lim min max P 0 (φ 6= 0),
P π (φ 6= 1) = 0.
(3)
n→∞ φ
(n − 1)! π∈S n−1
If the parameter (n, k, β) satisfies
s

hard boundary :

1−β º

log n log n
∨
,
n
k

minimax detection is possible, and an exponential time maximum likelihood test (5) ensures (3). If, in
addition, the parameter (n, k, β) satisfies
p
r
log n
1
easy boundary : 1 − β º
∨
,
k
k
then a near-linear time spectral test (7) ensures (3).
Proof of Theorem 2 consists of two parts, which will be addressed in the following two sections, respectively.
6

3.1 Maximum Likelihood Test
Consider the test statistic T1 as the objective value of the following optimization
T1 (A) := max 〈P π B P πT , A〉,

(4)

Pπ

where P π ∈ {0, 1}n×n is taken over all permutation matrices and A is the observed adjacency matrix. The
maximum likelihood test φ1 : A → {0, 1} based on T1 by
(

φ1 (A) =

1 if T1 (A) ≥
0

k
n−1 nk + 2

q

2
k
n−1 nk · log n! + 3

· log n!

o.w.

(5)

³q
´
The threshold is chosen as the rate k 2 + O
k 2 n log ne ∨ n log ne : if the objective value is of a greater
order, then we believe the graph is generated from the small-world rewiring process with strong ties;
otherwise we we cannot reject the null, the random graph model with only weak ties.

Lemma 1 (Guarantee for Maximum Likelihood Test). The maximum likelihood test φ1 in Equation (5)
succeeds in detecting the small world random structure when
s

1−β º

log n log n
∨
,
n
k

in the sense that
(

lim

n,k(n)→∞

max

)
X
1
P 0 (φ1 6= 0),
P π (φ1 6= 1) = 0.
(n − 1)! π∈S n−1

Remark 1. Lemma 1 can be viewed as the condition on the signal and noise separation. By solving
the combinatorial optimization problem, the test statistics aggregates the signal that separates from the
noise the most. An interesting open problem is, if we solve a relaxed version of the combinatorial optimization problem (4) within polynomial time complexity φrel
1 , how much stronger the condition on 1−β
needs to be to ensure power.

3.2 Spectral Test
For the spectral test, we calculate the second largest eigenvalue of the adjacency matrix A as the test
statistic
T2 (A) := λ2 (A).

(6)

The spectral test φ2 : A → {0, 1} is
φ2 (A) =

½

p
p
1 if T2 (A) º k ∨ log n
0
o.w.

(7)

Namely, if λ2 (A) passes a certain threshold, we classify the graph as a small-world graph. Evaluation of
(7) only requires near-linear time O ∗ (n 2 ).

7

Lemma 2 (Guarantee for Spectral Test). The second eigenvalue test φ2 in Equation (7) satisfies
(
)
X
1
lim
max P 0 (φ2 6= 0),
P π (φ2 6= 1) = 0
n,k(n)→∞
(n − 1)! π∈S n−1
whenever
r

1−β º

1
∨
k

p

log n
k

.

The main idea behind Lemma 2 is as follows. Let us look at the expectation of the adjacency matrix,
E A = (1 − β)(1 − β

k
k
) · P πT B P π + β
· (J − I ),
n −1
n −1

where J is the matrix of all ones. The main structure matrix P πT B P π is a permuted version of the circulant
matrix (see e.g. (Gray, 2006)). The spectrum of the circulant matrix B is highly structured, and is of
distinct nature in comparison to the noise matrix A − E A.

4 Reconstructable Region: Fast Structural Reconstruction
In this section, we discuss reconstruction of the ring structure in the Watts-Strogatz model. We show
that in the reconstructable region (region IV in Figure 1), a correlation thresholding procedure succeed
in reconstructing the ring neighborhood structure. As a by-product, once the neighborhood structure
is known, one can distinguish between random edges and neighborhood edges for each node. A natural question is whether there is another algorithm that can work in a region (beyond region IV) where
correlation thresholding fails. We show that in a certain regime with large k, a spectral ordering procedure outperforms the correlation thresholding procedure and succeeds in parts of regions III and IV (as
depicted in Figure 2 below).

4.1 Correlation Thresholding
Consider the following correlation thresholding procedure for neighborhood reconstruction.
Algorithm 1: Correlation Thresholding for Neighborhood Reconstruction
Data: An adjacency matrix A ∈ Rn×n for the graph G(V, E ).
Result: For each node v i , 1 ≤ i ≤ n, an estimated set for neighborhood Nˆ (v i ).
1. For each node v i , calculate the correlation 〈A i , A j 〉 for all j 6= i ;
©
ª
2. Sort the 〈A i , A j 〉, j ∈ [n]\{i } in a decreasing order, select the largest k ones to form the
estimated set Nˆ (v i ) ;
Output: Nˆ (v i ), for all i ∈ [n]
The following lemma proves consistency of the above Algorithm 1. Note the computational complexity is O (n · min{log n, k}) for each node using quick-sort, with a total runtime O ∗ (n 2 ).
Lemma 3 (Consistency of Correlation Thresholding). Consider the Watts-Strogatz random graph WS(n, k, β).
Under the reconstructable regime IV (in Figure 1), that is,
s
µ
¶
log n
log n 1/4
1−β Â
∨
,
(8)
k
n
8

correlation thresholding provides a consistent estimate of the neighborhood set N (v i ) w.h.p in the sense
that
|Nˆ (v i )4N (v i )|
= 0,
n,k(n)→∞ i ∈[n]
|N (v i )|
lim

max

where 4 denotes the symmetric set difference.
One interesting question in small-world networks is to distinguish between strong ties (structural
edges induced by the ring lattice structure) and weak ties (edges due to random connections). The above
lemma addresses this question by providing a consistent estimate of the neighborhood set for each node.
The condition under which consistency of correlation thresholding is ensured corresponds to the reconstructable region in Figure 1. One may ask if there is another algorithm that can provide a consistent
estimate of the neighborhood set beyond region IV. The answer is yes, and we will show in the follow15
ing section that under the regime when k is large (for instance, k º n 16 ), indeed it is possible to slightly
improve on Algorithm 1.

4.2 Spectral Ordering
Consider the following spectral ordering procedure, which approximately reconstructs the ring lattice
7
structure when k is large, i.e., k Â n 8 .
Algorithm 2: Spectral Reconstruction of Ring Structure
Data: An adjacency matrix A ∈ Rn×n for the graph G(V, E ).
Result: A ring embedding of the nodes V .
1. Calculate top 3 eigenvectors in the SVD A = U ΣU T . Denote second and third eigenvectors as
u ∈ Rn and v ∈ Rn , respectively;
2. For each node i and the associated vector A ·i ∈ Rn , calculate the associated angle θi for vector
(u T A ·i , v T A ·i );
Output: the sorted sequence {θi }ni=1 and the corresponding ring embedding of the nodes. For
each node v i , Nˆ (v i ) are the closest k nodes in the ring embedding.
The following Lemma 4 shows that when k is large, Algorithm 2 also provides consistent reconstruction of the ring lattice. Its computational complexity is O ∗ (n 2 ).
Lemma 4 (Guarantee for Spectral Ordering). Consider the Watts-Strogatz graph WS(n, k, β). Assume k is
large enough in the following sense:
1>

log k
log k 7
≥ lim
> .
n,k(n)→∞ log n
8
n,k(n)→∞ log n
lim

Under the regime
1−β Â

n 3.5
,
k4

(9)

the spectral ordering provides consistent estimate of the neighborhood set N (v i ) w.h.p. in the sense that
|Nˆ (v i )4N (v i )|
= 0,
n,k(n)→∞ i ∈[n]
|N (v i )|
lim

max

where 4 denotes the symmetric set difference.
9

In Lemma 4, we can only prove consistency of spectral ordering under the technical condition that k
is large. We do not believe this is due to an artifact of the proof. Even though the structural matrix (the
signal) has large eigenvalues, the eigen-gap is not large enough. The spectral ordering succeeds when
the spectral gap stands out over the noise level, which implies that k needs to be large enough.
Let us compare the region described in Equation (9) with the reconstructable region in Equation (8).
15
We observe that spectral ordering pushes slightly beyond the reconstructable region when k Â n 16 , as
shown in Figure 2.
1

=n

y

,0 < y < 1

y

I

1/2
II

III

IV 0

1/4
IV
1/2

x
k = nx , 0 < x < 1

Figure 2: Phase diagram for small-world networks: impossible region (red region I), hard region (blue
region II), easy region (green region III), and reconstructable region (cyan region IV and IV’). Compared
15
to Figure 1, the spectral ordering procedure extends the reconstructable region (IV) when k Â n 16 (IV’).

5 Discussion
Reconstructable region We addressed the reconstruction problem via two distinct procedures, correlation thresholding and spectral ordering; however, whether there exists other computationally efficient
algorithm that can significantly improve upon the current reconstructable region is still unknown. Designing new algorithms requires a deeper insight into the structure of the small-world model, and will
probably shed light on better algorithms for mixed membership models.
Comparison to stochastic block model Recently, stochastic block models (SBM) have attracted considerable amount of attention from researchers in various fields. Community detection in stochastic
block models focuses on recovering the hidden community information from the adjacency matrix that
contains both noise and the latent permutation. The hidden community structure for classic SBM is
illustrated in Figure 3 (the left one), as a block diagonal matrix. An interesting but theoretically more
challenging extension to the classic SBM is the mixed membership SBM, where each node may simul-

10

taneously belong to several communities. The problem becomes more difficult when there are a growing number of communities and when each node belongs to several communities at the same time.
Consider one easy case of the mix membership model, where the mix membership occurs only within
neighborhood communities, as shown in the middle image of Figure 3. The small-world network we are
investigating in this paper can be seen as an extreme case (shown on the right-most figure) of this easy
mixed membership SBM, where each node falls in effectively k local clusters.

Figure 3: The structural matrices for stochastic block model (left), mixed membership SBM (middle),
and small-world model (right). The black location denotes the support of the structural matrix.
In the small-world networks, identifying the structural links and random links becomes challenging since that are many local clusters (in constrast to relative small number of communities in SBM).
This multitude of local clusters makes it difficult to analyze the effect of the hidden permutation on the
structural matrix. We view the current paper as an initial attempt at attacking this problem.

6 Technical Proofs
Proof of Theorem 1. Denote the circulant matrix by B (it is B π for any π ∈ S n−1 ). The likelihood on X ∈
Rn×n for WS model is
(
k
k
)
1 − β(1 − β n−1
β n−1
L n,k,β (X |B ) = exp log
· 〈X , B 〉 + log
· 〈X , J − I − B 〉
k
k
β(1 − β n−1
)
1 − β n−1
¾
k
k
+nk log(β(1 − β
)) + n(n − 1 − k) log(1 − β
)
n −1
n −1
(Ã
!
k
k
k
1 − β(1 − β n−1 )
β n−1
β n−1
= exp log
−
log
·
〈X
,
B
〉
+
log
· 〈X , J − I 〉
k
k
k
β(1 − β n−1
)
1 − β n−1
1 − β n−1
¾
k
k
+nk log(β(1 − β
)) + n(n − 1 − k) log(1 − β
) .
n −1
n −1
For the Erdős-Rényi model, the likelihood is
k
log n−1k
1 − n−1

(

L n,k (X ) = exp

)
k
· 〈X , J − I 〉 + n(n − 1) log(1 −
) .
n −1

11

The Kullback-Leibler divergence between this two model is expressed in the following
P B (X )
KL(P B ||P 0 ) = E X ∼P B log
P 0 (X )
( Ã

k
k
β n−1
k
n−1
= E X ∼P B − log
· 〈X , J − I 〉 − n(n − 1) log(1 −
)
− log
k
k
n −1
1 − n−1
1 − β n−1
Ã
!
)
k
k
β n−1
1 − β(1 − β n−1
)
k
k
− log
+ log
· 〈X , B 〉 + nk log(β(1 − β
)) + n(n − 1 − k) log(1 − β
)
k
k
n −1
n −1
)
β(1 − β n−1
1 − β n−1
Ã
! ¿
À
k
k
β n−1
k
k
n−1
= − log
)B + β
(J − I ), J − I
− log
· (1 − β)(1 − β
k
k
n −1
n −1
1 − n−1
1 − β n−1
Ã
! ¿
À
k
k
1 − β(1 − β n−1
)
β n−1
k
k
+ log
−
log
·
(1
−
β)(1
−
β
)B
+
β
(J
−
I
),
B
k
k
n −1
n −1
β(1 − β n−1
)
1 − β n−1

!

k
k
k
) + nk log(β(1 − β
)) + n(n − 1 − k) log(1 − β
)
n −1
n −1
n −1
"
#
¸
·
k
k
1 − β n−1
1 − β n−1
1
1
k
= n(n − 1) log
− nk log − log + log
nk 1 − (1 − β)β
k
k
β
β
n −1
1 − n−1
1 − n−1
"
#
·
¸
k
1 − β(1 − β n−1
)
1
k
+ log + log
nk 1 − β(1 − β
)
k
β
n −1
β n−1
·
·
¸
¸
k
1 − β n−1
k2
1
k
n (n − 1 − k) + (1 − β)β
= − log · nk 1 + β − β
+ log
k
β
n −1
n −1
1 − n−1
·
¸
k
1 − β(1 − β n−1 )
k
· nk 1 − β(1 − β
) .
+ log
k
n −1
β
− n(n − 1) log(1 −

(10)

n−1

Via the inequality log(1 + x) < x for all x > −1, we can further simplify the above expression as
·
¸
·
¸
k
(1 − β)(1 − β n−1
)
k
k2
2 k
KL(P B ||P 0 ) ≤ nk(1 − β) −β + β
+ (1 − β)β
+
nk (1 − β) + β
n −1
n(n − 1 − k)
n −1
β k
n−1

(11)
·
¸
k
(1 − β)2 (1 − β n−1
)
k
k2
≤ nk(1 − β) (1 − β)β
+ (1 − β)β
+
n(n − 1) ≤ C · n 2 (1 − β)2 ,
n −1
n(n − 1 − k)
β
(12)
2

k
where 0 < C < 12 n(n−1)
+ β1 is some universal constant (note we are interested in the case when β is close
to 1).
Remark that when k ¹ n 1/2 , the above bound can be further strengthened, in the following sense
(recall equation (10))

·
¸
·
¸
k
)
1 − β(1 − β n−1
k2
k
k
KL(P B ||P 0 ) ≤ nk(1 − β) −β + β
+ (1 − β)β
+ log
· nk 1 − β(1 − β
)
k
n −1
n(n − 1 − k)
n −1
β n−1
)
(
k
k
1 − β(1 − β n−1
) 1 − β(1 − β n−1
)
n
≤ log
·
· k 2β
.
k
k
n −1
β
β
n−1

n−1

12

Denote t :=

k
1−β(1−β n−1
)
k
β n−1

=

1−β n−1
β
k

+ β. Thus we have
KL(P B ||P 0 ) ≤ t log t · k 2 β

n
.
n −1

(13)

Suppose for some constant α∗ > 0, and α = α∗ · β1 (1 − n1 )2 , we have the following
t ≤α

n log ne

1

·

k2

n log n

log α k 2 e


n log n
log log α k 2 e
n log ne
n log ne


· 1−
<α
.
and t log t ≤ α
n log n
k2
k2
log α 2

(14)

(15)

k

Plug in the expression for t into (14), if
n

log e
1−β
1
1
k
log n
1
≤ α(1 +
)·
·
−
³
n log ne
n log ne
β
n −1
k
n
−
1
k
log α k 2
log k 2
we have
t ≤α

n log ne
k2

·

1
log α

n log ne
k2

⇒ t log t < α

(16)

n log ne
k2

which further implies (via equation (13))
X
n
1
KL(P B π ||P 0 ) ≤ t log t · k 2 β
≤ α∗ · log(n − 1)!.
(n − 1)! π∈S n−1
n −1

Recalling Equation (10), if
s

1−β ≤

n
α∗ (n − 1) log e
³
·
C
n2

s

log n
n

(17)

we have
X
1
KL(P B π ||P 0 ) ≤ n 2 (1 − β)2 ≤ α∗ · log(n − 1)!.
(n − 1)! π∈S n−1

We invoke the following Lemma on minimax error through Kullbak-Leibler divergence.
Lemma 5 (Tsybakov (2009), Proposition 2.3). Let P 0 , P 1 ,. . . , P M be probability measures on (X , A ) satisfying
M
1 X
KL(P j ||P 0 ) ≤ α · log M
M j =1

with 0 < α < 81 . Then for any ψ : X → [M + 1]
s
)
Ã
!
p
M
1 X
M
2α
P 0 (ψ 6= 0),
P j (ψ 6= j ) ≥ p
1 − 2α −
.
M j =1
log M
M +1

(

max

13

(18)

Collecting Equations (16) and (17), if either one of the conditions in Equations (16) and (17) holds,
we have
X
1
KL(P B π ||P 0 ) ≤ α∗ · log(n − 1)!.
(n − 1)! π∈S n−1

(19)

Putting things together, if
s

1−β ≺

log n log n
∨
,
n
k

we have that Equation (19) hold. Applying Lemma 5, we complete the proof
s
)
(
Ã
!
p
(n−1)!
X
1
(n − 1)!
2α
lim min max P 0 (φ 6= 0),
P i (φ 6= i ) ≥ lim
1 − 2α −
= 1−2α.
p
(n − 1)! i =1
log(n − 1)!
n→∞ φ
n→∞ 1 + (n − 1)!

Proof of Lemma 1. Let us state the well-known Bernstein’s inequality (Boucheron et al. (2013), Theorem
2.10), which will be used in the proof of this lemma.
Lemma 6 (Bernstein’s inequality). Let X 1 , . . . , X n be independent bounded real-valued random variables.
Assume that there exist positive numbers v and c such that
n
X
i =1

E[X i2 ] ≤ v,

X i ≤ 3c, ∀1 ≤ i ≤ n a.s.
then we have, for all t > 0,
Ã
P

n
X

!
p
(X i − E X i ) ≥ 2v t + c t ≤ e −t .

(20)

i =1

First, let us consider the case when the adjacency matrix A is generated from the Erdős-Rényi random
k
graph ER(n, n−1
). Recall Bernstein’s inequality Lemma 6, for any P π with π ∈ S n−1 , we know 〈P π B P πT , A〉
has the same distribution as 〈B, A〉. Thus
in law

〈P π B P πT , A〉 == 〈B, A〉 = 2
=2

X

X

Ai j Bi j

i>j

E[A i j ]B i j + 2

i>j

X

(A i j − E[A i j ])B i j

i>j

k
nk + 2
≤
n −1

s

k
2
nkt + t
n −1
3

with probability at least 1 − exp(−t ). Here the last step is through Bernstein’s inequality. There are nk/2
P
k
k
non-zero B i , j , i > j , and it is clear that A i j ∼ Bernoulli( n−1
), 2 i > j E[A i j ]B i j = nk n−1
. Thus we can take
1
c = 3 and
X
X
nk k
v=
E[A i j B i j ]2 =
E[A i j ]2 B i j =
2 n −1
i<j
i<j
14

in Lemma 6. Via the union bound, take t = log n!, we have
s
k
k
2
max 〈P π B P πT , A〉 ≤
nk + 2
nk · log n! + · log n!
Pπ
n −1
n −1
3
with probability at least 1 − (n − 1)! exp(− log n!) = 1 − n1 .
Alternatively, suppose A is from the small-world rewiring model WS(n, k, β), with permutation being
the identity π = e. With probability at least 1 − exp(− log n) = 1 − n1 ,
max 〈P π B P πT , A〉 ≥ 〈B, A〉
Pπ

= 〈B, E[A]〉 + 〈B, A − E[A]〉
q
k
≥ (1 − β + β2
)nk − nk · log n
n −1
where the last step is from Hoeffding’s inequality: it is clear that for location (i , j ) when B i j 6= 0,
E[A i j ] = 1 − β + β2

k
,
n −1

and 0 ≤ A i j ≤ 1 almost surely.
Therefore if there exist a threshold T > 0 such that
q
k
k
(1 − β + β2
)nk − nk · log n > T >
nk + 2
n −1
n −1

we have that

s

2
k
nk · log n! + · log n!
n −1
3

(21)

)
(n−1)!
X
1
1
P i (φ1 6= 1) ≤ lim
P 0 (φ1 6= 0),
= 0.
n,k(n)→∞ n
(n − 1)! i =1

(

lim

n,k(n)→∞

max

The detailed calculation of Equation (21) yields that the test succeeds with high probability whenever
s
log n log n
1−β º
∨
.
n
k

Proof of Lemma 2. Under the rewiring model (Watts-Strogatz model) WS(n, k, β) with permutation P π
P π AP πT = (1 − β)(1 − β

k
k
)·B +β
· (J − I ) + Z
n −1
n −1

where J = 11T ∈ Rn×n , B is the ring structured signal matrix defined in Equation (2). We denote in short
A = E A + Z as this signal and the noise part, and
½

Bi j =

1 if 0 < |i − j | ≤ k2 mod n − 1 − k2
0
elsewhere

B is a circulant matrix, whose spectrum is highly structured, and Z is a zero-mean noise random matrix.
We first study the random fluctuation part, Z = A − E A. Let us bound the expectation EkA − E Ak
as a starting step, for any adjacency matrix A ∈ Rn×n using the symmetrization trick. Denote A 0 ∼ A
15

as the independent copy of A sharing the same distribution. Take E ,G ∈ Rn×n as random symmetric
Rademacher and Gaussian matrices with entries E i j , G i j being, respectively, independent Rademacher
and Gaussian. Denoting A ◦ B as matrix Hadamard product, we have
EkA − E Ak = E sup 〈(A − E A)v, v〉 = E sup 〈(A − E A 0 A 0 )v, v〉
kvk`2 =1

kvk`2 =1
0

≤ E A E A 0 sup 〈(A − A )v, v〉 = EE E A E A 0 sup 〈[E ◦ (A − A 0 )]v, v〉
kvk`2 =1

kvk`2 =1

≤ E A EE sup 〈[E ◦ A]v, v〉 + E A 0 EE sup 〈[−E ◦ A 0 ]v, v〉
kvk`2 =1

kvk`2 =1

2
= 2E A EE sup 〈[E ◦ A]v, v〉 ≤ p
· E A EE sup 〈[EG [|G|] ◦ E ◦ A]v, v〉
2/π
kvk`2 =1
kvk`2 =1
r
r
π
π
· E A EE EG sup 〈[|G| ◦ E ◦ A]v, v〉 =
· E A EG sup 〈[G ◦ A]v, v〉
≤
2
2
kvk`2 =1
kvk`2 =1
r
π
=
· E A (EG kG ◦ Ak) .
2
Recall the following Lemma from Bandeira and van Handel (2014).
Lemma 7 (Bandeira and van Handel (2014), Theorem 1.1). Let X be the n × n symmetric random matrix
with X = G ◦ A, where G i j , i < j are i.i.d. N (0, 1) and A i j are given scalars. Then
EG kX k ≤ max
i

sX
j

A 2i j + max |A i j | ·
ij

q

log n.

Thus via Jensen’s inequality and the above Lemma, we can continue
r
π
EkA − E Ak ≤
· E A (EG kG ◦ Ak)
2
sX
q
2
A i j + max |A i j | · log n
- E A max
i

≤

j

s
q
X
E A max A 2i j + log n
i

r

≤

ij

k +C 1 2

j

q

k log n +C 2 log n +

q
q
p
log n ³ k ∨ log n,

where the last step uses Bernstein inequality Lemma 6. Moving from expectation EkA − E Ak to concentration on kA − E Ak is through Talagrand’s concentration inequality (see, Talagrand (1996) and Tao (2012)
Theorem 2.1.13), since k·k is 1−Lipschitz convex function in our case (and the entries are bounded), thus
with probability at least 1 − n1 ,
kA − E Ak ≤ EkA − E Ak +C ·

q

log n ³

q
p
k ∨ log n.

Now let us study the structural signal part. Matrix B is of the form circulant matrix, the associated
polynomial is
x k/2 − 1
f (x) = (x + x n−k/2 ) ·
.
x −1
16

The eigen-structure is: collect for all j = 0, 1, ..., n/2
(cos 0, cos

2π j
2π2 j
2πn j
, cos
, . . . , cos
)
n
n
n

(sin 0, cos

2π j
2π2 j
2πn j
, sin
, . . . , sin
)
n
n
n

and

and the corresponding eigenvalue is
k/2
X

¶
2π j
λ j = f (w j ) = 2 cos i
.
n
i =1

Let us first assume

k
n

µ

≤ 12 , thus λ is the second largest eigenvalue
µ
¶
2 sin kπ
2π
(k + 2)π
2n
λ = 2 cos i
=
³ k.
π cos
n
sin n
2n
i =1
k/2
X

Using Weyl’s interlacing inequality, if there exist a T > 0 such that
λ2 (A WS ) ≥ λ2 (E[A WS ]) − kZ k > T > kZ 0 k > λ2 (A ER ),
where
q
p
k
λ2 (M ) − kZ k ≥ (1 − β)(1 − β
)λ − k ∨ log n,
n −1
q
p
kZ 0 k ≤ k ∨ log n,

then we have

(

lim

n,k(n)→∞

max

)
(n−1)!
X
1
P 0 (φ2 6= 0),
P i (φ2 6= 1) = 0.
(n − 1)! i =1

Therefore, we have the condition for which the second eigenvalue test succeeds:
q
p
k
)λ > k ∨ log n
n −1
p
p
r
log n
k log n ∨ log n
k
1
(1 − β)(1 − β
)>
∨
.
³
kπ
2 sin 2n
n −1
k
k
(k+2)π
cos
2n
sin π

(1 − β)(1 − β

n

Proof of Lemma 3. Take any two vectors A i · , A j · that are two rows of the adjacency matrix. Denote the
i , j -th rows have distance |π−1 (i )−π−1 ( j )|ring = x. This is equivalent to saying that the Hamming distance
of the corresponding signal vectors satisfies H(B i · , B j · ) = 2x − 2. Therefore the union of signal nodes for
i , j -th row is of cardinality |S i ∪ S j | = k + x − 1, common signal nodes is of cardinality |S i ∩ S j | = k − x + 1,

17

unique signal is of cardinality |S i 4S j | = 2x − 2, and |S ic ∩ S cj | = n − k − x − 1. The signal nodes is 1 with
k
k
), non signal is 1 with probability q = β n−1
, and we have
probability p = 1 − β(1 − β n−1

〈A i · , A j · 〉 =

X

X

Ai l A j l +

l ∈S i ∩S j

Ai l A j l +

X

Ai l A j l .

l ∈S ic ∩S cj

l ∈S i 4S j

©
ª
Observe as long as l 6= i , j , A i l and A j l are independent, and A i l A j l , l ∈ [n]\{i , j } are independent of
each other.
Let us bound each term via Bernstein’s inequality Lemma 6,
¶
µq
X
1
2
2
2p |S i ∩ S j |t + t
A i l A j l ∈ p |S i ∩ S j | ±
3
l ∈S i ∩S j
µq
¶
X
1
A i l A j l ∈ pq|S i 4S j | ±
2pq|S i 4S j |t + t
3
l ∈S i 4S j
¶
µq
X
1
2q 2 |S ic ∩ S cj |t + t
A i l A j l ∈ q 2 |S ic ∩ S cj | ±
3
l ∈S c ∩S c
i

j

with probability at least 1 − 6 exp(−t ). We take t = (2 + ²) log n for any ² > 0, such that with probability at
least 1 −C n −² , the above bound holds for all pairs (i , j ).
Thus for all |π−1 (i ) − π−1 ( j )|ring > k pairs,
2

〈A i · , A j · 〉 ≤ 2kpq + (n − 2k − 2)q +

µq

4kpq t +

q

2(n − 2k − 2)q 2 t

¶

+t ,

for |π−1 (i ) − π−1 ( j )|ring ≤ x pairs
µq
¶
q
p
2
2
〈A i · , A j · 〉 ≥ (k − x + 1)p + (2x − 2)pq + (n − k − x − 1)q −
2(k − x + 1)p t + 2(2x − 2)pq t + 2(n − k − x − 1)q t + t .
2

2

k
k
) and q = β n−1
, if x < x 0 with
Thus, with t = (2 + ²) log n, p = 1 − β(1 − β n−1

x0
:= 1 −C 1
k

s

log n 1
−C 2
k 1−β

s

log n
1
,
n (1 − β)2

we have
µq
¶
q
p
p
2
2
(k − x + 1)(p − q) ≥ 2t + (2 2 + 1)
kp + nq
2t
µq
¶
q
q
q
p
p
2
2
2
≥ 2t +
2kpq + (n − 2k − 2)q + (k − x + 1)p + (2x − 2)pq + (n − k − x − 1)q
2t ,
2

which further implies,
min

j :|π−1 (i )−π−1 ( j )|ring ≤x 0

〈A i · , A j · 〉 ≥ max

j ∉N (v i )

〈A i · , A j · 〉, ∀i

|Nˆ (v i )4N (v i )| k − x 0
max
≤
= C1
i ∈[n]
|N (v i )|
k
18

s

log n 1
+C 2
k 1−β

s

log n
1
.
n (1 − β)2

Therefore we can reconstruct the neighborhood consistently, under the condition
s
µ
¶
log n 1/4
log n
∨
.
1−β Â
k
n

Proof of Lemma 4. Since eigen-structure is not affected by permutation, we will work under the case
when the true permutation is identity. We work under a mild technical assumption that we have two
independent observation of the adjacency matrix, one used for calculated the eigen-vector, the other
used for projection. Note this is only a technical assumption for simplicity, and does not affect the thek
k
oretical result. Recall that A = M + Z , where M = (1 − β)(1 − β n−1
) · B + β n−1
· (J − I ) is the signal matrix.
n×n
Denote the eigenvectors of M to be U ∈ R
, and eigenvectors of A to be Û ∈ Rn×n . Classic Davis-Kahan
perturbation bound informs us that
kÛ·2 −U·2 k ≤

kZ k
kZ k
, kÛ·3 −U·3 k ≤
,
∆λ − kZ k
∆λ − kZ k

where the spectral gap ∆λ of M is
"
µ
µ
¶
¶#
k/2
k/2
X
X
2π
2π · 2
k
k
∆λ := (1 − β)(1 − β
) · (λ2 − λ3 ) = (1 − β)(1 − β
) · 2 cos i
− 2 cos i
n −1
n −1
n
n
i =1
i =1
"
#
kπ
kπ
2 sin 2n
k
(k + 2)π
(k + 2)π 2 sin n
k k3
= (1 − β)(1 − β
cos
)
−
³
(1
−
β)(1
−
β
) .
π cos
n −1
sin n
2n
n
n − 1 n2
sin 2π
n

From the proof of Lemma 2, we know with high probability
q
p
kZ k ¹ k ∨ log n.
We denote
tan θ̂i =

T
Û·3
A ·i
T
Û·2
A ·i

,

and
〈U·3 , M ·i 〉
tan θi =
=
〈U·2 , M ·i 〉

λ
p2 sin (i −1)2π
n
n
λ2
(i
−1)2π
p cos
n
n

= tan

(i − 1)2π
.
n

Observe that
tan θ̂i =

〈Û·3 , A ·i 〉
〈Û·2 , A ·i 〉

,

and for both the denominator and numerator, we have the bound
〈Û·2 , A ·i 〉 = 〈(Û·2 −U·2 ) +U·2 , M ·i + Z·i 〉
= 〈U·2 , M ·i 〉 + 〈Û·2 −U·2 , M ·i 〉 + 〈Û·2 , Z·i 〉
≤ U·2 , M ·i 〉 + kÛ·2 −U·2 kkM ·i k + |〈Û·2 , Z·i 〉|.
19

(22)

Thus we know
©
ª
max |〈Û·2 , A ·i 〉 − 〈U·2 , M ·i 〉|, |〈Û·3 , A ·i 〉 − 〈U·3 , M ·i 〉|
©
ª
≤ max kÛ·2 −U·2 kkM ·i k + |〈Û·2 , Z·i 〉|, kÛ·3 −U·3 kkM ·i k + |〈Û·3 , Z·i 〉|
p
p
q
p
k ∨ log n
·
k(1
−
β)
+
log n
≤
p
p
λ2 − λ3 − k ∨ log n

(23)
(24)
(25)

where the last line follows from the definition of principal angle and Davis-Kahan bound and Hoeffding’s
inequality for 〈Û·2 , Z·i 〉. Proceeding with Equation (22), without loss of generality, assume 0 ≤ (i −1)2π
≤ π2 ,
n
for 0 ≤ (i −1)2π
≤ π4
n
p p
p
p
k∨ log n
λ2
(i
−1)2π
p sin
p p
+
· k(1 − β) + log n
n
n
λ2 −λ3 − k∨ log n
tan θ̂i ≤
(26)
p p
p
p
k∨ log n
λ
p2 cos (i −1)2π −
p
p
· k(1 − β) − log n
n
n
λ2 −λ3 − k∨ log n
(
)
p
p
p
q
p
sin (i −1)2π
+δ
k ∨ log n
n
n
, with δ =
·
=
· k(1 − β) + log n
(27)
p
p
λ2
λ2 − λ3 − k ∨ log n
−δ
cos (i −1)2π
n
tan θ̂i ≥

−δ
sin (i −1)2π
n
cos (i −1)2π
+δ
n

,

(28)

with similar bounds for cot θ̂i with
δ³

2.5

n
1
k 3 1−β

π
4

(i −1)2π
n

≤

≤

π
2.

Here the stochastic eror is bounded in the sense

→ 0. From the above equation, we have
|θ̂i − θi | ≤ min{| tan θ̂i − tan θi |, | cot θ̂i − cot θi |}
¾
½
2δ
δ(1 + tan θi ) δ(1 + cot θi )
,
≤ 1
.
≤ min
cos θi − δ
sin θi − δ
p −δ
2

For any i , we have the bound on the stochastic error |θ̂i − θi | < C · δ ³
neighborhood, the support is |θ j − θi | ≤
min

j ∉N (v i )

|θ̂ j − θ̂i | ≥

2πk
n .

n 2.5 1
.
k 3 1−β

And for all j ∈ N (i ) in the

Fix any i , for any j ∉ N (v i ),

2πk
2πk
max
|θ̂ j − θ̂i |,
−C δ > (
−C 0 δ) +C δ ≥
| j −i |<k−C 0 nδ
n
n

p
with C ≤ 4 2 and C 0 > 2C . Therefore, the following bound on symmetric set difference holds
2.5

n
0
|Nˆ (v i )4N (v i )| C 0 · nδ C · n · k 3
max
≤
≤
i ∈[n]
|N (v i )|
k
k

In summary under the condition
n 3.5
,
k4
one can recover the neighborhood consistently w.h.p. in the sense
1−β Â

|Nˆ (v i )4N (v i )|
= 0.
n,k(n)→∞ i ∈[n]
|N (v i )|
lim

max

20

1
1−β

.

acknowledgement
The authors thank Elchanan Mossel for many helpful discussions and suggestions for improving the
paper.

References
Luıs A Nunes Amaral, Antonio Scala, Marc Barthelemy, and H Eugene Stanley. Classes of small-world
networks. Proceedings of the national academy of sciences, 97(21):11149–11152, 2000.
Afonso S Bandeira and Ramon van Handel. Sharp nonasymptotic bounds on the norm of random matrices with independent entries. arXiv preprint arXiv:1408.6185, 2014.
Alain Barrat and Martin Weigt. On the properties of small-world network models. The European Physical
Journal B-Condensed Matter and Complex Systems, 13(3):547–560, 2000.
Itai Benjamini and Noam Berger. The diameter of long-range percolation clusters on finite cycles. arXiv
preprint math/0012070, 2000.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic
theory of independence. OUP Oxford, 2013.
Don Coppersmith, David Gamarnik, and Maxim Sviridenko. The diameter of a long range percolation
graph. In Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, pages
329–337. Society for Industrial and Applied Mathematics, 2002.
Robert M Gray. Toeplitz and circulant matrices: A review. now publishers inc, 2006.
Jon Kleinberg. The small-world phenomenon: An algorithmic perspective. In Proceedings of the thirtysecond annual ACM symposium on Theory of computing, pages 163–170. ACM, 2000.
Vito Latora and Massimo Marchiori. Efficient behavior of small-world networks. Physical review letters,
87(19):198701, 2001.
Stanley Milgram. The small world problem. Psychology today, 2(1):60–67, 1967.
Cristopher Moore and Mark EJ Newman. Epidemics and percolation in small-world networks. Physical
Review E, 61(5):5678, 2000.
Mark EJ Newman and Duncan J Watts. Scaling and percolation in the small-world network model. Physical Review E, 60(6):7332, 1999.
CJ Stam, BF Jones, G Nolte, M Breakspear, and Ph Scheltens. Small-world networks and functional connectivity in alzheimer’s disease. Cerebral cortex, 17(1):92–99, 2007.
Michel Talagrand. A new look at independence. The Annals of probability, pages 1–34, 1996.
Terence Tao. Topics in random matrix theory, volume 132. American Mathematical Soc., 2012.
Alexandre B Tsybakov. Introduction to nonparametric estimation, volume 11. Springer Series in Statistics,
2009.
21

Remco Van Der Hofstad. Random graphs and complex networks. Available on http://www. win. tue.
nl/rhofstad/NotesRGCN. pdf, page 11, 2009.
Duncan J Watts. Small worlds: the dynamics of networks between order and randomness. Princeton
university press, 1999.
Duncan J Watts and Steven H Strogatz. Collective dynamics of ‘small-world’networks. nature, 393(6684):
440–442, 1998.

22

