Temporal Bipartite Projection and Link Prediction for Online Social Networks

Abstract—In user-item networks, the link prediction problem has received considerable attentions and has many applications (e.g., recommender systems, ranking item popularity) in recent years. Many previous works commonly fail to utilize the dynamic nature of the networks. This paper focuses on dealing with the temporal information and proposes an algorithm to cope with the link prediction problem on bipartite networks. We describe a temporal bipartite projection method that yields a projected item graph, called the temporal projection graph (TPG). Based on the TPG, we propose a scoring function called STEP (Score for TEmporal Prediction) for each user-item pair. STEP leverages the historical behaviors of individual users and the social aggregated behaviors learned from the TPG for the link prediction problem. Furthermore, we use TPG and PageRank to rank the popularity of items. To validate our algorithms, we perform various experiments by using the DBLP author-conference dataset, the Flickr dataset and the Delicious dataset. We show that our results of the link prediction problem for new links are substantially better than other temporal link prediction algorithms. We also find the item rankings generated by our approach match very well with that existed in the real world. Keywords-bipartite network; bipartite network projection; link prediction; PageRank; I