Effectiveness of Centrality Measures for Competitive Influence Diffusion in Social Networks - Fairouz Medjahed; Elisenda Molina; Juan Tejada (Mathematics)
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.