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

کریم زادگان مقدم, داود; احمدی شکیب, سیده معصومه; ثنائی, محمدرضا

doi:10.22034/apj.2025.723052

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

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

نویسندگان

داود کریم زادگان مقدم ¹

سیده معصومه احمدی شکیب ²

محمدرضا ثنائی ³

¹ دانشیار و عضو هیات علمی دامشگاه پیام نور، تهران، ایران

² دانشکده مدیریت و حسابداری، واحد قزوین، دانشگاه آزاد اسلامی، قزوین، ایران

³ گروه مدیریت، دانشکده مدیریت و حسابداری، واحد قزوین، دانشگاه آزاد اسلامی، قزوین، ایران

10.22034/apj.2025.723052

چکیده

شبکه‌های اجتماعی عمدتاً در قالب نمودارهایی با تعداد زیادی راس و یال در قالب یک ماتریس مجاورت نمایش و تحلیل می‌شوند. لبه‌ها روابط بین افراد را نشان می‌دهند و به عنوان پیوند بین رئوس عمل می‌کنند. ویژگی‌های ساختاری هر شبکه با ویژگی‌های لبه‌ها و رئوس درون آن تعیین می‌شود. در این تحقیق که بر روی انواع داده‌های شبکه‌های اجتماعی از پایگاه داده دانشگاه استنفورد انجام شد، از روش پیش پردازش با استفاده از الگوریتم استعماری رقابتی برای عملیات انتخاب ویژگی‌هایی با بالاترین شایستگی (کمترین هزینه) استفاده شد. برای ارزیابی تأثیر انتخاب ویژگی بر خروجی نهایی، آزمایش‌هایی با و بدون عملیات انتخاب ویژگی با استفاده از الگوریتم‌های مختلف که معمولاً در این زمینه استفاده می‌شوند، انجام شد. شاخص‌های معتبر مانند دقت، تشخیص، حساسیت و عمده به طور مستقل بر روی نتایج خروجی با میانگین 10 اجرای برنامه اندازه‌گیری شدند. مقایسه نتایج بین سناریوهای با و بدون انتخاب ویژگی تأثیر قابل توجهی بر همه شاخص‌های نتیجه نهایی نشان داد. بسیاری از ویژگی‌ها در مجموعه داده‌ها یا استفاده نشده بودند یا حاوی حداقل اطلاعات بودند. حذف نکردن این ویژگی‌ها نه تنها بار محاسباتی را افزایش داد، بلکه بر دقت نتایج خروجی به دلیل اجرای زمان‌بر تأثیر گذاشت.

کلیدواژه‌ها

پیش‌بینی لینک

الگوریتم‌های فرااکتشافی

پیش‌پردازش داده‌ها

عنوان مقاله English

Link prediction system in social networks based on meta-heuristic algorithm

نویسندگان English

Davood Karimzadgan Moghadam ¹

Seyyede Masoume Ahmadi Shakib ²

Mohammad Reza Sanaei ³

¹ Associate Professor and Faculty Member of Payam Noor University, Tehran, Iran.

² Department of Management and Accounting, Qazvin Branch, Islamic Azad University, Qazvin, Iran

³ Department of Management and Accounting, Qazvin Branch, Islamic Azad University, Qazvin, Iran

چکیده English

Social networks are primarily represented and analyzed in the form of graphs with a large number of vertices and edges, structured as an adjacency matrix. The edges indicate relationships between individuals and act as connections between the vertices. The structural characteristics of each network are determined by the features of the edges and vertices within it. In this research, conducted on various types of social network data from the Stanford University database, a preprocessing method was employed using a competitive colonial algorithm for feature selection with the highest merit (lowest cost). To evaluate the impact of feature selection on the final output, experiments were conducted both with and without feature selection operations using various algorithms commonly used in this field. Valid metrics such as accuracy, precision, sensitivity, and recall were independently measured on the output results with an average of 10 program executions. The comparison of results between scenarios with and without feature selection showed a significant impact on all metrics of the final outcome. Many features in the datasets were either unused or contained minimal information. Not removing these features not only increased the computational burden but also affected the accuracy of the output results due to time-consuming execution.

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

Link prediction

meta-heuristic algorithms

data preprocessing

[1] Kumar, A., et al. Link prediction techniques, applications, and performance: A survey. Physica A: Statistical Mechanics and its Applications, 553(6) (2020). https://doi.org/10.1016/j.physa.2020.124289.

[2] Shao, H., et al. Link prediction algorithms for social networks based on machine learning and HARP. IEEE Access, 7. pp. 122722-122729 (2019). https://doi.org/10.1109/ACCESS.2019.2938202.

