Cost-Aware Influence Maximization in Multi-Attribute Networks

The popularity of Online Social Networks (OSNs) led to numerous applications that harness the benefits of immediate information exchange among numerous users of the network. This property is particularly utilized by OSNs campaigns that exploit of the "word-of-mouth" effect exhibited in the network. The problem Influence Maximization (IM), i.e., identifying the appropriate subset of users to initiate the propagation of a specific campaign, is widely studied in the literature. Various models have been proposed to capture the way information propagates in the network, yet a unified model that considers the important parameters of (i) correlation among campaigns propagating in the network and (ii) the different attributes of the propagating entities coupled with the users distinct preferences in certain attributes, is lacking. Additionally, the majority of the works assume uniform costs and revenues among users. Finally, the IM problem is addressed solely offline, i.e., after the seed selection process no further action is defined. In this work we propose the Multi-Attribute Correlated Independent Cascade (MAC-IC) propagation model to tackle the aforementioned limitations of existing propagation models. Given the MAC-IC model we design a two-phase Greedy Offer Selection (GOES) algorithm to address the IM problem under variable costs and revenues generated by the users. During the offline phase, the seeds to initiate the propagation of a specific item are identified. In the online phase, the propagation is monitored, the blockers are detected and real-time incentives may be offered to convince them to participate in the campaign. We prove that the GOES offline phase achieves an approximation ratio of 1 − 1/e. Through an extensive experimental evaluation we demonstrate the efficiency of our approach compared to state-of-the-art schemes.