Time stamp based set covering greedy algorithm

Abstract

Influence maximization deals with finding a small set of target nodes that can be initially activated, such that the influence spread beginning with this causes maximum number of expected activated nodes in the network. Most of the existing algorithms for choosing the seed set concentrate only on the structural properties of the network. We would like to emphasize that it is equally important that a user should be actively involved with his neighbours in order to successfully influence them. Hence a novel measure termed as 'Activeness' of a user which is based on timestamp of the user's recent communication with his neighbours is considered. On the same lines, we propose time stamp based set covering greedy (TSCG) algorithm for seed set selection and a Time stamp based threshold model to map the information diffusion in the network. As a part of our experiments, we compare and analyse the results with degree centrality measure and set covering greedy(SCG) algorithm and cite that the spread achieved by our proposed algorithm though lesser in some cases, is more accurate. Copyright 2015 ACM.