Estimating Top-k Betweenness Centrality Nodes
in Online Social Networks
Kazuki Nakajima

Kenta Iwasaki

Toshiki Matsumura

Kazuyuki Shudo

Tokyo Institute of Technology Tokyo Institute of Technology Tokyo Institute of Technology Tokyo Institute of Technology
Tokyo, JapanTokyo, JapanTokyo, JapanTokyo, Japankazuibasou@gmail.com
iwaken59371518@gmail.com
toshiki7507@gmail.com
shudo@is.titech.ac.jp

Abstract—Betweenness centrality is a widely used network
measure in social network analysis. There are many algorithms
for calculating or approximating this measure, but most ofthese algorithms assume that all network information is known.
Therefore, since we can obtain little information for online social
networks because of security and privacy concerns, we must
consider a crawling-based algorithm.
Herein, we propose a new crawling-based algorithm for estimating the top-k nodes with the highest betweenness centrality
in online social networks. The proposed algorithm approximatesthe ego betweenness centrality of the nodes sampled via arandom walk and approximates the top-k nodes with the highest
betweenness centrality in a graph as the top-k nodes with thehighest approximated ego betweenness centrality in the sampled
nodes. This algorithm makes the same number of requests to an
application programming interface as existing algorithms because
we reuse sampled nodes for approximation. Our experimental
results show that the proposed algorithm can estimate the topk nodes of real social networks more accurately than existing
methods when sample size is very small.
Index Terms—social network, betweenness centrality, ego betweenness centrality, random walk

I. I NTRODUCTION
Online social networks (OSNs) have recently gained considerable attention. For example, Twitter had over 300 million
monthly active users in 2018 [1]. There are many studies thathave analyzed a particular OSN as a graph with nodes of users
and edges of relationships among users. In [2]–[4], the authors
investigate structural measures of OSNs such as the clustering
coefficient, average shortest path length, and graphlets.
Identifying influential users in an OSN is important inmarketing [5], [6]. Centrality indicates the importance of nodes
in a graph. In particular, the betweenness centrality proposedby Freeman [7] has been actively used in network analysis[8]–[10]. The betweenness centrality of a node is defined as
the sum of the ratio of the shortest paths between any two
nodes in a graph that pass through that node. Users with highbetweenness centrality in OSNs are instrumental for the spreadof information because these nodes are present on many of theshortest paths in a graph.
Our goal is to estimate the top-k nodes with the highest
betweenness centrality in OSNs. If we have all the information
about a network, we can estimate the top-k betweenness
centrality nodes using an exact algorithm [11] or approximation algorithms [12]–[17]. However, these methods cannot be

Fig. 1. Overview of crawling-based algorithms that estimate top-k nodes.

applied to OSNs because privacy and security concerns prevent
one from obtaining complete network information. In practicalscenarios, we can obtain the information about a target user
by making a request to the application programming interface(API). In most OSNs, we can sample the information using
a crawling algorithm that traverses a list of neighboring users
provided by the API. However, this gives considerably lessthan total information because the number of requests per unit
time is limited for most OSNs.
Therefore, we need crawling-based algorithms that consider
the limitation of requests. As shown in Fig. 1, crawling-basedalgorithms consist of two methods: (1) the sampling method
in which the nodes or edges are sampled from a graph bycrawling and (2) the estimation method in which the top-k
nodes with the highest betweenness centrality in the graphare estimated from the sampled information. Two indices areused for the evaluation of each method: the collection ratio
and the overlap ratio [18]. The former is the ratio of the top-k
nodes that are sampled, whereas the latter is the ratio of the
top-k nodes that are accurately estimated. A sampling methodneeds to be chosen whose collection ratio is overall high inmost graphs because the nodes that are not sampled cannot be
estimated. In addition, we need an estimation method whose
overlap ratio is high.
In this paper, we propose a new crawling-based algorithm toestimate the top-k betweenness centrality nodes in OSNs. The
proposed method approximates the ego betweenness centrality[16] of the nodes sampled via a random walk and thenapproximates the top-k betweenness centrality nodes in agraph as the nodes with the highest approximated top-k ego

Proc. IEEE ISPA-IUCC-BDCloud-SocialCom-SustainCom 2018,
pp.1128-1135, December 2018

