Estimating the Clustering Coefficient of a Social
Network by a Non-Backtracking Random Walk
Kenta Iwasaki, and Kazuyuki Shudo
Tokyo Institute of Technology

Abstract—The clustering coefficient of social networks can be
estimated via an unbiased sampling technique such as random
walk sampling. To this end, we propose an algorithm that assumes
no prior knowledge of the network and that accesses the network
only through a publicly available interface. The clustering
coefficient of a network is estimated by counting triangles ina non-backtracking random walk (NBRW). A social network
is viewed as an undirected graph and the NBRW is retrieved
through a public interface, which theoretically guarantees its
retrieval. In a simulation study on real social networks, theproposed method achieved higher efficiency and accuracy thanthe prior state-of-the-art method based on a simple random walk.
Index Terms—social network, clustering coefficient, random
walk

I. I NTRODUCTION
Online social networks (OSNs) have become increasingly
popular in recent years. The most popular OSN, Facebook,counted more than 1.8 billion members in January 2017 1 . This
popularity has sparked growing interest in the properties of
OSNs. There are prior work [6], [10] that determines structural
measures of OSNs, including the clustering coefficient.
However, estimating network characteristics of OSNs isa difficult task, because such networks are typically toolarge to measure and their complete datasets are typicallyunavailable, primarily because of privacy concerns [2].
For example, independent sampling which directly obtains
uniform, independent node samples for unbiased estimation,is infeasible from such a large unknown network. In practicalscenarios, the social network may be available only through apublic interface such as an application programming interface(API), which queries and obtains information about a target
node. In most social networks, the public interface provides alist of a user’s neighboring nodes. By applying this function
iteratively to a random member of the neighbor list, one
can effectively perform a random walk on the network.
Considering the delay and query limit of APIs, the sample
should be small but representative. In the example of Fig. 1,
the researchers obtain a neighbor list by repeatedly querying
the API.
However, to calculate the clustering coefficient of a node,
the researcher must query nodes other than the sampled
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).
1 https://www.statista.com/statistics/272014/global-social-networks-rankedby-number-of-users/

Fig. 1. Sampling through the API of a social network.

nodes. Therefore, the clustering coefficient of the network isdifficult to obtain. Hardiman et al. [8] estimated the clustering
coefficient of social networks from the sampling queries alone.
They achieved efficient estimation by counting triangles during
random walk sampling.
Conversely, a simple random walk usually diffuses slowly
across the network, leading to poor estimation accuracy. In
particular, because the next node is selected in purely random
fashion, the walk often returns to the previous node thatwas just visited. This backtracking produces many duplicate
samples over a short to moderate time span, reducing theestimation accuracy. Obviously, such backtracking transitions
should be avoided whenever possible, and the walk should besteered toward unvisited nodes without biasing the estimation.
Lee et al. [9] proposed a non-backtracking random walk
(NBRW) with re-weighting that guaranteed not only unbiased
graph sampling but also smaller asymptotic variance of theestimators than a simple random walk.
In this paper, we propose an efficient and accurate
method for estimating the clustering coefficients of networks.
While sampling, our method counts triangles via a NBRW.
Combining this way of counting triangles with NBRW is
not trivial. We combined these two ideas and adjusted to beable to estimate unbiased. We theoretically proved that the
proposed method can perform the unbiased estimation andshowed theoretical and experimental results that it is more
efficient and better than the existing method.
This paper is organized as follows. Section II shows related
work. Section III provides notations and preliminaries. Section
IV describes our method. Section V compares the method withthe existing method. Section VI summarizes our contributions.
II. R ELATED W ORKThis section describes related work, in which the averageclustering coefficient is estimated by the crawling-based graph

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

sampling method. Ribeiro et al. [10] estimated the network
average clustering coefficient using a simple random walk(SRW). Their computation requires augmenting the set ofsampled nodes with further exploration of the ego network.
To calculate the local clustering coefficient at a special nodev, a range of ego networks of v must be known. Gjaka etal. [6] explored an OSN graph using a Metropolis-Hastings
random walk that generates uniform samples from the nodeset. This method also requires further exploration of the ego
network. Such methods are inefficient because exploring theego network requires additional API queries.
Hardiman et al. [8] estimated the network average clustering
coefficient by a random walk that did not explore the ego
network. Their method outperformed competing approaches[6], [10] on all social networks in their study [8]. However,they used an SRW, which (as mentioned above) diffuses
slowly over the space and compromises the estimation
accuracy. During a transition, the SRW frequently returns to
the just-visited node.
In this paper, we perform a NBRW that avoids theprevious node whenever possible. The proposed method isconceptualized in Section 3 and developed in Section 4. In
Section 5, we show that the proposed algorithm outperforms
Hardiman et al.’s approach [8] on various social networks. The
paper briefly concludes with Section 6.
III. N OTATIONS AND P RELIMINARIESThis section describes the notations, definitions, and thebasic idea the of the proposed method (counting triangles
during NBRW) .

