Discovering your selling points: Personalized social influential tags exploration

• Main Authors: LI, Yuchen, TAN, Kian-Lee, FAN, Ju, ZHANG, Dongxiang
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2017
• Subjects: Social networking; influence spread; Databases and Information Systems; Digital Communications and Networking; Social Media
• Online Access: https://ink.library.smu.edu.sg/sis_research/4021; https://ink.library.smu.edu.sg/context/sis_research/article/5023/viewcontent/p619_li.pdf
• Institution: Singapore Management University

Social influence has attracted significant attention owing to the prevalence of social networks (SNs). In this paper, we study a new social influence problem, called personalized social influential tags exploration (PITEX), to help any user in the SN explore how she influences the network. Given a target user, it finds a size-k tag set that maximizes this user’s social influence. We prove the problem is NP-hard to be approximated within any constant ratio. To solve it, we introduce a sampling-based framework, which has an approximation ratio of 1−ǫ 1+ǫ with high probabilistic guarantee. To speedup the computation, we devise more efficient sampling techniques and propose best-effort exploration to quickly prune tag sets with small influence. To further enable instant exploration, we devise a novel index structure and develop effective pruning and materialization techniques. Experimental results on real large-scale datasets validate our theoretical findings and show high performances of our proposed methods.