کد مقاله : 1402041443131 بازدید : 2168 صفحه: 229 - 246

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

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

محورهای موضوعی : هوش مصنوعی و رباتیک

فاطمه حسین خانی ¹ , علی هارون آبادی ² , سعید ستایشی ³

1 - گروه مهندسی کامپیوتر، دانشکده فنی و مهندسی، واحد تهران مرکز، دانشگاه آزاد اسلامی، تهران، ایران
2 - استادیار، گروه مهندسی کامپیوتر و فناوری اطلاعات، دانشکده فنی و مهندسی، واحد تهران مرکزی، دانشگاه آزاد اسلامی، تهران، ایران
3 - دانشگاه صنعتی امیر کبیر

تاریخ دریافت : 1402/04/14 تاریخ پذیرش : 1403/05/22 تاریخ انتشار : 1403/09/17

کلید واژه: پیش بینی پیوند, شبکه های اجتماعی علامت دار, اعتماد, عدم اعتماد, محاسبات فازی ,

چکیده مقاله :

پیش بینی پیوند امری ضروری برای بررسی پیوند بین گره ها در شبکه های اجتماعی است. گسترش و مدل سازی شبکه های اجتماعی منجر به پیدایش شبکه های اجتماعی به صورت علامت دار، جهت دار و وزنی می شود. روابط کاربران در شبکه های اجتماعی علامت دار جنبه های ذهنی و نامتقارن وابسته به این حوزه را تعریف می کنند، لذا هر دو اصطلاح اعتماد و عدم اعتماد چالش برانگیز هستند. برای حل مسئله پراکندگی در شبکه ها و غلبه بر ابهام در روابط، یک روش اعتماد-عدم اعتماد مبتنی بر محاسبات فازی برای محاسبه قدرت پیوندها پیشنهاد می شود. هدف روش پیشنهادی پیش بینی پیوند برای حل مسئله پراکندگی در شبکه های اجتماعی علامت دار با ترکیب ویژگی های توصیف کاربران در شبکه های اجتماعی است که با تاثیر مستقیم گره های برتر و تاثیر غیرمستقیم گره های معمولی بر پیش‌بینی رتبه‌بندی ها ارزیابی می شود. اعتماد با یک سیستم فازی ممدانی مبتنی بر ویژگی های انعکاس شباهت فازی، اعتماد کلی و عدم اعتماد کلی تعیین می شود. ارزیابی روش پیشنهادی با معیار دقت بر روی مجموعه داده های شبکه های اجتماعی Epinions وSlashdot انجام شد. دقت روش پیشنهادی در مجموعه داده هایEpinions و Slashdotبه ترتیب برابر 0.991 و 0.998 می باشد. نتایج به دست آمده نشان می دهد روش پیشنهادی نسبت به مشکل پراکندگی داده ها در شبکه های اجتماعی علامت دار قوی عمل می-کند و این اثربخشی مدل پیشنهادی را بیان می نماید.

چکیده انگلیسی:

Link prediction is an important to check link between nodes in social networks. The modeling of social networks leads to emergence of signed, directed and weighted social networks. The relationships of users in social networks are characterized by subjective, asymmetric and ambiguous aspects related to this domain, then both terms of trust and distrust are challenging. To solve the problem of sparsity in networks and overcome ambiguity in relationships, a trust-distrust method based on fuzzy computational is proposed to calculate strength of links. The purpose of proposed link prediction is to solve problem of sparsity in signed social networks by combining descriptive features of users with the direct influence of top nodes and the indirect influence of common nodes on rating prediction. Trust is determined by a Mamdani fuzzy system based on mirroring of similarity fuzzy features, overall trust and overall distrust. The evaluation of the proposed method was done with the accuracy measure on datasets of Epinions and Slashdot. The accuracy of proposed method in Epinions and Slashdot datasets is 0.991 and 0.998, respectively. The obtained results show that proposed method works well for problem of data sparsity in signed social networks and show the effectiveness of proposed model.

منابع و مأخذ:

[1] X.Li, H.Fang, and J.Zhang, “FILE: A novel framework for predicting social status in signed networks”, Thirty-Second AAAI Conference on Artificial Intelligence, AAAI18 - Artificial Intelligence and the Web, Vol.32, No.1, 2018, PP.330–337.
[2] K.Akilal, M.Omar, and H.Slimani, “Characterizing and using gullibility, competence, and reciprocity in a very fast and robust trust and distrust inference algorithm for weighted signed social networks”, Knowledge-Based Systems, Vol.192, 2020, PP.1-11.
[3] H.Shirgahi, M.Mohsenzadeh, and H.H.S.Javadi, “A new method of trust mirroring estimation based on social networks parameters by fuzzy system”, International Journal Machine Learning & Cybernetics, Springer. Vol.9, 2018, PP.1153–1168.
[4] V.Kant, and KK.Bharadwaj, Fuzzy computational models of trust and distrust for enhanced recommendations, International Journal of Intelligent Systems, Vol.28, 2013, PP.332–365.
[5] N.Girdhar, S.Minz, and K.K.Bharadwaj, “Link prediction in signed social networks based on fuzzy computational model of trust and distrust”, Soft Computing, Vol.23, 2019, PP.12123–12138.
[6] Z.Duan, W.Xu, Y.Chen, and L.Ding, “ETBRec: a novel recommendation algorithm combining the double influence of trust relationship and expert users”, Applied Intelligence, Vol.52, 2022, PP.282–294.
[7] N.D.Nur, A.H.Sitil, S.Muntadher, S.Firdaus, and N.Anuar, “Applications of link prediction in social networks: A review”, Journal of Network and Computer Appllicatins, Vol.166, 2020, PP.1-31.
[8] X.Zhu, and Y.Ma, “Sign Prediction on Social Networks Based Nodal Features”, Journal of Complexity, Vol.2020, 2020, PP.1-11.
[9] R.E.Veras De Sena Rosa, F.A.S.Guimarães, R.d.S.Mendonça and V.F.d.Lucena, “Improving Prediction Accuracy in Neighborhood-Based Collaborative Filtering by Using Local Similarity”, IEEE Access, Vol.8, 2020, PP.142795-142809.
[10] H.Ghorbanzadeh, A.Sheikhahmadi, M.Jalili, and S.Sulaimany, “A Hybrid Method of Link Prediction in Directed Graphs”, Expert Systems with Applications, Vol.165, 2020, PP.1-13.
[11] D.Wang, Da-wei, Y.Yih and M.Ventresca, “Improving neighbor-based collaborative filtering by using a hybrid similarity measurement”, Expert Systems with Applications, Vol.160, 2020, PP.1-23.
[12] X.Wang, Y.Chai, H.Li, and D.Wu, “Link prediction in heterogeneous information networks: An improved deep graph convolution approach”, Decision Support Systems, Vol.141, 2021, PP.113448-113460.
[13] H.Tahmasbi, M.Jalali, and H.Shakeri, “TSCMF: Temporal and social collective matrix factorization model for recommender systems”, Journal of Intelligence Information Systems, Vol.56, 2021, PP.169–187.
[14] C.He, H.Liu, Y.Tang, S.Liu, X.Fei, Q.Cheng, and H.Li, “Similarity preserving overlapping community detection in signed networks”, Future Generation Computer Systems, Vol.116, 2021, PP.275-290.
[15] R.I.Yaghi, H.Faris, I.Aljarah, A.M.Al-Zoubi, A.A.Heidari, and S.Mirjalili, “Link Prediction Using Evolutionary Neural Network Models”, Evolutionary Machine Learning Techniques, Vol.32, 2020, PP.85-112.
[16] R.E.Tillman, P.Vamsi, Ch.Jiahao, R.Prashant and M.Veloso, “Heuristics for Link Prediction in Multiplex Networks”, In Proceedings of ECAI'2020, 24th European Conference on Artificial Intelligence, Vol.325, 2020, PP.1938-1945.
[17] F.Guo, W.Zhou, Z.Wang, Ch.Ju, Sh.Ji, Q.Lu, "A link prediction method based on topological nearest-neighbors similarity in directed networks", Journal of Computational Science, Vol.69, 2023, PP.102002-102016.
[18] H.Liu, Z.Zhenzhen, B.Fan, H.Zeng, Y.Zhang, and G.Jiang, “PrGCN: Probability prediction with graph convolutional network for person re-identification”, Neurocomputing, Vol.423, 2021, PP.57-70.
[19] X.Hu, X.Xiong, Y.Wu, M.Shi, P.Wei, and Ch.Ma, "A Hybrid Clustered SFLA-PSO algorithm for optimizing the timely and real-time rumor refutations in Online Social Networks", Expert Systems with Applications, Vol.212, 2023, PP.118638-118670.
[20] Y.Xu, Z.Feng, X.Zhou, M.Xing, H.Wu, X.Xue, Sh.Chen, Ch.Wang and L.Qi, "Attention-based neural networks for trust evaluation in online social networks", Information Sciences, Vol.630, 2023, PP.507-522.
[21] M.Nooraei.Abadeh, M.Mirzaie, “A differential machine learning approach for trust prediction in signed social networks”, Supercomput, Vol.79, 2023, PP.9443–9466.
[22] T.Zhang, W.Li, L.Wang, and J.Yang, “Social recommendation algorithm based on stochastic gradient matrix decomposition in social network”, Journal of Ambient Intelligence and Humanized Computing. Vol.11, 2020, PP.601-608.
[23] P.Srilatha, R.Manjula, and C.P.Kumar, “Link Prediction on Social Attribute Network Using Lévy Flight Firefly Optimization”, Advances in Artificial Intelligence and Data Engineering, Vol.1133, 2021, PP.1299-1309.
[24] E.Nasiri, K.Berahmand, and Y.Li, “Robust graph regularization nonnegative matrix factorization for link prediction in attributed networks”, Multimedia Tools and Applications, Vol.82, 2023, PP.3745–3768.
[25] S.Ghasemi, and A.Zarei., “Improving link prediction in social networks using local and global features: a clustering-based approach, Progress in Artificial”, Intelligence, Vol.11, 2022, PP.79–92.
[26] Suryakant, and T.Mahara, A New Similarity Measure Based on Mean Measure of Divergence for Collaborative Filtering in Sparse Environment, Procedia Computer Science, Vol.89, 2016, PP.450–456.
[27] https://snap.stanford.edu/data/soc-Epinions1. html,Last Visited (01, October. 2022).
[28] http://snap.stanford.edu/data/soc-Slashdot0902.html, Last Visited (01, October.2022).
[29] J.Golbeck, “Combining provenance with trust in social networks for semantic content filtering”, International Provenance and Annotation Workshop, Vol.4145, 2006, PP.101–108.

