Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

5-2017

Abstract

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.

Keywords

Social networking, influence spread

Discipline

Databases and Information Systems | Digital Communications and Networking | Social Media

Research Areas

Data Science and Engineering

Publication

SIGMOD '17: Proceedings of the 2017 ACM International Conference on Management of Data, Chicago, IL, May 14-19

First Page

619

Last Page

634

ISBN

9781450341974

Identifier

10.1145/3035918.3035952

Publisher

ACM

City or Country

New York

Additional URL

https://doi.org/10.1145/3035918.3035952

Download

Share

COinS