betweenness centrality in the sampled nodes. Our experimental
results show that the overlap ratio of the proposed method ishigher for real social networks when sample size is very small
than that of existing methods in [18] and [19].
II. RELATED WORK
A number of studies have focused on estimating the top-k
betweenness centrality nodes. In this section, we describe thecases in which all the network information can be obtainedand discuss cases in which only a limited amount of network
information can be obtained.
A. Cases Wherein All Network Information Can Be Obtained
Currently, the fastest known algorithm for exactly calculating the betweenness centrality of all the nodes is Brandes’ algorithm [11]. This algorithm solves the single-source
shortest path problem (SSSP) from every node (v) and thentraverses backward on these paths to efficiently compute thecontribution of the shortest paths from v to the betweenness
centrality of other nodes. The algorithm requires at leastO(nm) time for the unweighted graphs and O(nm+n2 log n)time for the weighted graphs, where n is the number of nodes
and m is the number of edges. Therefore, for considerablylarge graphs, Brandes’ algorithm is not practical for performing exact calculations. For this reason, many approximation
algorithms have been proposed [12]–[17].
There are two approximation approaches that are used toestimate the top-k betweenness centrality nodes. The first
approach is to approximate the betweenness centrality of
all nodes via a random sampling [12]–[14]. Brandes andPich solved the SSSP using a small set of nodes randomly
sampled from nodes in a graph [12]. Yoshida randomly
sampled node pairs and computed their shortest paths byusing the breadth-first search algorithm [13]. Riondato andKornaropoulos approximated the betweenness centrality of allnodes by randomly sampling the shortest paths between any
two nodes [14].
The second approach is to approximate the top-k betweenness centrality nodes as the top-k nodes of another centrality[15]–[17]. The other centrality needs to be calculated easily foreach node from little information, and many of the top-k nodesof another centrality should be top-k betweenness centrality
nodes. Pfeffer and Carley used the k-betweenness centrality(proposed by Borgatti and Everett [20]), which selected nodepairs with the shortest path length of k or less from a graph[15]. Everett and Borgatti used the ego betweenness centralityof each node, which selects the node pairs from their neighbors
and is equivalent to 2-betweenness centrality [16]. Kourtellis
et al. proposed the k-path centrality [17] and used it for
approximation. The k-path centrality considers random paths
in a graph whose length is k or less but which need notnecessarily be the shortest paths. In addition, Kourtellis et al.
proposed an algorithm that approximates the k-path centralityof all nodes via a random sampling.
In this study, we used ego betweenness centrality; however,
our method is different from that proposed in previous research[16] in terms of the assumption that considerably limited
information is available from OSNs. Everett and Borgatti
assumed that all the network information was available when
they calculated the ego betweenness centrality of all the nodes.
Therefore, it is impractical to apply this method to OSNs
because we can obtain the little information. For the same
reason, other exact or approximation algorithms [11]–[15],[17] can not be applied.
B. Cases Wherein Limited Network Information Can Be Obtained
There are two crawling-based algorithms which can beapplied to OSNs [18], [19]. Each crawling-based algorithm iscomposed of two methods: (1) the sampling method in which
the nodes or edges are sampled from a graph by crawlingand (2) the estimation method in which the top-k nodes are
estimated from the sampled information. Lim et al. introduced
the following indicators for evaluating each method [18].
Collection ratio: The ratio of the number of top-k nodes
that are sampled to k.
• Overlap ratio: The ratio of the number of top-k nodes
that are accurately estimated to k.
•

The collection ratio depends on the sampling method, whereas
the overlap ratio depends on the estimation method.
First, we describe sampling methods. Ideally, we shouldchoose the sampling method whose collection ratio is overallhigh for many networks with small sample size. There are anumber of crawling-based sampling methods, such as breadthfirst search sampling and random walk sampling. Previous
studies [18], [19] have compared the collection ratios ofvarious crawling-based sampling methods, and the collection
ratio of random walk sampling was found to be overall highin most graphs. In addition, when we use a random walksampling, we have the advantage of being able to performa theoretical analysis because the stationary distribution of arandom walk can be calculated.
Next, we describe estimation methods. Maiya and BergerWolf induced a subgraph, G′ , from a set of sampled nodes,
V ′ , in the graph G = (V, E) and approximated the top-k
betweenness centrality nodes in G as the top-k betweenness
centrality nodes in G′ [19]. A subgraph induced by V ′ in G is
defined as G′ = (V ′ , E ′ ), where E ′ = {(vi , vj ) ∈ E : vi , vj ∈V ′ }.
Lim et al. approximated the top-k nodes with the highest
betweenness centrality nodes in G as the top-k nodes with thehighest degree centrality among the nodes sampled via a random walk [18]. Nodes with high degree centrality frequently
have high betweenness centrality [21], [22]. In addition, thedegree centrality of each sampled node can be calculated
exactly because all neighboring nodes of the sampled nodes
are obtained via a random walk.
Our method approximates the top-k betweenness centrality
in a graph as the top-k nodes with the highest approximatedego betweenness centrality in the nodes sampled via a random
walk. In Section V, we show that the overlap ratio of our

