2017/11/29 by Kai Han, Yuntian He, Han, Kai +9
Computer Science · Mathematics · #Algorithm #Approximation algorithm #Complexity and Algorithms in Graphs #Computer science #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Logarithm #Machine learning #Mathematical optimization #Mathematics #Mobile Crowdsensing and Crowdsourcing #Optimization and Search Problems #Running time #Scale (ratio) #Selection (genetic algorithm) #Set (abstract data type) #Social and Information Networks (cs.SI) #Social media #Social network (sociolinguistics) #Time complexity #cs.DS #cs.SI
paper · pdf · doi:10.48550/arxiv.1711.10665
submitted
openalex publication_date 2017/11/29 · arxiv created 2017/12/20 · arxiv updated 2017/12/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.