Title: Cost-Effective Seed Selection in Online Social Networks,
Abstract: We study the min-cost seed selection problem in online social networks, where
the goal is to select a set of seed nodes with the minimum total cost such that
the expected number of influenced nodes in the network exceeds a predefined
threshold. We propose several algorithms that outperform the previous studies
both on the theoretical approximation ratios and on the experimental
performance. Under the case where the nodes have heterogeneous costs, our
algorithms are the first bi- criteria approximation algorithms with polynomial
running time and provable logarithmic performance bounds using a general
contagion model. Under the case where the users have uniform costs, our
algorithms achieve logarithmic approximation ratio and provable time complexity
which is smaller than that of existing algorithms in orders of magnitude. We
conduct extensive experiments using real social networks. The experimental
results show that, our algorithms significantly outperform the existing
algorithms both on the total cost and on the running time, and also scale well
to billion-scale networks.