Back to Top

■ Influence Maximization in a Many Cascades World

Influence Maximization in a Many Cascades World, Iouliana Litou, Vana Kalogeraki, Dimitrios Gunopulos, IEEE ICDCS, Atlanta, GA, USA, June 5 - 8, 2017
Online Social Networks (OSNs) are widely utilized in viral marketing campaigns exploiting the word-of-mouth effect. Various propagation models have been proposed to describe the way cascades unfold in OSNs. Based on the existing propagation models, several studies address the problem of influence maximization, where the objective is to identify an appropriate subset of users to initiate the spread of a contagion. However, existing approaches ignore an important factor in the propagation process, i.e., the correlation of multiple contagions simultaneously cascading in the social network and how these affect the users' decisions regarding the adoption of a contagion. Although recent works look into either the competition or the complementarity among a pair of contagions, a uniform model that describes the propagation of multiple cascades with varying types and degrees of correlations is lacking. This work constitutes the first attempt to fill this gap. We formulate a novel propagation model, the Correlated Contagions Dynamic Linear Threshold (CCDLT), that considers the correlation of many contagions in either competitive or complementary manner. Our proposed model allows for different degrees of competition/complementarity among cascades. We further consider that users may dynamically switch states regarding the contagion they promote during the propagation process, based on the influence of their neighborhoods. We then design a greedy seed selection algorithm that identifies the appropriate subset of users to participate in a specific contagion in order to maximize its spread and we formally prove that it approximates the best solution at a ratio of 1 - 1/e. Through an extensive experimental evaluation we demonstrate the superiority of our approach over existing schemes.
Bibtex Entry.
  author    = {Iouliana Litou and
               Vana Kalogeraki and
               Dimitrios Gunopulos},
  title     = {Influence Maximization in a Many Cascades World},
  booktitle = {37th {IEEE} International Conference on Distributed Computing Systems,
               {ICDCS} 2017, Atlanta, GA, USA, June 5-8, 2017},
  pages     = {911--921},
  year      = {2017},
  crossref  = {DBLP:conf/icdcs/2017},
  url       = {},
  doi       = {10.1109/ICDCS.2017.163},
  timestamp = {Fri, 21 Jul 2017 13:46:43 +0200},
  biburl    = {},
  bibsource = {dblp computer science bibliography,}