The week's pick
Reseach Article
Influence Maximization in Social Networks using Learning Automata
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 129 - Number 8 |
| Year of Publication: 2015 |
| Authors: Afshin Mohammadi, Keyhan Khamforoosh |
10.5120/ijca2015906898
|
Afshin Mohammadi, Keyhan Khamforoosh . Influence Maximization in Social Networks using Learning Automata. International Journal of Computer Applications. 129, 8 ( November 2015), 4-10. DOI=10.5120/ijca2015906898
Abstract
Influence maximization problem is one of the challenges in online social networks. This problem refers to finding a small set of members of a social network, by activation of whichinformation propagation can be maximized using one of the propagation models such as independent cascade model. For the maximization problem, the greedy algorithm has beenpresented which isclose to optimal response by 67% in terms of accuracy; but, the problem of this method is its inefficiency in the social networks with a large number of members. The performed works on the improvement of the greedy algorithm have been mostly faced with the problem of scalability, dependence on graph structure, or need for large memory. In this paper, a method was presented using automata learning which could preserve its efficiency in large social networks and obtainresults with near-optimal values. For this purpose, space of the problem was reduced by removing low-degree nodes and the effective nodes for starting propagation in social network was found by automata learning which is optimal for achieving global optimization. The obtained results of this paper showed that the proposed method was efficient in large social networks and its results wereclose to the ones obtained by the greedy algorithm in terms of accuracy.
References
- Rashotte,L.,Socialinfluence.Theblackwellencyclopediaofsocial psychology, 2007. 9: p. 562-563.
- Chen, W., Y. Yuan, and L. Zhang. Scalable influence maximization in social networks under the linear threshold model. in Data Mining (ICDM), 2010 IEEE 10th International Conference on. 2010. IEEE.
- Kempe, D., J. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social network. in Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. 2003. ACM.
- Saha, B. and S. Navlakha, Survey on Information Diffusion. 2008.
- Guille, A., et al., Information diffusion in online social networks: A survey. ACM SIGMOD Record, 2013. 42(1): p. 17-28.
- Gui-sheng, Y., W. Ji-jie, and L. Jia. Intelligent Viral Marketing algorithm over online social network. in Networking and Distributed Computing (ICNDC), 2011 Second International Conference on. 2011. IEEE.
- Domingos, P. and M. Richardson. Mining the network value of customers. in Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. 2001. ACM.
- Wang, C., W. Chen, and Y. Wang, Scalable influence maximization for independent cascade model in large-scale social networks. Data Mining and Knowledge Discovery, 2012. 25(3): p. 545-576.
- Leskovec, J., et al. Cost-effective outbreak detection in networks. in Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. 2007. ACM.
- Goyal, A., W. Lu, and L.V. Lakshmanan. Celf++: optimizing the greedy algorithm for influence maximization in social networks. in Proceedings of the 20th international conference companion on World wide web. 2011. ACM.
- Cheng, S., et al., StaticGreedy: solving the scalability-accuracy dilemma in influence maximization. proceedings of CIKM2013, 2012.
- Capone, L., N. Di Mauro, and F. Esposito, Optimizing a static greedy algorithm for influence maximization. 2013.
- Chen, W., Y. Wang, and S. Yang. Efficient influence maximization in social networks. in Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. 2009. ACM.
- Jung, K., W. Chen, and W. Heo, IRIE: A scalable influence maximization algorithm for independent cascade model and its extensions. 2011.
- Yang, W.-S. and S.-X. Weng, Application of the Ant Colony Optimization Algorithm to the Influence-Maximization Problem. 2012.
- Narendra, K.S. and M. Thathachar, Learning automata-a survey. Systems, Man and Cybernetics, IEEE Transactions on, 1974(4): p. 323-334.
- Mousavian, A., A. Rezvanian, and M.R. Meybodi, Solving Minimum Vertex Cover Problem Using Learning Automata. arXiv preprint arXiv:1311.7215, 2013.
- Soleimani-Pouri, M., A. Rezvanian, and M.R. Meybodi. Solving maximum clique problem in stochastic graphs using learning automata. in CASoN. 2012.
Index Terms
Keywords