متن کامل:

$G:\دوفصلنامه ارتباطات و فناوری اطلاعات\ITRC-Logo\English.png$

Journal of Information and

Communication Technology

Volume 16, Issue 61-62, Autumn and Winter 2024, pp. 229-246

Trust Based Link Prediction Using Fuzzy Computational Model in Social Networks

Fatemeh Hoseinkhani1, Ali Harounabadi2¹, Saeed Setayeshi 3

1 Department of Computer Engineering, Central Tehran Branch, Islamic Azad University, Tehran, Iran.

2 Department of Computer Engineering, Central Tehran Branch, Islamic Azad University, Tehran, Iran.

3 Department of Medical Radiation Engineering, Amirkabir University of Technology, Tehran, Iran.

Received: 05 July 2023, Revised: 16 May 2024, Accepted: 12 August 2024

Paper type: Research

Abstract

Link prediction is important to check links between nodes in social networks. The modeling of social networks leads to the emergence of signed, directed, and weighted social networks. The relationships of users in social networks are characterized by subjective, asymmetric, and ambiguous aspects related to this domain, both terms of trust and distrust are challenging. To solve the problem of sparsity in networks and overcome ambiguity in relationships, a trust-distrust method based on fuzzy computational is proposed to calculate the strength of links. The purpose of the proposed link prediction is to solve problems of sparsity in signed social networks by combining descriptive features of users with the direct influence of top nodes and the indirect influence of common nodes on rating prediction. Trust is determined by a Mamdani fuzzy system based on mirroring of similarity fuzzy features, overall trust, and overall distrust. The evaluation of the proposed method was done with the accuracy measure on datasets of Epinions and Slashdot. The accuracy of the proposed method in Epinions and Slashdot datasets is 0.991 and 0.998, respectively. The obtained results show that the proposed method works well for problems of data sparsity in signed social networks and shows the effectiveness of the proposed model.

Keywords: Link Prediction, Signed Social Networks, Trust, Distrust, Fuzzy Computational.

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

فاطمه حسین خانی1، علی هارون آبادی2²، سعید ستایشی3

1 گروه مهندسی کامپیوتر، دانشکده فنی و مهندسی، واحد تهران مرکز، دانشگاه آزاد اسلامی، تهران، ایران.

2 گروه مهندسی کامپیوتر، دانشکده فنی و مهندسی، واحد تهران مرکز، دانشگاه آزاد اسلامی، تهران، ایران.

3 گروه مهندسی پرتوپزشکی، دانشکده مهندسی انرژی و فیزیک، دانشگاه صنعتی امیرکبیر، تهران، ایران.

تاریخ دریافت: 14/04/1402 تاریخ بازبینی: 27/02/1403 تاریخ پذیرش: 22//05/1403

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

چکيده

پیشبینی پیوند امری ضروری برای بررسی پیوند بین گرهها در شبکههای اجتماعی است. گسترش و مدلسازی شبکههای اجتماعی منجر به پیدایش شبکههای اجتماعی به صورت علامتدار، جهتدار و وزنی میشود. روابط کاربران در شبکههای اجتماعی علامتدار جنبههای ذهنی و نامتقارن وابسته به این حوزه را تعریف میکنند، پس هر دو اصطلاح اعتماد و عدم اعتماد چالشبرانگیز هستند. برای حل مسئله پراکندگی در شبکهها و غلبه بر ابهام در روابط، یک روش اعتماد-عدم اعتماد مبتنی بر محاسبات فازی برای محاسبه قدرت پیوندها پیشنهاد میشود. هدف روش پیشنهادی پیشبینی پیوند برای حل مسئله پراکندگی در شبکههای اجتماعی علامتدار با ترکیب ویژگیهای توصیف کاربران در شبکههای اجتماعی است که با تاثیر مستقیم گرههای برتر و تاثیر غیرمستقیم گرههای معمولی بر پیش‌بینی رتبه‌بندیها ارزیابی میشود. اعتماد با یک سیستم فازی ممدانی مبتنی بر ویژگیهای انعکاس شباهت فازی، اعتماد کلی و عدم اعتماد کلی تعیین میشود. ارزیابی روش پیشنهادی با معیار صحت بر روی مجموعه دادههای شبکههای اجتماعی Epinions وSlashdot انجام شد. صحت روش پیشنهادی در مجموعه دادههایEpinions و Slashdotبه ترتیب برابر 0.991 و 0.998 میباشد. نتایج بهدست آمده نشان میدهد روش پیشنهادی نسبت به مشکل پراکندگی دادهها در شبکههای اجتماعی علامتدار قوی عمل میکند و این اثربخشی مدل پیشنهادی را بیان مینماید.

کلیدواژگان: پیش‌بینی پیوند، شبکههای اجتماعی علامتدار، اعتماد، عدم اعتماد، محاسبات فازی.

[1] * Corresponding Author’s email: a.harounabadi@iauctb.ac.ir

[2] * رایانامة نويسنده مسؤول: a.harounabadi@iauctb.ac.ir

1- مقدمه

