A pool-based simulated annealing approach for preference-aware influence maximisation in social networks

The influence maximisation problem is a crucial problem for various social network applications. For example, in viral marketing, cascade adoptions are triggered by selecting a small set of users to share their product experiences. Recent studies integrate user information to measure influence spread, which is suitable for practical applications. However, these studies primarily investigate information in a simplified form, such as user tags that can be translated into semantic functions. In this paper, we incorporate complex user information, especially user preferences expressed as linear orderings over a set of similar products. We introduce a preference-aware influence maximisation (PAIM) problem and propose an Independent Cascade Ranking model for the diffusion of linear orderings. Building on this model, we integrate user preferences by measuring the influence spread as scores derived from these linear orderings using voting rules. To address the PAIM problem, we propose a meta-heuristic approach with greedy search (PMHG), a modification of simulated annealing with fewer parameters. The PMHG builds a candidate pool based on users’ degrees, estimates the influence spread by restricting influence within a local area, and accepts good neighbour solutions with a greedy search strategy. We evaluate PMHG's performance across four real social networks and compare the results against six benchmarks. Experimental results show that PMHG outperforms baseline approaches in balancing solution quality and running time, particularly in large networks.