document: Efficient influence maximization in social networks Influence maximization is the problem of finding a small subset of nodes ( seed nodes ) in a social network that could maximize the spread of influence . In this paper , we study the efficient influence maximization from two complementary directions . One is to improve the original greedy algorithm of ( 5 ) and its improvement ( 7 ) to further reduce its running time , and the second is to propose new degree discount heuristics that improves influence spread . We evaluate our algorithms by experiments on two large academic collaboration graphs obtained from the online archival database arXiv.org . Our experimental results show that ( a ) our improved greedy algorithm achieves better running time comparing with the improvement of ( 7 ) with matching influence spread , ( b ) our degree discount heuristics achieve much better influence spread than classic degree and centrality-based heuristics , and when tuned for a specific influence cascade model , it achieves almost matching influence thread with the greedy algorithm , and more importantly ( c ) the degree discount heuristics run only in milliseconds while even the improved greedy algorithms run in hours in our experiment graphs with a few tens of thousands of nodes . Based on our results , we believe that fine-tuned heuristics may provide truly scalable solutions to the influence maximization problem with satisfying influence spread and blazingly fast running time . Therefore , contrary to what implied by the conclusion of ( 5 ) that traditional heuristics are outperformed by the greedy approximation algorithm , our results shed new lights on the research of heuristic algorithms .
doc_bio_tags: O B I O B I B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O