Information coverage maximization for multiple products in social networks

Abstract Different from most existing work which is focus on maximizing the influence of a single product in viral marketing, we study the k kinds of products information coverage maximization problem (k-PICMP). Since a company usually produces different products for different people and the active node set cannot completely represent the coverage of the products information propagation due to the neglect for informed users, our problem has its practical significance. The target of the k-PICMP is to choose M users to maximize the information coverage of k kinds of products. To give a high-quality solution for the proposed problem under the IC model, we formulate the k-PICMP as two different problems: k-PICMTP with total size constraint and k-PICMIP with individual size constraint. Then we prove that the objective function we want to solve is a k-submodular function, it aims at maximizing the value of the function by selecting k disjoint seed sets with cardinality constraint. Next, we present greedy algorithms under the total size constraint and individual size constraint to solve the k-PICMTP and k-PICMIP, respectively. Extensive experiments on three real-world datasets verify the performance of our proposed algorithms.