Call for Paper - July 2018 Edition
IJCA solicits original research papers for the July 2018 Edition. Last date of manuscript submission is June 20, 2018. Read More

Influence Maximization in Social Networks using Learning Automata

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2015
Authors:
Afshin Mohammadi, Keyhan Khamforoosh
10.5120/ijca2015906898

Afshin Mohammadi and Keyhan Khamforoosh. Article: Influence Maximization in Social Networks using Learning Automata. International Journal of Computer Applications 129(8):4-10, November 2015. Published by Foundation of Computer Science (FCS), NY, USA. BibTeX

@article{key:article,
	author = {Afshin Mohammadi and Keyhan Khamforoosh},
	title = {Article: Influence Maximization in Social Networks using Learning Automata},
	journal = {International Journal of Computer Applications},
	year = {2015},
	volume = {129},
	number = {8},
	pages = {4-10},
	month = {November},
	note = {Published by Foundation of Computer Science (FCS), NY, USA}
}

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

  1. Rashotte,L.,Socialinfluence.Theblackwellencyclopediaofsocial psychology, 2007. 9: p. 562-563.
  2. 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.
  3. 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.
  4. Saha, B. and S. Navlakha, Survey on Information Diffusion. 2008.
  5. Guille, A., et al., Information diffusion in online social networks: A survey. ACM SIGMOD Record, 2013. 42(1): p. 17-28.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. Cheng, S., et al., StaticGreedy: solving the scalability-accuracy dilemma in influence maximization. proceedings of CIKM2013, 2012.
  12. Capone, L., N. Di Mauro, and F. Esposito, Optimizing a static greedy algorithm for influence maximization. 2013.
  13. 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.
  14. Jung, K., W. Chen, and W. Heo, IRIE: A scalable influence maximization algorithm for independent cascade model and its extensions. 2011.
  15. Yang, W.-S. and S.-X. Weng, Application of the Ant Colony Optimization Algorithm to the Influence-Maximization Problem. 2012.
  16. Narendra, K.S. and M. Thathachar, Learning automata-a survey. Systems, Man and Cybernetics, IEEE Transactions on, 1974(4): p. 323-334.
  17. Mousavian, A., A. Rezvanian, and M.R. Meybodi, Solving Minimum Vertex Cover Problem Using Learning Automata. arXiv preprint arXiv:1311.7215, 2013.
  18. Soleimani-Pouri, M., A. Rezvanian, and M.R. Meybodi. Solving maximum clique problem in stochastic graphs using learning automata. in CASoN. 2012.

Keywords

Social networks, Influence maximization,Propagation models,Learning automata