Semantics-aware influence maximization in social networks

Yipeng Chen, Qiang Qu*, Yuanxiang Ying, Hongyan Li, Jialie Shen

*Corresponding author for this work

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

Influence Maximization (IM) plays an essential role in various social network applications. One such application is viral marketing to trigger a large cascade of product adoption from a small number of users by utilizing “Word-of-Mouth” effect in social networks. IM aims to return a set of users that can influence the largest fraction of a network, such as the early user who demonstrates the good features of a product in marketing. The traditional IM algorithms treat all users equally and ignore semantic context associated with the users, though it has been studied previously. To consider the semantics, we introduce a semantics-aware influence maximization (SIM) problem. The SIM problem integrates semantic information of users with influence maximization by measuring influence spread based on semantic values under a given model, and it aims to find a set of users that maximizes the influence spread, shown to be NP-hard. Generalized Reverse Influence Set based framework for SIM problems (GRIS-SIM) is used to solve SIM with different semantics, which provides a (1−1/e−ε)-approximation solution for each SIM instance. To our knowledge, the guarantee is state-of-the-art in the IM studies. GRIS-SIM enables auto-generation of sampling strategies for various social networks. In this study, we also present three sampling strategies that can be generated to achieve the best approximation guarantee, and one of the three is proved to be the optimal strategy by having the same performance guarantee within the optimal time. Furthermore, in order to show the generality and effectiveness of the proposed GRIS technique, we apply it into solving other IM problems (e.g., the distance-aware influence maximization, DAIM). Extensive experiments on both real-life and synthetic datasets demonstrate the effectiveness, efficiency, and scalability of our methods. The results on large real data show that GRIS-SIM is able to achieve 58% improvement on average in expected influence compared with rivals, and the method adopting GRIS can achieve 65% improvement on average.

Original languageEnglish
Pages (from-to)442-464
Number of pages23
JournalInformation Sciences
Volume513
Early online date09 Nov 2019
DOIs
Publication statusPublished - 01 Mar 2020

Keywords

  • Influence maximization
  • Influence measurement
  • Social network analysis
  • User semantics

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Semantics-aware influence maximization in social networks'. Together they form a unique fingerprint.

Cite this