Metropolis-Hastings Random Walk
with a Reduced Number of Self-Loops
Toshiki Matsumura, and Kazuyuki Shudo
Tokyo Institute of Technology
toshiki7507@gmail.com, and shudo@is.titech.ac.jp

Abstract—The random walk (RW) is one of the effective
sampling methods for large-scale networks such as the Internet
and social networks. While a simple RW method tends to visit
nodes with high degrees, the Metropolis-Hastings random walk
(MHRW) algorithm has ready-to-use characteristics, wherein
the nodes visited by the algorithm distribute uniformly. However, because the MHRW algorithm conducts many self-looping
operations and the spread of its crawler is slow, it requires
many samples in order to secure sufficient accuracy. This study
proposes a RW that requires less self-looping than MHRW did
while maintaining the ready-to-use characteristics. The readyto-use characteristics are achieved by appropriately changing
the adaption probability of MHRW and choice probabilityof neighboring nodes. Our experiments demonstrated that the
proposed RW required less self-loop operations than MHRW
did. Moreover, the cost of the proposed algorithm is discussed
keeping applications to real networks in mind.
Index Terms—graph sampling, Metropolis-Hastings random
walk, cost-conscious

I. I NTRODUCTION
Graph sampling is a sampling method for data that forma graph structure such as social and traffic networks [1]. Its
methodologies can be broadly categorized into two types,
namely, random sampling and crawling-based sampling. Random sampling is a method that selects and samples nodes
and edges with independent probabilities from the network,whereas crawling-based sampling is a method that selects
and samples neighboring nodes and edges. Crawling-based
sampling, in particular, is being actively studied because it canbe applied to situations that are difficult for random sampling
due to restrictions related to security and protection of privacy[2]–[6].
Graph sampling has a diverse range of purposes including
the optimization of the calculation and visualization of graphs.
For the purpose of accurate estimation of feature values, therandom walk (RW) technique is most commonly used. RW
is one of the Markov chains, in which the state of the next
point is determined solely by the current state. Its probabilityof visiting each node characteristically converges toward astationary distribution. As the simplest stationary distributionof RW is proportional to the degree of each node, a sampled
node string concentrates on the nodes with high degrees. On
the other hand, since its stationary distribution is uniform, theMetropolis-Hastings random walk (MHRW) has ready-to-use
characteristics, whereby the expected value of the result ofa direct analysis of the sampled node string coincides withthe feature value of the population. As is the case with simple

RW methods, the MHRW algorithm selects a neighboring nodeand then decides whether to transit to that node or self-loop
to the current node according to the given choice probability.
While the MHRW algorithm has the merit of ready-to-use
characteristics, it also has demerits such as increase in thenumber of steps to achieve a certain level of accuracy because
it samples the same node repeatedly due to self-looping,or unnecessary costs incurred to learn the degrees of thecandidates for transition.
This study proposes a RW method that maintains the readyto-use characteristics, which is the merit of MHRW, yet
has less self-loops than MHRW. The study proves that the
proposed method satisfies the ready-to-use characteristics byappropriately changing the adaption probability of MHRW
and choice probability of neighboring nodes. In addition,
experiments on four networks demonstrated that the numberof self-loops in our methods is less than that of the existing
MHRW algorithm. The proposed method requires information
about two neighboring nodes; therefore, its shortcoming isthe difficulty of its application to real networks. In orderto overcome it, the degree of the node yet to be visited
was approximated using the average degree of the entire
network, which allowed us to achieve the same cost as thatof the MHRW algorithm. The average degree of the network
was estimated from the samples obtained using the MHRW
algorithm, which was run for the first few dozen percent of its
steps. The sample node string was generated in the remaining
steps using this average degree and the proposed method. As
the sample node string generated by the MHRW algorithm
used to obtain the average degree also follows the uniform
distribution, the sample node strings of the MHRW algorithm
and proposed method can be combined to estimate the feature
value of the population.
The rest of this paper is organized as follows. Chapter 2
will discuss the definitions and description of the terminology
used in this study. Chapter 3 will discuss our proposed method.
Chapter 4 will discuss the cost required for applying the
proposed method to real networks. Chapter 5 will discuss
the comparative experiment with MHRW; Chapter 6 will
discuss the related analyses. Finally, Chapter 7 will discuss
the contributions made by this study and future challenges.
II. P REPARATIONThis chapter defines the symbols used in this paper andpremise of graphs. In addition, several algorithms of the RW

Proc. IEEE ISPA/BDCloud/SocialCom/SustainCom 2019,
Deceomber 2019

②Decide to transit or stay

①Random selection of transition

are discussed.

candidates

A. Notation

min 1,

1/2

