The Link Prediction Problem under a Belief Function Framework

Link prediction is a key research area in social network analysis that enables to understand how social networks evolve over time. It involves predicting the links that may appear in the future based on a snapshot of the social network. Various techniques addressing this problem exist but most of them deal with it under a certain framework. Yet, complete information about the social network of interest is frequently not available as knowledge about the nodes and edges may be partial and incomplete, hence any analysis approach must handle uncertainty in the prediction task. In this paper, we examine the link prediction problem in uncertain social networks by adopting the theory of belief functions. Firstly, a new graph-based model for social networks that encapsulates the uncertainties in the links' structures is proposed. Secondly, we use the assets of the belief function theory for combining pieces of evidence induced from different sources and decision making to propose a novel approach for predicting future links through information fusion of the neighboring nodes. The performance of the new method is validated on a real world social network graph of Facebook friendships.