Prediction of missing links based on community relevance and ruler inference

The link prediction algorithm which based on node similarity is the research hotspot in recent years. In addition, there are some methods which based on the network community structure information to predict the missing links, however, these studies only concerned about the obvious information between different communities such as direct links. We found that it is hard to predict the missing links if the two communities have little direct connections. In fact, there is similarity between communities such as the similarity between nodes and this similarity is significant for prediction. So, we define a community similarity feature which named community relevance by using not only the obvious information but also the latent information between different communities in this paper. Then a novel algorithm which based on the community relevance and ruler inference is proposed to predict missing links. In this method, we extract the community structure by using the local information of the network first. Next, calculate the relevance of each pair of communities by using the new community relevance indices. Finally, a simple prediction model which based on ruler inference is applied to estimate the probability of the missing links. It is shown that the proposed method has more effective prediction accuracy and the community relevance features improve the predictor with low time complexity, with experiments on benchmark networks and real-world networks in different scales, and compared with other ten sate of the art approaches.