Link prediction in social networks based on local weighted paths

A graph path, a sequence of continuous edges in a graph, is one of the most important objects used in many studies of link prediction in social networks. It is integrated in measures, which can be used to quantify the relationship between two nodes. Due to the smallworld hypothesis, using short paths with bounded lengths, called local paths, nearly preserves information, but reduces computational complexity compared to the overall paths in social networks. In this paper, we exploit local paths, particularly paths with weight, for the link-prediction problem. We use PropFlow [16], which computes information flow between nodes based on local paths, to evaluate a relationship between two nodes. The higher the PropFlow, the higher the probability that the nodes will connect in the future. In this measure, link strength has a strong link to the measure’s performance as it directs information flow. Therefore, we investigate ways of building a model that can efficiently combine more than one useful property into link strength so that it can improve the performance of PropFlow. © Springer International Publishing Switzerland 2014.