پیش‌بینی پیوند به عنوان یکی از زمینههای تحقیقاتی پرکاربرد در شبکههای اجتماعی شناخته میگردد که وظیفه اصلی آن پیش‌بینی پیوندها در آیندهای نزدیک بین کاربران و آیتمها است. تشکیل این پیوندها و یا عدم پیوندها به معنای ایجاد اعتماد و یا عدم اعتماد بین کاربران میباشد. این رفتارها در شبکهها، توجه به شبکههای اجتماعی علامتدار را بیشتر میکند که در طی چندسال اخیر به طور گسترده مورد بررسی قرار گرفتهاند، زیرا روابط کاربران را بهتر از شبکههای اجتماعی بدون علامت نشان میدهند. شبکههای اجتماعی علامتدار رابطه بین دو گره را تعیین میکنند که به عنوان پیوند مثبت یا منفی نامگذاری میشوند. در واقع در پیش‌بینی پیوند برای روابط علامتدار سه نوع ارتباط اجتماعی بین دو کاربر درنظر گرفته میشود: مثبت (اعتماد/(1+))، منفی (عدم اعتماد/(1-)) و عدم رابطه (عدم وجود پیوند/(صفر)). پیوند مثبت نشان‌دهنده وجود یک رابطه قابل اعتماد و پیوند منفی نشان‌دهنده وجود یک رابطه غیرقابل اعتماد است. افزایش علاقه به شبکههای اجتماعی علامت‌دار، نیاز به بازنگری در مسائل پیش‌بینی پیوند را افزایش داده است]1[. محاسبات فازی به صورت تقریبی به جای استدلال دقیق در بیان روابط که فقط اعتماد و یا فقط عدم اعتماد را مدل میکند، استفاده میشود. برای حل این تضاد برای مقادیر قطعی در روابط اعتماد، از محاسبات فازی استفاده میشود.

به منظور بررسی اعتماد در شبکههای اجتماعی میبایست معیارهایی که ویژگیهای اجتماعی کاربران را توصیف میکنند و بر میزان اعتماد کاربران تاثیرگذاری بسزایی دارند، مورد بررسی قرار گیرند. این ویژگیها باید به گونه ای باشند که مشکل پراکندگی بین کاربران در شبکههای اجتماعی را به خوبی حل نمایند و همچنین پیش‌بینی پیوند را با دقت بالا و سرعت زیاد انجام دهند. از این رو، ویژگیهایی در این تحقیق مورد استفاده قرار میگیرند که حائز شرایط باشند. این ویژگیها عبارتند از: تشابه اولویت، تجربه، عمل متقابل، صفات اجتماعی محلی و چگالی اشتراک برای تعیین اعتماد و عدم اعتماد کلی ]2[ و ]4[ و ]5[ و انعکاس شباهت فازی¹ اعتماد و عدم اعتماد]3[. ویژگیهای فوق بر میزان اعتماد و عدم اعتماد تاثیر میگذارند زیرا هم رابطه اعتماد و عدم اعتماد را با توجه به رابطه بین دو کاربر و همسایگان آنها بررسی میکنند و هم به حل تعارض عقاید کاربران اطمینان دارند. همچنین نسبت به پراکندگی شبکه قوی‌تر عمل میکنند و سرعت قابل قبولی را برای اجرا به همراه دارند. از این رو، معیارهای انتخاب شده برای تعیین اعتماد نسبت به سایر ویژّگیها غالب میباشند. ویژگیهای فوق در روش پیشنهادی، یک راه حل مناسب برای پیش‌بینی پیوند مثبت و منفی در شبکههای اجتماعی فراهم میکند و به کاربران کمک میکند که تا به چه کسانی و به چه اندازه در شبکههای اجتماعی اعتماد داشته باشند. از آنجا که در میزان اعتماد و یا عدم اعتماد، قطعیت وجود ندارد، این معیارها براساس روشهای محاسبات فازی ارائه میشود.

همچنین در سالهای اخیر، الگوریتمهای توصیهگر، مورد توجه قرار گرفتهاند. الگوریتم توصیهگر فیلترینگ مشارکتی یکی از پرکاربردترین تکنیک‌های الگوریتمهای توصیهگر است که از داده‌های رتبه‌بندی کاربر برای مدل‌سازی استفاده می‌کند. الگوریتم فیلترینگ مشارکتی، همراه با اطلاعات اجتماعی، با افزودن اطلاعات اجتماعی بین کاربران هنگام مدل‌سازی مشخص می‌شود. با الگوریتم فیلترینگ مشارکتی میتوان رابطه اعتماد را بر رتبه‌بندیهای پیش‌بینی شده برای انتخاب گرههای برتر بکار برد. با تاثیر مستقیم گرههای برتر بر رتبه‌بندیهای پیش‌بینی شده میتوان بر رابطه اعتماد تاثیرگذاری بیشتری داشت]6[.

هر یک از معیارهای پیش‌بینی پیوند به صورت جداگانه و یا تلفیقی در ادبیات تحقیق مورد بررسی، مبتنی بر الگوریتمهای مختلف مورد بررسی قرار گرفته‌اند. اما ارائه روشی که بتواند این معیارها را به درستی انتخاب نموده تا به گونهای کنار هم قرار گیرند که بیشترین دقت پیش‌بینی را داشته باشد، ضروی میباشد. از آنجا که عدم قطعیت در شناسایی رابطه کاربران و امتیازدهی آیتم‌ها وجود دارد، ترکیب این معیارها برای پیش‌بینی اعتماد و عدم اعتماد براساس سیستم‌های فازی انجام میشود.

بنابراین، نوآوری این تحقیق بر روی موارد ذیل متمرکز میگردد:

1. برای استخراج گرههای برتر، یک روش انتخاب پیشنهاد می‌شود که گرههای برتر را براساس دو ویژگی میزان اعتماد و ویژگی مثبت گرهها محاسبه میکند.

2. به منظور حل مسئله پراکندگی بین کاربران در شبکهها و افزایش دقت در تشخیص اعتماد، یک روش پیش‌بینی پیوند بین کاربران براساس ترکیب مجموعه از ویژگیها استفاده می‌شود که این ویژگیها عبارتند از: ویژگیهای انعکاس شباهت فازی اعتماد و عدم اعتماد و مجموعه ویژگیهای مرتبط با آن و اعتماد کلی و عدم اعتماد کلی با مجموعه ویژگیهای مرتبط با آن.

3. به منظور پیش‌بینی اعتماد و عدم اعتماد در شبکههای اجتماعی علامتدار، یک سیستم فازی مبتنی بر ویژگیهای فوق طراحی میشود.

ادامه این مقاله به این صورت سازماندهی میشود: بخش دوم به کارهای مرتبط با شبکههای اجتماعی علامتدار میپردازد. مدل پیش‌بینی پیوند پیشنهادی در بخش سوم توصیف خواهد شد. بخش چهارم مجموعه دادهها و معیارهای ارزیابی مورد استفاده برای تجزیه و تحلیل شبکههای اجتماعی علامتدار و مطالعه آزمایش‌های روش پیشنهادی را مورد بررسی قرار خواهد داد. نهایتا، در فصل پنجم، نتیجه‌گیری از یافتههای کار خود به همراه برخی از جهتگیریهای تحقیقاتی آینده ارائه خواهد شد.

2- کارهای مرتبط

به عنوان زمینه تحقیقاتی پایه شبکههای اجتماعی، پیش‌بینی پیوند به طور روزافزون جامعه تحقیقاتی این زمینه را به خود جذب کرده است. تحقیقات متعددی برای مشکل پیوندهای گمشده و مقابله با مشکل پراکندگی در شبکه‌های اجتماعی علامت‌دار² انجام شده که برخی فقط بر اعتماد تمرکز میکنند، برخی دیگر هم بر اعتماد و هم بر عدم‌‌اعتماد. هریک از تحقیقات مورد بررسی در ادبیات موضوع، دارای روش پیشنهادی متفاوتی میباشند. به طورنمونه برخی از آنها مبتنی بر روشهای بانظارت و برخی مبتنی بر روشهای بدون نظارت هستند، برخی از روشها احتمالاتی و برخی مبتنی بر منطق ذهنی هستند و یا برخی از روشها براساس معیارهای تعاملی محلی و برخی براساس معیارهای تعاملی سراسری میباشند. با توجه به اینکه الگوریتمهای پیش‌بینی پیوند براساس معیار شباهت، دقت کمتری را نسبت به برخی از روشها به دلیل دامنه کاربردها ایجاد میکند، اخیراً، روشهای بیشماری برای پیش‌بینی پیوند ارائه شده است که در ادامه برخی از آنها مورد بررسی قرار میگیرد. پیش‌بینی پیوند در شبکههای اجتماعی به چهار روش مبتنی بر شباهت، مبتنی بر احتمالات، مبتنی بر الگوریتم و روشهای ترکیبی تقسیم میشوند که هر یک از این گروهها، خود شامل زیر گروههایی میباشد که در آن گروه بررسی میگردد ]7[.

2-1- رویکردهای پیش‌بینی پیوند مبتنی بر شباهت

روشهای پیش‌بینی پیوند مبتنی بر معیار شباهت به سه گروه: شاخصهای محلی، شاخصهای سراسری و شاخصهای شبه محلی تقسیم میشوند. به منظور بررسی معیارهای شباهت، هدف کار ژو و ما ]8[، پیش‌بینی علامت با دو شاخص: شباهت و اعتبار ترجیحی بود. شاخص اندازهگیری شباهت-عدم شباهت برای ویژگیهای مشترک جفت گرهها استفاده میشود تا تعادل اجتماعی را نگه دارد و تئوری حالت را حفظ کند. مزیت اندازهگیری ویژگیهای مشترک جفت گرهها در مدل پیش‌بینی پیشنهادی منجر میشود که به بهترین شکل از دادههای موجود برای پیش‌بینی علامت پیوندهای از دست رفته استفاده شود. اما اشکال آن است که فقط دو شاخص اندازهگیری شباهت-عدم شباهت در اعتبارسنجی مدل، استفاده میگردد. شا وراس دی سنا روسا و همکاران ]9[، از خوشهبندی محلی برای یافتن گروهی از اشیاء مشابه استفاده نمودند که مزیت آن توانایی بهرهبرداری از ساختارهای همبستگی متعدد بین کاربرانی میباشد که ترجیحات خود را برای اشیایی که احتمالاً دارای ویژگی‌های مشابه هستند، بیان میکنند. اما این روش حساس به رتبهبندی اختصاص یافته موجود به هر خوشه میباشد و نیاز به حافظه و زمان بیشتری برای ذخیره خوشهها دارد. در روشهای مبتنی بر شباهت شبه محلی، قربان زاده و همکاران]10[ به بررسی ارتباط بین گرهها با معیارهای محلی ترکیبی و رابطه همسایهها و تعداد همسایههای مشترک با توجه به مرکزیت و اعتبار همسایههای مشترک پرداختند و پیش‌بینی پیوند بین دو گره که همسایگی مشترک ندارند، را بررسی نمودند. ونگ و همکاران]11[، به بهبود فیلترهای مشترک مبتنی بر همسایگی با استفاده از ترکیب معیارهای شباهت ترکیبی پرداختند و به مزایایی مانند عدم درج اطلاعات کاربران یا گزینهها و کاهش زمان و حافظه مصرفی اشاره نمودند، اما مدیریت پویا بودن ترجیحات کاربر امکان پذیر نبود. ایکسیو و همکاران ]12[، به ارزیابی اعتماد در شبکههای اجتماعی علامت دار براساس شبکه عصبی مبتنی بر مکانیسم توجه دوسطحی با ویژگیهای سراسری کاربران پرداختند. ویژگی‌های برتر کار ایشان، مکمل بودن داده‌های کاربران با یکدیگر، بررسی همزمان اطلاعات همسایگان مورد اعتماد کاربران و تداوم زمانی رفتارهای کاربران میباشد.

2-2- رویکردهای پیش‌بینی پیوند مبتنی بر احتمالات

روشهای پیش‌بینی پیوند مبتنی بر معیار احتمالات به چهار گروه: مدل فاکتورسازی تانسور احتمالی، مدل متغیر پنهان احتمالی، مدل مارکوف و مدلسازی برچسب پیوند تقسیم میشوند. در بررسی روشهای مبتنی بر احتمالات، ونگ و همکاران ]13[ بیان نمودند که پیش‌بینی پیوند در شبکه اطلاعات ناهمگن براساس یک روش یادگیری عمیق گراف بهبود یافته برای یادگیری تعبیه راس پیش‌بینی شده با حداقل اطلاعات ازدست رفته برای کشف جوامع محلی بکار میرود و مزایای این روش عبارت است از: کشف جامع با شباهت درون جامعه و بین جامعه، استفاده از ویژگیهای ذاتی موجودیتهای مختلف شبکه و یک لایه هسته بهینهسازی شده برای معیار شباهت تعبیه شده در راسهای جفت نودها. طهماسبی و همکاران ]14[، در حیطه فعالیت فاکتورسازی ماتریس، مدل فاکتورسازی ماتریس جمعی زمانی و اجتماعی برای سیستمهای توصیه کننده برحسب تنظیمات ترجیحی کاربر با مرور زمان را بررسی نمودند و هدف آنها جمع اطلاعات رتبه‌بندی کاربران و اطلاعات اعتماد اجتماعی به طور مشترک در روش فاکتورسازی ماتریس و قابلیت توسعه روش پیشنهادی بر روی مجموعه دادههای بزرگ با میلیونها کاربر و گزینه بود، اما مشکل آن بود که تعاملات کاربران در هر زمان را براساس اعتماد ضمنی و نه براساس اعتماد صریح بررسی کردند. همچنین مشکل کاربران مبتدی (شروع سرد) که هیچ رتبه و هیچ رابطه اعتمادی نداشتند را حل نکردند. ژانگ و همکاران]15[، به بررسی الگوریتم توصیه اجتماعی مبتنی بر تجزیه ماتریس تصادفی در شبکه اجتماعی با ایجاد یک ماتریس برای شبکه اجتماعی و یک ماتریس برای رتبه‌بندی کاربر پرداختند و تابع هدف فاکتورسازی ماتریس را با قاعده گذاری اجتماعی طراحی نمودند. مزیت روش ایشان، ترکیب اطلاعات کاربران و امتیازدهی به آنها در یک ماتریس با الگوریتم فاکتورسازی ماتریس بود، اما ایراد آن، تاثیر محدود بودن جستجو به کاربرانی که با هم در ارتباط هستند، بر روی پیشنهادات جستجو بود. هی و همکاران ]16[، به بررسی روش مبتنی بر شباهت با استخراج اطلاعات شباهت گره و اطلاعات ساختار هندسی توپولوژی پیوند و فاکتورسازی ماتریس نیمه غیرمنفی باینری منظم برای حفظ همپوشانی تشخیص جوامع پرداختند و اهداف همپوشانی تشخیص جوامع و تقسیم گرهها به خوشههای مختلف با پیوندهای مثبت درون خوشهای و پیوندهای منفی بین خوشه ای را دنبال کردند، اما با توجه به میلیونها گره در شبکههای اجتماعی، زمان مصرفی الگوریتم ایشان بالا بود. نصیری و همکاران]17[، منظمسازی نمودار محکم فاکتورسازی ماتریس غیر منفی برای پیش‌بینی پیوند در شبکههای مورد بررسی را برای مکمل بودن ساختار توپولوژیکی و ویژگیهای گرهها در پیش‌بینی پیوند ارزیابی نمودند.

2-3- رویکردهای پیش‌بینی پیوند مبتنی بر الگوریتم

روشهای پیش‌بینی پیوند مبتنی بر معیار الگوریتم به سه گروه: فراابتکاری، فاکتورسازی ماتریس و یادگیری ماشین تقسیم میشوند. در بررسی روشهای مبتنی بر الگوریتم، یاگی و همکاران ]18[، هدف از تحقیق خود را پیش‌بینی پیوند با استفاده از ترکیب شبکه عصبی و الگوریتمهای تکاملی: ژنتیک، یهینهسازی ازدحام ذرات و جستجوی حشرات بیان نمودند و مزیت کار ایشان، استفاده از شبکه عصبی به عنوان دستهبند برای مجموعه داده پیش‌بینی پیوند و مدیریت توزیع نامتوازن مجموعه داده با تکنیک نمونهبرداری و میانگینگیری به عنوان تابع برازندگی بود. سریلاتا و همکاران]19[، پیش‌بینی پیوند در شبکههای اجتماعی با الگوریتم بهینهسازی کرم شبتاب براساس اطلاعات ویژگی گرهها را معرفی نمودند و از پیش‌بینی پیوند مبتنی بر کرم شبتاب برای بهبود عملکرد روش شباهت بهره بردند. مزیت کار ایشان، استفاده از گرههای اجتماعی و ترکیب ویژگیهای آنها با همدیگر بود. گیو و همکاران ]20[، شباهت توپولوژیکی نزدیکترین همسایهها در یک شبکه هدایت شده را برای حل مشکل بررسی جهت لبه و اطلاعات گره شبکه پیشنهاد کردند. در ابتدا، این مطالعه باعث بهبود شاخص سورنسن در شبکه‌های هدایت شده شد و سپس شکل ماتریسی هر شاخص پایه را با جبر ماتریسی بیان کردند. نهایتا توپولوژی نزدیکترین همسایگان هر شاخص پایه را برای به دست آوردن شاخص شباهت توپولوژیکی نزدیکترین همسایهها استخراج نمودند. نورایی آباده و میرزایی ]21[، به بررسی روش یادگیری ماشین برای استخراج ویژگیها در پیش‌بینی ارزش اعتماد شبکههای اجتماعی علامت دار پرداختند تا به درک ماهیت پویای شکل‌گیری و تکامل گروه در شبکه‌های اجتماعی برای توصیف بهتر نحوه جمع‌آوری گره‌های اعتماد افراد و تشکیل جوامع دست پیدا نمایند. تیلمن و همکاران ]22[، پیش‌بینی پیوند شبکههای چندسطحی با سه الگوریتم مبتنی بر تعداد و سطح را بررسی نمودند و از ساختار همبستگی نوع ارتباطات براساس یک آستانه تئوری در شبکههای دنیای واقعی بهره بردند، اما تعریف دقیق مقدار آستانه با توجه به مولفههای الگوریتم امکانپذیر نبود.

2-4- رویکردهای پیش‌بینی پیوند مبتنی بر روشهای ترکیبی

در بررسی روشهای ترکیبی که براساس ترکیب روشهای مذکور میباشد، لیو و همکاران]23[، پیش‌بینی احتمالات با شبکه کانولوشن گراف برای شناسایی مجدد افراد را بررسی نمودند و اهدافی از جمله: تشکیل یک زیرگراف نمونه برای هر گره با اطلاعات متنی محلی مبتنی بر یادگیری و مبتنی بر اطلاعات غنی از گرههای مرکزی، انعطافپذیری و اثربخشی روش پیشنهادی را بیان نمودند، اما برای یادگیری شبکه، استخراج ویژگی و تخمین شباهت میتوانستند روشهای قویتر بکار ببرند. هیو و همکاران ]24[، به منظور رد شایعات به موقع و در زمان واقعی به منظور اعتمادسازی، ترکیبی از الگوریتمهای بهینه سازی جهش قورباغه و بهینه سازی ازدحام ذرات پیشنهاد دادند که برای ایجاد اعتماد از سه ویژگی درجه صمیمیت، قابلیت اطمینان و اعتبار استفاده نمودند و دو زیر الگوریتم برای تکذیب شایعات به موقع و تکذیب سریع شایعات برای مسدود کردن مداوم شایعات در طول تکامل حقایق در هر خوشه را بکار بردند.

با بررسی تحقیقات انجام شده در زمینه ادبیات موضوع مشخص گردید که در کارهای انجام شده برای روشهای مبتنی بر شباهت، علی رغم مزایای آنها، معایبی وجود دارد. به طور نمونه در کارهای ]8[ و ]9[، فقط معیارهای محلی مسئله در شبکههای اجتماعی مورد بررسی قرارگرفتهاند. درحالیکه کاربرد معیارهای محلی و سراسری در کنار یکدیگر در بهبود دقت پیش‌بینی پیوند تاثیر بسزایی خواهد داشت. در کارهای]10[ و ]12[، مدل شبکههای اجتماعی براساس گرافهای بدون علامت هستند و از نوع گرافهای جهت دار، علامتدار و یا وزنی استفاده نشده است که میتوان از ترکیب این ویژگیها استفاده نمود. به منظور بررسی دقیق پیوند بین گرهها، میتوان از ویژگیهای مناسب و همچنین ترکیب ویژگی‌ها ]8[ و ]11[، استفاده نمود. در بین روش‌های احتمالی برای پیش‌بینی پیوند در کارهای ]10[ و ]23[، مشخص شد می‌توان از سایر الگوریتمها برای آزمایش عملکرد روش پیشنهادی و همچنین اعمال روشهای قوی برای یادگیری شبکه، استخراج ویژگی و تخمین شباهت برای بهبود پیش‌بینی پیوند استفاده نمود. همچنین با ترکیب اطلاعات کاربران و امتیازدهی به آنها در یک ماتریس واحد، الگوریتم توصیه اجتماعی دوست پیشنهاد میشود که فضای جستجو هدف آن محدود میباشد. میتوان فرایندهای جستجو را بر روی کاربران بیشتری که با هم در ارتباط هستند، اعمال نمود تا فضای جستجو و الگوریتم جستجوی جدیدی را بکار برده تا نحوه امتیازدهی به کابران دقیق گردد]15[. برای روشهای فراابتکاری مبتنی بر پیش‌بینی پیوند، میتوان از سایر الگوریتمهای تکاملی جهت بررسی فرایند بهبود پیش‌بینی پیوند استفاده نمود ]19[و ]23[. از ویژگیهای مطرح شده برای الگوریتمها به صورت ترکیبی در مابقی الگوریتمهای این گروه استفاده میشود تا میزان تاثیرگذاری ویژگیها در شرایط متفاوت بررسی گردد. در شبکههای چند سطحی به منظور حفظ ساختار همبستگی نوع ارتباطات براساس یک آستانه تئوری در شبکههای دنیای واقعی میتوان استفاده نمود. اما تعیین دقیق مقدار آستانه با توجه به مولفههای الگوریتم، بسیار مهم میباشد تا براساس آن بتوان به نتایج بهتری در پیش‌بینی پیوند دست یافت. همچنین تعییین ساختار همبستگی مشخص برای شبکههای چندسطحی در رسیدن به این هدف، بسیار حائز اهمیت میباشد]22[. با بررسی کارهای انجام شده در زمینه فاکتورسازی ماتریس مشاهده شد که برای پیش‌بینی پیوند اطلاعات رتبه‌بندی کاربران و اطلاعات اعتماد اجتماعی به طور مشترک در روش فاکتورسازی ماتریس جمع آوری شده است. تعاملات کاربران در هر زمان براساس اعتماد ضمنی بررسی میشود و اعتماد صریح نادیده گرفته شده است و حل مشکل کاربران مبتدی (شروع سرد) که هیچ رتبه و هیچ رابطه اعتمادی ندارند، بررسی نشده است]14[. به منظور همپوشانی گرهها در تشخیص جوامع، تقسیم گرهها به خوشههای مختلف با پیوندهای مثبت درون خوشهای و پیوندهای منفی بین خوشهای انجام میشود که این فرایند منجر به نادیده گرفتن زمان مصرفی و نهایتا بالا رفتن زمان مصرفی الگوریتم با توجه به میلیونها گره در شبکههای اجتماعی میشود. به منظور بهبود پیش‌بینی پیوند و زمان مصرفی میتوان بررسی همسایگی و نزدیکی گرهها در مرتبه اول و دوم را بررسی نمود]16[.

در تحقیقات مبتنی بر روش یادگیری ماشین مشخص گردید که روشهای مبتنی بر یادگیری عمیق، به علت بررسی چندسطحی، نتایج دقیقتری فراهم مینمایند. ولی به نسبت، زمان مصرفی بیشتری به علت چندسطحی بودن دارند]13[. به منظور افزایش دقت در بهبود پیش‌بینی پیوند، میتوان از توابع برازندگی مختلف به خصوص توابع فازی استفاده نمود ]18[. در کار ] 19[ از روش‌های مبتنی بر شباهت برای پیش‌بینی پیوند استفاده شده است که هم جهت لبه شبکه را برای پیش‌بینی پیوندها در نظر میگیرد و هم از اطلاعات گرههای شبکه استفاده میکند.

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

3- روش پیشنهادی

در این تحقیق مدل پیشنهادی متفاوتی برای پیش‌بینی پیوند در شبکههای اجتماعی علامتدار براساس اطلاعات گرهها و قدرت پیوندها بین کاربران برای شبکههای اجتماعی علامتدار ارائه خواهد شد. مبنای اصلی برای روش پیشنهادی، مدل محاسباتی فازی است که مبتنی بر قدرت پیوندهای محاسبه شده از نظر مقادیر اعتماد-عدم اعتماد و انعکاس شباهت فازی اعتماد و عدم اعتماد بین کاربران شبکه است و به اصطلاح پیش‌بینی پیوند در شبکههای اجتماعی علامتدار با اعتماد و عدم اعتماد مبتنی بر فازی ³ نامیده میشود. الگوریتم روش پیشنهادی در شکل 1 نشان داده شده است. روش پیش‌بینی پیوند پیشنهادی، با بررسی احتمال وجود پیوند بین کاربران و آیتمها در آینده براساس روشهای مبتنی بر شباهت از جمله روش معیار میانگین واگرایی، میزان شباهتهایشان را بررسی میکند. نهایتا سیستم فازی ممدانی با چهار ورودی اعتمادکلی، عدم اعتمادکلی و انعکاس شباهت فازی اعتماد و عدم اعتماد طراحی میشود که خروجی سیستم فازی مبین اعتماد و یا عدم اعتماد با پیش‌بینی پیوند مثبت یا منفی میباشد.

مهم‌ترین مزیت روش پیشنهادی، استفاده از سیستمهای فازی طراحی شده مبتنی بر عدم قطعیت در بررسی میزان اعتماد و عدم اعتماد کاربران نسبت به یکدیگر در شبکههای اجتماعی به همراه ترکیب ویژگیهای موثر در تعیین میزان اعتماد میباشد. سایر مزایای ویژگیهای موثر مورد استفاده عبارتند از:

· فاکتور تشابه اولویت، تجربه و عمل متقابل در کار گریدهار و همکاران ]4[ و ]5[. این ویژگیها هم اطلاعات محلی و هم اطلاعات سراسری کاربران را در مورد پیوندهای متقابل بین کاربران و نظریه تعادل اجتماعی براساس اعتماد و عدم اعتماد بررسی میکند.

· ویژگی صفات اجتماعی محلی در کار اکیلال و همکاران ]2[، خصوصیات اجتماعی بسیاری وجود دارند که بر اعتماد تاثیر می‌گذارند، علت انتخاب این ویژگی، سادگی و سهولت درک آنها می‌باشد. علاوه براین، مزایای دیگری مانند انعطافپذیری و قوی بودن نسبت به پراکندگی شبکههای اجتماعی و صحت بالا را دارد.

· ویژگیهای محلی و سراسری مبتنی بر خوشه‌بندی⁴ ]25[: براساس معیارهای شباهت با تعیین ویژگی‌های جدید مربوط به موقعیت و رفتار دینامیکی گره‌ها انجام میشود.

· ویژگی انعکاس شباهت فازی در کار شیرگاهی]3[، مبتنی بر اطلاعات محلی بوده و نیاز به تصمیمگیری سراسری ندارد. از اینرو، روشی توزیع شده است و علاوه بر دقت بالا، سرعت قابل قبولی دارد. با ترکیب ویژگیهای اثرگذار و ارائه راهکار سیستم فازی، مقیاس‌های، صحت، دقت و فراخوانی بهبود مییابند.

جدول 1 خلاصهای از نمادها و علائم را نشان میدهد.

[1] Fuzzy Trust Mirroring

[2] Sparsity in Signed Social Networks

[3] link prediction in signed social networks with fuzzy model -based trust and distrust (LPSSN-FTD)

[4] Local and Global Clustering (LGC)

شکل 1. بلوک دیاگرام روش پیشنهادی

3-1- معیارمیانگین واگرایی مبتنی بر محاسبه اعتماد-عدم اعتماد

مقداردهی اولیه، براساس اطلاعات موجود در مورد کاربران است که میزان شباهت کاربران را براساس اولویت‌هایشان بررسی می‌کند. برای این منظور، می‌توان از معیارهای مبتنی بر شباهت استفاده نمود که در این تحقیق از روش معیار میانگین واگرایی¹ بهره گرفته می‌شود. معیار میانگین واگرایی برای محاسبه شباهت در رتبه‌بندی کاربران براساس عادات رتبه‌بندی به منظور پیوند آینده بین کاربر و کاربر استفاده می‌گردد. MMD بین یک جفت کاربر می‌تواند با رابطه (1) محاسبه می‌شود]26[:

جدول 1. خلاصه ای نمادها و علائم
علائم	توصیف	علائم	توصیف
	وزن یال از گره u به گره v		فاصله اقلیدسی بین بردارهای u و v
	آیتم‌های مورد علاقه کاربر u		آیتمهای غیرعلاقه توسط کاربر u
	تعداد کل گرهها در اعتماد مستقیم به گره i	M	ماتریس مجاورت با سطرها و ستونهای برای نام گرهها
	مقدار اعتماد مستقیم از گره i به گره j		تعداد همسایگان گرهv
	مقدار اعتماد مستقیم گره i به گره j		برداری براساس بردار رتبه‌بندی کاربر
	قدرت برخوردهای منفی از کاربر j		قدرت برخوردهای مثبت از کاربر j
	بایاس کاربر		بایاس آیتم
	بردار ویژگی پنهان d بعدی آیتم j	،	بردار ویژگی پنهان d بعدی کاربر u
μ	میانگین رتبه‌بندی کلی	α	رابطه وزنی بین اولویت گره و اولویت برتر
Experts	گره‌های برتر انتخاب شده		وزن اعتماد گره u به گره برتر e
	اعتبار گره i		بردار رتبه‌بندی کاربر

پس وجود پیوند آینده بین کاربر و کاربر با چک کردن شباهت بین آنها پیش‌بینی خواهد شد. اگر شباهت بین دو کاربر بیشتر یا مساوی با مقدار آستانه مطابق رابطه (1) باشد، پس میتوان پیوند آینده را پیش‌بینی کرد؛ در غیر این صورت، اگر شباهت کمتر از مقدار آستانه باشد، پیش‌بینی پیوند با اطلاعات موجود امکان پذیر نیست و از این رو هیچ پیش‌بینیای وجود نخواهد داشت.

مقدار آستانه با رابطه (2) تعریف میشود:

(1)

اگر مقدار آستانه بالاتر باشد، کاربران تشابه بیشتری دارند (و بالعکس) و به این ترتیب، صحت پیش‌بینی پیوند گمشده بین کاربران افزایش می‌یابد. با این حال، از آنجا که مجموعه دادههای دنیای واقعی بسیار پراکنده هستند، مقدار آستانه بالا منجر میشود که شانس یافتن کاربران مشابه کاهش یابد.

3-2- انتخاب گره‌های برتر

در این بخش، رابطه اعتماد براساس بردار ویژگی تعیین میشود تا گرههای برتر تولید شوند. در واقع، رابطه اعتماد در تعیین گرههایی با اولویت بیشتر تاثیر میگذارد]6[.

· تعریف 1: درجه اعتماد و نگرش مثبت در شبکههای اجتماعی، اگر گرهها بارها مورد اعتماد واقع شوند، احتمال برتر شدن آنها بیشتر میشود. درجه اعتماد کاربر u با تعداد کاربران مورد اعتماد تعیین می‌شود. مقدار و با رابطه (3) و (4) محاسبه می‌شود ]6[:

(2)

که در آن ، max و minبه ترتیب حداکثر و حداقل مقدار اعتماد کاربر، k درجه اعتماد کاربر u و Nu تعداد آیتم‌های رتبه‌بندی کاربر u برای مقادیر بیشتر از 3 را نشان می‌هد، اگر مقدار رتبه‌بندی هر کاربر برای هر آیتم بیشتر از 3 باشد، نگرش مثبت ایجاد ‌شده و کاربر در فرایند رتبه‌بندی فعال‌تر می‌شود.

· تعریف 2: با تعریف 1، می‌توان هر گره را به یک گره اولیه براساس رابطه (5) تبدیل نمود:

(3)
(4)

که ، به صورت نزولی مرتب شده و چند مقدار اول به عنوان مجموعه گرههای برتر اولیه در نظر گرفته میشود.

· تعریف 3: براساس تعریف 2، هر کاربر میتواند به گره برتر اولیه تبدیل شود. ابتدا تعداد گره برتر اولیه تعیین میگردد، گرههای برتر اولیه براساس تعداد دفعاتی که مورد اعتماد هستند تعیین و رتبه‌بندی می‌شوند. کاربران در n تای بالا به عنوان برتر انتخاب می‌شوند. ویژگی‌های گرههای برتر عبارتند از: 1- از اطلاعات رتبه‌بندی و اعتماد برای تعریف گره استفاده می‌شود. 2- باتوجه به ویژگیهای گرههای برتر، تعداد دفعات اعتماد و نگرش مثبت رتبه‌بندی تعیین می‌شود. 3- گره‌های مورد اعتماد گرههای برتر اولیه، کاملاً بررسی می‌شوند. رتبه‌بندی پیش‌بینی برای گرههای برتر در رابطه (6) تعریف می‌شود]6[:

(5)

کاربر مورد اعتماد به طور غیرمستقیم با تغییر بردار ویژگی کاربر بر رتبه‌بندی‌های پیش‌بینی تأثیر می‌گذارد، پس بردار ویژگی کاربر با بردار ویژگی دوست مورد اعتماد نزدیک میشود، یعنی: . رتبه‌بندی نهایی پیش‌بینی براساس رابطه (7) است ]6[:

(6)

3-3- محاسبه انعکاس شباهت فازی اعتماد و عدم اعتماد

در این مرحله برای تعیین اعتماد و عدم اعتماد بین دو گره، از سیستم فازی استفاده میشود. این بخش از روش پیشنهادی انعکاس شباهت فازی مبتنی بر اعتماد و عدم اعتماد² نامیده میشود که مبتنی بر ویژگیهایی از جمله مرتبه ورودی و خروجی، کیفیت مرتبه ورودی و خروجی و چگالی محلی ورودی و خروجی است که در ادامه شرح داده میشوند. سپس، ترکیبی از ویژگیهای ذکر شده بیان میگردد تا میزان شباهت بین دو گره بدست آید. نهایتا، مقدار انعکاس شباهت فازی اعتماد و عدم اعتماد براساس میزان تشابه محاسبه میشود. محدوده مجموعههای فازی، قواعد و ساختار سیستمهای فازی براساس مقادیر محاسبه شده ویژگیهای مطرح شده در گرهها تعیین میگردد. دامنه متغیرهای ورودی و خروجی مجموعههای فازی براساس بخشهایی از مجموعه دادههای Epinions تعیین میشود تا توزیع نسبتاً مساوی از دادهها در این مجموعهها وجود داشته باشد. تمام توابع مجموعههای فازی برای متغیرهای ورودی و خروجی پارامترها به صورت ذوزنقه ای یا مثلثی هستند و سه مجموعه فازی کم، متوسط و زیاد برای ویژگیهای ورودی و ویژگیهای خروجی در نظر گرفته میشود]3[.

ابتدا اعتبار هر گره براساس رابطه (8) محاسبه میشود:

(7)

ویژگیهای موثر در محاسبه انعکاس شباهت فازی به شرح زیر معرفی میگردند:

· مرتبه بیرونی، پارامتری است که میگوید تا چه حد یک کاربر در یک شبکه با اطلاعات سایر کاربران ارتباط دارد]3[.

(8)

· مرتبه درونی، پارامتری است که اطلاعات یک کاربر را از سایر کاربران دریافت میکند. مرتبه درونی تعداد پیوندهای ورودی با کاربر کانونی نسبت به مقدار حداکثر آن است]3[.

(9)

· کیفیت رتبه بیرونی و کیفیت رتبه درونی میزان دستیابی به کاربران را که از کاربران دیگر میرسد یا رسیدن به دیگر کاربران را در دو مرحله میسنجد. بنابراین، این پارامترها میزان ارتباط یک کاربر با کاربران دیگر را نشان میدهد که خود دارای مرتبههای بالایی هستند]3[. کیفیت رتبه بیرونی با رابطه (11) تعریف میشود:

(10)

· کیفیت رتبه درونی با رابطه (12) تعریف میشود:

(11)

· چگالی محلی مرتبه بیرونی، میزان انتقال اطلاعات کاربر به همسایگان متصل را اندازه‌گیری میکند]3[.

(12)

· چگالی محلی مرتبه درونی، میزان اطلاعات بدست آمده کاربر از همسایگان متصل را اندازه‌گیری میکند.

(13)

پس از محاسبه شباهت بین گرهها، براساس سیستم ممدانی فازی با شش ورودی از هر یک از ویژگیها: مرتبه ورودی و خروجی، کیفیت مرتبه ورودی و خروجی و چگالی محلی ورودی و خروجی به صورت جداگانه، یک خروجی با مقدار تشابه کلی محاسبه میشود. انعکاس شباهت فازی براساس مقدار شباهت کلی با توجه به آگاهی خاص هر گره از مقدار اعتبار سراسری آن، با رابطه (15) محاسبه میشود:

(14)

نهایتا نتایج حاصل از روش انعکاس شباهت فازی مبتنی بر اعتماد و عدم اعتماد محاسبه میگردد. هدف از انعکاس شباهت فازی، تصمیم‌گیری بر این موضوع است که آیا اعتماد یا عدم اعتماد وجود دارد یا خیر؟. که براساس رابطه (16) محاسبه میشود:

(15)

3-4- محاسبه فاکتورهای اعتماد کلی و عدم اعتماد کلی

در این مرحله ابتدا برای تعیین اعتماد کلی و عدم اعتماد کلی بین دو گره، از پنج ویژگی: تشابه اولویت، تجربه، عمل متقابل، صفات اجتماعی محلی و چگالی اشتراک استفاده میشود که به شرح زیر میباشند. سپس براساس روابط میانگین وزنی مقدار اعتماد کلی و عدم اعتماد کلی بین دو گره محاسبه میشود. این بخش از روش پیشنهادی، اعتماد کلی و عدم اعتماد کلی در شبکههای اجتماعی علامت دار³ نامیده میشود.

· تشابه اولویت

تشابه اولویت نشان میدهد که اعتماد کلی ایجاد شده در بین کاربران شبکه براساس شباهتها و تمایزات اجتماعی مانند علاقه به گزینههای مشترک یا عنوانهای⁴ مشترک میباشد. تشابه اولویت مبتنی بر اعتماد در رابطه (17) و مبتنی بر عدم اعتماد در رابطه (18) محاسبه میشود]5[.

(16)

· تجربه

باعث میشود یک کاربر از هر چیزی یا همه چیز مربوط به برخوردهای گذشته خود با سایر کاربران تاثیر بگیرد. تجربه مبتنی بر اعتماد در رابطه (19) و مبتنی بر عدم اعتماد در رابطه (20) محاسبه میشود.

(17)
(18)

· عمل متقابل

اگر دو نفر به یکدیگر اعتماد داشته باشند، نفع و اگر بیاعتماد باشند، انتقام افزایش مییابد. عمل متقابل بین کاربر و مبتنی بر اعتماد در رابطه (21) و مبتنی بر عدم اعتماد در رابطه (22) محاسبه میشود]5[.

(19)	Trust_Exp(
(20)	Distrust_Exp(

در اینجا، بیانگر قابلیت اطمینان است که بدون داشتن اطلاع یا عدم اطمینان در ارزش متقابل اعتماد بین کاربر و کاربر است. مقدار توافق بین کاربر و کاربر است. اختلاف بین کاربر و کاربر است.

· صفات اجتماعی محلی

صفات اجتماعی محلی عبارتند از: زودباوری، بدگمانی، شایستگی، عدم شایستگی و عمل متقابل. این ویژگی ترکیبی از مجموعه ویژگیهای مرتبط با آن است که با رابطه (23) محاسبه میشود ]2[:

(21)	Trust_Rec(
(22)	Distrust_Rec(

که در آن براساس حاصلجمع زودباوری و شایستگی، براساس حاصلجمع بدگمانی و عدم شایستگی و براساس حاصلجمع عمل متقابل گره نسبت به سایر گرهها و عمل متقابل نسبت به سایر گرهها محاسبه میشود. برای محاسبه مقدار اعتماد و عدم اعتماد براساس این ویژگیها از رابطه (24) استفاده میگردد:

(23)

· چگالی اشتراک

چگالی تعداد دوستان مشترک گره‌های u و v در شبکه اجتماعی است]25[. چگالی اشتراک مبتنی بر اعتماد در رابطه (25) و مبتنی بر عدم اعتماد در رابطه (26) محاسبه میشود.

(24)

به منظور محاسبه چگالی دادهها، از ضریب خوشهبندی به صورت رابطه (27) استفاده میشود]25[.

(25)
(26)

4- ارزیابی روش پیشنهادی

این بخش شامل معرفی مجموعه دادههای مورد استفاده برای ارزیابی روش پیشنهادی در بخش 4-1، معرفی الگوریتمهای مورد مقایسه در بخش 4-2، و همچنین معیارهای مورد استفاده برای ارزیابی کارایی و عملکرد مدلهای پیشنهادی در بخش 4-3 میباشد. علاوه بر این، آزمایش‌های مختلفی بر روی مجموعه داده‌های شبکههای اجتماعی در بخش 4-4 توصیف می‌شود. نهایتا در بخش 4-5، به بحث و کنکاش روش پیشنهادی میپردازد.

4-1- توصیف مجموعه دادهها

مجموعه داده Epinions شامل هفت جدول تحت عنوان: شباهت، اعتماد، کاربر، نظرات، تجارت، آیتمها و دستهبندی میباشد که ویژگیهای نظرات در مورد آیتمهای موجود را برای محاسبه معیارها استفاده میکند. آیتمها میتوانند به صورت محصول یا خدماتی باشند که هر کدام به یک دسته منحصر به فرد تعلق دارند. امتیاز در رتبه‌بندی [1-5] میباشد که 1 نشان‌دهنده کمترین و 5 نشان‌دهنده بالاترین امتیاز است که میتواند توسط یک کاربر به یک آیتم داده شود. این مجموعه داده از 2 فایل تشکیل شده است : 1- تعداد کاربران، آیتمها، نظرات و رتبه‌بندیهای ارائه شده توسط کاربران به آیتمها، 2- وضعیتهای اعتماد ارائه شده توسط کاربران که در جدول 2 نشان داده شده است]27[.

مجموعه داده Slashdot یک وب سایت خبری اجتماعی است که بر تعاملات و بحثهای فناوری و جامعه تمرکز دارد. در Slashdot، به جای تشکیل رتبه‌بندی کاربر به آیتمها ، رتبه‌بندیهایی به صورت کاربران با برچسب گذاری آنها به عنوان "دوست" (رتبه بالا) یا "دشمن" (رتبه پایین) ارائه میشوند. هیچ رتبه خنثی در Slashdot وجود ندارد و کاربران میتوانند دیگران را به عنوان دوست یا دشمن اضافه کنند که به صورت پیوندهای مثبت و پیوندهای منفی در توپولوژی شبکه نمایش داده میشوند. آیتمها همان خود کاربران شبکه هستند که رتبهبندی را دریافت میکنند و کاربران افرادی هستند که حداقل یک امتیاز را میدهند که از این ویژگیها به عنوان محاسبه معیارها استفاده میشود. تعداد کاربران و آیتمها در جدول 2 نشان داده شده است]28[.

جدول 2. اطلاعات مجموعه داده

(27)

تعداد مثلثات	تعداد آیتمها	تعداد کاربران
1624481	508837	75879	Epinions
602592	948464	82168	Slashdot

مقایسههای روش پیشنهادی و کارهای پیشین بر روی دادههای یکسان از مجموعه دادهها انجام گردیده است.

4-2- الگوریتمهای مورد ارزیابی

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

· پیش‌بینی پیوند مبتنی بر اطلاعات محلی و سراسری⁵ ]5[: یک مدل محاسباتی فازی مبتنی بر اعتماد و عدم اعتماد است که در دو مدل پیش‌بینی پیوند مختلف مبتنی بر اطلاعات محلی و اطلاعات محلی-سراسری برای غلبه بر مشکل پراکندگی در شبکههای اجتماعی علامتدار پیشنهاد شده است.

· قابلیت ارزیابی-شایستگی-عمل متقابل⁶]4[: پیش‌بینی اعتماد و عدم اعتماد را در شبکههای اجتماعی علامتدار براساس فاکتورهای قابلیت ارزیابی، شایستگی و عمل متقابل انجام میدهد.

· ویژگیهای محلی و سراسری مبتنی بر خوشه‌بندی⁷ ]25[: یک الگوریتم خوشه‌بندی زیرفضایی برای گروه‌بندی اشیاء اجتماعی است که براساس معیارهای شباهت با تعیین ویژگی‌های جدید مربوط به موقعیت و رفتار دینامیکی گره‌ها انجام میشود.

4-3- معیارهای ارزیابی

برای اعتبارسنجی کارایی مدل پیشنهادی، از معیارهایی که در ادامه معرفی میشوند، استفاده میشود که برای محاسبه صحت و مسائل دستهبندی مناسب هستند. در ابتدا متغیرهای مورد استفاده در معیارها به صورت زیر تعریف میشود.

· صحت⁸: عبارتست از نسبت نمونههای صحيح پیش‌بینی شده به کل نمونههاي موجود:

در اینجا ، TP: مثبت درست⁹، TN : منفی درست¹⁰، FN: منفی غلط¹¹ و FP: مثبت غلط¹² را نشان میدهد.

· دقت¹³: عبارتست از نسبت ميزان نمونههاي مثبت پیش‌بینی شده که به درستي تشخيص داده شدهاند به کل نمونه‌های مثبت:

(28)

· فراخوانی¹⁴: عبارتست از نسبت ميزان نمونههايی که به درستی جز نمونههای مثبت پیش‌بینی شده به کل نمونههای مثبت واقعی:

(29)

[1] Mean measure of divergence (MMD)

[2] TD-Trust Mirroring

[3] Signed social networks based on total trust and distrust (SSN-TTD)

[4] Topics

[5] Local and Global Information based Link Prediction (LGILP)

[6] Gullibility, Competence, and Reciprocity (GCR)

[7] Local and Global Clustering (LGC)

[8] Accuracy

[9] True Positives (TP)

[10] True Negatives (TN)

[11] False Negatives (FN)

[12] Flase Positives (FP)

[13] Precision

[14] Recall

اشتراک گذاری

آدرس مقاله

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

رایمگ

پیوندهای سایت

مراکز مرتبط

پشتیبانی

صفحات رسمی