EDGE SAMPLING USING NETWORK LOCAL INFORMATION

arXiv:1710.04772v1 [math.ST] 13 Oct 2017

CAN M. LE
Abstract. Edge sampling is an important topic in network analysis. It provides a natural way to reduce network size while retaining desired features of the original network.
Sampling methods that only use local information are common in practice as they do
not require access to the entire network and can be parallelized easily. Despite promising
empirical performance, most of these methods are derived from heuristic considerations
and therefore still lack theoretical justification. To address this issue, we study in this
paper a simple edge sampling scheme that uses network local information. We show
that when local connectivity is sufficiently strong, the sampled network satisfies a strong
spectral property. We quantify the strength of local connectivity by a global parameter
and relate it to more common network statistics such as clustering coefficient and Ricci
curvature. Based on this result, we also derive a condition under which a hypergraph
can be sampled and reduced to a weighted network.

1. Introduction
Network analysis has become an important area in many research domains. It provides
a natural way to model and analyze data in the presence of complex interdependence
among entities. A network typically consists of a set of nodes representing the entities of
interest and a set of edges between nodes encoding the relations between the nodes. For
example, in a social network such as Facebook or Twitter, nodes are users and there is an
edge between two users if they are friends. Studying the structure of a network provides
valuable information about how entities interact and may help predict the formmation of
different groups [12, 10].
As real-world networks are often very large, it is difficult and often impossible to store
or even get access to the entire data set. It is therefore desirable to preprocess the data
to reduce the network size before performing any analysis. A natural method that has
been studied in network literature is to reduce the number of edges, also known as graph
sparsification [6, 41, 40]. For a network of n nodes, instead of storing possibly n2 edges,
one can sample and store just O(n log n) edges and still retain some features of the original
network, depending on the sampling scheme [30, 40].
One of the simplest sampling schemes is to independently delete edges with probability
1 − ε, where ε ∈ (0, 1) is a tuning parameter; this is also known as bond percolation
[3, 27, 8, 30]. For a network G = (V, E) with the set of nodes V and the set of edges
E, the adjacency matrix A is a symmetric matrix with entries Aij = 1 if there is an
edge between node i and node j, and Aij = 0 otherwise. If ε is sufficiently large so that
Ω(n log n) edges are retained, then by a concentration inequality [30],
p
kAε − εAk = O( εkAk log n).

Here Aε is the adjacency matrix of the sparsified network and hereafter k.k denotes the
operator norm. The advantage of this sampling scheme is that it can be done separately
for every edge without additional information from other edges. However, this method
1

2

CAN M. LE

only preserves cuts of large sets of nodes [41]; here, the cut of a set of nodes is the number
of edges between that set and its complement in V .
Another sampling scheme that approximately preserves all cuts is proposed by [40].
Instead of using the same probability ε as in bond percolation model, each edge is now
sampled with a probability proportional to its effective resistance. Under this sampling
scheme, the (weighted) sparsified network H of G, also known as the spectral sparsifier,
satisfies
(1 − ε)xT LG x ≤ xT LH x ≤ (1 + ε)xT LG x
(1.1)
for all vectors x. Here LG P
= D − A denotes the Laplacian of G, where D is the diagonal
matrix with degrees di = j∈V Aij on the diagonal; similarly, LH = DH − WH denotes
the Laplacian of H, where WH = (wij ) is the
Pweighted adjacency matrix of H and DH is
the diagonal matrix with weighted degrees nj=1 wij on the diagonal. Despite the strong
spectral property, this method requires access to the entire network for computing effective
resistances of edges, which may be prohibitive in practice. Also, the computation involves
a complicated linear system solver of Spielman and Teng that is not easy to implement
in practice. Although some improvements of [40] are now available, they still rely on
complicated linear system solvers [19, 18].
It has been observed that many real networks have very strong non-Euclidian local
structure [46, 43]. This reflects the belief that incident nodes exhibit the transitivity
property: if i and j are connected and j and k are connected then it is likely that j and k
are also connected. One way to quantify the transitivity is via clustering coefficient [46].
For each node i ∈ V , the local clustering coefficient of i is defined as the ratio between the
number of triangles containing i and the maximum number of triangles it can form with
incident nodes
|{(j, k) ∈ E : (i, j) ∈ E, (i, k) ∈ E}|
.
ci =
di (di − 1)/2
The clustering coefficient of a network G is the average of all local clustering coefficients
1 X
ci .
c=
|V |
i∈V

