Predictability of diffusion-based recommender systems

摘要

Numerous diffusion-based recommendation algorithms (DBA) have been extended to improve the performance of such methods further. However, it is still not clear to what extent recommendation accuracy can be improved if we continue to extend existing algorithms. In this paper, we propose an ideal method to quantify the possible maximum recommendation accuracy of DBA, which is regarded as predictability of algorithms. Accordingly, the ideal method is applied to the extensively analyzed datasets. The result illustrates that the accuracy of DBA can still be improved by optimizing the resource allocation matrix on a dense network. Nevertheless, improving accuracy on sparse networks is difficult, mainly because the current accuracy of DBA is very close to its predictability. We find that the predictability can be enhanced effectively by multi-step resource diffusion, especially for inactive users (with less historical data). In contrast to common belief, there are plausible circumstances where the higher predictability of DBA does not correspond to active users. Additionally, we demonstrate that the recommendation accuracy is overestimated in the real online systems by random partition used in the literature, suggesting the recommendation in the real online systems may be a tough task.