Comparing Graph Sampling Methods Basedon the Number of Queries
Kenta Iwasaki and Kazuyuki Shudo
Tokyo Institute of Technology

Abstract—Random walk-based graph sampling methods caneffectively estimate feature values in large-scale social networks
wherein the node IDs are unknown. Real social networks are
sampled by repeatedly querying their APIs to acquire the lists ofadjacent nodes. These queries can then become a bottleneck inthe sampling process because nearly all social network services
restrict the rate at which queries can be issued. However,most existing graph sampling studies have not focused on thenumber of queries but have instead compared methods basedon sample size. Therefore, such graph sampling methods cannot
be recommended for estimating feature values in actual social
networks. This study presents an approach to assess graphsampling methods that focus on the number of queries. This
describes the time taken by algorithms for typical random
walk-based graph sampling methods, such as a simple random
walk with re-weighting (SRW-rw), a non-backtracking random
walk with re-weighting (NBRW-rw), and a Metropolis ‒ Hastings
random walk (MHRW), which require queries. The graphsampling precision was then experimentally evaluated based on
sample size and query number standards using actual social
networks, and the types of changes that occur were observed.
Index Terms—graph sampling, social graph, random walk

I. I NTRODUCTION
The sampling of large-scale networks is a fundamental
and important issue in analyzing social networks, such as
online social networks (OSNs) and the World Wide Web.
Several studies have used sampling for estimating networkfeature values when working with huge networks, wherein theentire network cannot be considered or when general network
information, such as node IDs, cannot be obtained [1] [2] [3].
When sampling is used to extract sub-graphs, (i.e., graphs thatmodel parts of the network structure as sets of nodes andedges), it is called graph sampling [4].
Since general network information, such as node IDs, is
not typically published; therefore, estimating social networks
feature values can be difficult. For example, uniform
independent sampling, which randomly samples node IDs,cannot be used because the node IDs are unknown. Graphsampling methods that track adjacency relations, known as
crawling methods, are therefore more practical [5]. Amongthese crawling methods, random walk-based methods are
particularly effective because their algorithms are simple andeasy to implement. In addition, they allow us to conduct
This work was supported by JSPS KAKENHI Grant Numbers 2570008
and 16K12406. This work was supported by New Energy and Industrial
Technology Development Organization (NEDO).

unbiased graph sampling using Markov chain analysis.
Random walks are not the only possible approach: scanning
methods, such as breadth-first sampling (BFS) [6], have also
been proposed; however, since their sampling deviations are
unknown, they are unsuitable for estimating feature values.
When applying a crawling method to an actual social
network, the sampling process involves repeatedly either
querying, e.g., the OSN s API, or scraping. Herein, eachquery acquires a list of nodes adjacent to the current
Internet-connected node. In the example shown in Figure 1,
the researcher is using a query to acquire a list of adjacentnodes. As another example, a previous study [2] showed
how Facebook could be sampled by repeatedly acquiring thefriend lists of Facebook users. In the sampling process, theacquisition of the adjacent node list with a query can become
a bottleneck because with many social networks, the numberof queries that can be used within a fixed unit of time isrestricted. In addition, even if this were not restricted, given thefact that access via communications is slower than the speedof accessing computer memory or a disk, the acquisition of theadjacent node list via the query may still become a bottleneck.
Therefore, the performance of the graph sampling methodshould be compared based on the number of queries. However,comparisons of the estimation accuracy using the graphsampling method are based on existing studies [7], [8], which
often involve experiments based on sample sizes (the lengthof a sample sequence); thus, recommending an appropriate
method for sampling actual social networks can be difficult.
This study proposes a comparison of sampling methods that
focuses on the number of queries. This comparison describes
the timing within the algorithm for typical random-walk-basedgraph sampling methods, such as a simple random walkwith re-weighting (SRW-rw) [5], [9], a Metropolis ‒ Hastings
random walk (MHRW) [5], [9], [10], and a non-backtracking
random walk with re-weighting (NBRW-rw) [7], which require
queries. The feature values are estimated based on the numberof queries for actual social networks, and the performance ofthe graph sampling methods was compared.
This paper is organized as follows. Section II describes
the background for this study and explains the notation anddefinition of terms. Section III describes the graph sampling
method using the random walk method. Section IV explains
the computational experiment conducted herein. Section V
discusses the related research, and Section VI summarizes thestudy.

Proc. IEEE ISPA-IUCC-BDCloud-SocialCom-SustainCom 2018,
pp.1136-1143, December 2018
 0d(v) = 0ord(v) = 1
