Average Path Length Estimation ofSocial Networks by Random Walk
Toshiki Matsumura, Kenta Iwasaki, and Kazuyuki Shudo
Tokyo Institute of Technology

Abstract—Average path length (APL) is an index of smallworld networks. Calculating APL accurately requires measuring
all of the shortest path lengths between two arbitrary nodes in a
network. However, obtaining an entire social network is difficult
because of security and privacy protection restrictions. Therefore,
sampling a portion of a network to estimate features can beeffective. In this research, we propose a method for estimating
APL using random walk, one of the crawling-based sampling
methods.
Index Terms—social network, complex network, graph sampling, average path length

I. I NTRODUCTION
The number of users of social networking services (SNS)is increasing every year, and interest in analyzing such huge
networks is increasing. For example, the number of Facebook
users exceeds 1.8 billion in 2017. There is a method foranalyzing the structure of a graph in which an SNS user is anode and the relation between two users is an edge. Networks
with huge and complex structures, such as a network of humanrelations, are called complex networks [1], and most social
networks are such networks.
In complex networks, average path length (APL) is anindex of the small-world property, representing the “size” ofa network [2]. APL is the average of the shortest path lengths(SPLs) between all two nodes in a network. Calculating
APL accurately requires obtaining all of the SPLs, but thisis unrealistic on a social network because information on
all nodes cannot be obtained owing to security and privacy
protection restrictions. Therefore, using graph sampling [3] toestimate this feature of a network using only a portion of the
network can be effective.
There are two types of graph sampling, random samplingand sampling by crawling. Random sampling is a method of
selecting nodes and edges from the network with independent
probabilities and sampling them. However, in a social network,
it is almost impossible to obtain information on all nodes in
the network. Sampling by crawling, a method of selecting andsampling adjacent nodes and edges without needing to know
the entire network can thus be applied to social networks.
Breadth-first sampling (BFS) and snowball sampling, oneof the typical crawling algorithm, can not accurately estimatefeatures of the original network because the sample is biased
around the initial node. On the contrary, random walk (RW)
is likely to spread to every corner of the original network, andthus might be able to estimate features of the original networkby analyzing the sampling list thoroughly. For these reasons,

we propose a method for estimating APL of a social network
using RW.
II. R ELATED WORK
According to [4], there are two scenarios for sampling large
networks: full access scenario and restricted access scenario.
In full access scenario, we can access to every node (oredge) of the network, and the main purpose of sampling isvisualization and acceleration. However, this scenario is not
related to our research, because the network we analyze isSNS, which is mostly limited in access. Thus, our goal is tofind a way to obtain APL ”accurately” in restricted accessscenario.
Qi and colleagues experimented with APL estimation
through graph sampling [5]. They estimated APL using four
sampling methods including BFS. Except for BFS, thesemethods assumes full access scenario and are difficult to apply
to social networks. Also, BFS is unstable in accuracy in termsof network features estimation.
III. P REPARATIONIn this section, we describe RW and the definition of APL.
A. RW
RW is a method of transitioning from the initial node to oneof the adjacent nodes and collecting the information regardingthat node. The simplest random walk, in which the transition
probabilities are uniformly random, is called simple random
walk (SRW). Let pvi ,vj be the transition probability of SRW
from node vi to node vj :
 1
vj ∈ N (vi )(1)pvi ,vj =dvi
 0 otherwise
where dvi and N (vi ) are the degrees of vi and the adjacentnode list, respectively.
The greatest advantage of random walk is that the visit
probability to each node can be calculated mathematically. For
example, the distribution π ′ of the visit probability to eachnode after step t by SRW is π ′ = (P r[xt = 1], P r[xt =2], ..., P r[xt = n]). π ′(i) converges to dvi /D [6], where π ′(i)is the ith element of π ′ . D is the sum of the degrees and is aconstant. That is, in SRW, the visit probability to each nodeis proportional to the degree.
The number of steps T until the visit probability converges
to a stationary distribution is called the mixing time [7].

Proc. 2018 IEEE Int'l Conf. on Big Data and Smart Computing(IEEE BigComp 2018), pp.611-614, January 20182
𝑣2

Nodes visited by random walk

Sample list

𝑣4

1

Observable nodes

4
𝑣6

𝑣1

Unobservable nodes

1

2

3

4

𝑣1

𝑣2

