The effect of network characteristics on competitive performances of centrality-based heuristics in influence maximization

Abstract

Online social networks enable people to disseminate a variety of information to masses easily, but under the budget and time constraints. To overcome these constraints, many seed selection approaches have been proposed in the literature to start dissemination from a small subset of people containing the most influential set of users in the network, named as Influence Maximization (IM) problem. The studies in IM have been conducted under the assumption that there is only one type of information spreading over a network. However, in the real world, there are more than one opposing information spreading over networks and performances of approaches are also affected by the competition between them, which is named as Competitive Influence Maximization (CIM) problem. More recently, it has been revealed that performances of approaches are also affected by the network topology. This thesis aims to investigate the direct effects of the network characteristics on performances of seed selection approaches in CIM. In this regard, a simulation-based study is conducted on 13 real-world network datasets by using an extension of Linear Threshold Model. The effects of the five network characteristics (average clustering coefficient, average degree, normalized average path length, normalized degree variance and density) are investigated. Furthermore, performances of the four most commonly used centrality-based heuristics (Betweenness Centrality, Degree Centrality, Closeness Centrality and Eigenvector Centrality) are compared in terms of their noncompetitive and competitive performances. To interpret how the performances of the heuristics change in response to the network characteristics, regression tree method is used. According to our concrete findings, heuristics are sensitive to the existence of an opponent in the network and the type of the opponent as it is expected. Furthermore, the effects of the network characteristics differ from non-competitive to competitive environment. The findings emphasize the importance of an integrated perspective in the effects of network characteristics and Competitive Influence Maximization.