Journal of Computer and Communications, 2014, 2, 82-89
Published Online March 2014 in SciRes. http://www.scirp.org/journal/jcc
http://dx.doi.org/10.4236/jcc.2014.24012
How to cite this paper: Lin, X., Shang, T. and Liu, J.W. (2014) An Estimation Method for Relationship Strength in Weighted
Social Network Graphs. Journal of Computer and Communications, 2, 82-89. http://dx.doi.org/10.4236/jcc.2014.24012
An Estimation Method for Relationship
Strength in Weighted Social Network Graphs
Xiang Lin, Tao Shang, Jianwei Liu
School of Electronic and Information Engineering, Beihang University, Beijing, China
Received December 2013
Abstract
Previous works mainly focused on estimating direct relationship strength in social networks. If
two users are not directly connected in a social network, there is no direct relationship. In order to
estimate the relationship strength between two indirectly c onn ec ted users as well as directly
connected users, this paper proposes an estimation method for relationship strength in weighted
social network graphs, which is based on the trust propagation strategy and the estimation of di-
rect relationship strength. Our method considers the length of a relationship path, the number of
relationship paths and the edge weights (direct relationship strength) along with a relationship
path to estimate the strength of indirect relationship. Then it synthesizes the direct and indirect
relationship strength to represent the strength of relationship between two users in social net-
works. Thus our method can fully estimate the relationship strength between any two users in a
social network no matter whether they are directly connected or not.
Keywords
Social Networks; Relationship Strength; Estimation
1. Introduction
With the rapid development of internet services, social network (SN) becomes a most popular service where
people interact with each other. Social network is a set of social actors and the relationships among them [1].
The relationship strength among users is different and can rapidly vary. Information on relationship strength
between two users is useful in many areas such as link prediction, item recommendation, newsfeed, people
search and so on. According to the estimation of relationship strength, the social network provider can improve
the quality of some social network services.
Recently, several++ works have focused on computing the relationship strength in social networks. Interac-
tion data has been used to predict the relationship strength [2,3], but this work only considered two levels of re-
lationship strength, namely, weak and strong relationships. Viswanath et al. [4] analyzed the relationships be-
tween users based on the Facebook’s “wall posts”, which ignored other interaction data. Xiang et al. [5] pro-
posed an unsupervised latent variable model for the estimation of relationship strength based on interaction ac-
tivity and user’s similarity. It uses a richer representation that can span the full spectrum from weak to strong
ties. Srba et al. [6] proposed a method to calculate the relationship strength by means of the interaction data and

X. Lin et al.
83
other “rate factors”. Yanagimoto et al. [7] proposed a relationship strength estimation method in social media. It
estimates relationship strength between web pages in social bookmarking services using a tag vocabulary.
However, nearly all these methods focus on estimating the strength of direct relationship while ignoring indi-
rect relationship between two users in social networks. For example, Alice and Bob have a common friend
though they are not friends. How to estimate the relationship strength between those users is a key problem and
is also very useful in social networks.
In this work, we mainly focus on indirect relationship strength as well as direct relationship strength. We
combine the estimation method of relationship intensity strength to estimate the direct relationship strength be-
tween two users. Firstly, the indirect relationship strength is estimated according to trust propagation strategy.
Secondly, the indirect relationship strength between two users is estimated according to the length of relation-
ship paths, the number of relationship paths and the edge weights along with the relationship paths. Finally, the
direct and indirect relationship strength is synthesized to represent the relationship strength between these two
users. Our method can fully estimate the relationship strength between any two users in a social network no
matter whether they are directly connected or not.
2. Related Work
2.1. Estimation of Direct Relationship Strength
Srba et al. [6] proposed a method to calculate the relationship intensity strength. This method denotes elementa-
ry interaction between two users (e.g., sending a message) or static common information (e.g., common hobby)
as a “rate factor”. Every rate factor influences the strength of a relationship in a positive or negative way de-
pending on the social aspect. And the rate factor from different sources (social networks) has a different impor-
tance, which is represented to be a weight. The final relationship strength is also influenced by the count of in-
stances of the rate factor.
Partial relationship intensity depends on the weight, the count of instances of the rate factor and time:
( )( )
1
,1ln 1
l
kj t
i
f
c
wf
I kjl
=
=++
∑
, (1)
where If is the partial relationship intensity for one rate factor,
kj
w
is the weight of the rate factor j for source k,
l is the count of instances of the rate factor in the relationship of two traced users, lc is the count of instances of
the rate factor, and ft is the function expressing time influence.
The final relationship intensity is calculated as the arithmetic average of the partial relationship intensity of all
sources. This method can estimate the strength of direct relationship between two users, but it ignores the indi-
rect relationship between the users who are not directly connected in the social network.
2.2. Trust Propagation Strategy
Until now, few of previous works have focused on indirect relationship, but there are a lot of works on indirect
trust computation. Although relationship is a different concept from trust, the propagation of indirect relation-
ship between two indirectly connected users is similar to the propagation of indirect trust.
Nasir et al. [8] introduced a shortest-path min-max strategy to compute the indirect trust between a source us-
er s and a target user t. A shortest path is defined as the path with the minimum number of edges. Let
,st
SP
be
the set of all shortest paths between s and t, the strongest shortest paths
,
SST
st
π
are the shortest paths with maxi-
mum strength.
( )()
{ }
,
,,
| max
st
SST
st stSP
SP strstr
ρ
ππ πρ
∈
∈∈ =
(2)
Let
,
s
st
in
be the reachable in-neighbors of t from s with the shortest distance from s among all the reachable
in-neighbors of t. Then the most reliable in-neighbors of t for s in the shortest paths strategy
,
smax
st
in
are the
nodes belonging to
,
s
st
in
having a maximum strength strongest shortest path from s.
( )( )
,
, ,,,
| max
s
st
smaxs SSTSST
stst svsx
x in
inv instrstr ππ
∈