Proc. IEEE ISPA-IUCC-BDCloud-SocialCom-SustainCom 2018,
pp.1128-1135, December 2018

proposed method is higher than that of existing methods [18],[19] on real social networks.
III. P RELIMINARIESIn this section, we describe the notation, several centrality
definitions, and random walk.

that pass through vi equals 0 because (vj , vk ) ∈ E. Therefore,
for each vj ∈ N (i),{1(vk ∈ Nj (i))σj,k (i)= |N (j)∩N (k)|.
σj,k0(otherwise)

A. Notations and Definitions
OSNs can be modeled as an undirected and unweighted
graph, G = (V, E), with a set of nodes, V = {v1 , v2 , ..., vn },and a set of edges E. We assume that |V | = n and that thegraph G is a simple and connected graph. Let N (i) = {vj ∈V : (vi , vj ) ∈ E} denote the set of neighbors of the nodesvi ∈ V and di = |N (i)| denote the degree of node vi .
The betweenness centrality of vi is defined as the sum of
the ratio of the shortest path between all pairs of nodes in thegraph that pass through vi [7]. Let σj,k denote the numberof shortest paths between vj and vk . For vi ∈ V , let σj,k (i)denote the number of shortest paths between vj and vk thatpass through vi . For any vi ∈ V and vj ∈ N (i), we define
σj,j (i)σj,j = 0.
Definition 1. The betweenness centrality of vi is defined as∑σj,k (i)BC(i) =.
σj,k
vj ,vk ∈V \{vi }The k-betweenness centrality is defined as the sum of theratio of the shortest paths between node pairs having theshortest path length as k or less [20]. Let disti,j denote theshortest path length between vi and vj .
Definition 2. The k-betweenness centrality of vi is defined as∑
σi1 ,i2 (i)BCk (i) =.
σi1 ,i2
vi1 ,vi2 ∈V \{vi },disti1 ,i2 ≤k

An ego network is a network comprised of a certain nodeand its neighbors. The ego betweenness centrality of vi is the
betweenness centrality of vi in the ego network of vi [16].
Definition 3. The ego betweenness centrality of vi is definedas∑σj,k (i)eBC(i) =.
σj,kvj ,vk ∈N (i)We define Nj (i) = N (i)\(N (j)∪{vj }). For a simple graph,the following proposition is obtained from this definition:
Proposition 1.
eBC(i) =∑∑vj ∈N (i) vk ∈Nj (i)1.
|N (j) ∩ N (k)|Proof. When vk ∈ Nj (i), the number of shortest paths
between vj and vk that pass through vi equals 1 because there
are no multiple edges and (vj , vk ) ∈/ E. In addition, there isa shortest path between vj and vk for each common neighborof vj and vk . Therefore, σj,k = |N (j) ∩ N (k)| holds. Whenvk ∈/ Nj (i), the number of shortest paths between vj and vk

We also obtain following proposition.
Proposition 2. For any nodes vi , the following inequality issatisfied:0 ≤ eBC(i) ≤ di (di − 1).
σ(i)Proof. For nodes vi ∈ V and vj , vk ∈ N (i), 0 ≤ σj,kj,k ≤1 holds. From Definition 3, the lower bound is obtained ifσ (i)and only if σj,kj,k = 0 for all vj , vk ∈ N (i). For any vj ∈σj,j (i)σj,j = 0. Therefore, the upper bound isσ (i)obtained if and only if σj,kj,k = 1 for all vj ∈ N (i) andN (i), we definedvk ∈ N (i)\{vj }.

The degree centrality of vi is defined as
DC(i) = di .
B. Random Walk
In a random walk, a walker uniformly selects a neighbor ina random fashion and traverses the node. This process repeats
until the target number of the sampled nodes is reached. We
sample the information, such as IDs in OSNs, of nodes which
traversed by random walk. Here let R = (x1 , x2 , ..., xr ) be asequence of indices of nodes sampled via a random walk withr steps. The transition probability of node vi to node vj in arandom walk is defined as{1(vj ∈ N (i))
pi,j = di.
0 (otherwise)
Let P r[A] denote the probability that event A occurred. We
denote the distribution induced by R as follows:
πR = (P r[xr = 1], P r[xr = 2], ..., P r[xr = n]).
After many steps, the probability P r[xr = i] converges toa certain value π(i). The vector π = (π(1), π(2), ..., π(n))
is called the stationary distribution of G. In particular, thestationary distribution of a random walk is given as follows[23]:diπ(i) =.
2|E|
Herein, we assume that the initial node vx1 is drawn fromthe stationary distribution of G, as described in [23]. In OSNs,
it is impossible to do this in practice. Therefore, we randomly
select the initial node from V and repeat the random walkprocess with some steps until it converges to the stationary
distribution, after which we start sampling. The number of thesteps depends on the mixing time of G and many OSNs are
known to have low mixing time [24].

Proc. IEEE ISPA-IUCC-BDCloud-SocialCom-SustainCom 2018,
pp.1128-1135, December 2018^ asDefinition 4. We define eBC(i)^ = di 2 Φ(i).
eBC(i)

Fig. 2. Example of a random walk.

IV. P ROPOSED M ETHOD
Our estimation method approximates the top-k nodes withthe highest betweenness centrality in a graph as the topk nodes with the highest approximated ego betweenness
centrality in the nodes sampled via a random walk. Many
OSNs have the low average shortest path length, which arecalled small world networks [25]. For example, in Twitter,
it is suggested that the average shortest path length is 4.12,
which is a considerably small value [26]. For such small world
networks, many nodes with high k-betweenness centrality [20]also have high betweenness centrality, where the value ofk is considerably small (e.g., 2, 3, and 4) [15], [27]. Thisis because high betweenness centrality nodes mediate many
node pairs whose shortest path length is small. We use the
ego betweenness centrality that is equal to 2-betweenness
centrality, because we need to make additional requests incomparison with those required for the existing methods [18],[19] when k was larger than 2. However, even though k is
2, as shown in our experiment, ego betweenness centrality isgood approximation for betweenness centrality in real social
networks.

For example, let vi be i in Fig. 2. Additionally, let R =(x1 , x2 , ..., x6 ) = (1, 5, 9, 8, 5, 7) be a sequence of indices of
the nodes sampled by a random walk of six steps. In thiscase, I(5) = {2, 5}, I(8) = {4}, and I(9) = {3} holds. For^ . When l = 2, the conditions
example, we calculate eBC(5)i = x2 = 5, vx1 = 1, vx3 = 9, and vx3 ∈ Nx1 (5) hold.
|N (x1 ) ∩ N (x3 )| = |{4, 5}| = 2; therefore, we conclude
that ϕ2 (5) = 12 . When l = 5, the conditions i = x5 = 5,
vx4 = 8, vx6 = 7, and vx6 ∈/ Nx4 (5) hold. Thus, we^conclude that ϕ5 (5) = 0. Consequently, we can obtain eBC(5)
d5 2
25
25
= |I(5)| Φ(5) = 2 (ϕ2 (5) + ϕ5 (5)) = 4 . Similarly, we obtain^ = eBC(9)^ = 0. In addition, eBC(1)^ , eBC(2)^ , eBC(3)^ ,eBC(8)^ , eBC(6)^ , and eBC(7)^ are not defined.
eBC(4)

We can obtain the following lemma:
Lemma 1. For any sampled nodes vi ∈ V , we have that^ = eBC(i).
E[eBC(i)]Proof. For each l ∈ I(i), both vxl−1 and vxl+1 are neighborsof vi because a random walk traverses the neighboring node.
Therefore, we obtain^ = E[di 2 Φ(i)] = E[di 2 ϕl (i)]E[eBC(i)]∑= di 2(P r[xl−1 = j, xl+1 = k|xl = i]

A. Approximating Ego Betweenness Centrality
Here, we describe how to approximate the ego betweenness centrality of nodes sampled via a random walk. Let
R = (x1 , x2 , ..., xr ) be a sequence of indices of the nodes
sampled via a random walk with r steps. We assume that theinitial node vx1 is drawn from the stationary distribution of G.
We define the set I(i) for each sampled node vi as follows:
I(i) = {l : xl = i, 2 ≤ l ≤ r − 1}.
When we visit vi at l step (2 ≤ l ≤ r − 1), l is an element of
I(i). For each l ∈ I(i), we define a variable ϕl (i) as follows:{1(vxl+1 ∈ Nxl−1 (i))ϕl (i) = |N (xl−1 )∩N (xl+1 )|.
0(otherwise)
We define a variable Φ(i) as follows:
1 ∑Φ(i) =ϕl (i)|I(i)|l∈I(i)For each sampled node vi which the condition I(i) ̸= ϕ holds,^ be the approximation for eBC(i).
let eBC(i)(1)

vj ,vk ∈N (i)

= di

2

∑

∑

× E[ϕl (i)|xl−1 = j, xl+1 = k])(P r[xl−1 = j, xl+1 = k|xl = i] (2)vj ∈N (i) vk ∈Nj (i)×1).
|N (j) ∩ N (k)|Eq. (1) holds because of the law of total expectation. Eq. (2)holds due to the definition of ϕl (i). The condition P r[xl−1 =j, xl+1 = k|xl = i] holds:
P r[xl−1 = j, xl+1 = k|xl = i]P r[xl−1 = j, xl = i, xl+1 = k]=P r[xl = i]P r[xl−1 = j] · pj,i · pi,k=P r[xl = i]
=

dj
1
1
2|E| · dj · di
di
2|E|

=

1
.
di 2

Proc. IEEE ISPA-IUCC-BDCloud-SocialCom-SustainCom 2018,
pp.1128-1135, December 2018

(3)
(4)
(5)

TABLE IDATASETS .
Network
Epinions [28]soc-buzznet [29]Gowalla [28]soc-academia [29]Dogster [28]soc-flickr [29]|V |75,877101,163
196,591
200,167
426,485
513,969|E|
405,739
2,763,066
950,327
1,022,440
8,543,321
3,190,452

V. E XPERIMENTAL R ESULTS

Fig. 3. An example of calculating ϕl (i).

Eq. (3) holds due to the definition of the conditional probability. Eqs. (4) and (5) holds because of the transition probability
and stationary distribution of a random walk. Therefore,
∑
∑
1
1
^
E[eBC(i)]= di 2
2 |N (j) ∩ N (k)|divj ∈N (i) vk ∈Nj (i)

=

∑

∑

vj ∈N (i) vk ∈Nj (i)1|N (j) ∩ N (k)|= eBC(i).

The approximation error is relatively large for nodes whose|I(i)| is small. However, small I(i) means that vi is visitedlittle, and such nodes have often low degree because nodes
with low degree is rarely traversed in a random walk. Their
exact ego betweenness centrality is also small frequently (See
Proposition 2).
B. Number of Requests to API
In OSNs, we can obtain the IDs for given user’s neighbors by making a request to the APIs. In a crawling-basedalgorithm, we need to consider the total number of requests
because we are allowed only a limited number of requests perunit time in most OSNs.
To avoid repetitive requests for the nodes that have alreadybeen traversed once, we store the IDs of the neighboring nodes
for each sampled node. Therefore, the number of requests to
the API of sampling via r steps of a random walk is equal to
the number of sampled nodes n′ (n′ ≤ r): all algorithms needto make requests at the least n′ times.
As well as existing crawling-based algorithms [18], [19],our algorithm only makes requests n′ times because there areno additional requests in approximating ego betweenness centrality of each sampled nodes. In our algorithm, we calculate
ϕl (i) for each l ∈ I(i). We consider the case of Fig. 3. We
can check vxl+1 ∈ Nxl−1 (i) and calculate ϕl (i) = 13 withoutsampling additional common neighbors such as vj . This isbecause we know N (xl−1 ) and N (xl+1 ) since we sampledthem.

We used real OSNs to evaluate our method. We focus onundirected and simple graphs by removing the directions ofedges if the graphs are directed, treating multiple edges asa single edge, and deleting the loops. Additionally, for an
unconnected graph, we deleted the nodes that are not containedin the largest connected component of the graph. Table I lists
number of nodes and number of edges.
To compare our method with existing methods [18], [19], we
use the collection ratio and the overlap ratio. Each crawlingbased algorithm consists of a sampling method and an estimation method. Both our and existing algorithms use thesame sampling method, namely random walk: these algorithms
have same collection ratio. Therefore, in order to compare
the overlap ratio of each estimation method, we calculate theoverlap ratio of each estimation methods from the same sample
nodes in each simulation. Each simulation is performed asfollows:
1) We sample n′ nodes from an original graph by a random
walk. we select the initial node of a random walk fromthe stationary distribution of the graph.
2) We estimate top-k nodes from the same n′ sampled
nodes by each estimation method (namely the proposed
method, Lim et al.’s method, and Maiya et al.’s method).
3) We calculate overlap ratios of each estimation method.
We ran the simulation independently 1000 times and compared the average of overlap ratios of each estimation method.
We discuss the average of each method when n′ is changed
and when k is changed, respectively.
First, we discuss the experimental result when n′ is changed.
Fig. 4 shows the average of the collection ratio and overlap
ratios of the proposed method and those of Lim et al. andMaiya et al. when we vary n′ from 1000 to 5000 in incrementsof 1000 (Indicated by a black dotted line, a black solid line,
a red solid line, a black dashed line, a black dash-dot line).
As mentioned above, each algorithm has the same collection
ratio. Note that the collection ratio is the maximum value ofthe overlap ratio, and it is advantageous to have these twovalues close to each other.
Firstly, we discuss the collection ratio of a random walk.
In all graphs, we could collect many top-10 nodes with thehighest betweenness centrality in spite of small sample sizes.
We often traverse nodes with high degree in a random walk:therefore, nodes with high betweenness centrality often havehigh degree or are close to nodes with high degree.

