An approximate marginal spread computation approach for the budgeted influence maximization with delay

Abstract

Given a social network of users with selection cost and a fixed budget, the problem of Budgeted Influence Maximization finds a subset of the nodes (known as seed nodes) for initial activation to maximize the influence, such that the total selection cost is within the allocated budget. Existing solution methodologies for this problem make two assumptions, which are not applicable to real-life situations. First, an influenced node of the current time stamp can trigger only once in the next time stamp to its inactive neighbors and the other one is the diffusion process continues forever. To make the problem more practical, in this paper, we introduce the Budgeted Influence Maximization with Delay by relaxing the single time triggering constraint and imposing an additional constraint for maximum allowable diffusion time. For this purpose, we consider a delay distribution for each edge of the network, and consider a node is influenced, if it is so, within the allowable diffusion time. We first propose an incremental greedy strategy for solving this problem, which works based on the approximate computation of marginal gain in influence spread. Next, we make two subsequent improvements of this algorithm in terms of efficiency by exploiting the sub-modularity property of the time delayed influence function. We implement the proposed methodologies with three benchmark datasets. Reported results show that the seed set selected by the proposed methodologies can lead to more number of influenced nodes compared to that obtained by other baseline methods. We also observe that between the two improvised methodologies, the second one is more efficient for the larger datasets. © 2021, The Author(s), under exclusive licence to Springer-Verlag GmbH Austria, part of Springer Nature.