New Influence-Aware Centrality Measures for Influence Maximization in Social Networks

Influence maximization in social networks is defined as determining a subset of seed nodes where triggering the influence diffusion through the social network leads to the maximum number of final influenced nodes. The tradeoff between the runtime efficiency and effectiveness in the quality of response is the main issue in presenting solutions for this NP-hard optimization problem. Centrality-based methods are applied as a category of efficient heuristic-based solutions to this problem. The two leading causes of losing effectiveness in centrality-based methods are ۱) only the link structure and non-awareness of influence diffusion are considered in determining the importance of nodes, and ۲) influence overlap exists among selected seed nodes. To address the first cause, an influence-aware betweenness centrality measure is proposed considering both IC and LT models. Moreover, an existing influence-aware closeness centrality measure for LT model is adopted to cover both LT and IC models. To address the second cause, a greedy-based method is proposed by applying influence-aware centrality measures to identify the influential nodes, next to proposing a Jacquard-based measure to overcome the influence overlap problem. The experiments consist of two parts where two real-world datasets are applied: ۱) the proposed influence-aware centrality measures are compared with their original versions, and ۲) the greedy-based method is compared with benchmark methods. The results indicate the effectiveness of the influence-aware centrality measures and the proposed greedy-based method in maximizing the influence spread in social networks.