Proc. IEEE ISPA-IUCC-BDCloud-SocialCom-SustainCom 2018,
pp.1128-1135, December 2018

TABLE II
T HE AVERAGE OVERLAP RATIO OF TOP -k NODES IN 1000 SIMULATIONS (n′ = 5000).
Network
Epinions
soc-buzznet
Gowallasoc-academia
Dogster
soc-flickr

Ours
k=10
0.881
0.903
0.856
0.851
0.915
0.763

Lim et al.
k=10
0.800
0.900
0.800
0.801
0.900
0.682

Maiya et al.
k=10
0.849
0.800
0.801
0.810
0.878
0.697

Ours
k=20
0.817
0.921
0.764
0.847
0.851
0.609

TABLE IIIT HE OVERLAP RATIO BETWEEN EXACT TOP 10 BETWEENNESSCENTRALITY NODES AND EXACT TOP 10 EGO BETWEENNESS CENTRALITY( DEGREE CENTRALITY ) NODES .
Network
Epinions
soc-buzznet
Gowallasoc-academia
Dogster
soc-flickr

Ego betweenness
1.0
0.9
0.9
0.8
1.0
0.9

Degree
0.8
0.9
0.8
0.8
0.9
0.7

Then, we compare the overlap ratios of the proposed method
and existing methods. We obtained three results. First, theoverlap ratios of proposed method are higher than those of Lim
et al.’s method in all graphs when n′ = 5000. The overlap ratioof the proposed method converges to the overlap ratio between
the exact top 10 betweenness centrality nodes and the exact top
10 ego betweenness centrality nodes in each graph. Similarly,
the overlap ratio of Lim et al.’s method converges to theoverlap ratio between the exact top 10 betweenness centrality
nodes and the exact top 10 degree centrality nodes. Table III
shows the exact overlap ratio of each method and the higher
overlap ratio is shown in bold. The proposed method achieved
higher overlap ratios than Lim et al.’s method, because theexact overlap ratios of ego betweenness centrality are higher
overall than those of degree centrality.
Second, the overlap ratios of the proposed method arelower than those of Lim et al.’s method in all graphs whenn′ = 1000. This is caused by rank error among the top
nodes with approximated ego betweenness centrality becauseof approximation error. In the future, we would like to improve
the approximation error of the proposed method.
Third, the overlap ratios of the proposed method are higher
overall than those of Maiya et al.’s method in all graphs. The
overlap ratio of Maiya et al.’s method depends on the induced
subgraph, and the betweenness centrality is defined globallyin a graph. Therefore, the overlap ratio of their method is
unstable when the number of sampled nodes is small.
Finally, we discuss the experimental result when k ischanged. Table II shows the average of overlap ratios of the
proposed method and those of Lim et al.’s method, and Maiya
et al.’s method when we set k as 10, 20 and 50, respectively.
The highest average overlap ratio among these methods iss
shown in bold. The overlap ratios of the proposed method
are higher than those of other methods in all graphs when

