Open Collections

Banerjee, Prithu

University of British Columbia

Motivated by applications such as viral marketing, the problem of influence maximization (IM) has been extensively studied in the literature. The goal is to select a small number of users to adopt an item such that it results in a large cascade of adoptions by others. Existing works have three key limitations. (1) They do not account for the economic considerations of a user in buying/adopting items. (2) They cannot model the complex interactions between multiple items. (3) For the network owner, maximizing social welfare is important to ensure customer loyalty, which is not addressed in prior work in the IM literature. In this work, we address all three limitations and propose a novel model called Utility driven Independent Cascade (UIC) that combines utility-driven item adoption with influence propagation over networks. We focus on several types of items such as mutually complementary only, competing only, and a mix of the two in the context of the filter bubble problem. We formulate the problem of social welfare maximization under each of these settings. We show that while the objective function is neither submodular nor supermodular, a constant or instance-dependent approximation can still be achieved. With comprehensive experiments on real and synthetic datasets, we demonstrate that our algorithms significantly outperform all baselines on large real social networks.

Text

2022-04-06

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/81107

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/