Efficient heuristic algorithms for influence propagation in social networks. (c2018)

Abstract

The study of how fast advertisements and ideas propagate across a social network started to gain notable attention recently. In this context, the notion of an influencer has been considered: an influencer is an individual capable of affecting the behavior, character and/or social opinion of others. Our objective in this work is to find a set of individuals that can collectively serve as influencers. We model the problem using the previously studied notion of a positive influence dominating set. The problem seeks a smallest set of positive-influencers assuming that an individual becomes positively influenced when the majority of his/her friends are influenced. We start by presenting and studying efficient heuristic algorithms for this problem and show how different types of social networks require different heuristic methods. Then we introduce the notion of an influence propagation function and use it to design an efficient algorithm across all types of networks. Finally, we introduce a new model that allows the maximization of influence propagation while selecting a much smaller set of influencers. Our experiments on a variety of social (sub) networks show that our algorithms can almost always manage to extract a small set of influencers through which we can effectively propagate a message throughout the whole network.