The graph structure is a data structure comprising nodes andedges that connect the nodes. For instance, in a social network
service (SNS), its users are the nodes, and the friendships
between the users are edges. Thus, it can be analyzed as
the graph structure. In this paper, a graph is denoted as
G(V, E), where V = {v1 , v2 , ..., vn } is the node cluster,and E = {(vi , vj )|vi , vj ∈ V, i 6= j} is the edge cluster.
Node number |V | and edge number |E| are set as n andm, respectively. The cluster of nodes neighboring node vi isdefined as N (vi ) = {vj ∈ V |(vi , vj ) ∈ E}, while the degreeof node vi is denoted as dP
i = |N (vi )|. When the total numbernof degrees is set to D = i=1 vi , D = 2E is true according
to the handshaking lemma. In addition, the average degree isdenoted as d = D/n. Graph G discussed in this paper is anundirected graph, i.e., it has links and no weights, and it isassumed not to have self-loops and multi-edges.

𝑑𝑖
2
=
𝑑𝑗
3

1/2

Fig. 1. Example of sampling using the MHRW algorithm. It generates asample list by repeating 1 and 2 .

proportional to the nodes’ degrees, and the selected samples
mainly consist of the nodes with high degrees. In addition, themixing time is an indicator of the number of steps required
until the distribution of samples obtained from RW converges
toward a stationary distribution [8]. The mixing time, tmix ,can be expressed as follows:
tmix () :=tmix (, vi ) :=max{tmix (, vi )}vi0min{|π − ei P t |1 ≤ , for all t0 ≥ t}t

B. Random walk
Graph sampling is a method for elucidating the overallcharacteristics of an entire graph using as little data as possible[1]. It is effective for large-scale graphs that are expensive toanalyze or graphs whose total topology cannot be obtained
due to security or privacy issues, which is often the case withsocial networks. Its methodologies can be broadly categorized
into two types, namely, random sampling and crawling-based
sampling. In this chapter, one of the crawling-based sampling
methods, RW, is discussed. RW is a method where samples arecollected using probabilistic transition from the initial node toone of its neighboring nodes. RW is one of the Markov chains.
The transition probability Pij from node vi to node vj of asimple RW (SRW), which is the simplest RW whose transition
probability is uniformly random, can be expressed as follows:
1
vj ∈ N (vi )
d
i
Pij =


0
otherwise
The most unique characteristic of RW is that it possesses
ergodicity when the following three conditions are satisfied:
1) it is possible to reach from a certain state to any otherstate;
2) it is not periodic; and3) the number of states is limited.
When RW possesses ergodicity, stationary distribution πexists simultaneously, and the probability of visiting each nodeconverges toward this stationary distribution. For example,
probability distribution π 0(t) of visiting each node after t stepsof SRW can be described as π 0(t) = (P r[xt = 1], P r[xt =2], ..., P r[xt = n]), where P r denotes the probability ofoccurrence of a phenomenon. When i-th element of π 0(t) is
0(t)
0(t)
set as πi , it is known that πi converges toward di /D [7].
D is the total number of degrees, and it is a constant. In
other words, the probability of visiting each node in SRW is

where | · |1 is called the total fluctuation distance andexpressed according to the following equation:n|π − ej P t |1 :=1X|πi − (ej P t )i |2 i=1

The value of parameter  in tmix () is often set to 1/4
or 1/8. The mixing time is closely related not only to thetraveling time and total visiting time but also to guarantee ofthe accuracy of estimation. Hence, it is an important criterion
when comparing RW techniques [9]–[12].
1) β-random walk (β-RW): β-RW [13] is a type of RW thatwas devised to shorten the traveling time and total visiting timeof SRW. Its transition probability can be expressed as follows:
Since visiting the nodes with low degrees becomes easieras β becomes larger, it is expected that it would thoroughly
visit all nodes of a graph when β is appropriately set unlike the
RW technique, which tends to visit nodes with higher degrees.
While the expected values of both the traveling time and total
visiting time of SRW are O(n3 ), it has been proven that thetraveling time and the total visiting time of β-RW can achieveO(n2 ) and O(n2 log n), respectively, when β = 1/2.
2) Metropolis-Hastings random walk (MHRW): MHRW is
a RW based on the Metropolis-Hastings (MH) algorithm [14],and it can converge samples toward a chosen distribution. In
most cases, it indicates the type where the samples follow theuniform distribution. The transition probability of MHRW canbe expressed as follows:

1
di


· min(1, ) = Qij · Aij vj ∈ N (vi )


di
dj




X
Pij =
1−
Pik
i=j



v
∈N
(v
)
i
k





0
otherwise

Proc. IEEE ISPA/BDCloud/SocialCom/SustainCom 2019,
Deceomber 2019