Fig. 2. Transitions of an NBRW over the nodes of G. The walker is currently
located at node w (with kw = 4) and has just visited node v. From w, it will
move to any neighbor except node v with equal probability.

1∑
ci
n i=1
n

C=

(2)

Our proposed method estimates the network averageclustering coefficient.
The first step of the estimation algorithm generates a random
walk. A random walk with r steps on G, denoted by R =(x1 , x2 , . . . , xr ), starts from an arbitrary node vx1 and thenmoves to a chosen probabilistically selected neighboring node.
This process repeats r − 1 times.
Herein, we apply two random walks: the SRW and thenon-backtracking random walk (NBRW) . The SRW on G
moves from a node to a neighboring node, which is randomly
and uniformly selected with with probability d1i . The NBRW
avoids backtracking to the previous node whenever possible.
Let Pr[A] denote the occurrence probability of event A. The
distribution induced by random walk, is defined as

A. Notations
The social graph of an OSN can be modeled as a connected,
undirected graph G = (V, E) with a set of nodes V ={v1 , v2 , . . . , vn } and a set of edges E. We assume that 3 ≤|V | = n < ∞. We also assume that graph G has no self-loops
def
and no multi-edges. Let N (v) = {w ∈ V : (v, w) ∈ E} be
the neighbor set of node v ∈ V , di = kvi = |N (vi )| be thedegree of node v.
A triplet of nodes (vj , vi , vk ) is called connected if there isan edge between vj and vi , and an edge between vi and vk ,and j < k.
A triangle is a connected triplet (vj , vi , vk ) in which vj andvk are connected by an edge. Let △i be the number of edges
between neighbors of vi .
The local clustering coefficient ci [5] of node vi defines theratio of the number of (vj , vi , vk ) triangles to the number of(vj , vi , vk ) connected triplets. Formally,

ci =


 0

di = 0 or di = 12△i
di (di − 1)otherwiseci ∈ [0, 1](1)

The network average clustering coefficient C [5] is definedasπ = (Pr[xr = 1], Pr[xr = 2], . . . , Pr[xr = n]).

(3)After many random walks, the probability Pr[xr =i] converges to a certain value π(i). The vector π =(π(1), π(2), . . . , π(n)) is called the stationary distribution of
G. As is well known, the stationary distribution of the SRW
is di /2|E| [3].
B. Non-Backtracking Random WalkThis subsection overviews the graph sampling method with
the NBRW proposed in [9] and presents its algorithm. Our
proposed algorithm is based on the NBRW, which minimizes
backtracking to the previous node while preserving the same
stationary distribution as the SRW.
In an NBRW with more than two neighbors (kw ≥ 2),
the walker at current node w randomly selects the next node
to visit among the neighbors of node w, except for theprevious node v. If the current node w has only one neighbor(kw = 1), the walk always returns to the previous node v. The
non-backtracking nature of the NBRW as it traverses the nodesof G is depicted in Fig. 2. The NBRW moves from its initialnode, which can be arbitrarily chosen, to any of its neighboring
nodes with equal probability (because no previous nodes havebeen visited).

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