𝑣5

𝑣6

Traceable edges

𝑣3

Untraceable edges

Fig. 1. An example of graph sampling by random walk: A subgraphcomprising colored nodes and thick edges is denoted as G′ .

The order of mixing time is approximately O(log2 n). Evenfor two nodes in the sample list by random walk, if the index
is greater than the mixing time, it is known that they can be
regarded as random sampling from the network [8].
The sampling image of RW is shown in Fig. 1.

𝑣5

3

Fig. 2. Example of elements in I, if m = 2

define a set I of node pairs that are more than a particularthreshold m above the mixing time as follows:

I = {(vxi , vxj )|m ≤ j − i ∧ 1 ≤ i < j ≤ r, xi ̸= xj }B. APL
APL is an indicator of the small-world property and is theaverage of SPLs between all of the nodes in the network. In
this study, since the graph is assumed to be a graph without
weight, SPL is also called the shortest step number (SSN).
Letting Svi ,vj be the SSN from node vi to node vj , APL L isdefined asL=2n(n − 1)∑

Svi ,vj(2)

1≤i<j≤n

When the total number of nodes in the network n increases,
and when L is at most as high as log n, the network satisfies
the small-world condition. In this paper, we estimate APL bygraph sampling.
IV. P ROPOSED M ETHOD
In this section, we propose a method for etimating the APL
of social networks by random walk.
A. Process of APL Estimation
The proposed method analyzes the sample list after sampling by SRW.
1) Sampling: We acquire a sample list for r steps fromgraph G by SRW. For the sampled node, the node ID and thenode ID of the adjacent node are held.
2) Selection of Node Pairs: To obtain the SSN, node pairs
are selected from the sample list. However, node pairs whose
indices are too close in the sample list are strongly correlated.
For example, there is a tendency for the SSN between theith node and the (i + 1)th node in the sample list to be onenecessarily and for the SSN between the node pairs having
close indices to be small. Therefore, in this method, we use“some distance” node pairs in the sample list collected by
SRW. This condition is necessary to ensure that the nodes in
the pairs are chosen randomly from the graph according to thestationary distribution of SRW, i.e., that they are sampled byrandom sampling. For the sample list (vx1 , vx2 , ..., vxr ), we(3)

These are the node pairs used for analysis. For example,
when a sample list as shown in the right-hand figure of Fig. 2
is acquired, if m = 2, the pair of nodes to be used as samplesis {(v1 , v5 ), (v1 , v6 ), (v2 , v6 )}, where the indices in the list are
separated by two or more.
3) Calculation of the SSN: The average of Svi ,vj in thenode pairs in I is the value to be calculated; however, it
is impossible to determine that Svi ,vj does not obtain the
topology of the entire G. Therefore, the SSN is obtained fromonly the information held. Specifically, we obtain Sv′ i ,vj for
G′ formed from nodes visited by SRW and its adjacent nodes.
．Sv′ i ,vj satisfies the relation of Svi ,vj ≤ Sv′ i ,vj .
4) Weighting and Calculation of the Estimated Value L̂
of L: SRW samples in a manner biased toward high-degree
nodes. In other words, node pairs selected by this method cannot successfully select samples of low-degree nodes. Therefore, we consider using a weight ω to eliminate this bias.
Let ϕ(ω) be the average of Sv′ i ,vj in node pairs in I
multiplied by the weight ω and ψ be the average of 1/dvi
in the sample list:

ϕ(ω)

ψ

=

=

1
|I|

∑

ωSv′ i ,vj(vi ,vj )∈Ir∑1
1
r i=1 dvi

These expected values are as follows:

Proc. 2018 IEEE Int'l Conf. on Big Data and Smart Computing(IEEE BigComp 2018), pp.611-614, January 2018

(4)

(5)

Barabasi-Albert∑1≤i<j≤n,i̸=j

E[ψ]

1
]
dvi
r
∑
1

=

dv dv
ωSv′ i ,vj i j
D D

i=1
r
∑

dvi

(i)

=

7.532

4.442

7.53

7.528
0

100

200

300

400

0

500

100

200

(11)

Gnutella

7.1

400

500

1250

1500

DBLP

7.605

7

6.9
6.8
6.7

6.6
6.5

7.6
7.595
7.59
7.585
7.58

7.575
7.57
7.565
7.56

6.4
0

50

100

150

