Multi-attribute based influence maximization in social networks: Algorithms and analysis

The most valuable feature of social networks is that they can generate contents for users and spread them quickly on the network, which is a very important platform for viral marketing. Most of the related work on viral marketing focuses on the spread of single information, while a product may associate with multiple attributes in real life. Information about multiple attributes of a product propagates in the social networks simultaneously and independently. The attribute information that a user receives will determine whether he would purchase the product or not. We extend the traditional single information influence maximization problem to the multi-attribute based influence maximization problem. We also present the Multi-dimensional IC model (MIC model) for the proposed problem, then formulate the problem as the Multi-attribute based Influence Maximization Problem (MIMP). The objective function for MIMP is proved to be non-submodular, then we solve the problem with two different algorithms: the Sandwich Algorithm and the Supermodular Algorithm, whose solutions can get a m a x { f ( S U ) f ‾ ( S U ), f _ ( S L ⁎ ) f ( S o ⁎ ) } ( 1 − 1 / e ) approximation ratio and an 1 / ( d + 2 ) approximation ratio to the optimal solution, respectively. Experiments based on the real world social network datasets verify the effectiveness and correctness of our proposed solutions.

Authors

• Qiufen Ni
• Jianxiong Guo
• Hongmin W. Du
• Huan Wang

Keywords

• Social network
• Influence maximization
• Multi-attribute