Link prediction in complex networks: a local naïve Bayes model
(2011)

Common-neighbor-based method is simple yet effective to predict missing links, which assume that two nodes are more likely to be connected if they have more common neighbors. In such method, each common neighbor of two nodes contributes equally to the connection likelihood. In this Letter, we argue that different common neighbors may play different roles and thus lead to different contributions, and propose a local näıve Bayes model accordingly. Extensive experiments were carried out on eight real networks. Compared with the common-neighbor-based methods, the present method can provide more accurate predictions. Finally, we gave a detailed case study on the US air transportation network. Introduction. – The problem of link prediction aims at estimating the likelihood of the existence of a link between two nodes in a given network, based on the observed links [1]. Recently, the study of link prediction has attracted much attention from disparate scientific communities. In the theoretical aspect, accurate prediction indeed gives evidence to some underlying mechanisms that drives the network evolution [2]. Moveover, it is very possible to build a fair evaluation platform for network modeling under the framework of link prediction, which might be interested by network scientists [1, 3]. In the practical aspect, for biological networks such as protein-protein interaction networks and metabolic networks [4–6], the experiments of uncovering the new links or interactions are costly, and thus to predict in advance and focus on the links most likely to exist can sharply reduce the experimental costs [7]. In addition, some of the representative methods of link prediction have been successfully applied to address the classification problem in partially labeled networks [8, 9], as well as identified the spurious links resulted from the inaccurate information in the data [10]. Motivated by the theoretical interests and practical significance, many methods for link predication have been proposed. Therein some algorithms are based on Markov chains [11–13] and machine learning [14, 15]. Another group of algorithms are based on node similarity [1, 16]. (a)Corresponding author:linyuan.lue@unifr.ch Common Neighbors (CN) is one of the simplest similarity indices. Empirically, Kossinets and Watts [17] analyzed a large-scale social network, suggesting that two students having many mutual friends are very probable to be friend in the future. Also in online society like Facebook, the users tend to be friend if they have common friends and therefore form a community. Extensive analysis on disparate networks suggests that CN index is of good performance on predicting the missing links [16, 18]. Lü et al. [19] suggested that in a network with large clustering coefficient, CN can provide competitively accurate predictions compared with the indices making use of global information. Very recently, Cui et al. [20] revealed that the nodes with more common neighbors are more likely to form new links in a growing network. The basic assumption of CN is that two nodes are more likely to be connected if they have more common neighbors. Simply counting the number of common neighbors indicates that each common neighbor gives equal contribution to the connection likelihood. However, sometimes different common neighbors may play different roles. For instance, the common close friends of two people who don’t know each other may contribute more to their possibly future friendship than their common nodding acquaintances. In this Letter, we propose a probabilistic model based on the Bayesian theory, called Local Näıve Bayes (LNB) model, to predict the missing links in complex networks. Based on the LNB model,