∈∈ =


(3)

X. Lin et al.
84
The final trust from s to t is calculated as
( )
( )
( ) ( )
,
,
( ,)maxmin,,
smax
st
SST
sv
v in
Trusts tstrwv t π
∈
=
. (4)
This method can compute the trust value from a source user s to a target user t, but it is incomplete because it
uses the minimum weight edge of a path to represent the path strength.
3. Estimation Method for Relationship Strength
We focus on estimating the relationship strength between two indirectly connected users as well as directly
connected users.
3.1. Relationship Strength
We define relationship strength as the closeness between two users in social networks. Direct relationship
strength (computed by users’ interaction data, similarity and so on) describes the closeness between two directly
connected users. If user A could find user B along with the edges in a social network graph, there exists a rela-
tionship path between them. Indirect relationship strength describes the closeness between two users who are not
directly connected, and it is calculated by the relationship paths between them. In addition, two users might have
direct and indirect relationship at the same time. So we should synthesize both cases to estimate users’ relation-
ship strength. The relationship types are illustrated in Figure 1.
Let
( )
,
ij
RS vv
,
( )
,
dij
RSv v
and
( )
,
idi j
RSv v
denote the synthetic relationship strength, direct relationship
strength and indirect relationship strength between two individuals
i
v
and
j
v
. Thus
( )( )( )
,,,
ijdij idij
RSvvRSv vRSv v αβ = +
, (5)
where
α
and
β
denote the weight coefficient of direct relationship strength and indirect relationship
strength. In addition,
α
and
β
satisfy the equation as follows:
1 ,0 α βαβ += >
. (6)
Let
{}
,, GV EW=
denote a weighted social network graph.
{ }
12
,,
n
V vvv=
is the user set of the social
network graph where
i
v
denotes the ith user and
Vn=
.
{ }
,ij
Ee=
is the edge set of the social network
graph where
,ij
e
denotes the edge between
i
v
and
j
v
. And the number of edges is denoted as
Em=
.
{ }
,ij
Ww=
is the weight set of edges in the social network graph where
,ij
w
denotes the weight of edge
,ij
e
,
and the value of an edge weight varies continuously from 0 to 1. A simple social network graph is illustrated in
Figure 2.
3.2. Estimation Method
We propose an estimation method for relationship strength in weighted social network graphs, which is based on
the estimation of direct relationship strength and the trust propagation strategy, just as described in the following
part:
0.5
Alice Bob
0.4
0.5
...
d
Alice Bob
0.5
...
0.4
0.5
Alice Bob
...
0.6
0.3
d
...
n
(a) (b) (c)
Figure 1. Relationship type. (a) Direct relationship; (b) Indirect relationship; (c) Synthetic relationship.