2△c(v) =i
otherwised(v)(d(v) − 1)
Fig. 1: Example of acquiring an adjacent node list via the API.

(1)

From the definition of the clustering coefficient, c(v) ∈[0, 1]
The clustering coefficient C for the entire network is definedas the mean value of the clustering coefficients for each node.

II. P REPARATIONIn this section, after explaining the method of notationand the definitions of the graphs, the graph feature values
used in this study are described. In addition, existinggraph sampling methods and existing methods of estimatingclustering coefficients are described.
A. Notation
Herein, social networks are expressed as an undirected
graph G(V, E). V = {v1 , v2 , ..., vn } is a set of nodes (termpoints), and the number of nodes for the graph as a whole isexpressed as n = |V |. E is the edge set. The adjacent node
set to node v ∈ V is N (v) = {w ∈ V : (v, w) ∈ E}. The
degree of node v is set to d(v) = |N (v)|.
B. Graph feature values
The typical feature values that characterize complex
networks are described herein. Complex networks are defined
as real-world networks with a huge, complex structure. Nearly
all social networks can be defined as complex networks. The
degree distribution and clustering coefficient estimation error
are used herein.
1) Degree distribution: If the node ratio for degree k for
all nodes is expressed as p(k), the degree distribution can be
defined. In social networks, the degree distribution follows thepower law. In other words, it becomes p(k) ∝ k −γ . This iscalled a scale-free property, which shows that although nearly
all nodes have a small degree, some nodes have a large degree.
These nodes with a large degree are frequently called hubs .
2) Clustering coefficient: The clustering coefficient is an
important feature value in the network and is often used in
network analyses [2]. In a complex network, a triangle is calleda cluster . The term cluster normally refers to a herd or agroup and is used in several ways in research analyses, suchas cluster analysis or cluster synchronicity. In this study, it is
only used to mean triangle. Many clusters are found withinmost real networks, and this is not limited to networks ofhuman relations . To define a network clustering coefficient,
the clustering coefficient c(v) from the number of triangles,
including a node v, is first defined. A method of selecting
two nodes from v neighboring nodes of which there ared(v) is as shown in d(v)(d(v) − 1)/2. Based on this, where
there are edges between the two selected nodes, there is one
triangle including these two nodes and the node v. Therefore,a maximum of d(v)(d(v) − 1)/2 triangles include v Here,
if the number of triangles including v is △i , the clustering
coefficient c(v) can be defined as follows.

C=

1 ∑
c(v)
n

(2)

v∈V

where c(v) is a value for the node and C is the value forthe graph G.
This is C ∈ [0, 1] in relation to any network, and this is C =1 in relation to a complete graph. In nearly all actual networks,
C is large; this is a characteristic of complex networks . In thisstudy, we estimate C for each random walk using the naiveand counting triangles method.
III. R ANDOM WALK - BASED GRAPH SAMPLING
This section explains the algorithm and impartiality of thegraph sampling method using the random walk method. First,
the impartial graph sampling as a base is explained, followedby the algorithm and the method of estimation using eachmethod. In this study, three typical methods of SRW-rw,
NBRW-rw, and MHRW are used.
A. Impartial sampling
When estimating the feature values focusing on the social
network node or topology, it is necessary to perform impartial
sampling using crawling. Thus, uniform node samples are
obtained via a random walk. In this section, our goal is to
impartially estimate the ratio of nodes with specific features.
In other words, impartial sampling involves constructing
a method of sampling using a random walk to obtain the
expectation values related to a uniform distribution of anarbitrary function f : V → R. That is, it is used as a methodof sampling, when expressing the uniform distribution asdef
u = [u(1), u(2), . . . , u(n)] = [1/n, 1/n, . . . , 1/n], in which∑
1def
Eu (f ) =
f (v)
(3)
n
v∈V

produces the expected estimated value. By selecting thefunction appropriately, it is possible to specify the feature
values for the desired node. For example, when estimating
the degree distribution (P{DG = d}, d = 1, 2, . . . , n − 1) of agraph G, f (v) = 1l{d(v)=d} for v ∈ V . We select the function
f so that if d(v) = d, f (v) = 1; otherwise, f (v) = 0.
Next, we discuss Markov chain theory, which is thenumerical foundation for impartial sampling using a random
walk on graph G. A typical random walk on graph G oran irreducible finite Markov chain {Xt ∈ V, t = 0, 1...}

Proc. IEEE ISPA-IUCC-BDCloud-SocialCom-SustainCom 2018,
pp.1136-1143, December 2018