Lim et al.
k=20
0.750
0.900
0.796
0.854
0.753
0.509

Maiya et al.
k=20
0.793
0.784
0.727
0.853
0.859
0.594

Ours
k=50
0.764
0.792
0.740
0.739
0.881
0.559

Lim et al.
k=50
0.740
0.740
0.719
0.740
0.844
0.335

Maiya et al.
k=50
0.781
0.719
0.716
0.656
0.804
0.565

k is equal to 10. Also, the proposed method has overall
higher ratios than those of the other methods when k isequal to 20 and 50. For some graphs, the overlap ratio of
the proposed method is lower than that of another method;
however, this is caused by the approximation error of ego
betweenness centrality. Future work consists of improving theapproximation error of ego betweenness centrality of sampled
nodes when the number of sampled nodes is small.
VI. C ONCLUSION
We proposed a new method to estimate the top-k betweenness centrality nodes via a random walk in OSNs. We approximated the ego betweenness centrality of the nodes sampled
via a random walk and the top-k betweenness centrality nodes
as the top-k nodes of the approximated ego betweenness
centrality in the sampled nodes. In our approximation method,
we reused the sampled nodes to avoid making additionalrequests. For OSNs wherein only limited information about
these networks can be obtained, our experimental results showthat the proposed method can estimate top-k nodes moreaccurately than existing methods. In future work, we would
like to improve the approximation error of ego betweenness
centrality of sampled nodes and propose estimation algorithms
for directed graphs.
VII. ACKNOWLEDGMENT
This work was supported by JSPS KAKENHI Grant Numbers 16K12406. This work was supported by New Energy andIndustrial Technology Development Organization (NEDO).
R EFERENCES[1] “Q22018
lettertoshareholders,”
http://files.shareholder.
com/downloads/AMDA-2F526X/6357113850x0x982955/
2C0E130D-5400-4185-9C99-7C00EF47461B/Q2 2018 Shareholder
Letter.pdf, 2018.
[2] K. Iwasaki and K. Shudo, “Estimating the clustering coefficient of asocial network by a non-backtracking random walk,” in Big Data andSmart Computing (BigComp), 2018 IEEE International Conference on.
IEEE, 2018, pp. 114–118.
[3] T. Matsumura, K. Iwasaki, and K. Shudo, “Average path length estimation of social networks by random walk,” in Big Data and Smart
Computing (BigComp), 2018 IEEE International Conference on. IEEE,
2018, pp. 611–614.
[4] X. Chen, Y. Li, P. Wang, and J. Lui, “A general framework for
estimating graphlet statistics via random walk,” Proceedings of the
VLDB Endowment, vol. 10, no. 3, pp. 253–264, 2016.
[5] D. Kempe, J. Kleinberg, and É. Tardos, “Maximizing the spread ofinfluence through a social network,” in Proceedings of the ninth ACM
SIGKDD international conference on Knowledge discovery and data
mining. ACM, 2003, pp. 137–146.

