On optimal preference diffusion over social networks

Abstract

It was well observed that a user's preference over a product changes based on his/her friends’ preferences, and this phenomenon is called “preference diffusion”, and several models have been proposed for modeling the preference diffusion process. These models share an idea that the diffusion process involves many iterations, and in each iteration, each user has his/her preference affected by some other preferences (e.g., those of his/her friends). When computing users’ preferences after a certain number of iterations, these models use users’ preferences at the end of that iteration only, which we believe is not desirable since users’ preferences at the end of other iterations should also have some effects on users’ final preferences. Therefore, in this paper, we propose a new model for preference diffusion, which takes into consideration users’ preferences at each iteration for computing users’ final preferences. Under the new model, we study two problems for optimizing the preference diffusion process with respect to two different objectives. One is easy to solve for which we design an exact algorithm and the other is NP-hard for which we design a (1−1∕e)-factor approximate algorithm. We conducted extensive experiments on real datasets which verified our proposed model and algorithms.