Influence maximization with deactivation in social networks

Tanınmış K., ARAS M. N., ALTINEL İ. K.

European Journal of Operational Research, cilt.278, sa.1, ss.105-119, 2019 (SCI-Expanded, Scopus) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 278 Sayı: 1
  • Basım Tarihi: 2019
  • Doi Numarası: 10.1016/j.ejor.2019.04.010
  • Dergi Adı: European Journal of Operational Research
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.105-119
  • Anahtar Kelimeler: Bilevel modeling, Influence maximization, Matheuristics, Metaheuristics, Stochastic optimization
  • Boğaziçi Üniversitesi Adresli: Evet

Özet

In this paper, we consider an extension of the well-known Influence Maximization Problem in a social network which deals with finding a set of k nodes to initiate a diffusion process so that the total number of influenced nodes at the end of the process is maximized. The extension focuses on a competitive variant where two decision makers are involved. The first one, the leader, tries to maximize the total influence spread by selecting the most influential nodes and the second one, the follower, tries to minimize it by deactivating some of these nodes. The formulated bilevel model is solved by complete enumeration for small-sized instances and by a matheuristic for large-sized instances. In both cases, the lower level problem, which is a stochastic optimization problem, is approximated via the Sample Average Approximation method.