Proc. IEEE ISPA-IUCC-BDCloud-SocialCom-SustainCom 2018,
pp.1128-1135, December 2018

[6] J. Weng, E.-P. Lim, J. Jiang, and Q. He, “Twitterrank: finding topicsensitive influential twitterers,” in Proceedings of the third ACM international conference on Web search and data mining. ACM, 2010, pp.
261–270.
[7] L. C. Freeman, “A set of measures of centrality based on betweenness,”
Sociometry, vol. 40, no. 1, pp. 35–41, 1977.
[8] M. P. Joy, A. Brock, D. E. Ingber, and S. Huang, “High-betweenness
proteins in the yeast protein interaction network,” BioMed ResearchInternational, vol. 2005, no. 2, pp. 96–103, 2005.
[9] M. E. Newman and M. Girvan, “Finding and evaluating community
structure in networks,” Physical review E, vol. 69, no. 2, pp. 026–113,
2004.
[10] R. Guimera and L. A. N. Amaral, “Modeling the world-wide airport
network,” The European Physical Journal B-Condensed Matter andComplex Systems, vol. 38, no. 2, pp. 381–385, 2004.
[11] U. Brandes, “A faster algorithm for betweenness centrality,” Journal ofmathematical sociology, vol. 25, no. 2, pp. 163–177, 2001.
[12] U. Brandes and C. Pich, “Centrality estimation in large networks,”
International Journal of Bifurcation and Chaos, vol. 17, no. 07, pp.
2303–2318, 2007.
[13] Y. Yoshida, “Almost linear-time algorithms for adaptive betweenness
centrality using hypergraph sketches,” in Proceedings of the 20th ACM
SIGKDD international conference on Knowledge discovery and data
mining. ACM, 2014, pp. 1416–1425.
[14] M. Riondato and E. M. Kornaropoulos, “Fast approximation of betweenness centrality through sampling,” Data Mining and Knowledge
Discovery, vol. 30, no. 2, pp. 438–475, 2016.
[15] J. Pfeffer and K. M. Carley, “k-centralities: Local approximations ofglobal measures based on shortest paths,” in Proceedings of the 21stInternational Conference on World Wide Web. ACM, 2012, pp. 1043–
1050.
[16] M. Everett and S. P. Borgatti, “Ego network betweenness,” Social
networks, vol. 27, no. 1, pp. 31–38, 2005.
[17] N. Kourtellis, T. Alahakoon, R. Simha, A. Iamnitchi, and R. Tripathi,“Identifying high betweenness centrality nodes in large social networks,”
Social Network Analysis and Mining, vol. 3, no. 4, pp. 899–914, 2013.

