Predicting Higher Order Links in Social Interaction Networks

Link prediction is a significant research problem in network science and has widespread applications. To date, much efforts have focused on predicting the links generated by pairwise interactions, but little is known about the predictability of links created by higher order interaction patterns. In this study, we investigated a new framework for predicting the links of different orders in social interaction networks based on edge orbit degrees (EODs) characterized by three-node and four-node graphlets. First, we defined a new problem of different-order link prediction to examine the predictability of links generated by different-order interaction patterns. Second, we quantified EODs for different-order link prediction and examined the performance of different-order predictors. The experiments on real-world networks show that higher order links are more accessible to be predicted than lower order (two-order) links. We also found that the closed three-node EOD has strong predictive power, which can accurately predict for both lower order and higher order links. Finally, we proposed a new method fusing multiple EODs (MEOD) to predict different-order links, and experiments indicate that the MEOD outperforms state-of-the-art methods. Our findings can not only effectively improve the link prediction performance of different orders, but also contribute to a better understanding of the organizational principle of higher order structures.