X. Lin et al.
85
Figure 2. A simple social network graph.
1) The direct relationship strength is estimated by the estimation method of relationship intensity strength.
And it is represented by the edge weight in the social network graph.
(7)
2) The indirect relationship strength is decided by the length of a relationship path, the number of relationship
paths and the edge weights of relationship paths. The number and the edge weights of relationship paths have a
positive correlation with the indirect relationship strength, while the length of a relationship path has a negative
effect.
Assuming that is a relationship path between and , the indirect relationship strength is described
as follows:
, (8)
where denotes the attenuation coefficient of the length of a relationship path, d denotes the length of the re-
lationship strength, denotes the jth edge weight of a relationship path.
Here is an attenuation function and its value varies continuously from 0 to 1, which is illustrated in
Figure 3. The function represents the weight coefficient of a relationship path among all the paths.
In general, there are more than one relationship path between two users. As the different length of a relation-
ship path has different influence on the relationship strength, we should not treat all paths as equivalent influ-
ence. Therefore, we take the weighted average rather than the arithmetic average to compute indirect relation-
ship strength of all paths.
Assuming that there are n relationship paths between and :
,
with weights
,
thus the indirect relationship strength of all paths is described as follows:
, (9)

X. Lin et al.
86
1
d
d
e
λ −
O
Figure 3. Function of e−λd.
where
i
P
denotes the ith relationship path of
i
v
and
j
v
,
i
d
denotes the length of
i
P
.
3) According to the direct and indirect relationship strength, the synthetic relationship strength is finally cal-
culated as follows:
( )()( )
11
,
1
,,,=+
i
i
i
d
ndj
ij
ijdijidij ijnd
i
ew
RSvvRSv vRSv vw
e
λ
λ
αβ αβ
−
==
−
=



= +⋅⋅
∑∏
∑
. ( 10)
3.3. Property
Theorem 1 The values of
( )
,
ij
RS vv
,
( )
,
dij
RSv v
and
()
,
idi j
RSv v
are all in the interval of
[ ]
0,1
.
Proof
For
,ij
w
is an edge weight between
i
v
and
j
v
and it is a continuous value in the interval of
[]
0,1
, we can
get that the value of
( )
,
dij
RSv v
is in the interval of
[ ]
0,1
because it equals to
,ij
w
. And the value of
i
P
is in the interval of
[ ]
0,1
because it is achieved by multiplying all the edge weights along with the relationship
path. The value of
( )
,
idi j
RSv v
is also in the interval of
[ ]
0,1
because it is estimated by weighted average of
all relationship paths. For
1 αβ +=
and
,0 αβ >
, the value of
( )
,
ij
RS vv
is in the interval of
[]
0,1
be-
cause it is the summation of
( )
,
dij
RSv v α
and
( )
,
idi j
RSv v β
.
Theorem 2 The continuous value of relationship strength from 0 to 1 can span the full spectrum from weak to
strong relationship strength.
Proof
According to Theorem 1, we can know that the values of
( )
,
ij
RS vv
,
( )
,
dij
RSv v
and
( )
,
idi j
RSv v
representing the strength of these three relationship types are all in the continuous interval of
[ ]
0,1
. And if the
value of relationship strength is close to 1, it represents stronger relationship strength. Meanwhile, if it is close to
0, it represents weaker relationship strength. Because there are countless values in the continuous interval of
[ ]
0,1
, the strength of direct relationship, indirect relationship and synthetic relationship represented by these
values can span the full spectrum from weak to strong relationship strength.
4. Search Algorithm of Relationship Paths
We should search all the paths from a source user s to a target user t before estimating indirect relationship
strength. However, there are too many paths if the social network is big enough and it results in high time over-
head. Therefore, we use a modified breadth first search (BFS) algorithm to search the shortest paths from s to
the neighbors of t. Algorithm 1 shows the search algorithm. These shortest paths and the edges between t and its
neighbors make up the relationship paths between s and t. The relationship paths between s and t are illustrated
in Figure 4.
Let
,st
SP
be the set of all shortest paths between s and t. And
,
t
st
in
is the set of all neighbors of t. The all re-
lationship paths are denoted as
,
SST
st
π
.
{ }
,,, ,
|| ,
SST t
stsv vtst
SPev in π ∈∈
(11)