Another measure of network transitivity that has recently attracted much attention is
the Ricci curvature [4, 17, 24, 7] . In Riemanian geometry, Ricci curvature is a fundamental
quantity that measures the degree to which the local geometry of a manifold deviates from
Euclidian geometry. It is well known that a manifold has positive Ricci curvature if and
only if the geodesic distance between any two close points is larger than the optimal
transportation distance between two small balls around these points [45]. Based on this
property, the notion of Ricci curvature has been extended to metric spaces by [31]. In
particular, when the metric space is a network equipped with the geodesic distance, Ricci
curvature is closely related to the local clustering coefficient [17].
Network local information has been used by several edge sampling methods that aim at
preserving certain features of networks such as number of connected components, diameter,
homophily, node centrality measures or community structure [28]. These methods sample
each edge of a network according to certain edge scores that depend for instance on Jaccard
similarity score [36], the number of triangles [14] or the number of quadrangles containing
the edge [29]; see also [14] for methods based on other local measures. Although these
methods have been empirically shown to perform well and can be parallelized easily, to
our best knowledge, there is still no theoretical guarantee of their performance. It is

3

also unclear if other features of networks (besides the targeting features considered) are
preserved.
To address this issue, we study in this paper a simple edge sampling scheme similar
to methods that use Jaccard similarity or number of triangles [36, 14]. Specifically, we
sample each edge (i, j) ∈ E of a network G = (V, E) with probability proportional to the
number of common neighbors that i and j have. For simplicity, we assume that numbers of
common neighbors are known for all edges. In practice, these numbers can be computed
exactly in parallel fashion [32, 14] or approximated by hashing [36, 37, 38]. We show
that when the local connectivity of a network is sufficiently strong, our sampling method
satisfies the spectral property (2.3); this provides theoretical evidence supporting edge
sampling methods based on local information [36, 29, 14].
Intuitively, as numbers of common neighbors increase, the network transitivity becomes
stronger and our sampling scheme becomes more similar to the sampling scheme using
effective resistances of edges. In contrast, as numbers of common neighbors decreases,
the sampling scheme become more similar to bond percolation. We quantify this intuition
using a global measure and relate it to the network transitivity and Ricci curvature. Based
on this result, we also derive a condition under which a hypergraph can be sampled and
reduced to a weighted graph. While the sparsified network under our sampling scheme
approximately preserves all cuts, it is interesting that the approximation accuracy only
depends on the average of local features. This result also confirms the usefulness of
network local information observed for example in the context of community detection
[33, 36, 35, 9, 11].
2. Edge sampling using common neighbors
We are interested in finding a sparsifier of G = (V, E) that satifies the spectral notion of
similarity introduced by Spielman and Teng [41, 42]. A sparsifier of G is a weighted sparse
network H = (V, EH , WH ) such that EH ⊆ EG and (1.1) holds for any vector x ∈ Rn .
Note that (1.1) is equivalent to (1 − ε)LG  LH  (1 + ε)LG and we write X  Y if Y − X
is a semi-positive definite matrix.
For each edge (i, j) ∈ E, let Tij be the number of common neighbors of i and j. To
form a sparsifier H = (V, EH , WH ), we sample m edges of G independently according to
a multinomial distribution with probabilities
pij = P

2
Tij +2

2 .
(i,j)∈EG Tij +2

(2.1)

If an edge (i, j) ∈ EG of the original graph G is selected, we add an edge to H with the
weight (mpij )−1 . Weights of edges of H are summed if edges are selected more than once.
Theorem 2.1 (Edge sampling using common neighbors). Consider an undirected connected graph G = (V, E). For each edge (i, j) ∈ E denote by Tij the number of common
neighbors of i and j. Let ε ∈ (0, 1) and denote
1 X
2
α=
.
(2.2)
n
Tij + 2
(i,j)∈EG

Form a weighted graph H by sampling 8αn log n/ε2 edges of G as described above. Then
with probability at least 1 − 1/n the following holds:
(1 − ε)LG  LH  (1 + ε)LG .

(2.3)

4

CAN M. LE

