Efficient Greedy Algorithms for Influence Maximization in Social Networks
1
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
Influence maximization is an important problem of finding a small subset ofnodes in a social network, such that by targeting this set, one will maximize theexpected spread of influence in the network. To improve the efficiency of algorithmKK_Greedy proposed by Kempe et al., we propose two improved algorithms,Lv_NewGreedy and Lv_CELF. By combining all of advantages of these two algorithms,we propose a mixed algorithm Lv_MixedGreedy. We conducted experiments on twosynthetically datasets and show that our improved algorithms have a matchinginfluence with their benchmark algorithms, while being faster than them.
Abstract
Influence maximization is an important problem of finding a small subset ofnodes in a social network, such that by targeting this set, one will maximize theexpected spread of influence in the network. To improve the efficiency of algorithmKK_Greedy proposed by Kempe et al., we propose two improved algorithms,Lv_NewGreedy and Lv_CELF. By combining all of advantages of these two algorithms,we propose a mixed algorithm Lv_MixedGreedy. We conducted experiments on twosynthetically datasets and show that our improved algorithms have a matchinginfluence with their benchmark algorithms, while being faster than them.
참고문헌 (14)
- P. Domingos, "Mining the network value of customers", Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp.57~66 (2001)
- M. Richardson, "Mining knowledge-sharing sites for viral marketing", Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp.61~70 (2002)
- D. Kempe, "Maximizing the spread of influence through a social network", Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp.137~146 (2003)
- B. Liu, "Time constrained influence maximization in social networks", Proceedings of the IEEE 12th International Conference on Data Mining, pp.439~448 (2012)
- W. Chen, "Scalable influence maximization for prevalent viral marketing in large-scale social networks", Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp.1029~1038 (2010)
- W. Chen, "Efficient influence maximization in social networks", Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp.199~208 (2009)
- W. Chen, "Scalable influence maximization in social networks under the linear threshold model", Proceedings of the IEEE 10th International Conference on Data Mining, pp.88~97 (2010)
- R. Narayanam, "A shapley value-based approach to discover influential nodes in social networks", IEEE Transactions on Automation Science and Engineering, 8(1), pp.130~147 (2011)
- J. Leskovec, "Cost-effective outbreak detection in networks", Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp.420~429 (2007)
- A. Goyal, "CELF++: optimizing the greedy algorithm for influence maximization in social networks", Proceedings of the 20th international conference companion on World wide web, pp.47~48 (2011)
- Y. Wang, "Community-based greedy algorithm for mining top-K influential nodes in mobile social networks", Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp.1039~1048 (2010)
- J. Lv, "A new community-based algorithm for influence maximization in social network", Journal of Computational Information Systems, 9(14), pp.5659~5666 (2013)
- R. Tarjan, "Depth-first search and linear graph algorithms", SIAM Journal on Computing, 1(2), pp.146~160 (1972)
- A. Lancichinetti, "Benchmark graphs for testing community detection algorithms", Physical Review E, 78(4), pp.046110~ (2008)