A generalized tree augmented naive Bayes link prediction model

This paper studies link prediction, a recently emerged hot topic with many important applications, noticeably in complex network analysis. We propose a novel similarity-based approach which improves the well-known naive Bayes method by introducing a new tree augmented naive (TAN) Bayes probabilistic model. It makes better link predictions since the model alleviates the strong independency hypothesis among shared common neighbors to match the real-world situation. To obtain the latent correlation among common neighbors, we exploit mutual information to quantify the influence from neighbors' neighborhood. This yields a better performance than those methods which employing more local link/triangle structure information. In addition, the TAN model are easily adopted to other common neighbors-based methods such as AA and RA. Experimental results on synthetic and real-world networks show that our algorithms outperform the baseline methods, in terms of both effectiveness and efficiency.