Generalized Self-profit Maximization in Attribute Networks

Profit maximization, an extension of classical Influence Maximization, asks for a small set of early adopters to maximize the expected total profit generated by all the adopters. This is a meaningful optimization problem in social network which has attracted many researchers' attention. Nevertheless, most of the related works are based on pure networks and one-entity diffusion model without considering the relationship of different promotional products and the influence of both emotion tendency and interest classification (label) in real marketing process. In this paper, we propose a novel nonsubmodular optimization problem, Generalized Self-profit Maximization in Attribute networks (GSMA), which is based on a community structure in attribute networks and captures the unilateral complementary relationship, a setting with complementary entities. To solve GSMA, the R-GSMA algorithm which is inspired by sampling method and martingale analysis is designed. We evaluate our proposed algorithm by conducting experiments on randomly generated and real datasets and show that R-GSMA is superior in effectiveness and accuracy comparing with other baseline algorithms.