C. Counting Triangles
Herein, we apply the “counting triangles” technique to the
NBRW. Previously, Hardiman et al. [8] estimated the network
average clustering coefficient by this technique in an SRW.
Let (xi−1 , xi , xi+1 ) be any set of consecutive triplets in arandom walk R = (x1 , x2 , . . . , xr ). By the nature of random
walks, (vxi−1 , vxi , vxi+1 ) is a connected triplet. Moreover,
if nodes vxi−1 and vxi+1 are connected by an edge, then(vxi−1 , vxi , vxi+1 ) is a triangular triplet (x1 , x2 , x3 ) is atriangular triplet because an edge connects node vx1 to nodevx3 . Conversely, the consecutive triplet (x2 , x3 , x4 ) is not atriangular triplet because no edge exists between nodes vx2and vx4 .
In practical situations, when the neighbor list includes thetwo most recently sampled nodes during transition to the next
node, then nodes vx1 and vx3 are connected. For example,
consider the walker located at node vx3 = v3 in Fig. 3. The
neighbor list of node vx3 is (v1 , v2 , v3 , v4 ), which includes thetwo most recently visited nodes vx1 = v1 . Therefore, we canconfirm that during the random walk sampling, an edge exists
between nodes vx3 and vx1 .
It is possible to ascertain the existence of an edge bychecking whether the last two sampled nodes have been
included in the neighbor list when making transition to next
node. For example, In Fig. 3, when a walker stays at a nodevx3 = v3 , a neighbor list of the node vx3 is (v1 , v2 , v3 , v4 ),and the last two sampled node vx1 = v1 is included in theneighbor list. Therefore we can confirm that an edge exists
between the nodes vx3 and the node vx1 while sampling via
random walk.
The counting triangles technique estimates the network
average clustering coefficient because the local clustering
coefficient defines the triangle-membership proportion of anode. However, this method is problematic when transiting
to the previous node in an SRW. For example, in Fig. 4, theconsecutive triplet (x1 , x2 , x3 ) can never be a triangular triplet
because the SRW backtracks to the previous node. Generally,
backtracking to the previous node prevents a triangular path.
Therefore, unless the edges are weighted, the proportion oftriangles in the SRW is expected to be low.
In fact, by upward weighting of the counted triangles,
the SRW-based approach proposed in [8] enables unbiased
estimation of the network average clustering coefficient,lowering the estimation accuracy.
This problem is overcome by the NBRW, as shown thefollowing section.

Fig. 3. Example of the counting triangles technique in random walk sampling.

Fig. 4. Example of transition to the previous node in the SRW.

Given a NBRW R′ = (x1 , x2 , . . . , xr ), we define a newvariable ϕ′k as follows: for 2 ≤ ∀k ≤ r − 1, if nodes vxk−1
and vxk+1 are connected, ϕ′k is 1, otherwise it is 0.
When vxk and vi are equal, the expected value of ϕ′k isE[ϕ′k | xk = i]=

2△i
= ci
di (di − 1)

(4)

The first equality holds because there are di (di − 1) equallyprobable combinations of (xk−1 , vi , xk+1 )(xk−1 ̸= xk+1 ),of which only 2△i form a triangle (vj , vi , vk ) or a reverse
triangle (vk , vi , vj ). The third equality holds by definition ofclustering coefficient of node vi .
To estimate C, we introduce two variables, i.e., the weighted
sum Φ of ϕj s and the sum Ψ of the reciprocal degrees of thesampled nodes:

1 ∑ ′ 1
ϕk
r−2
d xk

(5)

1∑ 1
r
dxk

(6)

r−1

Φ=
IV. P ROPOSED M ETHOD

k=2n

We now propose a method that estimates the network
average clustering coefficient of social networks via an NBRW.
Our idea stems from the counting triangles technique [8].
We prove that our estimate converges to the correct value,and demonstrate the superior effectiveness and accuracy our
method over the prior method.

Ψ=

k=1

The expectations of Φ and Ψ are easily determined bylinearity of the expectation and Eq (4):Proc. 2018 IEEE Int'l Conf. on Big Data and Smart Computing(IEEE BigComp 2018), pp.114-118, January 2018

According to Eq(15) and Eq(17),E[Φ]=E[ϕ′k
=

n
∑

1
]
dxk

π ′ (i)E[ϕ′k | xk = i]

i=1
n
∑

