Abstract
Influence maximization is a fundamental research problem in social networks. Viral marketing, one of its applications, aims to select a small set of users to adopt a product, so that the word-of-mouth effect can subsequently trigger a large cascade of further adoption in social networks. The problem of influence maximization is to select a set of K nodes from a social network so that the spread of influence is maximized over the network. Previous research on mining top-K influential nodes assumes that all of the selected K nodes can propagate the influence as expected. However, some of the selected nodes may not function well in practice, which leads to influence loss of top-K nodes. In this paper, we study an alternative influence maximization problem which is naturally motivated by the reliability constraint of nodes in social networks. We aim to find top-K influential nodes given a threshold of influence loss due to the failure of a subset of R(<K) nodes. To solve the new type of influence maximization problem, we propose an approach based on constrained simulated annealing and further improve its performance through efficiently estimating the influence loss. We provide experimental results over multiple real-world social networks in support. This research will further support practical applications of social networks in various domains particularly where reliability would be a main concern in a system deployment.
1. Introduction
Social networks provide an intuitive representation about individual connections and display interesting behavioral patterns across various populations of users (Wasserman & Faust, 1994). Social network analysis is attracting more and more attention from different research areas and becomes an important tool for developing intelligent systems in recommendation, crowdsourcing service and so on Domingos and Richardson (2001), Zafarani, Abbasi, and Liu (2014), Sun, Lin, and Xu (2015), Zeng et al. (2015).
6. Conclusions
The IMIL problem is motivated by practical thoughts on viral marketing. We aim to find top-K influential nodes given influence loss constraint in social networks. This problem is proved to be NP-hardness and existing methods fail to provide reasonably good solutions. To solve the problem, we developed a CSA based framework that optimizes top-K solutions while enforcing satisfaction of influence loss constraint. The development of CSA algorithms is not trivial in the new problem context as we need to investigate algorithmic convergence according to a particular domain based penalty function and practical parameter settings. We further proposed an enhanced version of the CSA algorithm that employs a new penalty function, and showed its significant improvement on the algorithmic efficiency.
