Positive influence maximization and negative influence minimization in signed networks under competitive independent cascade model

Cheng En Sung, Hao Shang Ma, Jen Wei Huang

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

Abstract

Influence maximization refers to the process of identifying a predefined number of nodes within a given social network with the aim of maximizing the spread of influence. Most previous work has focused on unsigned networks, which means the existence of polarity relationships has largely been disregarded. In this work, we define a Sign-aware Influence Maximization (SIM) problem, which involves identification of the seed set that would simultaneously maximize positive influence and minimize negative influence. We begin by considered competitive influence under various dominance mechanisms on SCIC model, which extends the classic Independent Cascade (IC) model by incorporating binary opinions and signed relationships. We then proved that the influence of SIM under the SCIC model is non-monotonic and non-submodular, which implies that simple greedy hill-climbing would be unable to achieve an approximation ratio of 1-1/e in seeking to resolve the SIM problem. We then developed a simulation-based algorithm called Sign-aware Competitive Maximum Influence Arborescence (S-CMIA) to simulate the propagation of influence within a local region. Experiment results demonstrate the superiority of the proposed algorithm over existing methods in resolving the SIM problem in terms of reward.

Original languageEnglish
Title of host publicationProceedings - 2020 IEEE 7th International Conference on Data Science and Advanced Analytics, DSAA 2020
EditorsGeoff Webb, Zhongfei Zhang, Vincent S. Tseng, Graham Williams, Michalis Vlachos, Longbing Cao
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages236-244
Number of pages9
ISBN (Electronic)9781728182063
DOIs
Publication statusPublished - 2020 Oct
Event7th IEEE International Conference on Data Science and Advanced Analytics, DSAA 2020 - Virtual, Sydney, Australia
Duration: 2020 Oct 62020 Oct 9

Publication series

NameProceedings - 2020 IEEE 7th International Conference on Data Science and Advanced Analytics, DSAA 2020

Conference

Conference7th IEEE International Conference on Data Science and Advanced Analytics, DSAA 2020
CountryAustralia
CityVirtual, Sydney
Period20-10-0620-10-09

All Science Journal Classification (ASJC) codes

  • Computer Vision and Pattern Recognition
  • Decision Sciences (miscellaneous)
  • Statistics, Probability and Uncertainty
  • Analysis
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Positive influence maximization and negative influence minimization in signed networks under competitive independent cascade model'. Together they form a unique fingerprint.

Cite this