Influence maximization aims to find a set of persons in a social network that can be used as seeds for a viral marketing campaign, such that the expected spread of influence is maximized. Standard approaches to this problem produce a single seed set that either maximizes influence, or the "bang for the buck" if the vertices are associated with a cost. In this paper we consider the problem of finding the cost-influence skyline, i.e., the collection of all seed sets that are Pareto optimal w.r.t. seeding cost and expected influence. Computing the cost-influence skyline has a number of advantages over finding a single solution only. First, it provides a better understanding of the trade-off between cost and influence, which enables the user to make an informed choice regarding the budget. Second, by computing the costinfluence skyline we obtain the optimal seed set for any given seeding budget, not only the one that corresponds to singleton solutions found by existing algorithms. In practice, the problem is to discover the skyline w.r.t. two functions spanned by all subsets of size k of a set of vertices. Due to the extremely large number of such subsets, this is a very hard problem. We present an efficient heuristic algorithm for computing the skyline when one of the functions is linear (e.g., the seeding cost) and the other submodular (e.g., expected influence). The experiments show that the cost-influence skyline can be computed in reasonable time for networks with up to a million vertices.
展开▼