X. Lin et al.
87
5. Experiments
In order to verify the effectiveness of the proposed method, we performed several experiments on a simple so-
cial network (Figure 5). First, we choose a source user s. Second, we estimate the relationship strength between
the source user s and the other users with two methods, including the method of relationship intensity strength [6]
and our estimation method of relationship strength.
We estimate the relationship strength between s and the other users based on the estimation method of rela-
tionship intensity strength, and then represent it with edge weight in the weighted social network graphs.
Before evaluating our method on estimating relationship strength, we set , and . If
two users have direct relationship strength besides indirect relationship strength, the direct relationship strength
should be more important than indirect relationship strength. It agrees with common sense.
At first we use the edge weight, estimated by Equation (7), to represent the direct relationship strength be-
tween two users. Secondly, we search the all relationship paths from a source user s to the other users in the
network. And then we estimate the indirect relationship strength using Equation (9). After that, we synthesize
the direct relationship strength and indirect relationship strength by Equation (10). The comparison of these two
methods is shown in Table 1.
Algorithm 1. Search algorithm of relationship paths.
Input: s: source node; t: target node
Output:
1) find the neighbors of t
2) for each
3)
4)
5) return
Figure 4. Relationship paths between s and t.
Figure 5. A simple weighted social network graph.

X. Lin et al.
88
Table 1. Comparison of our method and reference [6].
Source user
Relationship strength
Target user
s
Our Method Method of [6]
1
v
0.328 0.500
2
v
0.207 0.300
3
v
0.018 None
4
v
0.013 None
5
v
0.010 None
6
v
0.014 None
7
v
0.021 None
8
v
0.144 0.200
9
v
0.040 None
As shown in Table 1,
1
v
,
2
v
and
8
v
have the most strong relationship strength with the source user s in
both methods. The value of relationship strength in our method is smaller than that of relationship intensity
strength because our method considers the indirect relationship strength as well as direct relationship strength.
The indirect relationship strength will decrease the synthetic relationship strength. We can also see that the me-
thod in that of relationship intensity strength cannot estimate the indirect relationship strength (e.g., relationship
strength between s and
3
v
) though it can estimate the direct relationship strength. Since the indirect relationship
is much more common than the direct relationship in a social network, this method has a limitation on estimat-
ing relationship strength from a source user to a target user. Therefore, our method is more comprehensive on
the estimation of relationship strength in a social network.
6. Conclusion
In this paper, we proposed an estimation method for relationship strength in weighted social network graphs.
This method focuses on estimating the indirect relationship strength as well as direct relationship strength. The
indirect relationship strength of one relationship path is estimated by multiplying all the edge weights in the path.
And the final indirect relationship strength is a weighted average of all relationship paths. Compared to other
methods on estimating relationship strength, our method is much more comprehensive.
Acknowledgements
The authors would like to thank the National Basic Research Program of China (No. 2012CB315905), the
National Natural Science Foundation of China (No. 61272501, 4132056, 61173154), and the Beijing Natural
Science Foundation (No. 4132056) for valuable helps.
References
[1] Hanneman, R.A. and Riddle, M. (2005) Introduction to Social Network Methods.
http://faculty.ucr.edu/~hanneman/nettext/
[2] Kahanda, I. and Neville, J. (2009) Using Transactional Information to Predict Link Strength in Online Social Net-
works. Proceedings of the Third International ICWSM Conference, 74-81.
[3] Gilbert, E. and Karahalios, K. (2009) Predicting Tie Strength with Social Media. Proceedings of the SIGCHI Confer-
ence on Human Factors in Computing Systems, 211-220.
[4] Viswanath, B. , Mislove, A., Cha, M., Gummadi, K. P. (2009) On the Evolution of User Interaction in Facebook. Pro -
ceedings of the 2nd ACM workshop on Online Social Networks, 37-42.
[5] Xiang, R., Neville, J. and Rogati, M. (2010) Modeling Relationship Strength in Online Social Networks. Proceedings
of the 19th International Conference on World Wide Web, 981-990. http://dx.doi.org/10.1145/1772690.1772790

X. Lin et al.
89
[6] Srba, I. and Bielikova, M. (2010) Tracing Strength of Relationships in Social Networks. 2010 IEEE/WIC/ACM Inter-
national Conference on Web Intelligence and Intelligent Agent Technology, Toronto, 31 August-3 September 2010,
13-16.
[7] Yanagimoto, H. and Yoshioka, M. (2012) Relationship Strength Estimation for Social Media Using Folksonomy and
Network Analysis. WCCI 2012 IEEE World Congress on Computational Intelligence, Brisbane, 10-15 June 2012, 1-8.
[8] Nasir, S.U. and Ki m, T.H. (2013) Fast Trust Computation in Online Social Networks. IEICE Transactions on Commu-
nications, E96-B, 2774-2783.