Link Prediction in Social Networks

Introduction

Recently, Question-Answering Bulletin Boards (QABB), such as Yahoo! Answers, Stack Overflow, Windows Live QnA, Quora are getting popularity. Here, People ask questions and let somebody to answer that, in this way Communication is established here. Such communications on QABB connect users and those connections lead to form a social networks. If evolution of such social networks can be predicted, it would be quite helpful to encourage effective communications. For example, by studying the previous communication structures, a question can be recommended to a potential users, who can answer that question.

Link prediction between two nodes can be done mainly with the help of two types of information, attributes of nodes and structural properties of networks that connect nodes. Node attributes, in case of online social networks, consists of personal information of a user, which is not available very easily. However, the second type of information is easily available and that is only preferably used for link prediction. Studying structural properties of networks can be best done through graph proximity measures. This measure is based on two assumption that links in social networks can be predicted through graph proximity measures and the weights of existing links in the social networks. The weight of a link in social networks is defined by the number of encounters of two different users, among whom the link is established.

Weighted Graph Proximities

A link between two users is predicted by ranking all user pairs. The user pairs can be ranked based on some scores, these scores depends on different factors and can be calculated as given below.

First score calculation is based on the assumption that if two users have more common neighbours it is more likely that the two users are connected to each other. A connection weight Score(a,b) is assigned to each pair of nodes x and y, For a node a, let N(a) denotes the set of neighbours of a.

Further the concept of common neighbours was refined by giving more importance to the common neighbour having low degree.

The score can be further modified by taking into account the weights of the links. This can be represented as follows.

Each number indicates the weight of nearby link in Figure 1, and a thick link represents more than one encounters on QABB. According to original definition of common neighbours, Score(x,y) is 2. The score of weighted common neighbour as shown  in Figure 1, is 2.5.

Figure 1: Weighted Common Neighbours

So, finally the score can be defined as follows.

Conclusion

The link prediction in QABB can be done by using the concept of weighted graph proximity measures. Here, weights of links play very important role, by taking them into consideration the performance of link prediction is improved.