Journal of Computer and Communications, 2014, 2, 8289 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, 8289. 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 Email: shangtao@buaa.edu.cn 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. 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, 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 shortestpath minmax 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 be the set of all shortest paths between s and t, the strongest shortest paths are the shortest paths with maxi mum strength. ( )() { } , ,,  max st SST st stSP SP strstr ρ ππ πρ ∈ ∈∈ = (2) Let be the reachable inneighbors of t from s with the shortest distance from s among all the reachable inneighbors of t. Then the most reliable inneighbors of t for s in the shortest paths strategy are the nodes belonging to 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. 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 , and denote the synthetic relationship strength, direct relationship strength and indirect relationship strength between two individuals and . 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: . (6) Let denote a weighted social network graph. is the user set of the social network graph where denotes the ith user and . is the edge set of the social network graph where denotes the edge between and . And the number of edges is denoted as . is the weight set of edges in the social network graph where denotes the weight of edge , 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 ... 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. 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. Figure 3. Function of e−λd. where denotes the ith relationship path of and , denotes the length of . 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 , and are all in the interval of . Proof For is an edge weight between and and it is a continuous value in the interval of , we can get that the value of is in the interval of because it equals to . And the value of is in the interval of because it is achieved by multiplying all the edge weights along with the relationship path. The value of is also in the interval of because it is estimated by weighted average of all relationship paths. For and , the value of is in the interval of be cause it is the summation of and . 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 , and representing the strength of these three relationship types are all in the continuous interval of . 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 , 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 be the set of all shortest paths between s and t. And is the set of all neighbors of t. The all re lationship paths are denoted as . { } ,,, ,  , SST t stsv vtst SPev in π ∈∈ (11)
X. Lin et al. 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. Table 1. Comparison of our method and reference [6]. Relationship strength Target user s Our Method Method of [6] 0.328 0.500 0.207 0.300 0.018 None 0.013 None 0.010 None 0.014 None 0.021 None 0.144 0.200 0.040 None As shown in Table 1, , and 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 ) 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, 7481. [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, 211220. [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, 3742. [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, 981990. http://dx.doi.org/10.1145/1772690.1772790
X. Lin et al. [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 August3 September 2010, 1316. [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, 1015 June 2012, 18. [8] Nasir, S.U. and Ki m, T.H. (2013) Fast Trust Computation in Online Social Networks. IEICE Transactions on Commu nications, E96B, 27742783.
