ارائه روش بهبودیافته در حداکثر سازی پویایی نظرات مبتنی بر الگوریتم ژنتیک حریصانه

رعیت پرور, حسین; حسنی آهنگر, محمدرضا; سرکرده ئی, ابوالفضل

doi:10.47176/ECDJ.2025.1617

ارائه روش بهبودیافته در حداکثر سازی پویایی نظرات مبتنی بر الگوریتم ژنتیک حریصانه

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

نویسندگان

حسین رعیت پرور ¹

محمدرضا حسنی آهنگر ²

ابوالفضل سرکرده ئی ³

¹ کارشناسی ارشد ، دانشگاه جامع امام حسین(ع)، تهران، ایران

² استاد ، دانشگاه جامع امام حسین(ع)، تهران، ایران

³ دانشجوی دکتری ، دانشگاه جامع امام حسین(ع) ، تهران ، ایران

10.47176/ECDJ.2025.1617

چکیده

تحلیل داده‌های شبکه‌های اجتماعی برخط یکی از چالش‌های علمی موردتوجه در عصر حاضر است. در زمینه تحلیل نظرات کاربران در این شبکه‌ها، حداکثر سازی پویایی نظرات به‌عنوان یک حوزه پژوهشی جدید مطرح‌شده است. تحقیقات پیشین در این حوزه عمدتاً فرض کرده‌اند که نظرات گره‌ها ثابت و بدون تغییر هستند. همچنین، کمتر به تغییرات زمانی نظرات کاربران پرداخته‌شده است. در این مقاله، با در نظر گرفتن پویایی نظرات و تغییرات آن در طول زمان، روشی برای مسئله حداکثر سازی پویایی نظرات بر اساس الگوریتم ژنتیک حریصانه پیشنهادشده است. این روش شامل دو بخش اصلی است. مدل پویایی نظرات فعال‌شده و فرایند انتخاب گره‌های دانه. مدل پویایی نظرات فعال‌شده با استفاده از ترکیب مدل انتشار آستانه خطی و یادگیری Q بدون حالت طراحی‌شده است که تغییرات زمانی نظرات را در نظر می‌گیرد. برای انتخاب گره‌های دانه، الگوریتم ژنتیک حریصانه به کار گرفته‌شده است. پس از تعیین گره اولیه یا دانه، مدل پویایی نظرات فعال‌شده آغاز می‌شود. در این مرحله، گره اولیه و همسایگان آن بر اساس مدل انتشار آستانه خطی فعال‌سازی می‌شوند. سپس با بهره‌گیری از یادگیری Q بدون حالت، نظرات گره‌ها به‌روزرسانی می‌گردند. این فرآیند به‌صورت تکرارشونده ادامه می‌یابد تا زمانی که شرایط خاتمه موردنظر برآورده شوند. نتایج تجربی حاصل از آزمایش بر روی چهار مجموعه داده‌ی شبکه‌های اجتماعی امضاشده نشان می‌دهد که روش پیشنهادی در مقایسه با بهترین روش‌های موجود، در معیار تعداد گره‌های فعال 14 درصد و در معیار میانگین نظرات مثبت 27 درصد بهبود عملکرد داشته است

کلیدواژه‌ها

تحلیل شبکه‌های اجتماعی برخط حداکثر سازی پویایی نظرات گره دانه الگوریتم ژنتیک حریصانه یادگیری ;">Q

20.1001.1.23224347.1404.13.4.3.4

موضوعات

دفاع سایبری

عنوان مقاله English

An Improved Method for Dynamic Opinion Maximization Based on Greedy Genetic Algorithms

نویسندگان English

Hossein Rayatparvar ¹

Mohammad Hasani Ahangar ²

Aboulfazl Sarkardei ³

¹ Master's degree, Imam Hossein University, Tehran, Iran

² Professor, Imam Hossein University, Tehran, Iran

³ PhD student, Imam Hossein University (AS), Tehran, Iran

چکیده English

The analysis of online social network data represents a significant scientific challenge in contemporary research. Within the domain of user opinion analysis in these networks, dynamic opinion maximization has emerged as a nascent field of study. Prior investigations in this area have predominantly operated under the assumption of static, unchanging node opinions. Furthermore, the temporal evolution of user perspectives has received comparatively limited attention. This paper proposes a method for the dynamic opinion maximization problem, based on a greedy genetic algorithm, explicitly considering the dynamics of opinions and their evolution over time.The proposed method comprises two principal components: an activated opinion dynamics model and a seed node selection process. The activated opinion dynamics model is constructed by integrating the linear threshold model with stateless Q-learning, thereby explicitly accommodating the temporal fluctuations in opinions. A greedy genetic algorithm is employed for the selection of seed nodes. Following the identification of an initial seed node, the activated opinion dynamics model is initiated. During this phase, the seed node and its immediate neighbors are activated according to the linear threshold model. Subsequently, stateless Q-learning is utilized to update the opinions of the nodes. This iterative process continues until predefined termination criteria are satisfied. Experimental results on four signed social network datasets demonstrate that the proposed framework outperforms the state-of-the-art method by 14% in terms of the number of activated nodes and 27% in terms of average positive opinions.

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

