علوم رایانشی

علوم رایانشی

بیشینه‌‌سازی انتشار و کمینه‌‌سازی هزینه به صورت هم‌زمان درشبکه‌‌های اجتماعی مبتنی بر جدول درهم‌‌ساز

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

نویسندگان
1 دانشکده برق و کامپیوتر،‌دانشگاه کاشان، کاشان،‌ایران
2 استادیار، دانشکده برق و کامپیوترـ دانشگاه کاشان ،‌ایران
3 استادیار، دانشکده برق و کامپیوترـ دانشگاه کاشان - ایران
10.22034/csj.2024.203193
چکیده
با توسعة شبکه‌‌های اجتماعی، چالش‌های بیشتری در تحلیل آنها ایجاد شده است که نیازمند روش‌های دقیق‌تر و سریع‌تر هستند. یکی از آن چالش‌ها، یافتن افراد تأثیرگذار در شبکه‌های اجتماعی است که کاربردهای متنوعی مانند بازاریابی، انتشار اطلاعات و پیشگیری از بیماری‌ها دارد. بیشتر روش‌های پیشین این چالش را به عنوان یک مسئله تک هدفه دنبال می‌کردند؛ به حداکثر رساندن میزان انتشار در شبکه. در این راستا، تعداد مشخصی از افراد به عنوان افراد تاثیرگذار (یا اعضای بذر) انتخاب می‌شوند و میزان انتشار منجر از انتخاب آنها در شبکه ارزیابی می‌شود. در حالی که اهداف دیگری مانند هزینه انتخاب هر بذر نیز اهمیت ویژه‌ای دارد؛ به‌خصوص در امور تبلیغاتی و راهبرد‌‌های مدیریتی. در این مقاله حداکثر رساندن انتشار به‌عنوان یک مسئلة تک هدفه و همچنین کمینه‌‌کردن هزینه انتخاب بذرها با توجه به حداکثر رساندن انتشار به عنوان یک مسئلة دو هدفه در نظر گرفته شده است. نوآوری مقاله، استفاده از توابع درهم‌ساز در جهت افزایش سرعت اجرای چالش یافتن اعضای بذر است. در این راستا، الگورتیم H-GA (ترکیب الگوریتم ژنتیک و تابع درهم‌ساز) برای حل مسئلة تک هدفه و الگوریتمH-NSGA-II (ترکیب روش NSGA-II و تابع درهم‌ساز) برای حل مسئلة دو هدفه پیشنهاد می‌شود. در الگوریتم‌‌های پیشنهادی، استفاده از توابع درهم‌ساز باعث می‌شود تا از تکرار محاسبات ارزیابی جلوگیری شود. بدین‌ترتیب، ضمن حفظ دقت حل مساله یافتن اعضای بذر، بهبود قابل توجهی در زمان اجرا ایجاد می‌شود؛ بهبود زمان اجرا به طور متوسط 8/21% در تمامی آزمایش‌ها.
کلیدواژه‌ها
موضوعات