Parameter α in (2.2) measures the average strength of network local connectivity. When
the local connectivity is strong, i.e. α = O(1), Theorem 2.1 shows that we can preserve
network topology if we locally sample and retain O(n log n) edges. In contrast, if the
local connectivity is weak (for example when Tij = O(1)) then pij are similar, therefore
the sampling scheme is similar to bond percolation. Table 1 shows the value of α and
clustering coefficient c for some well-known real-world networks. Note that while these
networks are relatively sparse, their values of α are quite small, which suggests that realworld networks have strong local connectivity. The proof of Theorem 2.1 is given in
Appendix A.
Data
n
Average degree Clustering coefficient
Karate Club [47]
34
4.59
0.59
Dolphins [25]
62
5.13
0.30
Political Blogs [1]
1222
27.36
0.36
Ego-Facebook [26]
4039
43.69
0.62
Astro Physics Collaboration [22] 18772
21.10
0.68
Enron Email [21]
36692
10.02
0.72

α
1.40
1.58
3.04
1.96
1.94
1.56

Table 1. Statistics of some real-world networks.

3. Lower bound on parameter α
The following lemma provides a lower bound for parameter α in term of clustering
coefficient c and degrees di .
Lemma 3.1 (Lower bound on parameter α). For any undirected connected graph the
following holds:
1
.
(3.1)
α≥
2 P
4c + n i∈V d1i
Proof. For each node i, denote by Ni and ti the set of neighbors of i and the number of
triangles that contain i, respectively. Using Lemma A.2, we have
X
d2i
2|Ni |2
1
2
.
=
≥P
≥
Tij + 2
ti + di
2ci + d1
j∈Ni (Tij + 2)
j∈Ni

i

Summing over all nodes i and applying Lemma A.2 again, we obtain
X
X
n
1
4
|V |2

=
≥
≥
P
P
1
1
1
Tij + 2
2ci + di
2c + n i∈V
i∈V
(i,j)∈E
i∈V 2ci + di
The proof is complete by dividing both sides of this inequality by 2n.

1
di

.


Remark 3.2 (Order of parameter
α in Theorem 2.1). Lemma 3.1 provides a lower bound
P
for α in (2.2). If c & 1/n i∈V 1/di then the constant α in Theorem 2.1 satisfies α & 1/c.
The proof of Lemma 3.1 suggests that the upper bound α . 1/c also holds if Tij are
similar for most of edges of G. Table 1 provides a numerical evidence supporting this
heuristic argument.

5

Clearly, the bound α . 1/c does not hold for all networks. Below is an example of a
network for which two sides of (3.1) are of different orders. Let G = Rn ∪ Kn be the union
of a random d-regular graph Rn (c = d/n) of size n and a complete graph Kn (c = 1),
also of size n (we can connect Rn and Kn by an arbitrary edge to make G a connected
graph). If d = o(n) then an easy calculation shows that the left hand-side of (3.1) is of
order n2 /d while the right hand-side is of order n.
4. Upper bound on parameter α
In this section we recall the definition of Ricci curvature for graphs and show that if the
Ricci curvature of a graph is bounded from below by some constant κ0 > 0 then α ≤ 1/κ0 .
For a graph G, denote by d(i, j) the length of a shortest path connecting nodes i and
j. We attach to each node i of G a uniform probability measure mi with support being
the set of neighbors of i:
 1
di , if k ∈ Ni
mi (k) =
0, otherwise.
The optimal transportation distance between mi and mj is defined as follows:
X
W1 (mi , mj ) =
inf
d(k, k′ )ξ(k, k′ ),
ξ∈Π(mi ,mj )

(k,k ′ )∈V ×V

where Π(mi , mj ) is the set of all probability measures on V × V with marginals mi and
mj . Intuitively, ξ(k, k ′ ) represents the mass transported from k to k′ , and W1 (mi , mj )
is the optimal cost for moving a unit mass distributed evenly among neighbors of i to
neighbors of j. With this notion of distance between probability measures on G, the Ricci
curvature of two nodes i and j is defined by
κ(i, j) = 1 −

W1 (mi , mj )
.
d(i, j)

