Influence Maximization in Messenger-based Social Networks

Many online social networks have provided a messenger app (e.g., facebook messenger, direct message on Twitter) to facilitate communication between strong-tied friends. Meanwhile, some messenger apps (WeChat) also start to offer social-networking services ("WeChat Moments" (WM), a.k.a. friend circle(1)) that allow users to post pictures, texts, links of webpages, on their walls, which is called the messenger-based social network (Msg-SN). In online social networks, Key Opinion Leaders (KOLs) with millions of followers are easy to identify for helping viral marketing/advertising. However, most users of a messenger app have a small number of friends (e.g., hundreds of friends), which makes it challenging to detect a KOL in Msg-SN by only counting the number of his/her friends. In this paper, we study the influence maximization problem in the Msg-SN of finding the set of most influential KOL nodes that maximize the spread of information. We develop a novel efficient heuristic algorithm that calculates the influence by looking at the user's local contribution to the information diffusion process, which scales to large datasets with provable near-optimal performance. Experiment results using the real-world WeChat Moments data (on January 14th, 2016, 100 thousand users) show that our algorithms can identify the set of KOL nodes with a low time complexity.National Natural Science Foundation of China (NSFC) [61572051]CPCI-S(ISTP