Estimating Properties of Social Networks via Random Walk
considering Private Nodes
Kazuki Nakajima

Kazuyuki Shudo

Tokyo Institute of Technology
nakajima.k.an@m.titech.ac.jp

Tokyo Institute of Technology
shudo@is.titech.ac.jp

ABSTRACT
Accurately analyzing graph properties of social networks is a challenging task because of access limitations to the graph data. To
address this challenge, several algorithms to obtain unbiased estimates of properties from few samples via a random walk havebeen studied. However, existing algorithms do not consider private
nodes who hide their neighbors in real social networks, leading
to some practical problems. Here we design random walk-basedalgorithms to accurately estimate properties without any problems
caused by private nodes. First, we design a random walk-based
sampling algorithm that comprises the neighbor selection to obtainsamples having the Markov property and the calculation of weights
for each sample to correct the sampling bias. Further, for two graphproperty estimators, we propose the weighting methods to reduce
not only the sampling bias but also estimation errors due to private
nodes. The proposed algorithms improve the estimation accuracyof the existing algorithms by up to 92.6% on real-world datasets.

CCS CONCEPTS• General and reference → Estimation; • Mathematics of computing → Graph algorithms.

KEYWORDS
Social networks; Estimation; Sampling; Random walk; Private nodes
ACM Reference Format:
Kazuki Nakajima and Kazuyuki Shudo. 2020. Estimating Properties of Social
Networks via Random Walk considering Private Nodes. In Proceedings ofthe 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining(KDD ’20), August 23–27, 2020, Virtual Event, CA, USA. ACM, New York, NY,
USA, 11 pages. https://doi.org/10.1145/3394486.3403116

1

INTRODUCTION