Figure 1 shows Zachary’s karate club network [47] together with information of Ricci
curvatures of incident nodes (edges). Edges with negative curvatures are in blue, positive
curvatures – in red and zero curvatures – in black; widths of edges are proportional to
magnitudes of curvatures.
A lower bound κ ≥ κ0 > 0 on the curvature implies that W1 (mi , mj ) ≤ (1−κ0 )d(i, j) for
each pair of nodes i and j. In particular, if i and j are neighbors then W1 (mi , mj ) ≤ 1−κ0 .
Note that if G is a connected graph then the inverse is also true: If W1 (mi , mj ) ≤ 1 − κ0
holds for all pairs of neighbors i and j then W1 (mi , mj ) ≤ (1 − κ0 )d(i, j) holds for all
(i, j) ∈ V × V by a triangle inequality.
For social networks, positive Ricci curvature reflects the idea that people are better
off with the help of friends. Imagine that person i needs to transfer money to person j
who is not his friend. Without knowing the best route to reach j, i divides the money
and asks his friends to help him transfer the money to j. Similarly, j asks his friends to
accept the transferred money on his behalf. Positive Ricci curvature ensures that the cost
of transferring money in this way is smaller than the cost of sending money directly along
a shortest path.
Ricci curvature is also closely related to a simple random walk on a graph. If κ ≥ κ0 > 0
then [31] shows that the spectral gap between the two largest eigenvalues of the transition
probability matrix D −1 A is bounded from below by κ0 (see also [4] for an improvement

6

CAN M. LE

Figure 1. Zachary’s karate club network [47]. Edges with negative Ricci
curvatures are in blue, positive Ricci curvatures – in red and zero Ricci
curvatures – in black; widths of edges are proportional to magnitudes of
Ricci curvatures.
of the bound). Thus, Ricci curvature of a graph controls how fast a simple random walk
on that graph mixes.
Lemma 4.1 (Upper bound on parameter α). If the Ricci curvature κ of a graph G satisfies
κ ≥ κ0 for some constant κ0 > 0 then α ≤ 1/κ0 .
Proof. Consider an edge (i, j) of G. The masses of mi and mj are evenly distributed
among neighbors of i and j, respectively. To transport mi to mj , except those masses at
common neighbors of i and j that may not have to be moved, we need to move the rest
along routes of distances at least one. Since the masses that do not require transportation
is at most cij · min{1/di , 1/dj } and d(i, j) = 1, we have
1 − κ0 ≥ W1 (mi , mj ) ≥ 1 − cij · min{1/di , 1/dj }.
This implies cij ≥ κ0 / min{1/di , 1/dj }. Summing over all edges (i, j) of G, we obtain
X
1 XX
n
2 X
2
min{1/di , 1/dj } =
min{1/di , 1/dj } ≤ .
≤
2 + cij
κ0
κ0
κ0
i∈V j∈Ni
(i,j)∈E
(i,j)∈E
P
For the last inequality we use the fact that
j∈Ni min{1/di , 1/dj } ≤ 1. The proof is
complete.

Remark 4.2. Lemma 4.1 requires that Ricci curvatures of all edges of graph G are bounded
from below by κ0 . This assumption can be relaxed by a weaker assumption that the
number of edges with Ricci curvatures less than κ0 is of order O(n). With this assumption,
the upper bound of α becomes α ≤ 1/κ0 + O(1).
5. Sparsifying Hypergraphs
Strong local conectivity of a network is often caused by the fact that each node belongs
to several tightly connected small groups [13]. To simplify the analysis, we assume in this
section that within each small group, all nodes are connected. Under this assumption,
a network can be modeled by a hypergraph G = (V, E) which consists of a set of nodes

7

V and a set of hyperedges E where each hyperedge is a subset of V . We derive in this
section a condition under which a hypergraph can be sampled and reduced to a weighted
network. This provides an example when our sampling scheme works well and may be
useful in practice as a computational acceleration technique.
The Laplacian previously defined for networks can be naturally extended to hypergraphs
through clique expansion [34, 2]. For a hypergraph G = (V, E), the evaluation of the
Laplacian LG at a vector x is defined by
XX
LG (x) =
(xi − xj )2 .
e∈E i,j∈e

