The temporal aspects of the evidence-based influence maximization on social networks^†

^†This research was conducted in part at the Department of Computer Science and Information Systems, University of Jyvaskyla, P.O. Box 35, Jyvaskyla, FI-40014, Finland.

Abstract

The influence maximization problem selects a set of seeds to initiate an optimal cascade of decisions. This paper uses parallel cascade evidence-based diffusion modelling, which views influence as a consequence of the evidence exchange between the connected actors, to investigate the temporal aspects of the social cascade propagation and effective time horizon for long-term campaign planning. Mixed-integer programming is used to explore the optimal timing of evidence injection and the ensuing network behaviour. The paper defines the notion of mid-term and long-term cascade stability and analyses the dynamics of social cascades for varied evidence discount factor values. This exploration reveals that the time horizon setting affects the optimal placement of seeds in a given problem and, hence, has to be set in a way to reflect the decision-maker's short-term or long-term goals. A Cplex-based heuristic algorithm is developed to iteratively find such a preferable cascade stability time horizon. Moreover, a conducted fractional factorial experiment reveals that the forgetfulness effect and the presence of competition significantly affect the cascade persistence. Somewhat counter-intuitively, it is discovered that a strong positive evidence can become more persistent (long-lasting) in the presence of weak opposing evidence.

Keywords:

• influence maximization
• social networks
• time horizon
• stable cascade
• seed selection
• optimization

AMS Subject Classification:

• 91D30
• 90C11
• 97M70

Acknowledgments

The authors acknowledge the anonymous referees whose remarks improved the quality of this paper significantly. The authors also acknowledge the funding agencies for the support.

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCiD

Mohammadreza Samadi  http://orcid.org/0000-0002-2997-5552

Notes

^† This research was conducted in part at the Department of Computer Science and Information Systems, University of Jyvaskyla, P.O. Box 35, Jyvaskyla, FI-40014, Finland.

1. An interested reader may refer to Samadi et al. [30] for a comprehensive discussion of using Bayesian hypothesis for IM modelling and mathematical programming for solving the resulting problem instances.

2. Throughout this paper, whenever α (β) is used, it refers to the equal value of and ( and ).

Additional information

Funding

While contributing to this work, the second author was supported in part by the Academy of Finland [grant number 268078] (MineSocMed), and in part by the 2015 U.S. Air Force Summer Faculty Fellowship Program, sponsored by the Air Force Office of Scientific Research. This support is gratefully acknowledged.