200

250

300

0

250

m

(12)

300

m

m

(10)

1 dvi
d D
i=1 vi
n
D

=

7.534

4.441

(9)
π

7.536

4.443

4.4415

(8)

7.54

7.538

4.444

4.44354.4425

E[=

Average Path Length(7)1≤i<j≤n,i̸=j

=

4.445

4.4445

ωSv′ i ,vj π (i) π (j)Average Path Length=

Average Path Length

(6)

∑

7.542

4.4455

Average Path Length

E[ϕ(ω)] =Random network

4.446

E[ωSv′ i ,vj ]

500

750

1000

m

Fig. 3. Transformation of L̂ resulting from increasing m from one in each
network

Define L̂ as follows:L̂ =ϕ( dv 1dv )
i

j

(13)

ψ2

This expected value as follows with attention to Svi ,vj ≤Sv′ i ,vj :E[L̂] =
=
≥
=

1
n2

∑

V. E XPERIMENTSv′ i ,vj

1≤i,j≤n,i̸=jn−1
2n n(n − 1)n−1
2
n n(n − 1)n−1
Lnthan expected. On the contrary, if m is too large, the elementsof I decreases in number and the estimated value must be
obtained with only a few samples, with the result that thevariance becomes large. Therefore, we must increment m,
estimate APL, and observe the change in L̂.

∑(14)
Sv′ i ,vj

(15)

Svi ,vj(16)

1≤i<j≤n∑1≤i<j≤n(17)

That is, the estimated value L̂ converges to a value greaterthan n−1
n L. Since n is sufficiently large in SNS, it can be
regarded as n−1
n L ≃ L. In addition, as we increase the sample
number by SRW, Sv′ i ,vj converges to Svi ,vj , with the result thatL̂ approaches L.
B. Svi ,vj and Sv′ i ,vj
The shortest path often includes nodes that are hubs of the
network. Considering a complex network, the subgraph G′ of
G has many hubs, since SRW has the property that it is easy tovisit a node with a high degree. In other words, it is consideredthat there is no extremely large difference between the shortest
path in G′ and that in G.
C. How to Determine Threshold m
Since the mixing time is a value that varies depending on
the random walk method and the network to be used, it isdifficult to determine. If m is less than the mixing time, thenode pairs that are not independent, i.e., node pairs connectedby a relatively short number of steps, are sampled, with theresult that the estimated value converges to a smaller value

In this section, we examine the method of determining m
mentioned in Section I V and we evaluate the estimate by the
proposed method using this m. For comparison, we use two
APL estimation methods, using BFS and determining APL ofa subgraph using SRW.
A. Network Datasets
For the experiment, we use four datasets, a network createdaccording to the Barabasi-Albert (BA) model, one of the generation models of complex networks, a random network, andtwo datasets of the Stanford Network Analysis Project (SNAP)[9]. The characteristics of each network are summarized inTable I I.
TABLE IS UMMARY OF DATASETS
Network
BA modelRandom Network
Gnutella
DBLP

n100, 000
100, 000
62, 581
317, 080

D/n
9.99959.99244.72756.6221L
4.29895.26315.9355
6.7815

B. Preliminary Experiment
We experiment with each network on the method of determining m, as described in Section I V. Specifically, we
sampled nodes by SRW as much as 5% of the total number ofnodes n, and observed changes in value resulting increasingm. The results are shown in Fig. 3. According to this result,increasing m in any network shows that the estimated value
begins to converge at some point. For example, looking at

Proc. 2018 IEEE Int'l Conf. on Big Data and Smart Computing(IEEE BigComp 2018), pp.611-614, January 2018

Barabasi-Albert

4
3
2

Proposed Method
APL of G'
BFS

1
0
0

1

2

Random network

14

5

3

4

100

12

90

10

80

Average Path Length

Average Path Length

6

70

8

60

6

50

4

40

2

30

0
0

5

1

sampling rate (%)

23sampling rate (%)

4

5

20
10
0

Gnutella

8
6
4
2
0
0

1

2

3

4

5

sampling rate (%)

Gnutella

DBLP

10

Average Path Length

Average Path Length

10

DBLP

BA model Random network

8

6

Fig. 5. Near perfect match rate between Svi ,vj and Sv′ i ,vj

4

2
0
0

1

2

3

4

sampling rate (%)

Fig. 4. Transformation of L̂ with respect to sample rate in each network

the Gnutella network in Fig. 3, we understand that the value
begins to converge with m approximately equal to 50. In otherwords, the mixing time of the SRW in the Gnutella networkis roughly 50. Assuming that m is 100, it can be consideredthat sufficiently independent node pairs can be selected. In thisway, m is determined for each network.
C. Estimation Experiment of Average Distance
We observe the change of L̂ mentioned in Section I V
resulting from changing the sample rate. Fig. 4 shows thetransition of L̂ for each network. m is determined as describedin Section V.
D. Results and Discussion
As the sample rate increases, the proposed method shows atrend gradually approaching from a value larger than the true
value; in the three networks except the random network at the
sample rate of 5%, it turns out to be an accurate method. As
mentioned in Section IV, in a random network with uniform
degree and no large hub, it is considered to be a factor that
there is a large difference between Svi ,vj and Sv′ i ,vj . Actually,
Fig. 5 shows a perfect match rate between Svi ,vj and Sv′ i ,vj .
This shows that while the perfect match rate achieves 80% to
90% in the scale-free network, in the random network , it isextremely low. However, social networks often have extremely
many friendships for celebrities and others, and mostly they
are scale-free networks. Therefore, the proposed method canbe expected to be effective for social networks.
VI. S UMMARY AND F UTURE C HALLENGES
In this paper, we proposed a method for estimating APL
by graph sampling using random walk for social networks
for which random sampling is difficult. Since the proposed
method uses a crawling-based graph sampling method, it canbe applied to real SNS. Furthermore, the proposed method isan effective method for scale-free networks. The contributionof this research is that more accurate values can be got thanany other sampling method In real social networks.

5

The experiment reported in this study was conducted withthe sample rate set to 5% uniformly in each network. However,when graph sampling is actually applied to SNS, it is desirable
to set the time for random walk to crawl the network as, e.g.,
one week, and to estimate features using the obtained sample.
Finally, although the proposed method uses only portion of
the network, the calculation time takes O(r3 ) for the numberof samples r using Dijkstra’s method, the simplest method.
Solving this problem requires considering the efficiency of
the algorithm. For example, instead of selecting node pairs
separated by more than m steps from the sample list by SRW,
if we select node pairs that are just m steps away, accuracy
will be slightly worse but the number of calculations of the
SSN can be expected to decrease. Evaluation of this trade-off
is a subject for a future study.
ACKNOWLEDGMENT
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).
R EFERENCES[1] Réka Albert and Albert-László Barabási. Statistical Mechanics of Complex Networks. Reviews of Modern Physics, Vol. 74, No. 1, p. 47, 2002.
[2] Xiao Fan Wang and Guanrong Chen. Complex Networks: Small-World,
Scale-Free and Beyond. IEEE Circuits and Systems Magazine, Vol. 3,
No. 1, pp. 6–20, 2003.
[3] Pili Hu and Wing Cheong Lau. A Survey and Taxonomy of Graph
Sampling. arXiv preprint arXiv:1308.5865, 2013.
[4] Mohammad Al Hasan. Methods and Applications of Network Sampling.
In Optimization Challenges in Complex, Networked and Risky Systems,
pp. 115–139. INFORMS, 2016.
[5] Qi Ye, Bin Wu, and Bai Wang. Distance Distribution and Average Shortest
Path Length Estimation in Real-World Networks. In International
Conference on Advanced Data Mining and Applications, pp. 322–333.
Springer, 2010.
[6] David Aldous and Jim Fill. Reversible Markov Chains and Random
Walks on Graphs, 2002.
[7] Abedelaziz Mohaisen, Aaram Yun, and Yongdae Kim. Measuring the
Mixing Time of Social Graphs. In Proceedings of the 10th ACM
SIGCOMM Conference on Internet Measurement, pp. 383–389. ACM,
2010.
[8] Stephen J Hardiman and Liran Katzir. Estimating Clustering Coefficientsand Size of Social Networks via Random Walk. In Proceedings of the
22nd International Conference on World Wide Web, pp. 539–550. ACM,
2013.
[9] Stanford
Large
Network
Dataset
Collection.
https://snap.stanford.edu/data/.

Proc. 2018 IEEE Int'l Conf. on Big Data and Smart Computing(IEEE BigComp 2018), pp.611-614, January 2018