If we view x as a function on V then LG (x) measures the smoothness of x and it occurs
naturally in many problems of estimating smooth functions [39, 5, 16, 20, 23].
Let G = (V, E, W ) be a weighted graph such that (i, j) ∈ E if and only if both i and
j belong to at least one hyperedge of G; the weight wij of edge (i, j) is the number of
hyperedges that both i and j belong to. It is easy to see that LG (x) = xT LG x for every
x, where LG is the Laplacian of the weighted graph G defined by
X
xT L G x =
wij (xi − xj )2 .
(i,j)∈E

Thus, if we are only interested in smoothness induced by G of functions on V then we can
replace G with G. We call G the weighted graph induced by G.
To form a sparsifier H = (V, EH , WH ) of G, we sample with replacement m edges of G
with probability
Pij = P

−1
Cij
(i,j)∈EG

−1 ,
Cij

where Cij =

X

|e|.

(5.1)

e∈E: {i,j}⊆e

If an edge (i, j) ∈ EG is selected, we add (i, j) to EH with weight (mPij )−1 . Again,
weights are summed up if edges are sampled more than once. Next lemma shows that a
condition similar to (2.2) holds if each node of G belongs to a finite number of hyperedges.
Lemma 5.1 (Upper bound on parameter α for hypergraphs). Let G = (V, E) be a hypergraph and G = (V, E, W ) be the weighted graph induced by G. If each node of G belongs
to at most d hyperedges of G then
X
−1
Cij
≤ dn/2.
(5.2)
(i,j)∈EG

Proof. By definition of EG we have
X

−1
≤
Cij

(i,j)∈EG

X X

−1
.
Cij

e∈EG {i,j}⊆e

Since Cij ≥ |e| for each e ∈ EG that contains {i, j} and there are |e|(|e| − 1)/2 pairs
{i, j} ∈ e, it follows from above inequality that
X
X |e| − 1
dn
1 X
−1
Cij
≤
|e| ≤
≤
.
2
2
2
(i,j)∈EG

e∈EG

e∈EG

For the last inequality we use the assumption that each node belongs to at most d hyperedges.


8

CAN M. LE

Remark 5.2 (Tightness of the bound (5.2)). Without further assumptions on G, the dependence of the right hand-side of (5.2) on d is optimal. To see this, consider the following
example. Let k > 0 be an integer, n = k2 and V1 , ..., Vk be a partition of [n] := {1, ..., n}
such that each Vi contains exactly k elements Vi1 , ..., Vik . For each i ∈ [k], let σi be a
permutation of [k] given by σi (j) = i + j (mode k). Define the set of hyperedges of G as
a collection of subsets of the form
o
n
V1j , V2σi (j) , ..., Vkσk−1 (j) , 1 ≤ i, j ≤ k.
i

It is easy to see that every node of G is contained in exactly d = k hyperedges and every
pair
P of nodes of G is contained in at most one hyperedge. A simple calculation shows that
(i,j)∈EG 1/Cij = (d − 1)n/2.

Lemma 5.3 (Sparsification of hypergraphs). Let G = (V, E) be a hypergraph and G =
(V, E, W ) be the weighted graph induced by G. Let ε ∈ (0, 1) and assume that each node of
G belongs to at most d hyperedges of G. Form a weighted graph H by sampling 4dn log n/ε2
edges of G with probability Pij . Then with probability at least 1 − 1/n the following holds:
(1 − ε)LG  LH  (1 + ε)LG .
Proof. The proof of this lemma is similar to the proof of Theorem 2.1 with one exception

that we use the bound (5.2) in Lemma 5.3 instead of condition (2.2).
6. Discussion
We study in this paper an edge sampling algorithm that uses only the numbers of
common neighbors of incident nodes. These simple statistics provide an easy way to
measure the strength of network local connectivity through parameter α. However, in
practice we often have access to not only the numbers of common neighbors but also
local networks around edges. In that case, we should use the information of these local
networks, provided that it is available or easily computed. Measuring the strength of local
connectivity through local networks is more challenging and we leave it for future work.
Appendix A. Proof of Theorem 2.1
To prove Theorem 2.1, we will use the following result about concentration of the sum
of random matrices [44].
Theorem A.1 (Concentration of sum of matrices). Let Yk be independent nP
× n random
m
matrices
such
that
Y

0
and
kY
k
≤
M
for
all
1
≤
k
≤
m.
Let
S
=
m
k
k
k=1 Yk and
Pm
E = k=1 k E Yk k. Then for every ε ∈ (0, 1) we have
 2 