Online social networks (OSNs) have been primarily studied to understand the nature of global social structures, such as human connections and behaviors [1, 9, 10, 16, 20, 29]. A widely used approachto understand the structure is to analyze various graph properties,
such as the number of nodes (size), the average degree, and thedegree distribution. However, an accurate analysis of social graphs
is a challenging task because of access limitations to the graph data.
Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others than theauthor(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or
republish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from permissions@acm.org.
KDD ’20, August 23–27, 2020, Virtual Event, CA, USA© 2020 Copyright held by the owner/author(s). Publication rights licensed to ACM.
ACM ISBN 978-1-4503-7998-4/20/08. . . $15.00
https://doi.org/10.1145/3394486.3403116

Although some studies used complete graph data [1, 3, 21], all thedata is typically not available to researchers. In practical scenarios,
we sample a part of graph data through the application programming interfaces (APIs) to estimate properties [9, 10]. We can obtain
unbiased estimates if users are randomly sampled; however, it isfrequently difficult to randomly assign user IDs to the APIs [6, 11].
Several algorithms [5, 6, 11, 12, 22, 28] based on the re-weighted
random walk scheme [9, 10] have been studied to address thischallenge. Many OSNs have provided APIs to return the neighbordata of a queried user. By repeatedly utilizing this function for arandomly selected neighbor, we obtain samples with the Markov
property via a random walk on a social network. Then, we obtain
unbiased estimates of properties by re-weighting each sample tocorrect the sampling bias derived from the Markov chain analysis.
Previous studies have focused on accurate estimates with a small
number of queries because APIs are typically rate-limited [6, 11].
However, previous studies have ignored private users who do
not provide their neighbor data even if queried. Although previous
studies assume a network comprising only public users who publish
their neighbor data, a certain percentage of private users exist inreal social networks. For example, private users were about 27% on
Facebook [4] and 34% on Pokec [25], which is an OSN in Slovakia.
Private users cause some problems for existing algorithms. For
example, how do we deal with private users in a random walk sampling? If private users are sampled, we need to handle an exception
wherein the neighbor data cannot be obtained by approaches suchas returning to the public user sampled previously. However, if
such an exceptional process is performed, the Markov property ofa sample sequence cannot be guaranteed. This can prevent us fromobtaining unbiased estimates of properties. There is another serious
problem. A fast solution of problems in sampling is to not include
private users to the sample sequence; however, by not sampling
them, the sampling bias and weighting for each sample are different
from the assumptions of existing algorithms. Thus, the existingalgorithms cause estimation errors due to private users.
We aim to design re-weighted random walk algorithms considering private users to accurately estimate properties without any
problems caused by private users. To the best of our knowledge,
this study is the first to focus on the effect of private users on random walk-based estimators. First, we make three assumptions anddefine two access models (the ideal model and the hidden privacy
model), based on previous studies and our observations of real social
networks (Section 2). Then, we design sampling and estimation
algorithms based on these assumptions and access models.
This study has two main contributions. The first contribution isto enable us to successfully perform re-weighted random walk-basedalgorithms in real social networks including private users (Section 3).
We discuss the neighbor selection in a random walk by considering

Proc. 26th ACM SIGKDD Int'l Conf. on Knowledge Discovery & Data Mining(KDD 2020), August 2020

private users and derive the sampling bias of each user. Then, foreach access model, we describe the calculation of the weights tocorrect the sampling bias; particularly for the hidden privacy model,
we propose a method to approximate weights with much fewer
queries than exact calculation.
The second contribution is to enable us to accurately estimate
the size and average degree of a whole social graph including private
nodes (Section 4). Existing algorithms [6, 11, 12] cause errors due
to private users because the conventional weighting aims only tocorrect the sampling bias. We propose weighting methods to reduce
both sampling bias and errors due to private users. Moreover, wetheoretically explain that estimates obtained using the proposed
weighting converge to values with smaller expected errors than theprevious weighting.
Finally, we validate the theoretical claims and effectiveness ofthe proposed algorithms on extensive experiments using real social network datasets (Section 5). It is important to evaluate theperformance when the assumptions are not satisfied because theproposed algorithms are designed on some simplified assumptions.
We empirically show that the proposed algorithms perform well on
realistic datasets, such as a 92.6% improvement in the estimation
accuracy on the Pokec dataset including real private users.

2 PRELIMINARIES
2.1 Definitions and Notations
We represent a social network as a connected and undirected graph,
G = (V , E), where V = {v 1, ..., vn } denotes the set of nodes (users),
and E denotes the set of edges (friendship). Let di denote the degreeÍ(number of neighbors) of vi and D = vi ∈V di denote the sumof degrees. We define the average degree of G as davд = D
n . Eachnode, vi , has a privacy label, lpr i (i) ∈ {public, private}. The set ofprivacy labels is denoted by Lpr i = {lpr i (i)}vi ∈V .
We refer to connected subgraphs that consist of public nodes
on G as public-clusters. Let {Ci } denote a set of public-clusters andC ∗ = (V ∗, E ∗ ) denote the largest public-cluster. Let n∗ denote thenumber of nodes in C ∗ , and di∗ = |{v j ∈ V ∗ |(vi , v j ) ∈ E ∗ }| denotethe public-degree (the number of neighbors that publish their own
Íneighbors) of a node vi ∈ V ∗ . Let D ∗ = vi ∈V ∗ di∗ denote the sum∗∗of public-degrees. We define the average degree of C ∗ as davд= Dn∗ .
Let 1V ∗ (vi ) denote a function that returns 1 if vi ∈ V ∗ , otherwise 0.
Example: Let vi = i (1 ≤ i ≤ 10) in Figure 1. There are threepublic-clusters, C 1 , C 2 and C 3 , and C 1 is the largest public-cluster:

9

6

10

8

5

4

2

7

3

1

Figure 1: An example of a graph with privacy labels. Here,nodes 1 and 2 are private and others are public.
(2) Each node independently becomes private with probability p,otherwise public, where 0 ≤ p ≤ 1. We assume that each node
independently hides neighbors with a certain probability1 .
(3) The seed of a random walk is on the largest public-cluster. We
do not consider the number of queries performed to selectthe seed from nodes on the largest public-cluster, because
we consider that this number is sufficiently small.

2.3

Access Models

We do not assume the acquisition of all the graph data and theirrandom access. We assume that a graph G is static.
If we query a public node, the neighbor data are provided. If a
private node is queried, the neighbor data cannot be obtained2 . We
consider two models for the neighbor data that are provided whena public node, vi , is queried: ideal model and hidden privacy model.
The ideal model: Indices (IDs) and privacy labels of all neighborsof vi are obtained. For example, when a public node 4 is queried in
Figure 1, we obtain the set {(2, private), (5, public)}. Facebook asof the previous study [10] corresponds to this access model.
The hidden privacy model: Even though ids of all neighborsof vi are obtained, the privacy labels are not. For example, when apublic node 4 is queried in Figure 1, we obtain the set {2, 5}. Twitter
API as of June 2020 corresponds to this model [26, 27].

2.4

Markov Chain Basics

We introduce the basics of a Markov chain for theoretical analysisof random walk-based estimators. First, we describe the stationary distribution of a Markov chain, which is needed to derive thesampling bias. Let P = {Pi,j }i,j ∈S denote the transition probability
Ímatrix of a Markov chain on the state space, S. If π j = i ∈S πi Pi,jholds for all j ∈ S, π = {πi }i ∈S is the stationary distribution of P.
The following theorem holds for the stationary distribution π of P:• C 1 = ({4, 5, 6, 7, 9}, {(4, 5), (5, 6), (5, 7), (5, 9)})• C 2 = ({8, 10}, {(8, 10)})• C 3 = ({3}, {}).

Theorem 2.1. [19] If P is ergodic (i.e., irreducible and aperiodic),
the stationary distribution, π , uniquely exists.

Also, it holds n ∗ = 5, d 4∗ = 1, d 5∗ = 4, d 6∗ = 1, d 7∗ = 1, d 9∗ = 1.

Then, we review the strong law of large numbers for a Markov
chain, which is needed to ensure that the sample average converges
almost surely to its expected value:

2.2

Assumptions

We design algorithms based on the following three assumptions.
(1) The indices of all neighbors, including private neighbors, of aqueried public node are obtained. Facebook as of the previous
study [10] satisfied this assumption. We have confirmed that
Twitter as of June 2020 satisfies this assumption [26, 27].

Theorem 2.2. [5, 17] Let {X k } be an ergodic Markov chain withthe stationary distribution π on the finite state space S. For any
ÍÍ
function f : S → R, r1 rk =1 f (X k ) converges to i ∈S πi f (i) almost
surely as r → ∞ regardless of the initial distribution of the chain.
1 Intuitively, private nodes tend to have low degrees under Assumption 2, because thedegree distribution of social networks is typically biased to low degrees [1, 9, 10, 16, 20].
2 The output may be an error message or an empty set.

Proc. 26th ACM SIGKDD Int'l Conf. on Knowledge Discovery & Data Mining(KDD 2020), August 2020

3

RANDOM WALK SAMPLING

We design a random walk-based sampling algorithm that consistsof the neighbor selection to obtain samples having the Markov
property and the calculation of weights to correct the samplingbias. The proofs in this section are shown in the supplement.

3.1

Transition Neighbor Selection

In a simple random walk, we move to a randomly selected neighbor. If private nodes are sampled, practical problems on estimating
properties occur, because their neighbor data are unclear. For example, we cannot simply continue the algorithm, and it is difficult
to correct the sampling bias of sampled private nodes.
We believe that it is appropriate to move to a public neighborrandomly selected as Gjoka et al. [10] performed on Facebook3 .
We design the algorithm to obtain an index sequence of r sampled
nodes, denoted by {x k }kr =1 , as follows. First, we select a seed, v x 1 ∈C ∗ , as the first sample. Then, for 1 ≤ k ≤ r − 1, we randomly selecta node, u, from neighbors of the k-th sample, v x k . If u is public, wemove to u as next sample, v x k +1 ; otherwise, we randomly reselect aneighbor of v x k . In the ideal model, we check if a selected neighboru is public without an additional query. In the hidden privacy model,
we judge the privacy label of u by additionally querying u.

3.2

Sampling Bias

We derive the sampling bias caused by the designed random walk.
Let the probability that an event A will occur be denoted by Pr [A].
We define the distribution induced by the sequence of sampledindices as πr = (Pr [x r = i])vi ∈V .
We show that each node on the largest public-cluster is sampled
in proportion to the public-degree via the designed random walk.
Lemma 3.1. πr converges to the vector π = (pi 1V ∗ (vi ))vi ∈V afterd∗many steps of the designed random walk, where pi = Di∗ .

3.3

Public-Degree Calculation

We need to calculate the public-degree of each sample to correct
the sampling bias due to the public-degree.
In the ideal model, we can exactly calculate each public-degree
without additional query because the privacy labels of all the neighbors are obtained. Conversely, in the hidden privacy model, theexact calculation needs a considerable number of additional queries
to obtain privacy labels of all neighbors for each sample.
For the hidden privacy model, we propose a method to approximate each public-degree without additional queries by utilizing thehistory of neighbor selections of the designed random walk. We
record two values for each sample v x k : the total number of successful public neighbor selections, a x k , and that of neighbor selections,bx k . After sampling, each approximate value, dˆx∗k , is calculated asaxdˆx∗k ≜ d x k k .
bx k
The pseudo-code of the designed random walk with the proposed
approximation of public-degrees is shown in the supplement.
3 There is no detailed discussion of the effect of private nodes on re-weighted random
walk algorithms [10]. They focused on only the part comprising public nodes.

We ensure the convergence of the approximated public-degree
after many steps of the designed random walk.
Lemma 3.2. dˆx∗k converges to d x∗k for each sample, v x k , after many
steps of the designed random walk.
Then, we explain that the proposed method performs much fewer
queries than the exact method that exactly calculates the publicdegree of each sample. Here, for simplicity, we do not consider the
save of the indices of nodes queried once. Q(k) and Q̂(k) denotethe number of queries that are performed at the k-th sample by theÍ
exact and proposed methods, respectively. Let Q = r1 rk =1 Q(k)Íand Q̂ = r1 rk =1 Q̂(k) denote the ratio of the number of queries tothe sample size of the exact and proposed methods, respectively.
Lemma 3.3. The expectations of Q and Q̂ areÍ
vi ∈V ∗ d i
D∗∗vi ∈V ∗ d i d i
D∗

Í

and

, respectively.

Lemma 3.3 implies that the proposed method performs muchÍ
fewer queries than the exact method because vi ∈V ∗ di is intuÍ
itively much smaller than vi ∈V ∗ di∗di in real social networks.

4

PROPERTIES ESTIMATION

We design estimators for the size and the average degree via arandom walk designed in Section 3. We first introduce the existing
estimators and then propose estimators with improved weighting.
The proofs in this section are shown in the supplement.

4.1

Overview

Here we address a novel problem that the convergence values of
estimators have errors caused by private nodes. The conventional
estimators perform the weighting using only the public-degree tocorrect the sampling bias; consequently, the estimates converge
to the properties of the largest public-cluster. When a graph comprises only public nodes as have been assumed in previous studies,
the convergence values are equal to the properties of the originalgraph. However, when there are private nodes on a graph, the convergence values typically have errors due to private nodes, or more
specifically, the value of p.
It is unclear how to reduce the errors due to the value of p. If weknow the exact value of p, we can easily correct the errors; however,this is usually unknown. Moreover, we cannot apply existing methods to estimate the value of p based on privacy labels of samples(Section 3.C.3 in [10], Section 3.2 in [12] and Section 4.2.3 in [23]),
because private nodes are not included in samples.
We propose the weighting methods combining the public-degreeand degree to reduce the errors of convergence values due to thevalue of p. The proposed methods are based on the fact that the
public-degree follows the binomial distribution with parametersof the degree and 1 − p regarding the set of privacy labels under
Assumption 2. Proposed estimators provide the same convergencevalues when p = 0 and convergence values with smaller expected
errors when p > 0 as compared with the existing estimators.

4.2

Size Estimation

Existing estimator: The node collision (NC) algorithm is an effective estimator for the size [11, 12]. This algorithm examines sample

Proc. 26th ACM SIGKDD Int'l Conf. on Knowledge Discovery & Data Mining(KDD 2020), August 2020

pairs whose ordinal numbers in the sample sequence are more thana threshold, m, apart. Sample pairs whose ordinal numbers in thesample sequence are sufficiently apart can be regarded as being
independently sampled [11].
Let I = {(k, l) | m ≤ |k − l | ∧ 1 ≤ k, l ≤ r } denote the set of
integer pairs that are between 1 and r and at least m away. Let
ϕ k ,l denote a variable which returns 1 if x k = xl (this is called acollision), and otherwise, 0. The average of the number of collisions
ΦnN C , the average of the weights to correct the sampling bias ΨnN C ,and a size estimate n N C obtained by NC algorithm are as follows:
∗
ΨN C
1 Õ
1 Õ dxk
ΦnN C =
ϕ k ,l , ΨnN C =, n N C ≜ nN C
∗
|I |
|I |
d
Φn
(k ,l )∈I
(k ,l )∈I x l
It holds the following lemma expanded from the previous studies[11, 12] which assume graph with no private nodes.
Lemma 4.1. n N C converges to size of the largest public-cluster, n∗ .
We focus on the expectation of n ∗ regarding the set of privacy labels, Lpr i , to quantify the error between n ∗ and n. Epr i [X ] denotes
the expectation of a random variable X regarding Lpr i . We approximate the expectation of n ∗ regarding Lpr i under the condition that
all the public nodes belong to the largest public-cluster. Under thiscondition, it holds that Pr [vi ∈ V ∗ ] = Pr [lpr i (i) = public] = 1 − p.
The following lemma holds for the convergence value n ∗ :Lemma 4.2. Under the condition that all the public nodes belong
to the largest public-cluster, we have∗

Epr i [n ] = (1 − p)n.

It holds the following lemma regarding the convergence valuesof the proposed estimator.
∗v ∈V ∗ d i d i
∗ 2
(d
∗
vi ∈V
i)

that all the public nodes belong to the largest public-cluster, we haveÍ
Epr i [n ∗ ]Epr i [ vi ∈V ∗ di∗di ]Epr i [ñ] ≈= αp n.
Í
Epr i [ vi ∈V ∗ (di∗ )2 ]Theorem 4.6 implies that our convergence value is almost equal
to the entire size because the coefficient αp is empirically almost
equal to 1 for various values of p in real social networks.
The following corollary claims that the proposed estimator improves an expected convergence error for any values of p.
Corollary 4.7. Under the condition that all the public nodes
belong to the largest public-cluster, we haveÍ
Epr i [n∗ ]Epr i [ vi ∈V ∗ di∗di ]≤ n − Epr i [n∗ ] .
n−Í
Epr i [ vi ∈V ∗ (di∗ )2 ]4.3

Average Degree Estimation

Existing estimator: The Smooth algorithm [6] takes a rough estimate of the average degree, c, as an input and returns a moreaccurate estimate. Herein, we let c to be 0 because Dasgupta et al.
concluded that small values, 0 or 1, are desirable [6].
An estimate of the average degree obtained using the Smooth
Smoot h , is defined as follows:algorithm, davдr
Smoot h
davд
≜ Ír
.
1
k =1 d x∗ k

It holds the following lemma derived from the previous study[6] which assumes a graph with no private nodes.

Lemma 4.2 implies that an expected relative error of the convergence value in the existing estimator is 1 − p.
Proposed estimator: We improve the weighting for each sample pair to reduce the convergence error. We define the average ofthe proposed weights as Ψ̂n , then our estimation value as n̂:1 Õ dxkΨ̂nΨ̂n =, n̂ ≜ N C .
|I |
d x∗l
Φ
n
(k ,l )∈IÍ

Lemma 4.3. n̂ converges to ñ = n∗ Í iÍ(1−p) vi ∈V (d i )2
. Under the conditiondvi ∈V i [(1−p)d i +p]

Theorem 4.6. Let αp = Í.

When there are no private nodes on G, the following proposition
holds for each estimate and convergence value.
Proposition 4.4. When there are no private nodes on G, the two
estimation values, n N C and n̂, are equal, and the two convergencevalues, n∗ and ñ, are equal to the true value, n.
We clarify our convergence value, ñ, has the smaller expected
error for any values of p than the previous convergence value, n ∗ .
First, we show the following lemma:

Smoot h converges to the average degree of the largest
Lemma 4.8. davд∗
public-cluster, davд .
∗Then, we approximate the expectation of davдregarding Lpr i .

Lemma 4.9. Under the condition that all the public nodes belong
to the largest public-cluster, we have∗
Epr i [davд]≈

Epr i [D ∗ ]= (1 − p)davд .
Epr i [n∗ ]Lemma 4.9 implies that an expected relative error of the convergence value in the existing estimator is 1 − p.
Proposed estimator: We improve the weighting to reduce a
convergence error due to the value of p. We define our estimate asrdˆavд ≜ Ír.
1
k=1 d x k

The following lemma regarding our estimate holds:∗
Lemma 4.10. dˆavд converges to d˜avд = Í D d ∗ .
ivi ∈V ∗ di

The following proposition holds as well as Proposition 4.4.
Lemma 4.5. For any node vi ∈ V ∗ , we have
Epr i [di∗ ] = (1 − p)di ,
Epr i (di∗ )2 = (1 − p)di [(1 − p)di + p].

Proposition 4.11. When there are no private nodes on G, two
Smoot h and dˆestimates, davдavд , are equal, and two convergence values,∗davд
and d˜avд , are equal to the true value, davд .

Then, we approximate the expectation of ñ regarding Lpr i byderiving each expectation of the denominator and numerator of ñ.

The following theorem and corollary claim that the proposed
estimator improves an expected error of the convergence value.

Proc. 26th ACM SIGKDD Int'l Conf. on Knowledge Discovery & Data Mining(KDD 2020), August 2020

Orkut
LiveJournal
Facebook
YouTube
Pokec

10 4
10 5
10 6
100

101

0.999
0.998
Orkut
LiveJournal
Facebook
YouTube
Pokec

0.997
0.996

102 103
Degree104

0.0

Figure 2: Cumulative degree
distributions.

0.1

p

0.2

0.3

Figure 3: Coefficients αp .

0.8
0.6
1 p
Orkut
LiveJournal
Facebook
YouTube

0.4
0.2
0.0

0.0

0.1

p

Epr i

Epr i [D ∗ ]hÍ
i = davд .
d∗i

v i ∈V ∗ d i

Corollary 4.13. Under the condition that all the public nodes
belong to the largest public-cluster, we havedavд −

4.4

Epr i

v i ∈VdiEstimation in the Hidden Privacy Model

EXPERIMENTS

We evaluate the proposed algorithms using real social network
datasets. We aim to answer the following questions:(1) Do the proposed estimators improve the estimation accuracyof the size and average degree for various probabilities of p?
(Section 5.2)
(2) Do the proposed estimators perform acceptably in real-world
datasets including real private users? (Section 5.3)
(3) How does the proposed public-degree calculation for thehidden privacy model affect the estimation accuracy andnumber of queries? (Section 5.4)
(4) Is the number of queries performed in the seed selection due
to private nodes is small? (Section 5.5)

5.1

1.3
1.2
1.1
1.0
0.0

0.3

0.1

p

0.2

0.3

Table 1: Datasets.
NetworkYouTube [14]Pokec [18]Orkut [18]Facebook [24]
LiveJournal [18]n1,134,890
1,632,803
3,072,441
3,097,165
3,997,962

davд
5.27
27.32
76.28
15.28
17.35

Privacy label setting
based on Assumption 2
real labels
based on Assumption 2
based on Assumption 2
based on Assumption 2

Epr i [D ∗ ]Epr i [D ∗ ].
≤ davд −hÍi∗
di
Epr i [n∗ ]∗In the hidden privacy model, we calculate each estimate using theapproximated public-degree, dˆx∗k . Even in this model, Lemmas 4.1,
4.3, 4.8, and 4.10 hold because of Lemma 3.2.

5

0.2

Orkut
Livejournal
Facebook
YoutubeFigure 4: Relative size of the Figure 5: Average absolute sizeof isolated public-clusters.
largest public-cluster.

Theorem 4.12. Under the condition that all the public nodes belong
to the largest public-cluster, we have
Epr i [d˜avд ] ≈Average absolute size ofisolated public-clusters

10

3

Relative size oflargest public-cluster

10 2

1.4

1.0

1.000
Coefficients ↵p

Cumulative distribution

100
10 1

Experimental Setup

Datasets: We use datasets of known size and average degree, YouTube,
Pokec, Orkut, Facebook, and LiveJournal. For these five datasets, we
focus on undirected and connected graphs by the pre-processing:(1) removing the directions of edges if the original graphs are directed and then (2) deleting the nodes that are not contained in thelargest connected component of the original graph. All the following experiments are unaffected because the above pre-processing is
performed before setting privacy labels and any processing is not
added to the graph after the privacy labels are set. The Pokec dataset
contains all graph data of the Pokec network, including 552525 real
private users (about 33.8%) and the real privacy labels. Table 1 lists

the size and average degree of five datasets. Additionally, we use
a dataset [15] of 1,016,275 samples of real public Facebook users
via random walk during October 2010 to evaluate the actual performance of the proposed estimators. This dataset contains the ID,
exact public-degree, and exact degree of each sampled public user.
Accuracy measure: We apply the normalized root mean squareerror (NRMSE) to evaluate both the bias and variance of estimators
1[5, 11, 17, 28]. NRMSE is defined by (E[( x̃x − 1)2 ]) 2 , where x̃ denotes
the estimation value and x denotes the true value. We performed
each experiment independently 1000 times to estimate the NRMSE.
Privacy label settings: For YouTube, Orkut, Facebook, and
LiveJournal, we independently set each privacy label as privatewith probability p and otherwise public, according to Assumption
2. The probability p is from 0.0 to 0.30 in increments of 0.03 because
there were actually tens of percentages of private users [4, 7, 25].
The set of privacy labels is independently given for each experiment. For Pokec, we apply the set of real privacy labels containedin the dataset. Table 1 lists how to set privacy labels in five datasets.
Seed selection: On YouTube, Orkut, Facebook, LiveJournal, andPokec, the seed of a random walk is selected randomly from nodes
on the largest public-cluster and independently for each experiment.
Sample size: The sample size, i.e., the length of a random walk,r , is 1% of the total number of nodes on YouTube, Orkut, Facebook,and LiveJournal. On Pokec, the sample size is varied from 0.5% to
5% of the total number of nodes in increments of 0.5%.
Threshold in size estimators: The threshold, m, in size estimators is 2.5% of the sample size, as set in a previous study [11].
Degree distributions: Figure 2 shows the cumulative degree
distributions of five datasets. We see that the degree distribution isbiased to low degrees in all datasets.
Coefficients αp : Figure 3 shows the coefficients αp that is defined in Theorem 4.6 for various values of p in five datasets. We seethat the coefficients αp are almost equal to 1.0 for every value of p.

Proc. 26th ACM SIGKDD Int'l Conf. on Knowledge Discovery & Data Mining(KDD 2020), August 2020

0.0

0.1

0.2

p

0.3

NC
Proposed

0.0(a) YouTube

0.1

p

0.2

0.3

0.45
0.40
0.35
0.30
0.25
0.20
0.15
0.10
0.05
0.00

NC
Proposed
NRMSE

0.45
0.40
0.35
0.30
0.25
0.20
0.15
0.10
0.05
0.00

NRMSE

NC
Proposed
NRMSE

NRMSE

0.45
0.40
0.35
0.30
0.25
0.20
0.15
0.10
0.05
0.00

0.0

(b) Orkut

0.1

p

0.2

0.3

0.45
0.40
0.35
0.30
0.25
0.20
0.15
0.10
0.05
0.00

(c) Facebook

NC
Proposed

0.0

0.1

p

0.2

0.3

(d) LiveJournal

Figure 6: NRMSEs of the size estimates (the ideal model with 1% sample size).

0.15

0.20
0.15

0.30

SmoothProposed

0.25
0.20
0.15

0.20
0.15

0.10

0.10

0.10

0.10

0.05

0.05

0.05

0.05

0.00

0.00

0.00

0.0

0.1

0.2

p

0.3

0.0

(a) YouTube

0.1

p

0.2

0.3

0.0

0.1

p

0.2

0.00

0.3

0.0

0.1

p

0.2

0.3

(d) LiveJournal(c) Facebook(b) Orkut

SmoothProposed

0.25
NRMSE

0.20

0.30

SmoothProposed

0.25
NRMSE

NRMSE

0.30

SmoothProposed

0.25

NRMSE

0.30

0.0

0.1

0.2

p

0.3

0.45
0.40
0.35
0.30
0.25
0.20
0.15
0.10
0.05
0.00

NC
Proposed

0.0

0.1

p

0.2

0.3

0.45
0.40
0.35
0.30
0.25
0.20
0.15
0.10
0.05
0.00

NC
Proposed
NRMSE

NC
Proposed

NRMSE

0.45
0.40
0.35
0.30
0.25
0.20
0.15
0.10
0.05
0.00

NRMSE

NRMSE

Figure 7: NRMSEs of the average degree estimates (the ideal model with 1% sample size).

0.0(b) Orkut(a) YouTube

0.1

p

0.2

0.3

0.45
0.40
0.35
0.30
0.25
0.20
0.15
0.10
0.05
0.00

(c) Facebook

NC
Proposed

0.0

0.1

p

0.2

0.3

(d) LiveJournal

Figure 8: NRMSEs of the size estimates (the hidden privacy model with 1% sample size).

0.15

0.20
0.15

0.15

0.10

0.10

0.05

0.05

0.05

0.0

0.1

p

0.2

0.3

0.00

0.0

(a) YouTube

0.1

p

0.2

0.3

0.00

SmoothProposed

0.25

0.20

0.10

0.00

0.30

SmoothProposed

0.25

NRMSE

0.20

0.30

SmoothProposed

0.25
NRMSE

NRMSE

0.30

SmoothProposed

0.25

NRMSE

0.30

0.20
0.15
0.10
0.05

0.0

(b) Orkut

0.1

p

0.2

0.3

0.00

0.0

0.1

p

0.2

0.3

(d) LiveJournal(c) Facebook

0.0

0.1

p

0.2

(a) YouTube

0.3

0.45
0.40
0.35
0.30
0.25
0.20
0.15
0.10
0.05
0.00

0.30

NC
Proposed

0.30

SmoothProposed

0.25
0.20
0.15
0.10
0.05

0.1

p

0.2

(b) Orkut

Figure 10: NRMSEs of size convergence values.

0.3

0.20
0.15
0.10
0.05

0.00
0.0

SmoothProposed

0.25
NRMSE

NC
Proposed

NRMSE

0.45
0.40
0.35
0.30
0.25
0.20
0.15
0.10
0.05
0.00

NRMSE

NRMSE

Figure 9: NRMSEs of the average degree estimates (the hidden privacy model with 1% sample size).

0.00
0.0

0.1

p

0.2

(a) YouTube

0.3

0.0

0.1

p

0.2

0.3

(b) Orkut

Figure 11: NRMSEs of average degree convergence values.

Proc. 26th ACM SIGKDD Int'l Conf. on Knowledge Discovery & Data Mining(KDD 2020), August 2020

0.35

0.35

0.30

0.30
0.25

0.20

NRMSE

0.25
NRMSE

Relative size of the largest public-cluster: Figure 4 shows∗
the average relative size of the largest public-cluster, nn , over independent 1000 experiments for various probabilities of p in four
datasets. The upper limit is 1 − p (gray solid line). All the public
nodes on Pokec belong to the largest public-cluster.
Average absolute size of isolated public-clusters: Figure 5
shows the average absolute size of isolated public-clusters (i.e.,
public-clusters other than the largest public-cluster) over independent 1000 experiments for various probabilities of p in four datasets.
Pokec has no isolated public-clusters.

NC
Proposed

0.15

NC
Proposed

0.15
0.10

0.10

0.05

0.05
0.00

0.20

1

2
3
4
Sample rate (%)

0.00

5

1

2
3
4
Sample rate (%)5(b) The hidden privacy model(a) The ideal model

Figure 12: NRMSEs of size estimates on Pokec.

Figures 6 and 7 show the NRMSEs of each estimator for various
probabilities of p with 1% sample size in the ideal model. The NRMSEs of both estimators are equal when p = 0 because of Propositions
4.4 and 4.11. The proposed estimators have lower NRMSEs for mostprobabilities of p > 0 than those of the existing estimators. For example, the proposed estimators improve the NRMSE approximately
88.1%, e.g., from 0.294 to 0.035, for p = 0.3 in Figure 7 (b). Figures 8
and 9 show that the proposed estimators improve the NRMSEs on
all four datasets in the hidden privacy model as well.
The improvement of estimation errors results from that of expected errors of convergence values. Figures 10 and 11 show the
NRMSEs of convergence values obtained from Lemmas 4.1, 4.3, 4.8
and 4.10 for various probabilities of p on YouTube and Orkut. The
NRMSEs of both estimators are equal to 0 when p = 0 because of
Propositions 4.4 and 4.11. The proposed estimators improve the
NRMSEs of convergence values for any p > 0; this supports theclaims of Corollaries 4.7 and 4.13. We have obtained similar resultson Facebook and LiveJournal.
The errors of estimation and convergence values are affected by
the relative size of the largest public-cluster because we sample thenodes only on the largest public-cluster. On Orkut where almost
all the public nodes belong to the largest public-cluster (see Figure4), the convergence values of proposed estimators are almost equal
to true values for any probabilities of p (see Figures 10 and 11);
this supports the claims of Theorems 4.6 and 4.12. Consequently,
the NRMSEs of estimates on Orkut do not almost increase as theprobabilities of p increases (see Figures 6, 7, 8, and 9). Conversely, onYouTube where there are the most public nodes that do not belong
to the largest public-cluster among four datasets, the NRMSEs of
the estimation and convergence values relatively increases.

5.3

Estimation in Real-World Datasets

We evaluate the performance of the proposed estimators in two
realistic datasets including real private users.
5.3.1 Pokec. We use the Pokec dataset [18, 25] that contains all
the graph data and real privacy labels of the Pokec network. There
are 552525 private nodes (approximately 33.8%) on the Pokec graph.
We evaluate errors of estimates and convergence values obtainedby the existing and proposed estimators using this dataset.
Figures 12 and 13 show the NRMSEs of each estimator for various sample sizes. In both access models, the proposed estimators

0.30

0.30

0.25

0.25

0.20

NRMSE

Estimation Accuracy for Percentage ofPrivate Nodes
NRMSE

5.2

SmoothProposed

0.15

0.20

0.10

0.10

0.05

0.05

0.00

1

2
3
4
Sample rate (%)(a) The ideal model

5

SmoothProposed

0.15

0.00

1

2
3
4
Sample rate (%)5(b) The hidden privacy model

Figure 13: NRMSEs of average degree estimates on Pokec.
Table 2: Convergence values (CV) and relative errors (RE) in
Pokec (left column), and estimates obtained from samplesof public Facebook Users (right column).

Algorithm
NC
Proposed
SmoothProposed

Pokec
CV
RE
1080278.0 0.338
1646880.8 0.009
19.49
0.287
28.31
0.036

Real Facebook
Estimate
480298540.0
656874080.9
102.07137.03

improve the NRMSEs for all sample sizes. The proposed size estimator particularly improves the NRMSE by approximately 92.6%,
e.g., from 0.339 to 0.025, with a 5% sample size in Figure 12 (a).
The improvement of estimation errors results from that of theerrors of convergence values. The left column in Table 2 presents
the convergence values obtained from Lemmas 4.1, 4.3, 4.8 and4.10 and relative errors of each estimator. The proposed estimators
improve the relative errors by 97.3%, e.g., from 0.338 to 0.009, forthe size and 87.5%, e.g., from 0.287 to 0.036 for the average degree.
Moreover, the proposed estimators have convergence values thatare almost equal to the true properties of the whole Pokec graphincluding private nodes. Even though Assumption 2 does not holdfor the Pokec graph, we have obtained reasonable results as claimedin Theorems 4.6 and 4.12.
5.3.2 Real public Facebook user samples. We use a dataset [15] of
1,016,275 real public Facebook user samples obtained by a random
walk during October 2010. We can estimate the size and average
degree of Facebook as of October 2010 using existing and proposed

Proc. 26th ACM SIGKDD Int'l Conf. on Knowledge Discovery & Data Mining(KDD 2020), August 2020

ExactProposed

0.25
NRMSE

Proportion of queried nodes

0.30

0.20
0.15
0.10
0.05
0.00

0.0

0.1

p

0.2

0.3

(a) NRMSEs of the proposed
size estimatorthe proportion of queried nodes by tens of percent with almost thesame accuracy on other datasets as well.
10 1

Exact
Proposed

10 2
0.0

0.1

p

0.2

0.3

(b) Proportion of queried
nodes

Figure 14: Effects of the proposed calculation for publicdegrees on Orkut (the hidden privacy model with 1% samplesize).

estimators, because this dataset contains the ID, exact public-degree,and exact degree of each sampled public user.
The right column in Table 2 shows estimates of each estimator.
We set a threshold, m, in size estimators as 2.5% of the sample size,i.e., m = 25407. Although we cannot evaluate each error because
the true size and average degree of Facebook as of October 2010
are unknown, we believe that estimates are reasonable, considering
two findings in almost the same period.
First, Facebook reported that there were 500 million active users
as of July 2010 [8]. This suggests that there were at least 500 million
users including inactive users at that time. Notably, the estimatedsize in Table 2 includes both active and inactive users. Our estimate,i.e., 657 million, is greater than 500 million, and we speculate thatthe difference (approximately 157 million) includes inactive users.
Second, Catanese et al. obtained an unbiased estimate of the proportion of private users as 0.266 from uniform samples of Facebook
users in August 2010 [4]. From Lemmas 4.2 and 4.9 and Theorems
4.6 and 4.12, we can intuitively estimate the value of p, which isalmost equal to the proportion of private users, from the respectiveNC

estimates as p̂n ≜ 1 − n n̂and p̂avд ≜ 1 −Smoot hd av
д. Here, p̂n anddˆav д

p̂avд are the estimates of p obtained by the existing and proposed
estimators for the size and average degree, respectively. From Table
2, we obtain p̂n and p̂avд as 0.269 and 0.255, respectively, which
are considerably close to the ground truth value of 0.266.

5.4

Effectiveness of the Proposed
Public-Degree Calculation

We evaluate the proposed public-degree calculation for the hidden
privacy model. The proposed size estimator requires the publicdegree of each sample (see Section 4.2). Thus, we compare the size
estimation accuracy and proportion of queried nodes of the exact
and proposed methods. The exact method queries all neighbors ofeach sample to use the exact public-degree in weighting.
Figure 14 shows the experimental result with a 1% sample sizeon Orkut. The proposed approximation provides almost the same
estimation accuracy as the exact method (see Figure 14 (a)). The
proposed method queries approximately 1% nodes; however, theexact method queries over 50% nodes which are much greater than
1% sample size (see Figure 14 (b)). The proposed method reduces

5.5

Seed Selection from the Largest
Public-Cluster

In practical scenarios, we may require additional queries causedby restarting a random walk from another seed in the two cases:(1) when a selected seed is a private node and (2) when a selectedpublic seed is on an isolated public-cluster.
We believe that the number of queries performed in each caseis sufficiently small. For the case of (1), the proportion of private
nodes is empirically smaller than that of public nodes, e.g., 27%
on Facebook [4] and 34% on Pokec [25]. Additionally, one queryis enough to check the privacy label of a node. For the case of (2),
we believe that the number of queries is small under Assumption
2, because of the following two natures of graphs with degree
distributions biased to low degrees [2]. First, most public nodes
belong to the largest public-cluster. In our experiments, even if
0.640
p = 0.3, 99.1% , e.g., 0.694
0.7 in Orkut, 91.4%, e.g., 0.7 in LiveJournal,
0.580
82.8%, e.g., 0.7 in Facebook and 76.7%, e.g., 0.537
0.7 in YouTubeof public nodes belong to the largest public-cluster on average(see Figure 4). Therefore, a selected public seed will belong to thelargest public-cluster with high probability. Second, the size of theisolated public-clusters is considerably smaller than that of thelargest public-cluster. In our experiments, the average absolute size
is only approximately one for every probability of p (see Figure 5).
Therefore, few queries are performed on isolated public-clusters.
We believe that two real-world datasets support Assumption 3.
There is only the largest public-cluster on Pokec; the case of (2)cannot occur. The samples of real public Facebook users provide
an estimated size of 657 million and contain one million uniquesamples; we believe that the samples were obtained from the largest
public-cluster of Facebook as of October 2010.

6

RELATED WORK

Crawling techniques that traverse neighbors are effective to sample graph data in OSNs where neighbor data is obtained throughqueries. The breadth-first search is particularly a basic samplingtechnique applied in early studies on analyzing the graph structureof OSNs [1, 9, 10, 20, 29]. However, Gjoka et al., through the casestudy of crawling in Facebook, demonstrated that the breadth-firstsearch with a small sample size leads to a significant sampling biasthat is difficult to correct [9, 10].
Gjoka et al. designed a practical framework to obtain unbiased estimates of graph properties via a random walk-based sampling in social networks [9, 10]. Gjoka et al. clarified that the re-weighted random walk scheme, where each sample via random walk is weighted
to correct the sampling bias, is effective to obtain unbiased estimates. In this study, we have made the framework of Gjoka et al.
more practical by addressing the effects of private nodes on the
re-weighted random walk scheme for the first time. Specifically, we
have designed a random walk-based sampling algorithm considering private nodes and proposed the weighting methods to reduce
both sampling bias and estimation errors due to private nodes.
The estimation algorithms based on the re-weighted random
walk scheme have been studied for several properties [5, 6, 11, 12,

Proc. 26th ACM SIGKDD Int'l Conf. on Knowledge Discovery & Data Mining(KDD 2020), August 2020

22, 28]. The targeted properties widely range from those of thegraph such as the size and the average degree to those of the nodes
like centralities. We have designed the algorithms to accurately
estimate the size and average degree of the whole graph including
private nodes. This study has focused on estimators for only thesize and average degree; however, there is no particular reason to
be limited to these. The goal of weighting methods to reduce both
sampling bias and errors due to private nodes is shared in designing
all of the random walk-based estimators for social networks. Then,the methodology presented in our study will help these designs.
Ye et al. investigated the effects of private nodes on generalcrawling methods and empirically argued that private nodes cause
only a small reduction rate of the number of nodes and edges
that can be sampled by crawling, under Assumptions 1 and 2 [30].
However, Ye et al. did not support the validity of assumptions.
In this study, we have focused on the effects of private nodes on
random walk-based algorithms. Moreover, we have validated thethree assumptions through experiments using real-world datasets.
Kossinets experimentally discussed the effect of missing thenodes and edges on the properties of social networks [13]. Kossinets
reported that as the proportion of randomly deleted nodes increases,
errors of the size and average degree between the original graphand the remaining largest connected component increase. We havetheoretically analyzed these errors and designed algorithms to improve them under certain assumptions and access models. The
important differences from the study of Kossinets are as follows:(i) we can find most private nodes in neighbors of public nodes onsocial networks under Assumption 1 and (ii) we can reduce the errors due to private nodes by modifying the weighs for each sample
obtained from the largest public-cluster based on Assumption 2.

7

CONCLUSIONS

We have designed re-weighted random walk algorithms considering
private nodes for the first time. The previous studies have notaddressed the effects of private nodes on re-weighted random walkalgorithms because private nodes prevent us from performing asimple random walk on a social graph. We have broken through thissituation by making three assumptions. In particular, Assumption 2
which is seemingly too simple has brought surprisingly reasonable
results in experiments using real-world datasets. Our study has
opened the door to accurately estimate the whole graph topology
of social networks including private nodes.
There are mainly two future works. First, we plan to strengthen
the validity of three assumptions. To further verify Assumptions 1
and 2, we should additionally test the proposed estimators in realsocial networks including private nodes. To support Assumption
3 more, we will improve the sampling algorithm considering thecase that the seed is on an isolated public-cluster. Second, we plan
to design estimators considering private nodes for other properties,
such as clustering coefficients [11] and motifs (or graphlets) [5, 28].

ACKNOWLEDGMENTS
We would like to thank Dr. Minas Gjoka for kind replies to ourquestions. We would like to thank Prof. Naoto Miyoshi for helpfulcomments. This work was supported by New Energy and Industrial
Technology Development Organization (NEDO).

REFERENCES[1] Yong-Yeol Ahn, Seungyeop Han, Haewoon Kwak, Sue Moon, and Hawoong Jeong.
2007. Analysis of Topological Characteristics of Huge Online Social Networking
Services. In WWW. 835–844.
[2] Réka Albert, Hawoong Jeong, and Albert-László Barabási. 2000. Error and attack
tolerance of complex networks. Nature 406 (2000), 378–382.
[3] Lars Backstrom, Paolo Boldi, Marco Rosa, Johan Ugander, and Sebastiano Vigna.
2012. Four Degrees of Separation. In WebSci. 33–42.
[4] Salvatore A Catanese, Pasquale De Meo, Emilio Ferrara, Giacomo Fiumara, andAlessandro Provetti. 2011. Crawling Facebook for Social Network Analysis
Purposes. In WIMS. 1–8.
[5] Xiaowei Chen, Yongkun Li, Pinghui Wang, and John Lui. 2016. A General
Framework for Estimating Graphlet Statistics via Random Walk. PVLDB 10, 3(2016), 253–264.
[6] Anirban Dasgupta, Ravi Kumar, and Tamas Sarlos. 2014. On Estimating the
Average Degree. In WWW. 795–806.
[7] Ratan Dey, Zubin Jelveh, and Keith Ross. 2012. Facebook Users Have Become
Much More Private: A Large-Scale Study. In 2012 IEEE International Conference
on Pervasive Computing and Communications Workshops. 346–352.
[8] Facebook. 2010. Facebook 500 Million Stories. https://www.facebook.com/notes/
facebook/500-million-stories/409753352130/.
[9] Minas Gjoka, Maciej Kurant, Carter T Butts, and Athina Markopoulou. 2010.
Walking in Facebook: A Case Study of Unbiased Sampling of OSNs. In INFOCOM.
1–9.
[10] Minas Gjoka, Maciej Kurant, Carter T Butts, and Athina Markopoulou. 2011.
Practical Recommendations on Crawling Online Social Networks. IEEE Journal
on Selected Areas in Communications 29, 9 (2011), 1872–1892.
[11] Stephen J Hardiman and Liran Katzir. 2013. Estimating clustering coefficientsand size of social networks via random walk. In WWW. 539–550.
[12] Liran Katzir, Edo Liberty, and Oren Somekh. 2011. Estimating sizes of social
networks via biased sampling. In WWW. 597–606.
[13] Gueorgi Kossinets. 2006. Effects of missing data in social networks. Social
networks 28, 3 (2006), 247–268.
[14] Jérôme Kunegis. 2013. KONECT – The Koblenz Network Collection. In WWW.
1343–1350.
[15] Maciej Kurant, Minas Gjoka, Carter T Butts, and Athina Markopoulou. 2011.
Walking on a Graph with a Magnifying Glass: Stratified Sampling via Weighted
Random Walks. In SIGMETRICS. 281–292.
[16] Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. 2010. What isTwitter, a Social Network or a News Media?. In WWW. 591–600.
[17] Chul-Ho Lee, Xin Xu, and Do Young Eun. 2012. Beyond random walk andmetropolis-hastings samplers: why you should not backtrack for unbiased graphsampling. In SIGMETRICS. 319–330.
[18] Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network
Dataset Collection. http://snap.stanford.edu/data.
[19] David A Levin and Yuval Peres. 2017. Markov Chains and Mixing Times. Vol. 107.
American Mathematical Soc.
[20] Alan Mislove, Massimiliano Marcon, Krishna P Gummadi, Peter Druschel, andBobby Bhattacharjee. 2007. Measurement and Analysis of Online Social Networks.
In IMC. 29–42.
[21] Seth A Myers, Aneesh Sharma, Pankaj Gupta, and Jimmy Lin. 2014. Information
Network or Social Network? The Structure of the Twitter Follow Graph. In WWW.
493–498.
[22] Kazuki Nakajima and Kazuyuki Shudo. 2020. Estimating High Betweenness
Centrality Nodes via Random walk in Social Networks. Journal of Information
Processing (JIP) 28 (2020). (to appear).
[23] Bruno Ribeiro and Don Towsley. 2010. Estimating and Sampling Graphs with
Multidimensional Random Walks. In IMC. 390–403.
[24] Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Repository with
Interactive Graph Analytics and Visualization. In AAAI. 4292–4293.
[25] Lubos Takac and Michal Zabovsky. 2012. Data analysis in public social networks.
In International Scientific Conference and International Workshop Present Day
Trends of Innovations.
[26] Twitter. 2020. Twitter API GET followers/ids. https://developer.twitter.com/en/
docs/accounts-and-users/follow-search-get-users/api-reference/get-followersids.html.
[27] Twitter. 2020. Twitter API GET friends/ids. https://developer.twitter.com/en/
docs/accounts-and-users/follow-search-get-users/api-reference/get-friendsids.html.
[28] Pinghui Wang, John Lui, Bruno Ribeiro, Don Towsley, Junzhou Zhao, and Xiaohong Guan. 2014. Efficiently Estimating Motif Statistics of Large Networks.
TKDD 9, 2 (2014).
[29] Christo Wilson, Bryce Boe, Alessandra Sala, Krishna PN Puttaswamy, and Ben Y
Zhao. 2009. User interactions in social networks and their implications. In EuroSys.
205–218.
[30] Shaozhi Ye, Juan Lang, and Felix Wu. 2010. Crawling Online Social Graphs. In
APWEB. 236–242.

Proc. 26th ACM SIGKDD Int'l Conf. on Knowledge Discovery & Data Mining(KDD 2020), August 2020

In the supplement, we show the pseudo code and proofs that
could not be included in the main manuscript due to space limitations and the information for reproducing the experimental results.

of the stationary distribution. The probability Pr [x r = i] converges
to the corresponding stationary distribution after many steps. □B.2
A

PSEUDO-CODE

Algorithm 1 Random walk in the hidden privacy model.
Require: seed v x 1 ∈ C ∗ , sample size r
Ensure: sampling list R
1: R ← empty list
2: for k = 1 to r do
3:
d x k ← the degree of v x k
4:dˆx∗k ← 0
5:
append (x k , d x k , dˆx∗k ) → R
6:
if v x k has been visited for the first time then7:axk ← 08:
bx k ← 0
9:
end if10:
flag ← False
11:
while flag is False do
12:v x k +1 ← a neighbor of v x k chosen randomly
13:
bx k ← bx k + 1
14:
if v x k +1 is a public node then15:
axk ← axk + 1
16:
flag ← True17:
end if18:
end while
19: end for
20: for k = 1 to r doax
21:dˆx∗k ← d x k b k
22: end for

d x∗k
d x k because X̂ k (l) follows a Bernoulli distribution for each l. Then,d x∗
bx
it holds E[dˆx∗k ] = d x k d k = d x∗k . Because {X̂ k (l)}l =1k is a process ofxk
independent and identically distributed trials, dˆx∗k converges to its

expectation after many steps of the designed random walk becauseof the law of large numbers.
□

B.3

Algorithm 1 describes the designed random walk-based sampling using the proposed public-degree calculation in the hidden
privacy model. The process in lines from 11 to 18 will be successfully
performed, because the k-th sample, v x k , has at least one public
neighbor v x k −1 for 2 ≤ k ≤ r and v x 1 is on the largest public-cluster.
Additionally, it follows that bx k > 0 for each sample v x k , becausea neighbor selection is performed at least once for each sample.

Proof of Lemma 3.3

Proof. It holds Q(k) = d x k , because the exact method queries
all neighbors of each sample. Therefore, we haveÍ∗Õ d∗v i ∈V ∗ di dii
E[Q] = E[Q(k)] =E[Q(k)|x k = i] =
.
∗
∗
D
∗ D
v i ∈VThe first and second equations hold because of the linearity of
expectation and the law of total expectation.
Q̂(k) follows the geometric distribution with success probabilityd x∗k
d x k , because the proposed method randomly queries neighborsof v x k until the public neighbor is firstly selected. Thus, it holdsdx

E[Q̂(k)] = d ∗ k . Then, we havexkÍÕ d ∗ div i ∈V ∗ dii
E[Q̂] = E[Q̂(k)] =.
∗ d∗ =
D
D∗
∗
i

xk

23: return R

Proof of Lemma 3.2

Proof. Let X̂ k (l) denote a random variable which returns 1 if apublic neighbor of v x k is selected at the l-th trial, otherwise 0, whereÍbx
1 ≤ l ≤ bx k and it holds l =1k X̂ k (l) = a x k . It holds Pr [X̂ k (l) = 1] =v i ∈V□

Lemma 3.3 holds because of the above equations.

B.4

Proof of Lemma 4.1

Proof. First, we calculate the expectation of ΦnN C :hiÕ  d∗ 2i
E ΦnN C = E[ϕ k ,l ] =∗ .
D∗v i ∈VThe first equation holds because of the linearity of expectation.
The second equation holds because v x k and v xl are independentlyd∗

We show proofs of Lemmas 3.1, 3.2, 3.3, 4.1, 4.2, 4.3, 4.5, 4.8, 4.9,
4.10, Proposition 4.4, Theorems 4.6, 4.12, and Corollary 4.7.

sampled with the probability Di∗ . Then, we obtain
 ∗ 
h
i
Õ Õ d ∗ d j∗ d ∗Õ  d∗ 2
dx
i
i
i
∗
E ΨnN C = E ∗k =
=
n
∗ ∗ ∗
∗ .
dxl
∗
∗ dj D D∗ D

B.1

We conclude that n N C converges to n ∗ , because ΦnN C and ΨnN C

B

PROOFS

Proof of Lemma 3.1

Proof. First, it holds Pr [x r = i] = 0 for each node vi ∈ V \V ∗ ,because we cannot reach nodes not in V ∗ . Then, for each noded∗vi ∈ V ∗ , we show that Pr [x r = i] converges to Di∗ after many
steps. The designed random walk started from the seed on C ∗ has
the transition probability matrix P = {Pi,j }vi ,v j ∈V ∗ , where Pi,jis d1∗ , if (vi , v j ) ∈ E ∗ , otherwise, 0. P is ergodic because C ∗ is aiconnected graph, and hence, the stationary distribution uniquely
exists because of the Theorem 2.1. {pi }vi ∈V ∗ satisfies the definitionv i ∈V v j ∈Vv i ∈Vintuitively converge to their respective expectations.

B.5□

Proof of Lemma 4.2

Proof. We define the random variable X n (i) = 1V ∗ (vi ) for eachÍnode vi ∈ V . It holds n∗ = vi ∈V X n (i). The expected value of n∗regarding Lpr i is given by:ÕÕ
Epr i [n ∗ ] =Epr i [X n (i)] =Pr [vi ∈ V ∗ ] = (1 − p)n.
v i ∈Vv i ∈V

Proc. 26th ACM SIGKDD Int'l Conf. on Knowledge Discovery & Data Mining(KDD 2020), August 2020

The first and second equations hold because of the linearity of the
expected value and the law of total expectation.
□

B.6

Proof. As with the proof of the Lemma 4.1, we haveÕ d ∗d i
 dxi
E Ψ̂n = E ∗k = n∗
.
∗ )2
dxl
(D
∗
v ∈V
i

□

Proof of Proposition 4.4

Proof. When there are no private nodes on G, we have V ∗ = V
and di∗ = di for each node vi ∈ V ∗ , because C ∗ is equivalent to G.
Thus, it holds n N C = n̂ from the definitions. It holds n∗ = ñ = n
because of Lemmas 4.1 and 4.3.
□

B.8

Smoot h converges to the expected value after many steps
Because Φavд
Smoot h converges to d ∗ .
because of Theorem 2.2, davд
□
avд

B.12

Proof of Lemma 4.9

Proof. We define the random variable X avд (i) = di∗ 1V ∗ (vi ) forÍ
each node vi ∈ V . It holds D ∗ = vi ∈V X avд (i). The expected∗value regarding Lpr i of D can be derived:Õ
Epr i [D ∗ ] =Pr [vi ∈ V ∗ ]Epr i [di∗ ] = (1 − p)2 D.
v i ∈V

Consequently, it follows that Lemma 4.9 holds because of the above
equation and Lemma 4.2.
□

Proof of Lemma 4.5

Proof. di∗ follows the binomial distribution with parameters di
and 1−p regarding Lpr i , because each neighbor of vi independently
becomes a public node with probability 1 − p.
□

B.9

xk

v i ∈V

Because ΦnN C and Ψ̂n intuitively converge to the expected values

B.7

Proof of Lemma 4.8

Smoot h be the weighted average of 1 for samples.
Proof. Let Φavдd∗Smoot h as follows:
We calculate the expectation of ΦavдhiÕ d∗ 111iSmoot hE Φavд
=E ∗ =.
∗ ∗ = d∗dxk
avд
∗ D di

Proof of Lemma 4.3

respectively, n̂ converges to ñ.

B.11

Proof of Theorem 4.6

B.13

Proof of Lemma 4.10

Proof. Let Φ̂avд = r1Ír

1 be the weighted average of 1
dxk
k =1 d x k

for samples. Then, we have:Õ d∗ 111iE[Φ̂avд ] = E=.
∗d = ˜
dxk
D
i
d
∗
avд

Proof. We define the random variables X̂ n (i) = di∗di 1V ∗ (vi )and Ŷn (i) = (di∗ )2 1V ∗ (vi ) for each node vi ∈ V . Also, let X̂ =
Í
Í
Í
∗
∗ 2
v i ∈V ∗ di di and Ŷ = v i ∈V ∗ (di ) . It holds X̂ = v i ∈V X̂ n (i) andÍ
Ŷ = vi ∈V Ŷn (i). We obtain the expectation of X̂ regarding Lpr i :ÕÕ
Epr i [X̂ ] =Pr [vi ∈ V ∗ ]Epr i [di∗di ] = (1 − p)2(di )2 .

Since Φ̂avд converges to the expected value after many steps because of Theorem 2.2, dˆavд converges to d˜avд .
□The second equation hold because of Lemma 4.5. We note that thedegree di is a constant regarding Lpr i . Similarly, the expectationof Ŷ regarding Lpr i can be obtained as follows:Õ
Epr i [Ŷ ] =Pr [vi ∈ V ∗ ]Epr i [(di∗ )2 ]Proof. We define the random variable X̂ avд (i) = di 1V ∗ (vi ) foriÍd∗each node vi ∈ V . Also, let X̂ avд = vi ∈V ∗ di . It holds X̂ avд =i
Í
v i ∈V X̂ avд (i). We obtain the expectation of X̂ avд regarding Lpr i : ∗ÕdEpr i [X̂ avд ] =Pr [vi ∈ V ∗ ]Epr i i = (1 − p)2n.
div i ∈Vv i ∈Vv i ∈V= (1 − p)2

Õ

B.14

Proof of Theorem 4.12d∗v i ∈Vdi [(1 − p)di + p].

Using the fact that Epr i [D ∗ ] = (1 − p)2 D and the above equation,
we have that the Theorem 4.12 holds.
□

v i ∈V

Theorem 4.6 holds because of above equations and Lemma 4.2.

B.10

v i ∈V□

Proof of Corollary 4.7

Proof. From Lemma 4.2 and Theorem 4.6, it is sufficient to showthat |1 − αp | ≤ p. First, we show that 1 − αp ≥ 0:
Íp vi ∈V di
1 − αp = Í≥ 0.
v i ∈V di [(1 − p)di + p]
The inequality holds because it holds di ≥ 1 for each node vi ∈ V ∗and 0 ≤ p ≤ 1. It holds equality when p = 0. Therefore, it is enoughto show that 1 − αp ≤ p. We haveÍv i ∈V [di (di − 1)]
1 − αp − p = −(1 − p)p Í≤ 0.
v i ∈V di [(1 − p)di + p]
The inequality holds since it holds di ≥ 1 for each node vi ∈ V ∗and 0 ≤ p ≤ 1.
□

C

ADDITIONAL INFORMATION FOR
REPRODUCING EXPERIMENTAL RESULTS

All the original datasets are publicly available as follows:
YouTube: http://konect.uni-koblenz.de/networks/com-youtube
Pokec: http://snap.stanford.edu/data/soc-Pokec.html
Orkut: https://snap.stanford.edu/data/com-Orkut.html
Facebook: http://networkrepository.com/socfb-A-anon.php
LiveJournal: https://snap.stanford.edu/data/com-LiveJournal.html
Real public Facebook user samples: http://odysseas.calit2.uci.
edu/doku.php/public:osn_datasets#facebook_weighted_random_walks
The datasets and source code that were used to generate theresults in this paper are available at https://github.com/kazuibasou/
KDD2020.

Proc. 26th ACM SIGKDD Int'l Conf. on Knowledge Discovery & Data Mining(KDD 2020), August 2020