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.