−ε E
.
P {kSm − E Sm k > εE} ≤ n · exp
4M
Proof of Theorem 2.1. Let X be a random matrix that takes one of the |EG | matrix values:
X=

1
(ei − ej )(ei − ej )T
pij

with probability pij ,

where (i, j) ∈ EG and pij is defined by (2.1). Then
X
1
(ei − ej )(ei − ej )T = LG .
EX =
pij ×
pij
(i,j)∈EG

(A.1)

9

Let Xk be m independent copies of X. By the sampling scheme we have
m

LH =

1 X
Xk ,
m

E LH = LG .

k=1

−1/2

the squared root of
Denote by L−1
G the Moore-Penrose pseudoinverse of LG and by LG
.
Note
that
the
kernel
of
the
map
L
is
an
one-dimensional
vector
space spanned by
L−1
G
G
the all-one vector 1 and it is contained in the kernel of LH . Therefore inequality (2.3) is
equivalent to
m
1 X −1/2
−1/2
(1 − ε)I1 
(A.2)
LG Xk LG  (1 + ε)I1 ,
m
k=1

I−(1/n)11T

where I1 =
is the identity map on the (n−1)-dimensional subspace orthogonal
to the all-one vector 1.
−1/2
−1/2
To prove (A.2), we apply Theorem A.1 to Yk := LG Xk LG . Since Xk  0 and
E Xk = LG by (A.1), it follows that Yk  0 and k E Yk k = kI1 k = 1. To bound kYk k, note
that Yk takes one of the following matrix values

T
1  −1/2
−1/2
LG (ei − ej ) LG (ei − ej ) , (i, j) ∈ EG .
pij
By (2.1) and assumption (2.2) we have 1/pij ≤ nα(cij + 2)/2. Therefore
kYk k ≤ max

(i,j)∈EG

nα(cij + 2)
· (ei − ej )T L−1
G (ei − ej ).
2

(A.3)

For each (i, j) ∈ EG , let Nij be the set of common neighbors of i and j. Denote by
Gij = (Vij , Eij ) the subgraph of G such that
Vij = {i, j} ∪ Nij ,

Eij = {(i, j), (i, k), (j, k) : k ∈ Nij }.

Thus, Gij contains cij +2 vertices and 2cij +1 edges. Since Gij is a subgraph of G, it follows
that LGij  LG . On the (cij + 1)-dimensional subspace spanned by {ek : k ∈ Vij } and
−1
orthogonal to all-one vector 1, both LG and LGij are nonsingular, therefore L−1
Gij  LG
(see e.g. [15, Corollary 7.7.4]). In particular,
T −1
(ei − ej )T L−1
G (ei − ej ) ≤ (ei − ej ) LGij (ei − ej ).

(A.4)

We claim that the right hand side of (A.4) is equal to 2/(cij + 2). Let x = L−1
Gij (ei − ej ).
Then LGij x = ei − ej and by comparing the i-th and j-th components of LGij x and ei − ej ,
we have
X
X
(cij + 1)xi − xj −
xk = 1,
xi − (cij + 1)xj +
xk = 1.
k∈Nij

k∈Nij

Adding these equalities, we obtain xi − xj = 2/(cij + 2). Since the right hand side of (A.4)
is (ei − ej )T x = xi − xj , the claim is proved. Together with (A.3) and (A.4) this implies
kYk k ≤ nα. Therefore by Theorem A.1 we have
(
)
 2 
m
−ε m
1 X
P
.
Yk − I1 > ε ≤ n · exp
m
4αn
k=1

Inequality (A.2) then follows by choosing m = 8αn log n/ε2 .



10

CAN M. LE

Lemma A.2. For positive numbers x1 , x2 , ..., xk the following inequality holds


1
1
1
(x1 + x2 + · · · + xk )
+
+ ··· +
≥ k2 .
x1 x2
xk
The two sides are equal if and only if x1 = x2 = · · · = xn .
Proof. Using the inequality of arithmetic and geometric means, we have
1
1
1
+
+ ··· +
≥ k(x1 x2 · · · xk )−1/k .
x1 + x2 + · · · + xk ≥ k(x1 x2 · · · xk )1/k ,
x1 x2
xk

