علوم رایانشی

علوم رایانشی

بهبود حداکثر‌سازی گسترش انتشار اطلاعات در شبکه‌های اجتماعی به کمک معیارهای شباهت کاربران

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

نویسندگان
زهرا سجده 1
علیرضا رضوانیان 2
1 گروه مهندسی کامپیوتر، دانشکده فنی و مهندسی، دانشگاه علم و فرهنگ، تهران، ایران
2 استادیار، گروه مهندسی کامپیوتر، دانشکده فنی و مهندسی، دانشگاه علم و فرهنگ، تهران، ایران
10.22034/csj.2024.209866
چکیده
در سال‌های اخیر، استفاده از شبکه‌های اجتماعی به طور گسترده‌ای افزایش یافته و این شبکه‌ها به بستری محبوب برای تبلیغ محصولات و انتشار اطلاعات تبدیل شده‌اند. مسئله حداکثرسازی گسترش انتشار اطلاعات، که یکی از مسائل الگوریتمی کلیدی در زمینه انتشار اطلاعات است، به موضوعی داغ در تحلیل شبکه‌های اجتماعی مبدل شده است. حداکثرسازی گسترش انتشار اطلاعات در یک شبکه اجتماعی به معنای شناسایی مجموعه‌ای از چند گره محدود در یک شبکه اجتماعی است به طوری که با فعال‌سازی این مجموعه محدود، گره‌ها بتوانند براساس یک مدل انتشار مشخص، بیشترین میزان انتشار اطلاعات را ممکن سازند. در این مقاله، یک الگوریتم جدید برای یافتن گره‌های تاثیرگذار با هدف حداکثرسازی گسترش انتشار اطلاعات ارائه شده که از معیارهای شباهت کاربران در شبکه‌های اجتماعی بهره می‌برد. در الگوریتم پیشنهادی، پس از محاسبه شباهت میان گره‌های شبکه، یال‌ها وزن‌دهی شده و سپس معیارهای انتخاب بر روی گراف وزن‌دار اعمال می‌شود تا تاثیرگذارترین گره‌ها شناسایی شوند. کارایی الگوریتم پیشنهادی از طریق شبیه‌سازی توسط چندین آزمایش بر روی چند مجموعه داده استاندارد شبکه‌های اجتماعی ارزیابی شده و نتایج شبیه‌سازی‌ها نشان‌دهنده عملکرد مطلوب الگوریتم است؛ به طوری که از لحاظ شاخص نرخ پوشش، الگوریتم پیشنهادی براساس معیار شباهت جاکارد، نسبت به بهترین نتیجه رقیب در هر سناریو براساس نتایج 6 مجموعه داده مختلف به طور متوسط 87/6 درصد بهبود داشته است.
کلیدواژه‌ها
شبکه‌های اجتماعی
حداکثر‌سازی انتشار اطلاعات
معیار‌های شباهت
موضوعات
  1. S. Singh, D. Srivastva, M. Verma, and J. Singh, “Influence maximization frameworks, performance, challenges and directions on social network: A theoretical study,” Journal of King Saud University-Computer and Information Sciences, vol. 34, no. 9, pp. 7570–7603, 2022.
  2. Rezvanian, B. Moradabadi, M. Ghavipour, M. M. Daliri Khomami, and M. R. Meybodi, “Social Influence Maximization,” in Learning Automata Approach for Social Networks, A. Rezvanian, B. Moradabadi, M. Ghavipour, M. M. Daliri Khomami, and M. R. Meybodi, Eds., in Studies in Computational Intelligence. , Cham: Springer International Publishing, 2019, pp. 315–329.
  3. Kempe, J. Kleinberg, and É. Tardos, “Maximizing the spread of influence through a social network,” in Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, New York, USA: ACM Press, 2003, pp. 137–146.
  4. Zareie and R. Sakellariou, “Influence maximization in social networks: a survey of behaviour-aware methods,” Social Network Analysis and Mining, vol. 13, no. 1, p. 78, 2023.
  5. 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, ACM, 2001, pp. 57–66.
  6. Kempe, J. Kleinberg, and É. Tardos, “Influential nodes in a diffusion model for social networks,” in Automata, Languages and Programming, vol. 3580, in Lecture Notes in Computer Science, vol. 3580. , 2005, pp. 1127–1138.
  7. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance, “Cost-effective outbreak detection in networks,” in Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, 2007, pp. 420–429.
  8. Goyal, 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, ACM, 2011, pp. 47–48.
  9. Guo and W. Wu, “Influence Maximization: Seeding Based on Community Structure,” ACM Transactions on Knowledge Discovery from Data, vol. 14, no. 6, pp. 1–22, 2020..
  10. Zareie, A. Sheikhahmadi, and M. Jalili, “Identification of influential users in social network using gray wolf optimization algorithm,” Expert Systems with Applications, vol. 142, p. 112971, 2020.
  11. Saxena and P. Kumar, “A node activity and connectivity-based model for influence maximization in social networks,” Social Network Analysis and Mining, vol. 9, no. 1, p. 40, 2019.
  12. Ghayour-Baghbani, M. Asadpour, and H. Faili, “MLPR: Efficient influence maximization in linear threshold propagation model using linear programming,” Social Network Analysis and Mining, vol. 11, no. 1, p. 3, 2021.
  13. Gong and C. Guo, “Influence maximization considering fairness: A multi-objective optimization approach with prior knowledge,” Expert Systems with Applications, vol. 214, p. 119138, 2023.
  14. Bouyer, H. A. Beni, B. Arasteh, Z. Aghaee, and R. Ghanbarzadeh, “FIP: A fast overlapping community-based Influence Maximization Algorithm using probability coefficient of global diffusion in social networks,” Expert systems with applications, vol. 213, p. 118869, 2023.
  15. Wang, J. Zhao, L. Li, L. Jiao, J. Liu, and K. Wu, “A multi-transformation evolutionary framework for influence maximization in social networks,” IEEE Computational Intelligence Magazine, vol. 18, no. 1, pp. 52–67, 2023.
  16. Kumar, S. S. Singh, K. Singh, and B. Biswas, “Link prediction techniques, applications, and performance: A survey,” Physica A: Statistical Mechanics and its Applications, vol. 553, p. 124289, 2020.
  17. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” Proceedings of the National Academy of Sciences, vol. 99, no. 12, pp. 7821–7826, 2002.
  18. Lusseau, “The emergent properties of a dolphin social network,” Proceedings of the Royal Society of London. Series B: Biological Sciences, vol. 270, no. suppl_2, 2003.
  19. Park and M. E. Newman, “A network-based ranking system for US college football,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2005, no. 10, p. P10014, 2005.
  20. M. Gleiser and L. Danon, “Community structure in jazz,” Advances in complex systems, vol. 6, no. 04, pp. 565–573, 2003.
  21. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney, “Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters,” Internet Mathematics, vol. 6, no. 1, pp. 29–123, 2009.
  22. A. Adamic and N. Glance, “The political blogosphere and the 2004 U.S. election: divided they blog,” in Proceedings of the 3rd international workshop on Link discovery, Chicago Illinois: ACM, 2005, pp. 36–43.
  23. -C. Chen, W.-Y. Zhu, W.-C. Peng, W.-C. Lee, and S.-Y. Lee, “CIM: community-based influence maximization in social networks,” ACM Transactions on Intelligent Systems and Technology (TIST), vol. 5, no. 2, p. 25, 2014.
  24. M. D. Khomami, A. Rezvanian, N. Bagherpour, and M. R. Meybodi, “Minimum positive influence dominating set and its application in influence maximization: a learning automata approach,” Applied Intelligence, vol. 48, no. 3, pp. 570–593, 2018.
  25. M. D. Khomami, A. Rezvanian, M. R. Meybodi, and A. Bagheri, “CFIN: A community-based algorithm for finding influential nodes in complex social networks,” The Journal of Supercomputing, no. 77, pp. 2207–2236, 2021.
  26. Soltanzadeh and A. Rezvanian, “A New Pruning Method for Identifying Influential Nodes in Social Networks,” in 8th International Conference on Web Research (ICWR2022), Tehran, Iran, 2022, pp. 1–6.
  27. -L. He, Y. Fu, and D.-B. Chen, “A novel top-k strategy for influence maximization in complex networks with community structure,” PloS one, vol. 10, no. 12, 2015.