Efficient Network Seeding under Variable Node Cost and Limited Budget for Social Networks

The efficiency of information diffusion on networks highly depends on both the network structure and the set of early spreaders. Moreover, in various realistic scenarios, to seed different nodes implies different costs, as in the case of viral marketing, where costs often correlate with local network structure. The budgeted influence maximization (BIM) problem consists in determining a seed set whose diffusion maximizes the total number of influenced nodes, provided that the seeding cost is within a given budget. We investigate efficient seeding strategies for the BIM problem under the deterministic fixed threshold diffusion model. In particular, we introduce the concept of surrounding sets: relatively cheap seeds neighboring expensive, structurally-privileged nodes, which then become spreaders at lower costs. Numerical experiments with several real networks indicate our method outperforms strategies that seed nodes based on their influence/cost ratios. A key insight from our evaluation is that larger diffusion is generally attained from the surrounding sets that consider the two-hop neighborhood of influential nodes, as opposed to their immediate neighbors only.