Effectiveness of the K-core Nodes as Seeds for Influence Maximisation in Dynamic Cascades

Abstract: Influence maximisation is the problem of finding a small subset of nodes in a social network, known as seed nodes, which could maximise the spread of influence. Identifying seed nodes is of interest for marketing and information dissemination purposes. One of the algorithms used to rank a single node’s influence in the spreading process is the k-core decomposition. Most of the work done in this area had two main limitations: 1) worked with a static graph representation of the social network, and 2) did not tackle the possibility of the k-core being formed as a consequence of the domination of other sources such as the mass media or electronic militias and hence the limited contribution of the k-core in the influence dissemination. In this paper, we investigate the evolution of the k-core influence in dynamic meme cascades and scrutinize the effectiveness of using the k-core nodes for the influence maximisation. We propose a measure to estimate the ability of the k-core to disseminate its influence in dynamic cascades, and another to measure the relative strength of the k-core as an influence source among other sources of influence contributing to the cascade development. Finally, we propose combining the two measures to determine the influence domination of the k-core nodes, and hence the effectiveness of targeting these specific nodes for influence maximization. Using four real-life Twitter datasets, we evaluate the proposed measures. Due to the lack of ground truth about the various influence sources affecting the cascade, we examine the datasets for the existence of spam accounts where spam and electronic militias are one potential type of influence sources. We demonstrate how the spam existence indeed affects the correlation between the inner-most k-core size and the cascade size, and in effect, distorts the traditional evaluation of the k-core nodes as influence maximisers.