Lemma A.2 follows directly from these inequalities.
References
[1] L. A. Adamic and N. Glance. The political blogosphere and the 2004 US election. In Proceedings of
the WWW-2005 Workshop on the Weblogging Ecosystem, 2005.
[2] S. Agarwal, K. Branson, and S. Belongie. Higher order learning with graphs. ICML ’06, pages 17–24,
2006.
[3] N. Alon, I. Benjamini, and A. Stacey. Percolation on finite graphs and isoperimetric inequalities. Ann.
Probab., 32(3):1727–1745, 2004.
[4] F. Bauer, J. Urgen, and S. Liu. Ollivier-Ricci curvature and the spectrum of the normalized graph
Laplace operator. Math. Res. Lett., 19(6):1185–1205, 2012.
[5] M. Belkin, I. Matveeva, and P. Niyogi. Regularization and semi-supervised learning on large graphs.
COLT, 3120:624–638, 2004.
[6] A. A. Benczúr and D. R. Karger. Approximating s-t minimum cuts in Õ(n2) time. Proceedings of the
Twenty-eighth Annual ACM Symposium on Theory of Computing (STOC ’96), pages 47–55, 1996.
[7] B. B. Bhattacharya and S. Mukherjee. Exact and asymptotic results on coarse Ricci curvature of
graphs. Discrete Mathematics, 338(6):23–42, 2015.
[8] B. Bollobás, C. Borgs, J. Chayes, and O. Riordan. Percolation on dense graph sequences. Ann. Probab.,
38(1):150–183, 2010.
[9] P. Chin, A. Rao, and V. Vu. Stochastic block model and community detection in the sparse graphs :
A spectral algorithm with optimal rate of recovery. arXiv:1501.05021, 2015.
[10] S. Fortunato. Community detection in graphs. Physics Reports, 486(3-5):75 – 174, 2010.
[11] C. Gao, Z. Ma, A. Y. Zhang, and H. H. Zhou. Achieving optimal misclassification proportion in
stochastic block model. arXiv:1505.03772, 2015.
[12] A. Goldenberg, A. X. Zheng, S. E. Fienberg, and E. M. Airoldi. A survey of statistical network models.
Foundations and Trends in Machine Learning, 2:129–233, 2010.
[13] R. Gupta, T. Roughgarden, and C. Seshadhri. Decompositions of triangle-dense graphs. Proceedings
of the 5th conference on Innovations in theoretical computer science, pages 471–482, 2014.
[14] M. Hamann, G. Lindner, H. Meyerhenke, C. L. Staudt, and D. Wagner. Structure-preserving sparsification methods for social networks. Social Network Analysis and Mining, 6(22):1–22, 2016.
[15] R. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, 2013.
[16] J. Huang, S. Ma, H. Li, and C. H. Zhang. The sparse laplacian shrinkage estimator for high-dimensional
regression. Annals of Statistics, 39(4):2021–2046, 2011.
[17] J. Jost and S. Liu. Ollivier’s Ricci curvature, local clustering and curvature-dimension inequalities on
graphs. Discrete and Computational Geometry, 51(2):300–322, 2014.
[18] M. Kapralov, Y. T. Lee, C. Musco, C. Musco, and A. Sidford. Single pass spectral sparsification in
dynamic streams. SIAM J. Comput., 46(1):456–477, 2014.
[19] J. Kelner and A. Levin. Spectral sparsification in the semi-streaming setting. Theory of Computing
Systems, 53(2):243–262, 2013.
[20] A. Kirichenko and H. van Zanten. Estimating a smooth function on a large graph by bayesian laplacian
regularisation. Electron. J. Statist., 11(1):891–915, 2017.
[21] B. Klimt and Y. Yang. The enron corpus: A new dataset for email classification research. In Boulicaut
JF., Esposito F., Giannotti F., Pedreschi D. (eds) Machine Learning: ECML 2004, volume 3201,
pages 217–226, 2004.
[22] J. Leskovec, J. Kleinberg, and C. Faloutsos. Graph evolution: Densification and shrinking diameters.
ACM Transactions on Knowledge Discovery from Data (ACM TKDD), 1(1):2007, 2007.

11

