Generalized self-profit maximization and complementary-profit maximization in attribute networks

Profit Maximization problem is an extension of Influence Maximization problem and aims to find a small set of initial adopters to maximize the expected profit generated by all the adopters after information dissemination. To the best of our knowledge, almost all the related works about Profit Maximization focus on one-entity diffusion model. In addition, emotion tendency and interest classification also play a role in real marketing process while their importance are underestimated in a lot of research. In this paper, we propose two novel nonsubmodular optimization problems, Generalized Self-profit Maximization in Attribute networks (GSMA) and Generalized Complementary-profit Maximization in Attribute networks (GCMA). Based on attribute networks’ community structure, these two problems consider the influence of both emotion tendency and interest classification on information dissemination process. GSMA problem focuses on supplement relationship and aims to maximize the expected value of profit. Whereas GCMA problem concentrates on the dependency relationship between entities and its goal is boosting the expected value of profit generated by adopter for an entity by selecting some initial adopters for its complementing entities. To solve these two problems, the R-GPMA algorithm framework which is inspired by sampling method and martingale analysis is designed. We evaluate our proposed algorithm by conducting experiments on randomly generated and real data sets and show that R-GPMA is superior in effectiveness and accuracy comparing with other baseline algorithms.