Online social network analysis dynamic opinion maximization seed nodes genetic algorithm Q

learning

[1] D. C. Cercel and S. Trausan-Matu, “Opinion propagation in online social networks: A survey,” ACM Int. Conf. Proceeding Ser., 2014, doi: 10.1145/2611040.2611088.

[2] P. Xu, W. Hu, J. Wu, and W. Liu, “Opinion maximization in social trust networks,” IJCAI Int. Jt. Conf. Artif. Intell., vol. 2021-Janua, pp. 1251–1257, 2020, doi: 10.24963/ijcai.2020/174.

[3] X. Liu, X. Kong, and P. S. Yu, “Active opinion maximization in social networks,” Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Min., pp. 1840–1849, 2018, doi: 10.1145/3219819.3220061.

[4] Q. He et al., “Dynamic Opinion Maximization Framework With Hybrid Method in Social Networks,” IEEE Trans. Netw. Sci. Eng., vol. 10, no. 1, pp. 441–451, 2023, doi: 10.1109/TNSE.2022.3212124.

[5] Y. Li, J. Fan, Y. Wang, and K. L. Tan, “Influence Maximization on Social Graphs: A Survey,” IEEE Trans. Knowl. Data Eng., vol. 30, no. 10, pp. 1852–1872, 2018, doi: 10.1109/TKDE.2018.2807843.

[6] G. Zhang and C. You, “Influence Maximization Algorithms Research Based on Big Graphs,” Proc. - 2018 IEEE 18th Int. Conf. Softw. Qual. Reliab. Secur. Companion, QRS-C 2018, pp. 537–544, 2018, doi: 10.1109/QRS-C.2018.00096.

[7] A. Zareie and R. Sakellariou, “Influence maximization in social networks: a survey of behaviour-aware methods,” Soc. Netw. Anal. Min., vol. 13, no. 1, pp. 1–21, 2023, doi: 10.1007/s13278-023-01078-9.

[8] M. Azaouzi, W. Mnasri, and L. Ben Romdhane, “New trends in influence maximization models,” Comput. Sci. Rev., vol. 40, p. 100393, 2021, doi: 10.1016/j.cosrev.2021.100393.

[9] S. Banerjee, M. Jenamani, and D. K. Pratihar, “A survey on influence maximization in a social network,” Knowl. Inf. Syst., vol. 62, no. 9, pp. 3417–3455, 2020, doi: 10.1007/s10115-020-01461-4.

[10] M. Jaouadi and L. Ben Romdhane, “A survey on influence maximization models,” Expert Syst. Appl., vol. 248, no. September 2023, p. 123429, 2024, doi: 10.1016/j.eswa.2024.123429.

[11] Q. He et al., “Reinforcement-Learning-Based Dynamic Opinion Maximization Framework in Signed Social Networks,” IEEE Trans. Cogn. Dev. Syst., vol. 15, no. 1, pp. 54–64, 2023, doi: 10.1109/TCDS.2022.3141952.

[12] Q. He, H. Fang, J. Zhang, and X. Wang, “Dynamic Opinion Maximization in Social Networks,” IEEE Trans. Knowl. Data Eng., vol. 35, no. 1, pp. 350–361, 2023, doi: 10.1109/TKDE.2021.3077491.

[13] Bazdar, G., Abdollahi Azgomi, M.,‘a computational model to evaluate the agent of influence operations in online social networks’, Electronic and Cyber Defense, vol. 12, no. 1, pp. 89–107, 2024.(In Persian).https://dor.isc.ac/dor/20.1001.1.23224347.1403.12.1.8.6

[14] Jabbari Lotf, J., Abdollahi Azgomi, M., & Ebrahimi Dishabi, M. R, “A Dynamic Metaheuristic Algorithm for Influence Maximization in Social Networks,” vol. 11, no. 2, pp. 57-69, 2023(In Persian).https://dor.isc.ac/dor/20.1001.1.23224347.1402.11.2.5.8

[15] J. Jabari Lotf, M. Abdollahi Azgomi, and M. R. Ebrahimi Dishabi, “An improved influence maximization method for social networks based on genetic algorithm,” Phys. A Stat. Mech. its Appl., vol. 586, p. 126480, 2022, doi: 10.1016/j.physa.2021.126480.