Algorithm 1 Metropolis-Hastings random walk (MHRW)
Require: n0 : initial node, b: cost
Ensure: sample list: sample listvi ← n0
sample list ← {n0 }k←1while k < b do
Choose node vj u.a.r. from N (vi )Generate p ∼ U (0, 1)
if p ≤ min(1, ddji ) thenvi ← vj
append vj to sample list
else
append vi to sample list
end ifk ←k+1end while
return sample list

Algorithm 2 Proposed method
Require: n0 : initial node, b: cost
Ensure: sample list: sample listvi ← n0
sample list ← {n0 }k←1while k < b do
Choose node vj Qij from N (vi )Generate p ∼ U (0, 1)
Qi) thenif p ≤ min(1, Qjvi ← vj
append vj to sample list
else
append vi to sample list
end ifk ←k+1end while
return sample list

Q and A denote the probability of choosing a neighboringnode and adaption probability to decide whether to transit or tostay, respectively. They can be expressed as Qij = 1/di , Aij =min(1, di /dj ).
MHRW algorithm decides whether to transit or to self-loop
to the current node using the adaption probability A after
selecting a neighboring node using the transition probabilityof SRW. It adds the neighboring node to the sample list whenit transits to that node, and it adds the current node to thesample list again when it self-loops. While the self-looping is
one of the characteristics of MHRW algorithm, it also causes
degradation of the estimation accuracy due to the increaseof the mixing time through multiple sampling of the samenode and generation of an extra cost when transition is notmade even after obtaining the degree of a transition candidate.
MHRW algorithm is shown in Algorithm 1, and its actual
sampling flow is illustrated in Figure 1.

where Q represents the choice probability, and A represents
the adaption probability. Unlike the MHRW algorithm that
self-loops when it selects a node with a high degree as its
transition candidate, the proposed method employs the choiceprobability that is more likely to select a node when its degree
is lower. As a result of reducing the number of the self-loops,
the mixing time is reduced and the number of steps required toensure a satisfactory accuracy is also reduced. The proposed
algorithm is shown in Algorithm 2. In this paper, the following
two types of choice probabilities are examined.
β-MHRW changes the choice probability of MHRW to thatof β-RW. β is set to 1/2, which generates the shortest travelingtime and total visiting time, and the choice probability and theadaption probability can be respectively expressed as follows:

III. P ROPOSED METHOD
In the MHRW algorithm, the mixing time is increased dueto the self-looping, and it requires many samples to achieve asatisfactory level of accuracy. In this chapter, we propose a RW
that maintains the ready-to-use characteristics of the MHRW
algorithm while requiring less self-loops compared with the
MHRW algorithm.
A. Transition probability
The proposed RW method changes the choice probability of
MHRW from that of SRW. Due to this change, the adaption
probability is set based on Appendix 1 to satisfy the ready-touse characteristics. The transition probability of the proposed
method can be expressed as follows:
Qij Aij
vj ∈ N (vi )




X
1−
Pik
i=j
Pij =


v
∈N
(v
)

i
k

0
otherwise−1/2

Qij = Pdj

−1/2
vk ∈N (vi ) dk,

Aij = min(1, Qji /Qij )By employing the choice probability of β-RW, which is
proportional to the reciprocal of the degree, the number ofself-loops is expected to be reduced.
Reselecting MHRW selects a transition candidate uniformly,
and then reselects another transition candidate. Finally, it selects the candidate with a smaller degree. Its choice probability
and adaption probability can be respectively expressed asfollows:
2 · #{dj < dk }k∈N (i) + #{dj = dk }k∈N (i)
,
Qij =
d2i
Aij = min(1, Qji /Qij )B. Stationary distribution
The transition probability of the proposed method in relation
to any of the neighboring nodes is not zero. In addition, as thisstudy postulates that the subject graph is a linked undirected

Proc. IEEE ISPA/BDCloud/SocialCom/SustainCom 2019,
Deceomber 2019

Algorithm 3 Proposed cost reduction method
Require: n0 : initial node, b: cost, φ: Ratio of MHRW
Ensure: sample list: sample listvi ← n0
sample list ← {n0 }degree memory ← {n0 }: List of nodes whose degrees are
obtained
while length(degree memory) < φb do
Choose node vj u.a.r. from N (vi )if degree memory doesn’t contain vj thenappend vj to degree memory
end ifGenerate p ∼ U (0, 1)
if p ≤ min(1, ddji ) thenvi ← vj
append vj to sample list
else
append vi to sample list
end ifend while
average degree ← Average degree of the nodes insample list
while length(degree memory) < b do
Choose node vj Qij from N (vi ) (The degree of thenode that is not in degree memory is calculated as
average degree)
if degree memory doesn’t contain vj thenappend vj to degree memory
end ifGenerate p ∼ U (0, 1)
Q) (The degree of the node that is not in
if p ≤ min(1, Qjiijdegree memory is calculated as average degree) thenvi ← vj
append vj to sample list
else
append vi to sample list
end ifend while
return sample list

A. When the sample size is the cost
It is possible to conduct sampling while considering thesample size as the cost when one would like to set a constantnumber of the nodes to be obtained, or when there is a limited
memory for saving the nodes. As the proposed method hasless self-loops than the MHRW does, it is inferred that it cansample a wider variety of nodes when the sample size is thesame.
B. When obtaining degrees is the cost
It is possible to conduct sampling while considering thesample size as the cost when one would like to set a constantnumber of the nodes to be obtained, or when there is a limited
memory for saving the nodes. As the proposed method hasless self-loops than the MHRW does, it is inferred that it cansample a wider variety of nodes when the sample size is thesame.
When obtaining degrees is considered to be the cost, theproposed method requires a far higher cost than the MHRW
algorithm even for a per step basis. One possible method to
reduce the cost of the proposed method up to that of the
MHRW algorithm is to estimate the degrees of the nodes up
to the ones that are next to the neighboring nodes. While it ispossible to know the degree of a node without incurring any
cost if it is already obtained and stored in the memory, it is
not possible to know the degree of other nodes. Therefore, theproposed method supplements the degree of the node yet tobe obtained with the average degree. By repeating a sufficientnumber of steps, the number of the nodes whose degrees
are obtained can be increased and the samples are expected
to converge toward the uniform distribution. However, theaverage degree cannot be accurately derived without knowing
the information of the graph overall, and it is unlikely that the
information is given beforehand. Thus, a part of the cost is
used to conduct sampling using the MHRW algorithm, and theobtained samples are used to estimate the average degree. The
unbiased estimator of function f using RW can be expressed
as follows [16]:X
Eπ (f ) :=f (vi )πi
(1)
vi ∈V

graph, it is possible to reach any node from a given node. For
the same reason, it is not periodic. Furthermore, based on thepremise of the graph, it is clear that the number of nodes
is limited. From these three conditions, the proposed RW
possesses ergodicity and stationary distribution at the sametime. Based on Appendix 1, this stationary distribution is theuniform distribution.

where π is the stationary distribution of RW, and f : V → R
is a function that uses the node as its argument and returns areal number. As the stationary distribution of MHRW is π ={1/n, . . . , 1/n}, Equation (1) can be expressed as follows:

IV. C OST DISCUSSION

When f (vi ) = di , Equation (2) represents the average
degree. In this way, the average degree can be derived fromMHRW.
Following this, sampling using the proposed method, whose
cost is reduced by estimating the average degree, is conducted.
As the first sample from MHRW satisfies the ready-to-use
characteristics, it can also be used as a sample in its original

It is important to consider the cost when conducting sampling. Broadly speaking, there are two ways to consider thecost of MHRW. One is to regard the sample size as the cost,and another is to regard obtaining the degrees as the cost [15].
In this chapter, the behavior of the proposed method undereach of these cost considerations is discussed.

Eπ (f ) :=1 X
f (vi )
n

(2)

vi ∈V

Proc. IEEE ISPA/BDCloud/SocialCom/SustainCom 2019,
Deceomber 2019

TABLE I
DATA SET OVERVIEW.
Network
BA modelFacebook
DBLP
Amazonn10, 000
4, 039317, 080
334, 863m
29, 991
88, 234
1, 049, 866
925, 872

D/n
5.998
43.691
6.622
5.530

form, in addition to the estimation of the average degree. The
algorithm of the proposed method is shown in Algorithm 3.
When obtaining degrees is the cost, another merit of reducing the self-looping emerges. The MHRW obtains the degreeof a neighboring node when deriving the adaption probability.
When it self-loops, it does not make a transition to that nodeeven though the degree of the transition candidate has beenobtained. In other words, there are many nodes which are notincluded in the samples although their degrees are obtained.
The proposed method can reduce such an unnecessary cost by
reducing the number of self-loops.
V. E XPERIMENTIn this chapter, we verify, through experiments using various networks, whether the proposed method has less selfloops compared with the MHRW algorithm. Moreover, weverify whether the ready-to-use characteristics of the proposed
method is maintained after changing the choice probability andadaption probability of MHRW.
First, we compare the numbers of self-loops of the MHRW
algorithm and the proposed method after crawling for thesame number of steps, and verify whether the sample distribution converges toward a uniform distribution (Section
V-B). Following this, we conduct the same experiment keeping
applications to real networks in mind after equalizing the costof obtaining degrees of the MHRW algorithm and the proposed
method (Section V-C).
A. Data set
Networks generated using the Barabási-Albert (BA) model[17], which is one of the generative models for complex
networks, and the data sets of real networks published by
the Stanford Network Analysis Project (SNAP)1 are used forthe experiment. Facebook represents the sub-network obtained
from the SNS of the actual Facebook. Its nodes represent
the users and its edges represent the Follow relationships.
DBLP represents the network of the co-authorships of academic papers supplied by the DBLP computer science bibliography. Amazon represents the group purchasing network
obtained by crawling the Amazon website. Its nodes represent
merchandises and its edges represent the group purchasing
relationships indicating whether goods are purchased together
frequently or not. Table I shows the characteristics of each
network.
B. When obtaining degrees is not the cost
First, we compared the numbers of self-loops of the MHRW
algorithm and the proposed method after crawling of the same
1 https://snap.stanford.edu/data/

number of steps. Figure 2 shows the results of conducting
a trial where the step that is equivalent to 10% of the total
node number was performed 1000 times for each networkand the average of the self-loop numbers was obtained. These
results shows that the number of self-loops of the proposed
method is less than that of the MHRW algorithm for every
network. Moreover, L1 distance is used to verify whether the
samples of the proposed method are uniformly distributed.
The L1 distance can be expressed as the equation below. The
equation means that the closer the L1 distance is to zero, thecloser the distribution of the observed values is to the expecteddistribution.
n
X
L1 distance=|πi − πi0 |
i=1

where π denotes the distribution to be achieved and π 0denotes the actually obtained distribution of the samples.
Figure 3 shows the result of plotting the average of theL1 distance in relation to the step number obtained for 1000
times for each network. It shows that the proposed method not
only satisfies the ready-to-use characteristics but also obtains
samples generally closer to the uniform distribution comparedwith the MHRW algorithm. This is because the L1 distance ofthe proposed method is always smaller than that of the MHRW
algorithm for every network. It is inferred that this is due to thefact that the crawler avoided sampling only the same nodes;
hence, it spread further and collected more diverse nodes in
response to the reduction of the self-loop number.
C. When obtaining degrees is the cost
Next, we conducted an experiment with the proposed
method after reducing its cost and keeping applications toreal networks in mind. Here, it was postulated that obtaining
the degree of a node for the first time incurs the cost. The
obtained degree of the node is stored in the memory. In the
proposed method with a reduced cost, the parameter φ is used
to determine the ratio of the cost to be allocated to the MHRW
that obtains the average degree. In this experiment, the numberof self-loops and the L1 distances for φ = 0.1, 0.3, and 0.5
were compared with those of the MHRW algorithm. Whenφ = 1.0, it is MHRW. Figure 4 shows the comparison of thenumber of self-loops for φ = 0.1, 0.3, and 0.5 obtained using
the proposed method and the MHRW algorithm. This figure
shows that the lower the proportion of the MHRW is, the lower
the number of self-loops is. Meanwhile, Figure 5 shows thecomparison of the number of specific nodes. It shows that the
proposed method is able to sample a greater number of morediverse types of nodes even with the same cost compared with
the MHRW algorithm as the proportion of MHRW is lowered.
On the other hand, lowering the proportion of the MHRW
leads to worsening of the average degree estimation accuracy,
which may negatively affect the ready-to-use characteristicsof the proposed method. Figures 6 and 7 show the plot of theL1 distance for each network, which is the average of 1,000
observations, at 2%, 4%, 6%, 8%, and 10% of the cost of thetotal number of the nodes. According to the figures, β-MHRW

Proc. IEEE ISPA/BDCloud/SocialCom/SustainCom 2019,
Deceomber 2019

300
200
100
0

140
120
100
80
60
40
20
0

Reselecting1
2
3
β-MH
MHRW
MH

DBLP

16000
14000
12000
10000
8000
6000
4000
2000
0

14000

12000
10000
8000
6000
4000

2000
0

Reselecting2
3
MHRW
MH

1
β-MH

Reselecting1
2
3
β-MH
MHRW
MH

Amazon16000

the number of self-loop

400

Facebookthe number of self-loop

160

the number of self-loop

the number of self-loop

BA model500

Reselecting1
2
3
β-MH
MHRW
MH

Fig. 2. Number of self-loops of the proposed method and the MHRW algorithm for each network (Step number is 10% of the total number of the nodes).

1.2
1
0.8
0.6

MHRW
Reselecting-MH
β-MH

1.4

L1 distance

L1 distance

1.6

MHRW
Reselecting-MH
β-MH

1.4

1.2

DBLP

2

1
0.8

0.6

1.8

MHRW
Reselecting-MH
β-MH

1.6

1.4
1.2
1
0.8

1.8
1.4

1.2
1
0.8

0.6

0.6

0.4

0.4

0.4

0.2

0.2

0.2

0.2

0

0

0

100000200000 300000 400000

the number of step

0

40000

80000

120000the number of step

MHRW
Reselecting-MH
β-MH

1.6

0.4

0

Amazon2

L1 distance

1.6

Facebook

1.8

L1 distance

BA model1.8

003000000

6000000

9000000

0

the number of step

3000000

6000000

9000000

the number of step

Fig. 3. Transition of the L1 distance for each graph (Horizontal axis is the proportion of the number of steps in relation to the total number of the nodes).

has the shorter L1 distance than that of the MHRW for every
φ and every network. In particular, the smaller φ is, whichis the proportion of the MHRW used to obtain the average
degree, the closer the samples of the proposed method are to
the uniform distribution. Moreover, the value of L1 distanceof the Reselect MHRW algorithm can be said to be the sameor lower than that of the MHRW algorithm. These results
suggest that a lower estimation accuracy of the average degree
has a small impact on the ready-to-use characteristics of the
proposed method.
These experiments indicated that the proposed method is the
RW having less number of self-loops than that of the MHRW
while maintaining the ready-to-use characteristics. Moreover,it demonstrated that even when the obtaining degrees is thecost, the proposed method can achieve the same cost as the
one required by the MHRW algorithm without losing the
aforementioned merits when using the proposed cost reduction
method.
VI. R ELATED WORK
Lee et al. proposed an improvement of the MHRW algorithm, called the MH algorithm with delayed acceptance(MHDA), through a different approach from that of this study[18]. While this study reduced the self-loop probability of
the MHRW, the MHDA reduces the probability of transition
to the previous node. When the MHDA accidentally selected
the previous node as the transition candidate, it reselects thetransition candidate in a certain probability. As the self-loop
probability of the MHDA is equal to that of the MHRW
algorithm, it is inferred that combining MHDA with themethod proposed in this study would enable the productionof more expansive and better RWs.

Chierichetti et al. proposed the maximum-degree sampling(MD) that has the higher number of self-loops compared withthat of the MHRW algorithm [19]. When the obtaining degree
is the cost, the same node is one expense no matter how manytimes it is sampled. Thus, if the cost is the same, more samples
are collected when the number of the self-loops is higher. The
transition probability of the MD is expressed as follows:
1
vj ∈ N (vi )


d

max


di
Pij =
1−
i=j


d

max




0
otherwise
where dmax = max{d1 , d2 , ..., dn }. It has been demonstrated that when obtaining degree is the cost, the L1 distanceof the MD is smaller compared with that of the MHRW
algorithm. On the other hand, the cost for obtaining dmax
under this limited circumstance should be discussed.
VII. C ONCLUSION
This study proposed the RW method having less numberof self-loops than that of the existing MHRW while maintaining the ready-to-use characteristics by appropriately changing
the choice probability and the adaption probability of theMHRW. The proposed method achieved the reduction of thenumber of the self-loops by using the choice probability thatmakes the nodes with smaller degrees more likely to be
selected as the transition candidates. Moreover, the proposed
method achieved the ready-to-use characteristics by setting theProc. IEEE ISPA/BDCloud/SocialCom/SustainCom 2019,
Deceomber 2019

adaption probability, whose stationary distribution became theuniform distribution, using the MH algorithm.
In order to set the choice and adaption probabilities, theproposed method uses all degrees of the neighboring nodes andthe nodes next to them, whereas the MHRW algorithm uses
one of the neighboring nodes. Thus, the two methods cannot
be said to require the similar cost when applied to the real
networks such as SNS and the Internet. Therefore, we deviseda method to set the choice and adaption probabilities using
the average degree in place of the degrees of the nodes whose
degrees are yet to be obtained. Since the situation where theaverage degree is provided as a prior information would hardly
occur, it is estimated first by running the MHRW algorithm
using several dozen percent of the cost, and the proposed
method is performed using the remaining cost. In this way,
the cost of the proposed method was reduced to the similarlevel of that of the MHRW algorithm.
We compared the number of the self-loops and the readyto-use characteristics of the proposed method and the MHRW
algorithm for four networks in the experiments. The proposed
method demonstrated the better results for both the numberof the self-loops and the L1 distance, which is one of the indicators of the ready-to-use characteristics, in the experiment,
where the collected sample sizes of both methods were thesame. Moreover, we conducted the comparison of the proposed
method with a reduced cost and the MHRW algorithms. In the
proposed method with the reduced cost, the first 10%, 30%,
and 50% of the cost were used to obtain the average degree,
and the respective values of the number of the self-loops andthe L1 distance were observed. The results demonstrated thateven in the experiments with the same costs, the proposed
method has less number of the self-loops, and its sample iscloser to the uniform distribution.
Although we used two types of the probability of choosing
neighboring nodes in this study, other choice probabilities are
possible. We consider that the choice probability that makes
the node with the smaller degree more likely to be selected
results in the smaller number of the self-loops compared withthat of the MHRW algorithms. Therefore, obtaining a better
choice probability is a future objective.

A PPENDIX
Here, we discuss how the adaption probability of the
proposed method was set using the MH algorithm. The MH
algorithm is one of the representative Markov chain Monte
Carlo methods. Its purpose is to compose a sample list under
any probability distribution. In order to achieve this objective,
the Markov chain, which uniquely possesses a stationary
distribution, π, is employed. The stationary distribution andits uniqueness are guaranteed by satisfying the ergodicity andthe following detailed balance condition.

ACKNOWLEDGMENT

πi Pij = πj Pji

This work was supported by New Energy and Industrial
Technology Development Organization (NEDO).

When the stationary distribution is striving to be the uniform
distribution, Equation (A-1) becomes Pij = Pji . Now, we resolve the transition probability, P , into the choice probability,
Q, and the adaption probability, A, namely, Pij = Qij Aij .
At this point, the following equation is derived from Equation(A-1).
Qji
Aij
=
(4)
Aji
Qij

R EFERENCES[1] Pili Hu and Wing Cheong Lau. A survey and taxonomy of graphsampling. arXiv preprint arXiv:1308.5865, 2013.
[2] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graphs overtime: densification laws, shrinking diameters and possible explanations.
In Proc. ACM KDD 2005, pages 177–187. ACM, 2005.
[3] Minas Gjoka, Maciej Kurant, Carter T Butts, and Athina Markopoulou.
Practical recommendations on crawling online social networks. IEEE
Journal on Selected Areas in Communications, 29(9):1872–1892, 2011.
[4] Leo A Goodman. Snowball sampling. The annals of mathematicalstatistics, pages 148–170, 1961.
[5] Douglas D Heckathorn. Respondent-driven sampling: a new approachto the study of hidden populations. Social problems, 44(2):174–199,
1997.

[6] Matthew J Salganik and Douglas D Heckathorn. Sampling andestimation in hidden populations using respondent-driven sampling.
Sociological methodology, 34(1):193–240, 2004.
[7] David Aldous and Jim Fill. Reversible markov chains and random walks
on graphs, 2002.
[8] David A Levin and Yuval Peres. Markov chains and mixing times,
volume 107. American Mathematical Soc., 2017.
[9] Yuval Peres and Perla Sousi. Mixing times are hitting times of large
sets. Journal of Theoretical Probability, 28(2):488–519, 2015.
[10] Roberto Oliveira et al. Mixing and hitting times for finite markov chains.
Electronic Journal of Probability, 17, 2012.
[11] Jian Ding, James R Lee, and Yuval Peres. Cover times, blanket times,
and majorizing measures. In Proc. ACM STOC’11, pages 61–70. ACM,
2011.
[12] Kai-Min Chung, Henry Lam, Zhenming Liu, and Michael Mitzenmacher. Chernoff-hoeffding bounds for markov chains: Generalized andsimplified. arXiv preprint arXiv:1201.0559, 2012.
[13] Satoshi Ikeda, Izumi Kubo, and Masafumi Yamashita. The hitting
and cover times of random walks on finite graphs using local degree
information. Theoretical Computer Science, 410(1):94–100, 2009.
[14] Nicholas Metropolis, Arianna W Rosenbluth, Marshall N Rosenbluth,
Augusta H Teller, and Edward Teller. Equation of state calculations byfast computing machines. The journal of chemical physics, 21(6):1087–
1092, 1953.
[15] Kenta Iwasaki and Kazuyuki Shudo. Comparing graph sampling
methods based on the number of queries. In Proc. IEEE ISPA-IUCCBDCloud-SocialCom-SustainCom 2018, pages 1136–1143, 2018.
[16] Rong-Hua Li, Jeffrey Xu Yu, Lu Qin, Rui Mao, and Tan Jin. On random
walk based graph sampling. In Proc. IEEE ICDE 2015, pages 927–938.
IEEE, 2015.
[17] Réka Albert and Albert-László Barabási. Statistical mechanics ofcomplex networks. Reviews of modern physics, 74(1):47, 2002.
[18] Chul-Ho Lee, Xin Xu, and Do Young Eun. Beyond random walkand metropolis-hastings samplers: why you should not backtrack forunbiased graph sampling. ACM SIGMETRICS Performance evaluation
review, 40(1):319–330, 2012.
[19] Flavio Chiericetti, Anirban Dasgupta, Ravi Kumar, Silvio Lattanzi, andTamás Sarlós. On sampling nodes in a network. In Proc. WWW 2016,
pages 471–481, 2016.

(3)

When Aij = min(1, Qji /Qij ), it satisfies Equation (A-2).
This is called the Metropolis choice. When Qij = 1/di , thetransition probability of the MHRW is obtained. The readyto-use characteristics of the proposed method is satisfied by
setting the choice probability of β-RW as Q and the adaption
probability of the Metropolis choice as A.

Proc. IEEE ISPA/BDCloud/SocialCom/SustainCom 2019,
Deceomber 2019

1000
800
600
400
200
0

β-MH

Reselecting-MH

400
300
200
100

β-MH

60000
40000
20000

Amazon

60000

β-MH

Reselecting-MH

50000
40000
30000
20000
10000
0

MHRW

MHRW

1
2
3
4
φ=0.3
φ=0.5
φ=0.1
（φ=1.0）

1
2
3
4
φ=0.1
φ=0.3
φ=0.5
（φ=1.0）

MHRW

1
2
3
4
φ=0.3
φ=0.5
φ=0.1
（φ=1.0）（φ=1.0）Reselecting-MH

0

0

MHRW
1
2
3
4
φ=0.3
φ=0.5
φ=0.1

DBLP

80000

the number of self-loop

Reselecting-MH

the number of self-loop

the number of self-loop

β-MH

Facebook500

the number of self-loop

BA model1200

Reselecting-MH

840
820
800
780
760
7400

MHRW

1
2
3
4
φ=0.3
φ=0.5
φ=0.1
（φ=1.0）Facebook

360

β-MH

Reselecting-MH

340
320
300
280
2600

MHRW

DBLP

27000

β-MH

Reselecting-MH

26800

26600
26400
26200
26000
0

MHRW

1
2
3
4
φ=0.3
φ=0.5
φ=0.1
（φ=1.0）

1
2
3
4
φ=0.3
φ=0.5
φ=0.1
（φ=1.0）the number of unique nodeβ-MH

the number of unique node

BA model860

the number of unique node

the number of unique nodeFig. 4. Number of the self-loops of the proposed method and the MHRW algorithm for each network (Cost is 10% of the total number of the nodes).

Amazon

27400

β-MH

Reselect-MH

27200
27000
26800

26600
26400
262000

MHRW

1
2
3
4
φ=0.3
φ=0.5
φ=0.1
（φ=1.0）Fig. 5. Number of the specific nodes of the proposed method and the MHRW algorithm for each network (Cost is 10% of the total number of the nodes).

1.88
MHRW (φ=1.0)
φ=0.5
φ=0.3
φ=0.1

1.84

1.88
MHRW (φ=1.0)
φ=0.5
φ=0.3
φ=0.1

1.84

1.8

21

1.92

63

84

1.92

1.88
MHRW (φ=1.0)
φ=0.5
φ=0.3
φ=0.1

Percentage of cost to n

42

36

48

1.88
MHRW (φ=1.0)
φ=0.5
φ=0.3
φ=0.1

1.8

21

10 5 (%)

1.92

1.84

1.8

21

105 (%)

1.96

1.84

1.8

42

Amazon2

1.96

L1 distance

L1 distance

1.92

Facebook

2

1.96

1.96

L1 distance

Facebook

2

L1 distance

BA model2

Percentage of cost to n

42

36

48

21

10 5 (%)

42

36

48

105 (%)

Percentage of cost to n

Percentage of cost to n

Fig. 6. Transition of the L1 distance of the MHRW and the β-MHRW algorithms for each graph (Horizontal axis is the proportion of the cost of obtaining
degrees in relation to the total number of the nodes).

1.85
MHRW (φ=1.0)
φ=0.5
φ=0.3
φ=0.1

1.8

1.9
1.85
1.8
1.75

21

42

63

MHRW (φ=1.0)
φ=0.5
φ=0.3
φ=0.1

48

Percentage of cost to n

105 (%)

21

42

36

1.96

1.92

1.92

1.88

1.88

MHRW(φ=1.0)
φ=0.5
φ=0.3
φ=0.1

1.84

48

Percentage of cost to n

10 5 (%)

Amazon2

1.96

L1 distance

1.9

DBLP

2

1.95

L1 distance

L1 distance

1.95

1.75

Facebook

2

L1 distance

BA model

2

1.8

21

42

36

MHRW(φ=1.0)
φ=0.5
φ=0.3
φ=0.1

1.84

48

105 (%)

1.8

21

Percentage of cost to n

42

36

48

105 (%)

Percentage of cost to n

Fig. 7. Transition of the L1 distance of the MHRW and the Reselecting MHRW algorithms for each graph (Horizontal axis is the proportion of the cost ofobtaining degrees in relation to the total number of the nodes).

Proc. IEEE ISPA/BDCloud/SocialCom/SustainCom 2019,
Deceomber 2019