V ar[ϕ′k ] < V ar[ϕk
1
di

(7)
(8)

1 ∑
=
ci
2|E| i=1

(9)

n

n
∑
di 1
2|E| di
i=1
n
=
2|E|

(10)
(11)
(12)

As proven in [9], the NBRW and SRW can have the same
stationary distribution π ′ , namely, π ′ (i) = di /2|E|.
From the above equations, C is derived as
1∑
E[Φ]
C=
ci =
n i=1
E[Ψ]
n

(13)

Intuitively, both Φ and Ψ converge to their expected values
and the estimator Φ/Ψ converges to C, as shown below. The
estimator Ĉ of C, is defined as follows:
def Φ

Ĉ =

(14)
Ψ
To show that it is more effective than the existing method by
SRW, we calculate the variance value for the local clustering
coefficient in Eq (4).
V ar[ϕ′k ]=E[(ϕ′k )2 ] − {E[ϕ′k ]}22△i=· 12 − ci 2di (di − 1)

(15)

Conversely, the expectation value of the local clustering
coefficient by SRW in [9] is as follows:diE[ϕk] = cidi − 1(16)

ϕk is defined as follows: given an SRW R =(x1 , x2 , . . . , xr ) for 2 ≤ ∀k ≤ r − 1, and , if nodes vxk−1
and vxk+1 are connected, ϕ′k is 1, otherwise it is 0.
This variance value isV ar[ϕkholds. Therefore, the proposed method has smaller variance.

Finally, we support our theoretical findings in a simulation
study. We use various social network datasets published byby the Stanford Network Analysis Project (SNAP) [1]. The
dataset statistics are listed in Table I.
A. Networks on public datasets

E[Ψ]=E[=(18)

V. E VALUATION

di
1
=
ci
2|E|
d
i
i=1

1
]
d xk
n
∑
1
=
π ′ (i)
di
i=1

di
]
di − 1didi 2
di]=E[(ϕk) ] − {E[ϕk]}2di − 1di − 1di − 12△i
di}2 − ci 2(17)= 2 ·{ddii−1

The effectiveness of each estimator was evaluated on social
networks with known structure published by the Stanford
Network Analysis Project (SNAP) [1]. The dataset statistics
are listed in Table I .
1) Amazon Network: Based on the Customers Who BoughtThis Item Also Bought feature of the Amazon website, thisnetwork was collected by crawling the Amazon website. If a
product i is frequently co-purchased with product j, the graphcontains an undirected edge from i to j. Each product category
provided by Amazon defines a ground-truth community [1].
2) Digital Bibliography and Library Project (DBLP):
DBLP provides a comprehensive list of research papers incomputer science. In the DBLP co-authorship network, two
authors are connected if they have published at least one paper
together.
3) Gowalla: Gowalla is a location-based social networking
website in which users share their locations by checking in.
This undirected friendship network was collected through the
public API of the network. However, the service closed in
January 2012.
4) LiveJournal: LiveJournal is a free online blogging
community in which users declare and share their friendships.
TABLE IN ETWORK STATISTICS
Network
Amazon
DBLP
Gowalla
LiveJournal

n334,863
317,080
196,591
3,997,962

D/n
5.530
6.622
9.668
17.35

C
0.3967
0.6324
0.23670.2843Fig. 5 plots the the normalized root mean squared error(NRMSE) versus the number of steps in√the random walk[4], [10]. The NRMSEs calculated as C1 E[(Ĉ − C)2 ], we
determined in 1000 independently simulations of each case.
To estimate the NRMSE, each simulation was run
independently 1000 times. In all simulations, the initial
position of each random walk was drawn from the stationary
distribution as described in [4], unless otherwise specified. In
practical implementations, one can specify a burn-in periodthat allows the random walk to reach the steady-state [7].
Fig. 5 compares the NRMSEs of the proposed algorithm
and the previous algorithm, which uses the counting triangles

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

Fig. 5. Normalized root mean squared error (NRMSE) in the network clustering coefficient versus step number of the random walk.

technique in the SRW [8]. The results are presented for bothalgorithms on all datasets. The proposed NBRW estimatorconsistently outperformed the SRW estimator.

[10] B. Ribeiro and D. Towsley. Estimating and sampling graphs withmultidimensional random walks. In Internet Measurement Conference,
pages 390–403, 2010.

VI. C ONCLUSIONSWe proposed a method that estimates the network averageclustering coefficient via a NBRW. The proposed algorithm
considerably outperformed the prior state-of-the-art method on
various social networks.
R EFERENCES[1] Stanford large network dataset collection. https://snap.stanford.edu/data/.
[2] M. Al Hasan. Methods and applications of network sampling. In
Optimization Challenges in Complex, Networked and Risky Systems,
pages 115–139. INFORMS, 2016.
[3] D. Aldous and J. Fill. Reversible markov chains and random walks ongraphs, 2002.
[4] 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, pages 98–109. Springer,
2010.
[5] F. Costa, L, F. A. Rodrigues, G. Travieso, and P. R. V. Boas.
Characterization of complex networks: A survey of measurements.
Advances in Physics, 56(1):167–242, 2007.
[6] M. Gjoka, M. Kurant, C. Butts, and A. Markopoulou. Walking in
Facebook: A case study of unbiased sampling of OSNs. In Proceedings
IEEE Infocom, pages 1–9, 2010.
[7] M. Gjoka, M. Kurant, C. T. Butts, and A. Markopoulou. Practical
recommendations on crawling online social networks. Selected Areas inCommunications, IEEE Journal on, 29(9):1872–1892, 2011.
[8] 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, pages 539–550.
International World Wide Web Conferences Steering Committee, 2013.
[9] C.-H. Lee, X. Xu, and D. Y. Eun. Beyond random walk andmetropolis-hastings samplers: why you should not backtrack forunbiased graph sampling.
In ACM SIGMETRICS Performance
Evaluation Review, volume 40, pages 319–330, 2012.

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