[16] Q. He, Y. Lv, X. Wang, M. Huang, and Y. Cai, “Reinforcement Learning-Based Rumor Blocking Approach in Directed Social Networks,” IEEE Syst. J., vol. 16, no. 4, pp. 6457–6467, 2022, doi: 10.1109/JSYST.2022.3159840.

[17] Q. He et al., “Reinforcement-Learning-Based Competitive Opinion Maximization Approach in Signed Social Networks,” IEEE Trans. Comput. Soc. Syst., vol. 9, no. 5, pp. 1505–1514, 2022, doi: 10.1109/TCSS.2021.3120421.

[18] Q. He et al., “Dynamic Opinion Maximization Framework with Hybrid Method in Social Networks,” IEEE Trans. Netw. Sci. Eng., pp. 1–11, 2022, doi: 10.1109/TNSE.2022.3212124.

[19] Q. He et al., “Positive opinion maximization in signed social networks,” Inf. Sci. (Ny)., vol. 558, pp. 34–49, 2021, doi: 10.1016/j.ins.2020.12.091.

[20] Y. Li, J. Zhu, J. Jiao, and Q. Zhang, “Competitive Influence Minimization in Multi-Group Social Networks: An Opinion-Based Solution,” IEEE Trans. Netw. Sci. Eng., vol. 9, no. 4, pp. 2617–2630, 2022, doi: 10.1109/TNSE.2022.3168042.

[21] L. S. Alla and A. S. Kare, Opinion Maximization in Signed Social Networks Using Centrality Measures and Clustering Techniques. Springer Nature Switzerland, 2023. doi: 10.1007/978-3-031-24848-1_9.

[22] Q. He et al., “CAOM: A community-based approach to tackle opinion maximization for social networks,” Inf. Sci. (Ny)., vol. 513, pp. 252–269, 2020, doi: 10.1016/j.ins.2019.10.064.

[23] J. Jabari Lotf, M. Abdollahi Azgomi, and M. R. Ebrahimi Dishabi, “An improved influence maximization method for social networks based on genetic algorithm,” Phys. A Stat. Mech. its Appl., vol. 586, p. 126480, 2022, doi: 10.1016/j.physa.2021.126480.

[24] C. Dong, G. Xu, P. Yang, and L. Meng, “TSIFIM: A three-stage iterative framework for influence maximization in complex networks,” Expert Syst. Appl., vol. 212, no. August 2022, p. 118702, 2023, doi: 10.1016/j.eswa.2022.118702.

[25] 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 Trans. Netw. Sci. Eng., vol. 8, no. 2, pp. 1557–1570, 2021, doi: 10.1109/TNSE.2021.3064828.

[26] S. Kumar, F. Spezzano, V.S. Subrahmanian, C. Faloutsos. Edge Weight Prediction in Weighted Signed Networks. IEEE International Conference on Data Mining (ICDM), 2016.

[27] S. Kumar, B. Hooi, D. Makhija, M. Kumar, V.S. Subrahmanian, C. Faloutsos. REV2: Fraudulent User Prediction in Rating Platforms. 11th ACM International Conference on Web Searchand Data Mining (WSDM), 2018.

[28] Robert West, Hristo S. Paskov, Jure Leskovec, and Christopher Potts: Exploiting Social Network Structure for Person-to-Person Sentiment Analysis. Transactions of the Association for Computational Linguistics, 2(Oct):297–310, 2014.

[29] J. Leskovec, D. Huttenlocher, J. Kleinberg. Signed Networks in Social Media. CHI 2010.

[30] J. Leskovec, D. Huttenlocher, J. Kleinberg. Predicting Positive and Negative Links in Online Social Networks. WWW 2010.

[31] J. Leskovec, D. Huttenlocher, J. Kleinberg: Signed Networks in Social Media. 28th ACM Conference on Human Factors in Computing Systems (CHI), 2010.

[32] S. Aral and P. S. Dhillon, “Social influence maximization under empirical influence models,” Nat. Hum. Behav., vol. 2, no. 6, pp. 375–382, 2018, doi: 10.1038/s41562-018-0346-z.

[33] S. Brin and L. Page, Reprint of: the anatomy of a large-scale hypertextual web search engine, Computer Networks. 56(18) 2012 3825-3833.

J. Luo, X. Liu, and X. Kong, “Competitive opinion maximization in social networks,” Proc. 2019 IEEE/ACM Int. Conf. Adv. Soc. Networks Anal. Mining, ASONAM 2019, pp. 250–257, 2019, doi: 10.1145/3341161.3342899