[18] Y. S. Lim, D. S. Menasché, B. Ribeiro, D. Towsley, and P. Basu,“Online estimating the k central nodes of a network,” in Network Science
Workshop (NSW), 2011 IEEE. IEEE, 2011, pp. 118–122.
[19] A. S. Maiya and T. Y. Berger-Wolf, “Online sampling of high centrality
individuals in social networks,” in Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, 2010, pp. 91–98.
[20] S. P. Borgatti and M. G. Everett, “A graph-theoretic perspective on
centrality,” Social networks, vol. 28, no. 4, pp. 466–484, 2006.
[21] K.-I. Goh, E. Oh, B. Kahng, and D. Kim, “Betweenness centrality
correlation in social networks,” Physical Review E, vol. 67, no. 1, p.
017101, 2003.
[22] M. Barthelemy, “Betweenness centrality in large complex networks,”
The European Physical Journal B-Condensed Matter and Complex
Systems, vol. 38, no. 2, pp. 163–168, 2004.
[23] 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. ACM, 2013, pp. 539–550.
[24] A. Mohaisen, A. Yun, and Y. Kim, “Measuring the mixing time of social
graphs,” in Proceedings of the 10th ACM SIGCOMM conference on
Internet measurement. ACM, 2010, pp. 383–389.
[25] A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and B. Bhattacharjee, “Measurement and analysis of online social networks,” in Proceedings of the 7th ACM SIGCOMM conference on Internet measurement.
ACM, 2007, pp. 29–42.
[26] H. Kwak, C. Lee, H. Park, and S. Moon, “What is twitter, a social
network or a news media?” in Proceedings of the 19th international
conference on World wide web. ACM, 2010, pp. 591–600.
[27] M. Ercsey-Ravasz and Z. Toroczkai, “Centrality scaling in large networks,” Physical review letters, vol. 105, no. 3, p. 038701, 2010.
[28] “Konect datasets: The koblenz network collection,” http://konect.
uni-koblenz.de/.
[29] “The network data repository with interactive graph analytics andvisualization,” http://networkrepository.com.

Proc. IEEE ISPA-IUCC-BDCloud-SocialCom-SustainCom 2018,
pp.1128-1135, December 2018

(a) Epinions(b) soc-buzznet(c) Gowalla(d) soc-academia(e) Dogster(f) soc-flickr

Fig. 4. The average collection ratio and average overlap ratio value of each methods in 1000 simulations (k=10).

Proc. IEEE ISPA-IUCC-BDCloud-SocialCom-SustainCom 2018,
pp.1128-1135, December 2018