with reversibility is defined as having the following transitiondefprobability matrix P = {P (v, w)}v,w∈V
P (v, w) = P{Xt+1 = w | Xt = v}, v, w ∈ V,
(4)∑
For ∀v ∈ V , w∈V P (v, w) = 1. The transition probability
P (v, w) ≥ 0 is allocated to each edge (v, w) ∈ E, and it
is possible for the random walk to transition from node v
to node w. In addition, even when there is no self-loop ingraph G, the transition to the self-node can be set. For v ∈ V ,P (v, v) > 0 may exist. However, transitions between nodes
without edges are not possible. In other words, P (v, w) =0, ∀(v, w) ∈/ E (v ̸= w).
The stationary distribution is π = [π(v), v ∈ V ]. The
following estimator is defined for an arbitrary function f :V → R.
def 1µ̂t (f ) =

t
∑

t s=1

f (Xs )

(5)

Function f expectation values for the stationary distribution
π are given as follows.
∑def
Eπ (f ) =π(i)f (i).
(6)
i∈V

From Ref. [11], where {Xt } is a stationary distribution π
finite, irreducible Markov chain,µ̂t (f ) → Eπ (f ) almost surely (a.s.)(7)

is formed for an arbitrary initial distribution P{X0 = v}, v ∈V, ( t → ∞). However, Eπ (|f |) < ∞.
B. SRW-rw
SRW-rw is a sampling algorithm that includes a methodof calculating the estimated value from the sample nodecollection, whereas simple random walk (SRW) expresses
a simple random walk transition algorithm. This method isused based on a sample sequence obtained from SRW andan appropriate re-weighting process for achieving impartial
sampling. This is essentially a special case for weighted
sampling applied to the random samples generated by theMarkov chain. The basic idea of this method is that thedeviation in the sampling that occurs because of SRW
stationary distribution is corrected via re-weighting.
Here, we explain the method of acquiring graph G of the
SRW sample sequence. The Markov chain expressing thesample sequence for the nodes visited by SRW is {Xt }. If thistransition probability matrix is PSRW = P SRW (v, w)v,w∈V ,then P SRW (v, w) can be expressed as{ 1(v, w) ∈ E
SRW
d(v)
P
(8)
(v, w) =0
otherwise
The transition probability PSRW is irreducible, and thestationary distribution π SRW (v) = d(v)/(2|E|), v ∈ V is
known to be reversible.

Let us suppose that t samples {Xs }ts=1 are obtained from
SRW. Then, for the arbitrary function f : V → R, theweighted function w : V → R is determined as follows:1∑
w(Xs )f (Xs ) → Eπ (wf ) = Eu (f ) a.s. (9)t s=1tµ̂t (wf ) =Because this is an irreducible finite Markov chain, when t →∞,1∑w(Xs )f (Xs ) → Eπ (wf ) = Eu (f ) a.s. (10)t s=1t

µ̂t (wf ) =is a strongly consistent estimator. However, this is not practicalbecause |E| is not usually known in advance; therefore, thefollowing type of estimator is often used. When t → ∞,∑tw(Xs )f (Xs )µ̂t (wf )= s=1→ Eu (f ) a.s.
(11)∑tµ̂t (w)
s=1 w(Xs )Then, by setting w(v) = 1/d(v), an unbiased estimation
can be conducted. In this study, µ̂t (wf )/µ̂t (w), w(v) =1/d(v)(v ∈ V ) is treated as an unbiased estimator in SRW-rw.
As an example, we estimate the degree distribution using
SRW-rw. To estimate the degree distribution P{DG = d} forthe target graph G, we select f (v) = 1l{d(v)=d} for v ∈ V .
Then, for an arbitrary degree distribution d,∑t∑
1l{d(Xs )=d} /d(Xs )1µ̂t (wf )= s=1∑t→1l{d(v)=d} a.s.,µ̂t (w)n
s=1 1/d(Xs )v∈VThis demonstrates that the estimator µ̂t (wf )/µ̂t (w) is a valid
impartial estimation of the degree distribution P{DG = d}.
Queries are required within the SRW-rw algorithm when
determining the transition destination nodes from the adjacentnode list and when using degree information as weighting.
Because the degree information is known from the visitednode, the number of queries is equal to the number of uniquenodes among those visited.
C. Non-backtracking Random Walk with Re-weighting
In this section, we discuss NBRW-rw [7]. NBRW-rw isbased on a sample sequence obtained from nonbacktracking
random walk (NBRW) and a suitable reweighting process toachieve impartial sampling. This demonstrates that for thereweighting process in the second part, the same process canbe applied as in SRW-rw. In addition, we can see that theestimator using NBRW-rw produces a lower distribution value
than the estimator using SRW-rw [7]. This section describes
the NBRW transition method and provides an overview of theweighting process.
The NBRW transition method uses a random walk to
uniformly and randomly select from adjacent nodes while
avoiding a transition to the previous node. As an exception,
this does not apply when there is an initial node and a
degree-one node.
Now, we will explain the NBRW-rw re-weighting process.
Let us denote the t step node visited with NBRW as Xt′ ∈ V .
′Determining the next node Xt′ from Xt+1
depends on Xt′ andProc. IEEE ISPA-IUCC-BDCloud-SocialCom-SustainCom 2018,
pp.1136-1143, December 2018

′
on Xt−1
because of the algorithm, which avoids the previous
node. Therefore, {Xt′ }t≥0 is not a Markov chain in the V
node state space. However, we can see that this formed via
the following formula from Ref. [7].

1∑f (Xs′ ) → Eπ (f )a.s.
t s=1t

stationary distribution is a uniform distribution. If we assume
that t samples {Xt }ts=1 are obtained from MHRW because
there is an irreducible finite Markov chain for an arbitrary
function f : V → R, when t → ∞,1∑f (Xt ) → Eu (f ) a.s.,
t s=1
t

(12)

Because π is a stationary distribution of SRW, an impartial
estimation can be conducted using the same weighting process
as used in SRW [7] Queries are required within the NBRW-rw
algorithm when determining the transition destination from theadjacent node list and when using the degree information as
weighting. Similar to SRW-rw, because the degree information
is known from the visited node, the number of queries is equal
to the number of unique nodes among the visited.
D. Metropolis-Hastings Random Walk
Whereas with SRW or NBRW, samples tend to be biased
toward high degree nodes, MHRW can appropriately transformthe transition probability so that the stationary distribution isa uniform distribution. Because the Metropolis ‒ Hastings(MH) algorithm [12] performs sampling from a complex
probability distribution µ, this is a typical Markov chain
Monte Carlo (MCMC) method. We can see that if we need toperform sampling from a uniform distribution µv = n1 , as on
this occasion, we can achieve this by defining the transition
probability in the following way.

1
1
(v, w) ∈ E
 min(∑
d(v) , d(w) )MHP(v, w) =(13)
1 − y̸=v P M H (v, y) w = v
0otherwise
Then, the stationary distribution is π M H (v) = n1 , which
is a uniform distribution. Contrary to SRW, MHRW may
sometimes transition to its own node. In this case, we add
a new sample sequence. We can express this MH algorithm
as in Algorithm 1. Then, Xt ∈ V is the t-th node of MHRW,
and X0 is selected arbitrarily.
Algorithm 1 MH algorithm in MHRW (at time t).
randomly select node w from the adjacent node list N (Xt )generate p ∼ U (0, 1)t)
if p ≤ d(Xd(w) thenXt+1 ← v
else
Xt+1 ← Xt
end if
It is notable that Algorithm 1 does not require obtaining
its own transition probability P M H (v, v) and does not requireknowing the degree of the nodes in the t step node Xt adjacentnode list. Instead, if only the degree information for node w is
selected at random, it is possible to select whether to transition
to w.
Impartial estimations using MHRW, unlike SRW-rw, do
not require reweighting calculations because the MHRW

(14)

Note that, as expressed in Algorithm1, in the case of
self-transition, it is necessary to add one sample.
Queries are required within the MHRW algorithm when
stopping at node v, when acquiring the node v adjacent list,
and when used to obtain the degree information from thenode v transition destination nodes. Therefore, the numberof queries is basically the number of unique visited nodes;
however, where a self-loop occurs, additional queries are
required.
E. Graph sampling focusing on the number of queries
To estimate the feature values, graph sampling uses two
types of timings at which the adjacent node list can be acquired
as follows.
• When determining the next transition node using thecrawling algorithm• When calculating function f (v) to estimate feature
values, (from formula 5)
Crawling algorithm requires an adjacent node list acquisition
query to determine the next transition destination node. In
other words, for nodes that have been already visited, a queryis always used once to acquire the adjacent node list of that
node. With SRW and NBRW, the number of specific visited
nodes is equal to the number of queries in the crawlingalgorithm. In the case of MHRW, when a self-loop occurs,
there is a possibility that the query will be wasted; therefore,
the number of specific visited nodes ≤ number of queries in
the crawling algorithm. The adjacent node list of the nodes
that are visited once can be reused when revisiting and whenestimating feature values.
The number of queries when calculating function f (v) toestimate feature values differs according to the feature values
that are to be estimated. This can be broadly divided into cases
wherein feature value estimation is possible by reusing theadjacent node list obtained via the query used when runningthe crawling algorithm, as well as feature values for whichfurther queries are required. The former is a case wherein f (v)can be calculated using the information from the list adjacent
to node v. For example, clustering coefficient estimation uses
average degree, degree distribution, and the counting triangles
method. The latter equates to naive clustering coefficientestimation.
Figure 2 is an example of the node range using queries
for calculation when performing naive clustering coefficientestimation, i.e., f (v) = c(v). The blue nodes for the query
range used within the crawling algorithm should acquire
adjacent nodes with queries up to the yellow range to calculate
the clustering coefficients. In this way, the necessary query

Proc. IEEE ISPA-IUCC-BDCloud-SocialCom-SustainCom 2018,
pp.1136-1143, December 2018

(a) Mean number of queries(b) Mean sample size per 10,000
required for a 10,000-sample
queries.
size.
Fig. 2: Example of query range for obtaining adjacent node list.

range differs according to the feature value that has to beobtained via graph sampling. Incidentally, the range between
the focal adjacent node, as well as the adjacent nodes of thatadjacent node, is called the ego network.
In contrast, when estimating the same feature value, if themethod of setting f (v) changes, the necessary query range
may change. To use the example of clustering coefficients,using the counting triangles method, this is f (v) = ϕk · w(v)[8]. During this time, when ϕk is the k-th step, if an edge
exists between the node in the k+1 step and the k ‒ 1 node,
the value of ϕk will be 1; and if the edge does not exist, thevalue will be 0. The definition of w(v) changes based on the
random walk; however, this is a function that determines thedegree information. Therefore, the clustering coefficients canbe estimated using only the queries required in the crawlingalgorithm.
IV. E XPERIMENTS
The SRW-rw, NBRW-rw, and MHRW performance with thequery number standard and sample size standard are describedherein.
A. Data set
We performed an experiment using the social
network/citation network publicized with the Stanford
Network Analysis Project (SNAP) [13]. Table I shows an
overview of each data set. Cases wherein graph sampling canpractically occur are those in which the target social network
is unknown; however, we performed a simulation in relation
to graph data where the overall image is known.
TABLE I: Network statistical volume.
Networkclustering coefficient
Amazon
DBLP
GowallaNumber of nodes

Average degrees

Average

334,863
317,080
196,591

5.530
6.622
9.668

0.3967
0.6324
0.2367

B. Number of Queries by Random Walk
Figure 3 shows the mean number of queries and the sample
size when simulating 100 random walks each for SRW,NBRW, and MHRW. Figure 6a shows the average number

Fig. 3: Relation between number of queries and sample size byrandom walk for each network.

of queries required for the sample size (length of sample nodesequence) to reach 10,000 times when sampling SRW, NBRW,
and MHRW. Figure 6b shows the mean sample size to acquire
10,000 queries for each random walk. Based on the ascending
width size value, these queries are NBRW, SRW, and MHRW.
C. Clustering coefficient estimation
In this section, the two types of clustering coefficientestimation experiments performed in Figures 4 and 5 aredescribed. In both the experiments, we plotted the normalized
root-mean-square error (NRMSE) [14] with the horizontal axis
as the sample size (left side) and number of queries (rightside). The lower the NRMSE value, the √greater the estimation1
accuracy. NMRSE can be calculated C E[(Ĉ − C)2 ], whenĈ is the clustering coefficient estimated value.
In Figure 4, we fix the sampling method as SRW-rw. Then,
we compare NRMSE as an approximate method using thenaive estimation and counting triangles method. With Amazon,
DBLP, we selected 100 as the starting point and performed thesimulations independently. With Gowalla, we selected 10 as
the starting point and performed the simulation independently.
The naive method is defined as f (v) = c(v), v ∈ V in relation
to function f : V → R in formula 5. Here, c(v) is thefunction defined in formula 1. In other words, we calculate theclustering coefficients as defined for each node visited in the
random walk and perform impartial estimation using SRW-rw.
To calculate a clustering coefficient for a certain node theadjacent node lists for that node and for those adjacent nodes
should be acquired; consequently, queries other than random
walk transitions occur.
In contrast, the counting triangles method is a method toestimate clusters without additional queries in relation to thequeries required for random walk transitions. The details aredescribed in Appendix A. In Figure 5, we fix the clustering
coefficient estimation method as the counting triangles method
and compare the NEMSE when changing the transition method
via random walk. For each network, we selected 100 as thestarting point and performed the simulation independently.
We combined the SRW-rw, NBRW-rw, MHRW, and counting
triangles method; in addition, since a combination of theProc. IEEE ISPA-IUCC-BDCloud-SocialCom-SustainCom 2018,
pp.1136-1143, December 2018

Fig. 4: NMRSE for clustering coefficient estimation using naive
method and Counting Triangles method.

MHRW and counting triangles method has not been proposedin the past, a new algorithm in this study has been devised
herein, which is described in Appendix A.
D. Degree distribution estimation error
Degree distribution was estimated via random walk. We
evaluated the complementary cumulative distribution function
P{Dg > d}(CCDF) for each respective network and compared
SRW-rw, NBRW-rw, and MHRW. To estimate P{Dg > d},we defined f (v) = 1l{d(v)>d} , v ∈ V and estimated them.
Similar to the method for clustering coefficients, we comparedestimation accuracy by calculating√ NRMSE. Here, the methodof calculating NRMSE is x1 E[(x̂(t) − x)2 ]. x̂(t) is theestimated value when taking t samples, and x is the true value
when taking t samples. During this time, in case of impartial
estimation, x = limt→∞ x̂(t).
Figure 6 shows a simulation performed independently froma starting point of 100 for each network and plots the NRMSE
for each method. The sample size standard accuracy is on theleft side, whereas the query number standard accuracy is on
the right side. The smaller the value, the greater the accuracy;
NRMSE is calculated in the same way for MHRW estimation
accuracy. However, since poor results were obtained when
SRW-rw and NBRW-rw were separated, we displayed a graphcomparing only SRW-rw and NBRW-rw.
E. Observations
As described in Section III-E, graph sampling methods
were compared by focusing on the number of queries. From

Fig. 5: NRMSE when estimating the clustering coefficient for
random walk sequence using the Counting Triangles method.

Figure 3 ,we can compare the number of queries requiredin the crawling algorithm for each random walk. Figure
4 fixes the crawling algorithm and shows an example ofwhen the f (v) setting is changed. Figures 4 and 5 show
examples of fixing f (v) and changing the crawling algorithm.
From Figure 4, it is evident that the accuracy is reversed.
With a query number standard, the NRMSE for the counting
triangles method is smaller than that for the naive method;
therefore, accuracy is determined to be good, whereas witha sample size standard, the naive method exhibits better
accuracy because the counting triangles method calculates
f (v) in a probabilistic way. However, with the naive method,
the clustering coefficient calculation is performed as defined
because this method requires additional queries for calculating
f (v); thus, the counting triangles method produced better
results compared with the query number standard. In thiscase, when considering sampling in actual social networks,
the experiment results from the query number standard should
be used.
The graphs on the left side of Figures 5 and 6 show
a comparison of random walks based on the sample size
standard, and for each result, the accuracy improved in theorder of NBRW, SRW, and MHRW. The results of NBRW vs
SRW for the sample size standard are described in [7], [8]. The
sample size standard degree distribution NRMSE in Figure
6 generally has a lower value for NBRW than SRW, thus

Proc. IEEE ISPA-IUCC-BDCloud-SocialCom-SustainCom 2018,
pp.1136-1143, December 2018

is superior to NBRW-rw impartiality and SRW-rw. In addition,
several studies provide sampling techniques with the objectiveof estimating graph feature values. For methods specializing in
the estimation of clustering coefficients, Hardiman and Katzir[15] [16] were the first to propose the counting triangles
method as a method of approximation, as well as proposeda method combined with SRW-rw. Iwasaki et al. [8] proposeda graph sampling coefficient estimation method in combination
with NBRW-rw and demonstrated that it was superior to
SRW-rw. Combination of MHRW and the counting triangles
method have not been previously proposed; thus, this is a novel
study that proposes the combination of MHRW and counting
triangles method with an overview of the algorithm shown inAppendix A. Chiericetti et al. [17] described query complexity
in uniform sampling. Therein, rejection and maximum-degree
sampling was used for MHRW and graph preinformation,
which is different from the target method used in this study.

Fig. 6: NRMSE per degree d when estimating P{Dg > d}.

leading to the conclusion that NBRW is more accurate than
SRW. However, when looking at the query standard results,
the NBRW and SRW results appear to have an antagonistic
relation. As can be seen from Figure 3, the sample size per
query is larger for SRW compared with that NBRW. In otherwords, when considering the query number standard, the SRW
accuracy is reduced in relation to NBRW compared to the caseof the sample size standard; notably, the SRW accuracy may
even be reversed. In the same way in Figure 5, the accuracy
of NBRW and SRW in the query number standard is smaller
than in the case of sample size standard. Furthermore, thedifference between the accuracy of MHRW and SRW is thesame. With the sample size standard in Figure 5, SRW clearly
exhibits a higher accuracy than MHRW; however, from theresults of the query number standard, the difference in theiraccuracy is reduced and actually reversed with the experimenton DBLP.
V. R ELATED W ORK
Herein, we describe related studies for graph sampling.
Several studies have achieved impartial sampling fromthe network. Gjoka et al. [2] compared SRW-rw that
achieves impartial sampling by reweighting using the standard
distribution via SRW and MHRW using the MHRW algorithm,
thereby demonstrating that SRW-rw shows superior accuracy.
Lee et al. [7] proposed NBRW-rw derived from SRW-rw andshowed that from a logical and experimental perspective, that it

VI. C ONCLUSION
For graph sampling in actual social networks, performancecomparisons with the query number standard are important.
However, experiments using query number standards were
not performed previously because the methods recommended
in those studies may not be valid methods in actual social
networks. In addition, when proposing a new graph sampling
method in the future, it will be necessary to incorporate theresults of the performance comparison with query number
standards.
In this study, after demonstrating the focus points when
considering graph sampling based on the query number
standard, we demonstrated the difference between accuracy
using the traditional sampling size standard and the query
number standard using an experiment. We also demonstrated
an example of performing a query number standard experiment
in relation to the new method of estimating clustering
coefficients using a combination of MHRW and the counting
triangles method. For the previous graph sampling methods,
such as SRW-rw, NBRW-rw, and MHRW, with the sample
size standard, the accuracy was higher in NBRW-rw, SRW-rw,
and MHRW; however, by changing the query standard order,
the difference between each method became smaller. It wasdemonstrated that this may be reversed depending on the target
group and estimated feature values. Furthermore, we showed
an example in which, even when the feature value estimation
function f (v) is changed by method, the results are reversed
based on the sample size standard and query number standard.
Future issues include the logical expression of therelationship between the number of queries and sample size.
The relationship between the sample size number and feature
value estimation accuracy has been evidenced by past studies;so, it is expected that these results can be used to obtain
the relation between the number of queries and feature value
estimation accuracy.
R EFERENCES[1] Y.Y. Ahn, S. Han, H. Kwak, S. Moon, and H. Jeong. Analysis of
topological characteristics of huge online social networking services. In

Proc. IEEE ISPA-IUCC-BDCloud-SocialCom-SustainCom 2018,
pp.1136-1143, December 2018

Proceedings of the 16th international conference on World Wide Web,
pp. 835–844. ACM, 2007.
[2] M. Gjoka, M. Kurant, C.T. Butts, and A. Markopoulou. Walking in
Facebook: A case study of unbiased sampling of OSNs. In Proceedings
IEEE Infocom, pp. 1–9. IEEE, 2010.
[3] A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, andB. Bhattacharjee. Measurement and analysis of online social networks.
In Proceedings of the 7th ACM SIGCOMM conference on Internet
measurement, pp. 29–42. ACM, 2007.
[4] J. Leskovec and C. Faloutsos. Sampling from large graphs. In
Proceedings of the 12th ACM SIGKDD international conference on
Knowledge discovery and data mining, pp. 631–636. ACM, 2006.
[5] M. Gjoka, M. Kurant, C. T. Butts, and A. Markopoulou. Practical
recommendations on crawling online social networks. Selected Areasin Communications, IEEE Journal on, Vol. 29, No. 9, pp. 1872–1892,
2011.
[6] M. Kurant, A. Markopoulou, and P.dd Thiran. Towards unbiased bfs
sampling. Selected Areas in Communications, IEEE Journal on, Vol. 29,
No. 9, pp. 1799–1809, 2011.
[7] C. H. Lee, X. Xu, and D. Y. Eun.
Beyond random walkand metropolis-hastings samplers: why you should not backtrack
for unbiased graph sampling. In ACM SIGMETRICS Performance
Evaluation Review, Vol. 40, pp. 319–330, 2012.
[8] K. Iwasaki, K. Shudo. Estimating the clustering coefficient of a social
network by a non-backtracking random walk. In IEEE BigComp 2018,
pp. 114–118. IEEE, 2018.
[9] A. H. Rasti, M. Torkjazi, R. Rejaie, N. Duffield, W. Willinger,
and D. Stutzbach. Respondent-driven sampling for characterizing
unstructured overlays. In INFOCOM 2009, IEEE, pp. 2701–2705. IEEE,
2009.
[10] M. Al Hasan and M. J. Zaki. Output space sampling for graph patterns.
Proceedings of the VLDB Endowment, Vol. 2, No. 1, pp. 730–741, 2009.
[11] G. L. Jones, et al. On the markov chain central limit theorem. Probability
surveys, Vol. 1, pp. 299–320, 2004.
[12] W. K. Hastings. Monte carlo sampling methods using markov chains
and their applications. Biometrika, Vol. 57, No. 1, pp. 97–109, 1970.
[13] Stanford large network dataset collection. https://snap.stanford.edu/data/.
[14] K. Avrachenkov, B. Ribeiro, and D. Towsley. Improving random walkestimation accuracy with uniform restarts. In International Workshop on
Algorithms and Models for the Web-Graph, pp. 98–109. Springer, 2010.
[15] S. J. Hardiman and L. Katzir. Estimating clustering coefficients andsize of social networks via random walk. In Proceedings of the 22nd
international conference on World Wide Web, pp. 539–550. International
World Wide Web Conferences Steering Committee, 2013.
[16] L. Katzir and S. J. Hardiman. Estimating clustering coefficients andsize of social networks via random walk. ACM Transactions on the
Web (TWEB), Vol. 9, No. 4, p. 19, 2015.
[17] F. Chiericetti, A. Dasgupta, R. Kumar, S. Lattanzi, and T. Sarlós. On
sampling nodes in a network. In Proceedings of the 25th International
Conference on World Wide Web, pp. 471–481. International World Wide
Web Conferences Steering Committee, 2016.

A PPENDIX
In this appendix, we describe the basic thinking underlying
the counting triangles method as an approximation algorithm
for clustering coefficient estimation using experiments in thisstudy. In addition, we propose a counting triangles method
through MHRW, which has not been proposed until now.
The counting triangles method is a technical method toestimate clustering coefficients by investigating the triangularstructures that emerge during the random walk. Until now,
we have proposed a method by which the counting triangles
method can be applied to SRW and NBRW [8], [15]. A
salient aspect of the counting triangles method is that it
does not require additional queries, as the queries required
for random walk transitions do. As a method of calculating
the clustering coefficients as defined, additional queries wererequired to calculate clustering coefficients [2]. Therefore, it

is an important point whether additional queries are requiredor not.
The basic thinking behind the counting triangles method
is to uniformly and randomly select two nodes v1, v2 fromv adjacent nodes in relation to degree 2 or more nodes v
visited during the random walk. If an edge exists between
v1, v2, this is counted as a triangular structure. Here, theprobability expectation value that a triangular structure exists
is defined with a weighted coefficient, so that the clustering
coefficients of node v are equal. In case of SRW, the weighted
coefficient is d(v)/(d(v) − 1), and in case of NBRW, theweighted coefficient is 1. Nodes wherein the degree is 1 or
below have a clustering coefficient of 0; therefore, there is noneed to confirm the triangular structures. When implementing
this, v1 ∈ N (v2 ) or v2 ∈ N (v1 ) can be confirmed. Thus, it isnecessary to obtain the v1 or v2 adjacent node list. With thecounting triangles method using SRW and NBRW, by defining
v1 = {node visited one step before v} and v2 = {node visited
1 step after v}, two nodes can be uniformly and randomly
selected from the adjacent node list; this satisfies the state ofknowing the adjacent node list of one of the nodes without
requiring any additional queries.
Next, the counting triangles method with MHRW is
described. Owing to the fact that the MHRW transition
destination node is the node selected uniform and randomly
from the adjacent node list, this cannot be defined as v1 ={node visited one step before v}and v2 = { node visited 1
step after v}, as in SRW or NBRW. Therefore, it is necessary
to devise a way of selecting v1, v2. In this study, in relation
to node v of degree 2 or greater visited in MHRW, wedefine v1 as { transition destination candidate node w within
MHRW transition Algorithm 1 } and v2 as the { node selectedin uniform random from list N (v)/{v1 } after v1 has been
removed from the v adjacent node list }. At this time, theprobability expectation value v2 ∈ N (v1 ) is equal to theclustering coefficient of node v. Furthermore, with MHRW,
because it is necessary to know the degree of the transition
destination candidate nodes to obtain the receive rate to thetransition destination candidate nodes within the transition
algorithm, the v1 adjacent node list is obtained within thetransition algorithm. Therefore, an additional query is not
required when applying the counting triangles method.

Proc. IEEE ISPA-IUCC-BDCloud-SocialCom-SustainCom 2018,
pp.1136-1143, December 2018