[1]    M. Granovetter, "Network sampling: Some first steps," American journal of sociology, vol. 81, no. 6, pp. 1287-1303, 1976.
[2]    L. A. Sanchis, "Multiple-way network partitioning," IEEE Transactions on Computers, vol. 38, no. 1, pp. 62-81, 1989.
[3]    V. Chandola, A. Banerjee, and V. Kumar, "Anomaly detection: A survey," ACM computing surveys (CSUR), vol. 41, no. 3, pp. 1-58, 2009.
[4]    J. Yang and J. Liu, "Influence maximization-cost minimization in social networks based on a multiobjective discrete particle swarm optimization algorithm," IEEE Access, vol. 6, pp. 2320-2329, 2017.
[5]    K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, and A. Fast, "Nsga-ii," IEEE transactions on evolutionary computation, vol. 6, no. 2, pp. 182-197, 2002.
[6]    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, 2002, pp. 61-70.
[7]    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, 2001, pp. 57-66.
[8]    D. Kempe, 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, pp. 137-146.
[9]    D. Kempe, J. Kleinberg, and É. Tardos, "Influential nodes in a diffusion model for social networks," in Automata, Languages and Programming: 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005. Proceedings 32, 2005: Springer, pp. 1127-1138.
[10]  J. 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, 2007, pp. 420-429.
[11]  A. 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, 2011, pp. 47-48.
[12]  Y. Tang, X. Xiao, and Y. Shi, "Influence maximization: Near-optimal time complexity meets practical efficiency," in Proceedings of the 2014 ACM SIGMOD international conference on Management of data, 2014, pp. 75-86.
[13]  H. T. Nguyen, M. T. Thai, and T. N. Dinh, "A billion-scale approximation algorithm for maximizing benefit in viral marketing," IEEE/ACM Transactions On Networking, vol. 25, no. 4, pp. 2419-2429, 2017.
[14]  C. Borgs, M. Brautbar, J. Chayes, and B. Lucier, "Maximizing social influence in nearly optimal time," in Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, 2014: SIAM, pp. 946-957.
[15]  J. Lv, J. Guo, and H. Ren, "Efficient greedy algorithms for influence maximization in social networks," Journal of Information Processing Systems, vol. 10, no. 3, pp. 471-482, 2014.
[16]  L. C. Freeman, "Centrality in social networks: Conceptual clarification," Social network: critical concepts in sociology. Londres: Routledge, vol. 1, pp. 238-263, 2002.
[17]  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, 2009, pp. 199-208.
[18]  K. Jung, W. Heo, and W. Chen, "Irie: Scalable and robust influence maximization in social networks," in 2012 IEEE 12th international conference on data mining, 2012: IEEE, pp. 918-923.
[19]  D. Bucur and G. Iacca, "Influence maximization in social networks with genetic algorithms," in Applications of Evolutionary Computation: 19th European Conference, EvoApplications 2016, Porto, Portugal, March 30--April 1, 2016, Proceedings, Part I 19, 2016: Springer, pp. 379-392.
[20]  P. Krömer and J. Nowaková, "Guided genetic algorithm for the influence maximization problem," in Computing and Combinatorics: 23rd International Conference, COCOON 2017, Hong Kong, China, August 3-5, 2017, Proceedings 23, 2017: Springer, pp. 630-641.
[21]  C.-W. Tsai, Y.-C. Yang, and M.-C. Chiang, "A genetic newgreedy algorithm for influence maximization in social network," in 2015 IEEE International Conference on Systems, Man, and Cybernetics, 2015: IEEE, pp. 2549-2554.
[22]  D. Bucur, G. Iacca, A. Marcelli, G. Squillero, and A. Tonda, "Multi-objective evolutionary algorithms for influence maximization in social networks," in Applications of Evolutionary Computation: 20th European Conference, EvoApplications 2017, Amsterdam, The Netherlands, April 19-21, 2017, Proceedings, Part I 20, 2017: Springer, pp. 221-233.
[23]  J.-b. Guo, F.-z. Chen, and M.-q. Li, "A multi-objective optimization approach for influence maximization in social networks," in Proceeding of the 24th International Conference on Industrial Engineering and Engineering Management 2018, 2019: Springer, pp. 706-715.
[24]  P.-L. Lu, L. Zhang, J.-X. Tang, J.-M. Lan, H.-Y. Zhu, and S.-H. Song, "Solving the Influence Maximization-Cost Minimization Problem in Social Networks by Using a Multi-Objective Differential Evolution Algorithm," Journal of Computers, vol. 34, no. 5, pp. 285-303, 2023.
[25]  P. Wang and R. Zhang, "A multi-objective crow search algorithm for influence maximization in social networks," Electronics, vol. 12, no. 8, p. 1790, 2023.
[26]  L. Zhang, Y. Liu, F. Cheng, J. Qiu, and X. Zhang, "A local-global influence indicator based constrained evolutionary algorithm for budgeted influence maximization in social networks," IEEE Transactions on Network Science and Engineering, vol. 8, no. 2, pp. 1557-1570, 2021.
[27]  J. Yang and J. Liu, "Influence Maximization-Cost Minimization in Social Networks Based on a Multiobjective Discrete Particle Swarm Optimization Algorithm," IEEE Access, vol. 6, pp. 2320-2329, 2018, doi: 10.1109/ACCESS.2017.2782814.
[28]  S. Genetti, E. Ribaga, E. Cunegatti, Q. F. Lotito, and G. Iacca, "Influence Maximization in Hypergraphs using Multi-Objective Evolutionary Algorithms," arXiv preprint arXiv:2405.10187, 2024.
[29]  X. Fu, R. R. Bhatt, S. Basu, and A. Pavan, "Multi-objective submodular optimization with approximate oracles and influence maximization," in 2021 IEEE International Conference on Big Data (Big Data), 2021: IEEE, pp. 328-334.