Effectiveness of Centrality Measures for Competitive Influence Diffusion in Social Networks

This paper investigates the effectiveness of centrality measures for the influence maximization problem in competitive social networks (SNs). We consider a framework, which we call “I-Game” (Influence Game), to conceptualize the adoption of competing products as a strategic game. Firms, as players, aim to maximize the adoption of their products, considering the possible rational choice of their competitors under a competitive diffusion model. They independently and simultaneously select their seeds (initial adopters) using an algorithm from a finite strategy space of algorithms. Since strategies may agree to select similar seeds, it is necessary to include an initial seed tie-breaking rule into the game model of the I-Game. We perform an empirical study in a two-player game under the competitive independent cascade model with three different seed-tie-breaking rules using four real-world SNs. The objective is to compare the performance of centrality-based strategies with some state-of-the-art algorithms used in the non-competitive influence maximization problem. The experimental results show that Nash equilibria vary according to the SN, seed-tie-breaking rules, and budgets. Moreover, they reveal that classical centrality measures outperform the most effective propagation-based algorithms in a competitive diffusion setting in three graphs. We attempt to explain these results by introducing a novel metric, the Early Influence Diffusion (EID) index, which measures the early influence diffusion of a strategy in a non-competitive setting. The EID index may be considered a valuable metric for predicting the effectiveness of a strategy in a competitive influence diffusion setting.