A Multi-objective Algorithm for Identifying Influential Nodes in Social Networks

Document Type : Original Article

Authors

1 Department of Computer Engineering, University of Kurdistan, Sanandaj, Iran

2 Department of Computer Engineering, University of Kurdistan, Sanandaj, Iraد

Abstract

With the expansion of social networks, relationship between people has taken a new form. One of the important issues in social networks is social influence. Research on social influences and how information is disseminated in social networks, indicates that accepting or rejecting a new pattern by a person depends on the acceptance or rejection of the friends of that person. That is, because the people usually trust their friends more than other sources of advertising. As a result, many companies are focused on this type of advertisement which is called viral marketing. Given a large number of users in a social network, selecting the most influential users as target users, through which a company can reach the highest expansion in the network with the lowest cost, is of great importance. In this paper, a new method for identifying the influential nodes in social networks is proposed which is called MOSI (Multi-Objective algorithm based on Structured Information). The proposed method has two goals: "maximize profit" and "minimize similarity among selected users". The evaluation of the proposed method on real datasets indicates that our method has a greater expansion power in comparison with other similar methods.

Keywords

References

[1]     R. Narayanam and Y. Narahari, “A shapley value-based approach to discover influential nodes in social networks,” IEEE Transactions on Automation Science and Engineering, vol. 8, no. 1, pp. 130-147, 2011.
[2]     W. Chen, 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, pp. 199-208, 2009.
[3]     D. Easley and J. Kleinberg, Networks, crowds, and markets: Reasoning about a highly connected world. Cambridge University Press, 2010.
[4]     D. Easley and J. Kleinberg, “Networks, crowds, and markets: Reasoning about a highly connected world,” Significance, vol. 9, pp. 43-44, 2012.
[5]     C. Salavati, A. Abdollahpouri and Z. Manbari, “BridgeRank: A novel fast centrality measure based on local structure of the network”, Physica A: Statistical Mechanics and its Applications, 2017.
[6]     K. Xu, J. Li and Y. Song, “Identifying valuable customers on social networking sites for profit maximization,” Expert Systems with Applications, vol. 39, no. 17, pp. 13009-13018, 2012.
[7]     W. Chen, 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, pp. 88-97, 2010.
[8]     L. C. Freeman, “Centrality in social networks conceptual clarification,” Social networks, vol. 1, no. 3, pp. 215-239, 1978.
[9]     G. Sabidussi, “The centrality index of a graph,” Psychometrika, vol. 31, no. 4, pp. 581-603, 1966.
[10]  C. Dangalchev, “Residual closeness in networks,” Physica A: Statistical Mechanics and its Applications, vol. 365, no. 2, pp. 556-564, 2006.
[11]  P. Domingos and M. Richardson, “Mining the network value of customers,” in Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 57-66, 2001.
[12]  M. Richardson and P. Domingos, “Mining knowledge-sharing sites for viral marketing,” in Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 61-70, 2002.
[13]  C. M. Fonseca and P. J. Fleming, “Genetic Algorithms for Multiobjective Optimization: FormulationDiscussion and Generalization,” in ICGA, 1993, vol. 93, pp. 416-423: Citeseer.
[14]  N. Srinivas and K. Deb, “Muiltiobjective optimization using nondominated sorting in genetic algorithms,” Evolutionary computation, vol. 2, no. 3, pp. 221-248, 1994.
[15]  M. Richardson and P. Domingos, “Mining knowledge-sharing sites for viral marketing”, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 61-70, 2002
[16]  D. Kempe, J. Kleinberg and É. Tardos, “Influential nodes in a diffusion model for social networks”, International Colloquium on Automata, Languages, and Programming, pp. 1127-1138, 2005.
[17]  J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen and N. Glance, “Cost-effective outbreak detection in networks”, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 420-429, 2007.
[18]  A. Goyal, W. Lu and L.V. Lakshmanan, “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.
[19]  A. Goyal, W. Lu and L.V. Lakshmanan, “Simpath: An efficient algorithm for influence maximization under the linear threshold model”, Data Mining (ICDM), IEEE 11th International Conference on, pp. 211-220, 2011.
[20]  E. Cohen, D. Delling, T. Pajor and R.F. Werneck, “Sketch-based influence maximization and computation: Scaling up with guarantees”, Proceedings of the 23rd ACM International Conference on Information and Knowledge Management, pp. 629-638, 2014.
[21]  S. Cheng, H. Shen, J. Huang, W. Chen and X. Cheng, “IMRank: influence maximization via finding self-consistent ranking”, Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval, pp. 475-484, 2014.
[22]  C. Wang, L. Deng, G. Zhou and M. Jiang, “A global optimization algorithm for target set selection problems”, Information Sciences, pp. 101-118, 2014.
[23]  M. Heidari, M. Asadpour and H. Faili, “SMG: Fast scalable greedy algorithm for influence maximization in social networks”, Physica A: Statistical Mechanics and its Applications, pp. 124-133, 2015.
[24]  W.-S. Yang, S.-X. Weng, C. Guestrin, C. Faloutsos, J. VanBriesen and N. Glance, “Application of the ant colony optimization algorithm to the influence-maximization problem”, Int J Swarm Intell Evol Comput, pp. 1-8, 2012
[25]  N. Sinha and B. Annappa, “Cuckoo Search for Influence Maximization in Social Networks”, Proceedings of 3rd International Conference on Advanced Computing, Networking and Informatics, pp. 51-61, 2016.
[26]  Q. Jiang, G. Song, G. Cong, Y. Wang, W. Si and K. Xie, “Simulated Annealing Based Influence Maximization in Social Networks”, AAAI, pp. 127-132, 2011.
[27]  A. Mohammadi and M. Saraee, “Finding influential users for different time bounds in social networks using multi-objective optimization”, Swarm and evolutionary computation, pp. 158-165, 2018.
[28]  M. Kitsak, L.K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H.E. Stanley and H.A. Makse, “Identification of influential spreaders in complex networks”, vol. 6, pp. 888-893, 2010.
[29]  P. Bonacich and P. Lloyd, “Eigenvector-like measures of centrality for asymmetric relations,” Social networks, vol. 23, no. 3, pp. 191-201, 2001.
[30]  D. Chen, L. Lü, M.-S. Shang, Y.-C. Zhang and T. Zhou, “Identifying influential nodes in complex networks,” Physica a: Statistical mechanics and its applications, vol. 391, no. 4, pp. 1777-1787, 2012.
[31]  S. Gao, J. Ma, Z. Chen, G. Wang and C. Xing, “Ranking the spreading ability of nodes in complex networks based on local structure,” Physica A: Statistical Mechanics and its Applications, vol. 403, pp. 130-147, 2014.
[32]  محمدامیر عباسیان و حسین نظام‌آبادی‌پور، «الگوریتم جستجوی گرانشی چند هدفه مبتنی بر مرتب‌سازی جبهه‌های مغلوب نشده»، مجله مهندسی برق دانشگاه تبریز، دوره 41، شماره 1، صفحه 80-68، 1391
[33]  R. M. Anderson, R. M. May and B. Anderson, Infectious diseases of humans: dynamics and control. Wiley Online Library, vol. 28, 1992.
[34]  D. Jong and K. Alan, “Analysis of the behavior of a class of genetic adaptive systems, Engineering,” College of-Technical Reports, University of Michigan, 1975.
TABRIZ JOURNAL OF ELECTRICAL ENGINEERING
Volume 50, Issue 3 - Serial Number 93
November 2020
Pages 1293-1304

Files

Share

How to cite

Statistics