یک الگوریتم چندهدفه برای شناسایی گره‌های پرنفوذ در شبکه‌های اجتماعی

نوع مقاله : علمی-پژوهشی

نویسندگان

دانشکده مهندسی- گروه مهندسی کامپیوتر- دانشگاه کردستان

چکیده

با گسترش شبکه‌های اجتماعی، روابط بین افراد شکل تازه‌ای به خود گرفته است. یکی از مسائل مطرح در شبکه‌های اجتماعی، مسئله نفوذ اجتماعی است. پژوهش‌های انجام‌شده در مورد نفوذ اجتماعی و چگونگی انتشار اطلاعات در شبکه‌های اجتماعی، بیان‌گر این است که پذیرش یا رد یک الگوی جدید توسط یک فرد، به پذیرش یا رد دوستان آن فرد بستگی دارد. زیرا افراد به دوستان خود بیشتر از تبلیغات سایر منابع اعتماد دارند. درنتیجه، بسیاری از شرکت‌ها به سمت این روش که بازاریابی ویروسی نامیده می‌شود، متمایل شده‌اند. باوجود تعداد بسیار زیاد کاربران شبکه‌های اجتماعی، انتخاب ارزشمندترین کاربران به‌عنوان کاربران هدف که بتوان از طریق آن‌ها به بیش‌ترین میزان گسترش در شبکه با کم‌ترین هزینه دست‌یافت، از اهمیت زیادی برخوردار است. در این مقاله، یک روش جدید برای شناسایی گره‌های پرنفوذ در شبکه‌های اجتماعی به نام الگوریتم چندهدفه مبتنی بر اطلاعات ساختاری (MOSI) شده است. عملکرد روش پیشنهادی بر مبنای دو هدف «بیشینه‌سازی سود» و «کمینه‌سازی شباهت میان کاربران انتخابی» است. ارزیابی بر روی مجموعه داده‌های واقعی، نشان می‌دهد که روش پیشنهادی دارای قدرت گسترش بیشتری در مقایسه با روش‌های دیگر است.

کلیدواژه‌ها

عنوان مقاله [English]

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

نویسندگان [English]

  • Ch. Salavati
  • A. Abdollahpouri
  • Zh. Manbari
Department of Computer Engineering, University of Kurdistan, Sanandaj, Iran
چکیده [English]

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.

کلیدواژه‌ها [English]

  • Social networks
  • influential nodes
  • multi-objective optimization
  • Pareto front
  • genetic algorithm
  • SIR model

مراجع

[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.

فایل ها

هم رسانی

ارجاع به این مقاله

آمار