[23] T. Li, E. Levina, and J. Zhu. Regression with network cohesion. arXiv:1602.01192, 2016.
[24] Y. Lin, L. Lu, and S. T. Yau. Ricci-flat graphs with girth at least five. Communications in Analysis
and Geometry, 22(4):671–687, 2014.
[25] D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson. The bottlenose
dolphin community of doubtful sound features a large propor- tion of long-lasting associations. can
geographic isola- tion explain this unique trait? Behavioral Ecology and Sociobiology, 54:396–405,
2003.
[26] J. McAuley and J. Leskovec. Learning to discover social circles in ego networks. Neural Information
Processing Systems (NIPS), 2012.
[27] A. Nachmias. Percolation on dense graph sequences. Geometric and Functional Analysis, 19(4):1171–
1194, 2010.
[28] M. E. J. Newman. Networks: An introduction. Oxford University Press, 2010.
[29] A. Nocaj, M. Ortmann, and U. Brandes. Untangling hairballs – From 3 to 14 degrees of separation.
Duncan CA, Symvonis A (eds) Graph Drawing–22nd international symposium, GD 2014, Würzburg,
Germany, September 24-26, 2014, pages 101–112, 2014.
[30] R. Oliveira. Concentration of the adjacency matrix and of the laplacian in random graphs with independent edges. arXiv:0911.0600, 2010.
[31] Y. Ollivier. Ricci curvature of markov chains on metric spaces. Journal of Functional Analysis,
256(3):810–864, 2009.
[32] M. Ortmann and U. Brandes. Triangle listing algorithms: Back from the diversion. In McGeoch
C. C., Meyer U. (eds) 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and
Experiments, ALENEX 2014, Portland, Oregon, USA, pages 1–8, 2014.
[33] F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi. Defining and identifying communities
in networks. Proc. Natl. Acad. Sci. USA, 101(9):2658–2663, 2004.
[34] J. A. Rodrı́guez. On the Laplacian eigenvalues and metric parameters of hypergraphs. Linear and
Multilinear Algebra, 50(1):1–14, 2002.
[35] K. Rohe and T. Qin. The blessing of transitivity in sparse and stochastic networks. arXiv:1307.2302,
2013.
[36] V. Satuluri, S. Parthasarathy, and Y. Ruan. Local graph sparsification for scalable clustering. Proceedings of the 2011 international conference on Management of data (SIGMOD’11), pages 721–732,
2011.
[37] A. Shrivastava and P. Li. Densifying one permutation hashing via rotation for fast near neighbor
search. Proceedings of the 31st International Conference on Machine Learning (ICML-14), pages 557–
565, 2014.
[38] A. Shrivastava and P. Li. Asymmetric minwise hashing for indexing binary inner products and set
containment. Proceedings of the 24th International Conference on World Wide Web (WWW’15), pages
981–991, 2015.
[39] A. Smola and R. Kondor. Kernels and regularization on graphs. Learning Theory and Kernel Machines,
2777:144–158, 2003.
[40] D. A. Spielman and N. Srivastava. Graph sparsification by effective resistances. SIAM J. Comput.,
40(6):1913–1926, 2011.
[41] D. A. Spielman and S.-H. Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. Proceedings of the thirty-sixth annual ACM Symposium on Theory
of Computing (STOC-04), pages 81–90, 2004.
[42] D. A. Spielman and S. H. Teng. Spectral sparsification of graphs. arXiv:0808.4134, 2008.
[43] J. Ugander, B. Karrer, L. Backstrom, and C. Marlow. The anatomy of the facebook social graph.
arXiv:1111.4503, 2011.
[44] R. Vershynin. A note on sums of independent random matrices after Ahlswede-Winter. Available at
http: // www-personal. umich. edu/ ~ romanv/ teaching/ reading-group/ ahlswede-winter. pdf ,
2009.
[45] M. K. Von Renesse and K. T. Sturm. Transport inequalities, gradient estimates, entropy, and Ricci
curvature. Communications on Pure and Applied Mathematics, 58(7):923–940, 2005.
[46] D. J. Watts and S. H. Strogatz. Collective dynamics of ’small-world’ networks. Nature, 393:440, 1998.
[47] W. W. Zachary. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33(4):452–473, 1977.

12

CAN M. LE

University of California, Davis
E-mail address: canle@ucdavis.edu