[3] Sherkat, E., Rahgozar, M., Asadpour, M., Ant Colony Approach to Link Prediction in Social Networks, The CSI Journal on Computer Science and Engineering 12 (1) (2014) . 1-9. https://doi.org/10.1016/j.swevo.2018.03.001.

[4] Saadinezhad, H., Parvinniya, A., New link prediction criteria based on node composition and network structure. Soft Computing and Information Technology, 2, pp. 41-52 (1401). https://jscit.nit.ac.ir/article_151735_c67dc613817a84d127c6e844a821a0a3.pdf.

[5] Jalili, M., Orouskhani, Y., Asgari, M., Alipourfard, N., Perc, M. Link prediction in multiplex online social networks. Royal Society Open Science, 2: pp.160863 (2017). https://doi.org/10.1098/rsos.160863.

[6] Sharma, S., Singh, A. An efficient method for link prediction in weighted multiplex networks. Computational Social Networks, 3, no. 1: pp.7 (2016). https://doi.org/10.1186/s40649-016-0034-y.

[7] Yan, R., et al., SSDBA: the stretch shrink distance based algorithm for link prediction in social networks, Frontiers of Computer Science, 15(1) (2021), 1-8.

[8] Tang, R., et al., Interlayer link prediction in multiplex social networks: an iterative degree penalty algorithm, Knowledge-Based Systems. 194 (2020). https://doi.org/10.1016/j.knosys.2020.105598.

[9] Sayyarifard, S., Presenting a new link prediction method in social networks using deep learning methods. Third Conference on Electrical, Computer and Mechanical Engineering, pp. 39-50(1399).

[10] Zare, H., Shokrzade, H., Link prediction in social networks using the clustering method using the expectation maximization algorithm. The fourth national conference of new technologies (1400).

[11] Chen, H., et al., Multi-level graph convolutional networks for cross-platform anchor link prediction, Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining (2020), 1503–1511. https://doi.org/10.1145/3394486.3403201.

[12] Alzubaidi, M. N. 2023. LightGBM for link prediction based on graph structure attributes. ICIC Express Letters, Vol 14, 3: pp. 303-3011 (2023).

[13] Zare, H., & Shakorzadeh, H., Link prediction in social networks using clustering method with maximum expectation maximization algorithm, Fourth National Conference on Advanced Technologies in Electrical, Computer, and Mechanical Engineering in Iran. (2021). https://civilica.com/doc/1292870

[14] Sharma, A., et al., Link Prediction in Social Network using Artificial Neural Network. Int. J. Comput. Appl. 174 (2021), 26-30.

[15] Parvazeh, F., A. Harounabadi, and M. A. Naizari, A Recommender System for Making Friendship in Social Networks Using Graph Theory and users profile, Journal of Current Research in Science. 1(2016), 535.

[16] Piltan, Y., & Mojarrad, M., Introducing a new method for link prediction in social networks based on metaheuristic algorithms. Kahraba Quarterly. 6(25) (2019). https://civilica.com/doc/1442443

[17] Ahuja, R., et al., Using hierarchies in online social networks to determine link prediction, Soft Computing and Signal Processing, Springer (2019), 67-76.

[18] Siyari Fard, S., Presenting a new method for link prediction in social networks using deep learning techniques, Third Conference on Electrical, Computer, and Mechanical Engineering, (2020), https://civilica.com/doc/118916

[19] Shaeghi, H., & A. Ghasemi, Modeling a multi-input multi-output system for simultaneous prediction of price and load in intelligent networks with load management, Computational Intelligence in Electrical Engineering, 6 (4) (2015), 1-87.

[20] Luo, J., J. Zhou, and X. Jiang, A Modification of the Imperialist Competitive Algorithm With Hybrid Methods for Constrained Optimization Problems, Journal of PeerJ Computer Science. 8 (2021), e1075. https://doi.org/10.7717/peerj-cs.1075.

[21] Li, X., J. Chen, L. Sun, and J. Li, A new imperialist competitive algorithm with spiral rising mechanism for solving path optimization problems, Journal of PeerJ Computer Science. 8(2022), e1075. https://doi.org/10.7717/peerj-cs.1075.

[22] Tao, Xin-rui., J.-Q. Li, T.-H. Huang and P. Duan, Discrete imperialist competitive algorithm for the resource-constrained hybrid flowshop problem with energy consumption, Journal of Complex & Intelligent Systems. 7(2021), 311–326. https://doi.org/10.1007/s40747-020-00193-w.