Poster
Motif-oriented influence maximization for viral marketing in large-scale social networks
Mingyang Zhou · Weiji Cao · Hao Liao · Rui Mao
[
Abstract
]
Abstract:
The \emph{influence maximization (IM)} problem aims to identify a budget set of nodes with the highest potential to influence the largest number of users in a given cascade model in the viral marketing. In the traditional \emph{IM}, each user/node is considered independently as a potential target customer. However, in many scenarios, the target customers are motifs, and activating only one (or a few) users within a motif is useless in viral marketing, which, nevertheless, receives little attention. For example, if a motif of three friends plan to dine together, it is essential that all three users are targeted simultaneously for the restaurant advertisement to be successful.In this paper, we investigate the motif-oriented influence maximization problem under the linear threshold model. We demonstrate that the motif-oriented IM problem is NP-hard and the influence function exhibits neither supermodular nor submodular properties, in contrast to the submodular property in the classical \emph{IM} setting.To simplify the problem, we establish the submodular upper and lower bounds for the influence function. Leveraging the submodular property, we propose a natural greedy strategy that could maximize the upper and lower bounds simultaneously. Our algorithm has an approximation ratio of $\tau\cdot (1-1/e-\varepsilon)$ and a near-linear time complexity of $O((k+l)(m+\eta)\log \eta/\varepsilon^2)$.We conduct experiments on diverse datasets to validate the effectiveness of our proposed algorithms in terms of motif maximization.
Live content is unavailable. Log in and register to view live content