Influence Maximization in Multi-Relational Social Networks

Influence maximization (IM) is a classic problem, which aims to find a set of k users (called seed set) in a social network such that the expected number of users influenced by the seed users is maximized. Existing IM algorithms mainly focus on one-by-one influence diffusion among users with friendships. However, in addition to 1-to-1 friendships, 1-to-N group relations usually exist in real social platforms, which are seldom fully exploited by conventional methods. In this paper, with the real-world datasets in WeChat, the largest online social platform in China, we first study the IM problem in multi-relational social networks consisting of friendships and group relations, and propose a novel Generate&Extend framework to find influential seed users for product promotion. Specifically, to achieve a trade-off between effectiveness and efficiency, we present a truncated meta-seed generator to select a small number of users, which are influential with consideration of both friendships and group relations. More importantly, a structural seed extender is put forward to extend the meta-seed set, so as to encode the differentiated propagation structures between friendships and group relations. Extensive online/offline experiments on three real-world datasets demonstrate that Generate&Extend significantly outperforms the state of the arts. Our Generate&Extend has been deployed at WeChat for mini-program promoting, and severing more than 200 million users.