Non-submodularity and approximability: Influence maximization in online social networks

Huanyang Zheng, Ning Wang, Jie Wu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

Motivated by many Online Social Network (OSN)applications such as viral marketing, the Social Influence Maximization Problem (SIMP)has received tremendous attention. SIMP aims to select k initially-influenced seed users to maximize the number of eventually-influenced users. Under the independent cascade model, the SIMP has been proved to be NP-hard, monotone, and submodular. Therefore, a naive greedy algorithm that maximizes the marginal gain obtains an approximation ratio of 1-e-1. This paper extends the SIMP by considering the crowd influence which is combined group influence in additional to individual influence among a given crowd. Our problem is proved to be NP-hard and monotone, but not submodular. It is proved to be inapproximable within a ratio of V-1 for any in > 0. However, since user connections in OSNs are not random, approximations can be obtained by leveraging the structural properties of OSNs. We prove that the supmodular degree, denoted as Δ. of most OSNs has the following property V Δ O(V=0, i.e., Δo(V) for most OSNs. The supermodularity, denoted by is used to measure to what degree our problem violates the submodularity. Two approximation algorithms have been applied with ratios of 1 e+2 and 1-e-1(+1), respectively. Experiments demonstrate the efficiency and effectiveness of our algorithms.

Original languageEnglish (US)
Title of host publication20th IEEE International Symposium on A World of Wireless, Mobile and Multimedia Networks, WoWMoM 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781728102702
DOIs
StatePublished - Jun 2019
Event20th IEEE International Symposium on A World of Wireless, Mobile and Multimedia Networks, WoWMoM 2019 - Washington, United States
Duration: Jun 10 2019Jun 12 2019

Publication series

Name20th IEEE International Symposium on A World of Wireless, Mobile and Multimedia Networks, WoWMoM 2019

Conference

Conference20th IEEE International Symposium on A World of Wireless, Mobile and Multimedia Networks, WoWMoM 2019
Country/TerritoryUnited States
CityWashington
Period6/10/196/12/19

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Media Technology

Fingerprint

Dive into the research topics of 'Non-submodularity and approximability: Influence maximization in online social networks'. Together they form a unique fingerprint.

Cite this