Manuscript ID : A-10-2618-1 Visit : 8172 Page: 175 - 185

Article Type: Original Research

A Neighbor-based Link Prediction Method for Bipartite Networks

Subject Areas :

Golshan Sondossi ¹ , alireza saebi ² , S. Alireza hashemi G. ³

1 - University student
2 - University student
3 - Academic staff

Received: 2020-11-11 Accepted : 2021-03-09 Published : 2021-09-04

Keywords:

Abstract :

Social network analysis’ link prediction has a diverse range of applications in different areas of science. Bipartite networks are a kind of complex network, which can be used to describe various real-world phenomena. In this article, a link prediction method for bipartite network is presented. Uni-partite link prediction methods are not effective and efficient enough to be applied to bipartite networks. Thus, to solve this problem, distinct methods specifically designed for bipartite networks are required. The proposed method is neighbor based and consisted of measures of such. Classic uni-partite link prediction measures are redefined to be compatible with bipartite network. Subsequently, these modified measures are used as the basis of the presented method, which in addition to simplicity, has high performance rates and is superior to other neighbor-based methods by 15% in average.

References:

M. Newman, Networks. Oxford university press, 2018.
[2] A. Alamsyah, “Social network data analytics for market segmentation in indonesian telecommunications industry,” 2017, pp. 1–5.
[3] O. Allali, C. Magnien, and M. Latapy, “Link prediction in bipartite graphs using internal links and weighted projection,” 2011, pp. 936–941.
[4] P. Wang, B. Xu, Y. Wu, and X. Zhou, “Link prediction in social networks: the state-of-the-art,” Science China Information Sciences, vol. 58, no. 1, pp. 1–38, 2015.
[5] V. Martínez, F. Berzal, and J.-C. Cubero, “A survey of link prediction in complex networks,” ACM computing surveys (CSUR), vol. 49, no. 4, pp. 1–33, 2016.
[6] E. Gündoğan and B. Kaya, “A recommendation method based on link prediction in drug-disease bipartite network,” 2017, pp. 125–128.
[7] E. Gündoğan and B. Kaya, “A link prediction approach for drug recommendation in disease-drug bipartite network,” 2017, pp. 1–4.
[8] S. Aslan, B. Kaya, and M. Kaya, “Predicting potential links by using strengthened projections in evolving bipartite networks,” Physica A: Statistical Mechanics and its Applications, vol. 525, pp. 998–1011, 2019.
[9] S. Aslan and B. Kaya, “Time-aware link prediction based on strengthened projection in bipartite networks,” Information Sciences, vol. 506, pp. 217–233, 2020.
[10] Y.-J. Chang and H.-Y. Kao, “Link prediction in a bipartite network using wikipedia revision information,” 2012, pp. 50–55.
[11] S. Xia, B. Dai, E.-P. Lim, Y. Zhang, and C. Xing, “Link prediction for bipartite social networks: The role of structural holes,” 2012, pp. 153–157.
[12] M. Medo, M. S. Mariani, and L. Lü, “Link prediction in bipartite nested networks,” Entropy, vol. 20, no. 10, p. 777, 2018.
[13] C. Zhang, E. Chan, and A. Abdulhamid, “Link prediction in bipartite venture capital investment networks,” CS224-w report, Stanford, 2015.
[14] W. Wang, X. Chen, P. Jiao, and D. Jin, “Similarity-based regularized latent feature model for link prediction in bipartite networks,” Scientific reports, vol. 7, no. 1, pp. 1–12, 2017.
[15] X. Chen, D. Xie, L. Wang, Q. Zhao, Z.-H. You, and H. Liu, “BNPMDA: bipartite network projection for MiRNA–disease association prediction,” Bioinformatics, vol. 34, no. 18, pp. 3178–3186, 2018.
[16] D. Zhao, L. Zhang, and W. Zhao, “Genre-based link prediction in bipartite graph for music recommendation,” Procedia Computer Science, vol. 91, pp. 959–965, 2016.
[17] F. Xie, Z. Chen, J. Shang, X. Feng, and J. Li, “A link prediction approach for item recommendation with complex number,” Knowledge-Based Systems, vol. 81, pp. 148–158, 2015.
[18] Y. Cui, L. Zhang, Q. Wang, P. Chen, and C. Xie, “Heterogeneous network linkage-weight based link prediction in bipartite graph for personalized recommendation,” Procedia Computer Science, vol. 91, pp. 953–958, 2016.
[19] Y. Luo, Q. Liu, W. Wu, F. Li, and X. Bo, “Predicting drug side effects based on link prediction in bipartite network,” 2014, pp. 729–733.
[20] L. Zhang, J. Li, Q. Zhang, F. Meng, and W. Teng, “Domain knowledge-based link prediction in customer-product bipartite graph for product recommendation,” International Journal of Information Technology & Decision Making, vol. 18, no. 01, pp. 311–338, 2019.
[21] M. Koptelov, A. Zimmermann, B. Crémilleux, and L. Soualmia, “Link prediction via community detection in bipartite multi-layer graphs,” 2020, pp. 430–439.
[22] D. B. Larremore, A. Clauset, and A. Z. Jacobs, “Efficiently inferring community structure in bipartite networks,” Physical Review E, vol. 90, no. 1, p. 012805, 2014.
[23] G. Salton and J. Michael, “McGill,” Introduction to modern information retrieval, vol. 1, no. 4.1, pp. 4–1, 1986.
[24] A.-L. Barabâsi, H. Jeong, Z. Néda, E. Ravasz, A. Schubert, and T. Vicsek, “Evolution of the social network of scientific collaborations,” Physica A: Statistical mechanics and its applications, vol. 311, no. 3–4, pp. 590–614, 2002.
[25] T. Zhou, L. Lü, and Y.-C. Zhang, “Predicting missing links via local information,” The European Physical Journal B, vol. 71, no. 4, pp. 623–630, 2009.
[26] E. A. Leicht, P. Holme, and M. E. Newman, “Vertex similarity in networks,” Physical Review E, vol. 73, no. 2, p. 026120, 2006.
[27] L. A. Adamic and E. Adar, “Friends and neighbors on the web,” Social networks, vol. 25, no. 3, pp. 211–230, 2003.

Full-Text:

Article A-10-2618-1

دو فصلنامه علمي

فناوري اطلاعات و ارتباطات ایران

سال سیزدهم، شماره‌هاي 47 و 48، بهار و تابستان 1400

صص: 178_185

$E:\E Drive\logo\iicta Logo0.JPG$

یک روش پیش‌بینی پیوند مبتنی بر همسایه برای شبکه دوبخشی

گلشن سندسی* سید علیرضا هاشمی گلپایگانی**¹ علیرضا صائبی***

*دانش‌آموخته کارشناسی ارشد، دانشکده مهندسی کامپیوتر و فناوری اطلاعات، دانشگاه صنعتی امیرکبیر

** استادیار، دانشکده مهندسی کامپیوتر و فناوری اطلاعات، دانشگاه صنعتی امیرکبیر

***دانش‌آموخته کارشناسی ارشد، دانشکده مهندسی کامپیوتر و فناوری اطلاعات، دانشگاه صنعتی امیرکبیر

تاریخ دریافت: 21/08/1399 تاریخ پذیرش: 19/12/1399

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

چكیده

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

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

[1] نویسنده مسئول: سید علیرضا هاشمی گلپایگانی

sa.hashemi@aut.ac.ir

1 مقدمه

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

بر پایه گراف مانند مرکزیت، چگالی، قطر، ماژولاریتی و غیره بهره گرفت[2]. مصورسازی¹، تحلیل ساختاری شبکه²، تشخیص جوامع³، شبکه‌های جهان کوچک⁴، تحلیل موتیف‌ها⁵، پیش‌بینی پیوند⁶ و انتشار⁷ از جمله روش‌های مبتنی بر تحلیل شبکه اجتماعی هستند. از زمینه‌های به‌کارگیری تحلیل شبکه اجتماعی می‌توان به کسب‌وکارهای اینترنتی و بازاریابی الکترونیکی، علوم اجتماعی، توصیه‌گری، کشف تقلب و حوزه علوم سلامت اشاره کرد.

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

پیش‌بینی پیوند یکی از مسايل پراهمیت در ارتباط با شبکه و یکی از روش‌های اصلی در تحلیل شبکه اجتماعی است. در شبکه اجتماعی G(V,E) در زمان t، که V و E مجموعه گره‌ها و یال‌ها هستند، پیش‌بینی پیوند به شناسایی یال‌های جدید، یال‌های حذف‌شده یا یال‌های مشاهده نشده در زمان t’ می‌پردازد، به طوری که t’>t باشد. برای حل مسئله پیش‌بینی پیوند، لازم است آرایش یا تجزیه احتمالات وجود یال بین همه گره‌ها بررسی شود که معمولا از شباهت‌سنجی برای این کار استفاده می شود. روش‌های پیش‌بینی پیوند به این ترتیب دسته‌بندی می‌شوند[4]:

الف) روش‌های مبتنی بر گره

ب) روش‌های مبتنی بر توپولوژی: مبتنی بر همسایه، مبتنی بر مسیر⁸ و مبتنی بر قدم‌زنی تصادفی⁹.

ج) روش‌های مبتنی بر نظریه اجتماعی: مبتنی بر جوامع، مبتنی بر ۳تایی‌ها، مبتنی بر حفره‌های ساختاری، مبتنی بر استحکام پیوند و مبتنی بر هموفیلی.

شاخص‌های پیش‌بینی پیوند عمدتا مبتنی بر توپولوژی هستند و به ۳ گروه اصلی تقسیم می‌شوند[1]و[2]:

۱) معیارهای مبتنی بر همسایه‌ها، مانند همسایه‌های مشترک¹⁰، ضریب ژاکارد¹¹، ضریب آدامیک-آدار¹²، انضمام ترجیحی¹³ و تخصیص منابع¹⁴.

۲) معیارهای مبتنی بر مسیر، مانند مسیر محلی¹⁵، معیار کتز¹⁶ و شباهت استحکام ارتباط¹⁷.

۳) معیارهای مبتنی بر قدم‌زنی تصادفی، مانند زمان برخورد¹⁸، زمان طی کردن مسیر¹⁹، زمان شباهت کسینوسی²⁰ و رتبه صفحه ریشه‌دار²¹.

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

شکل 1. شمایی از پیش‌بینی پیوند در شبکه دوبخشی

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

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

۲ مطالعات پیشین

در این بخش به مرور مطالعات انجام‌شده درباره پیش‌بینی پیوند در شبکه دوبخشی پرداخته شده است. یکی از روش‌ های پایه برای پیش‌بینی پیوند در گراف دوبخشی، پیش‌بینی پیوند در گراف یک بخشی نگاشت‌شده گراف دوبخشی²³ است. [3]در گراف نگاشت‌شده، با استفاده از نوعی وزن دهی، پیش‌بینی پیوند را انجام می دهد. [6] پیوندهاي داخلی را به گراف نگاشت‌شده اضافه و سپس با استفاده از معیارهاي پیش‌بینی پیوند، پیوندهاي آتی را پیش‌بینی کرده است. در پژوهش [7]، مبتنی بر روش[6]، پس از دسته‌بندي یک نوع از گره ها که درمورد آن اطلاعات موجود است و اضافه یال بین گره‌هاي داخل هر دسته، اقدام به پیش‌بینی پیوند کرده است. [8] پس از نگاشت گراف دوبخشی به گراف وزن‌دار یک بخشی، درجه اهمیتی برای یال‌های پرامتیاز درنظر گرفته‌است و بررسی تغییرات درگذر زمان، به پیش‌بینی پیوند‌های جدید در شبکه‌های پویای پیچیده²⁴ پرداخته است. نویسندگان [8] در [9] نیز با درنظرگرفتن اینکه تغییرات شبکه در چه زمانی رخ داده‌اند، آستانه تعریف پیوندهای قوی و ضعیف را مورد مطالعه قرار داده‌اند.

گروهی از پژوهش‌های انجام‌شده، روش‌هایی مبتنی بر شباهت ارائه داده‌اند و معیارهاي کلاسیک پیش‌بینی پیوند را با جایگزینی همسایه با همسایه همسایه گره‌ها، با شبکه دوبخشی منطبق کرده‌اند[4]،[10] و[11]. [12] با استفاده از معیارهای کلاسیک پیش‌بینی پیوند، به پیش‌بینی ارتباطات ناموجود در شبکه‌های آشیانه‌ای²⁵ پرداخته است. [13] از ترکیب انضمام ترجیحی و خوشه‌بندي استفاده کرده است و پیوندها را داخل هر بخش پیش‌بینی می‌کند. [14] یک روش از ترکیب ساختار مبتنی بر شباهت و مدل ویژگی‌های پنهان ارائه کرده‌است. [15] با وزن‌دهی بر پایه دانش زمینه‌اي مسئله و ترکیب آن با تخصیص منابع، و [16] با تبدیل ماتریس مجاورت بر اساس شباهت بین گره‌هاي دو گروه، پیش‌بینی پیوند را انجام داده‌است. درروش مورد استفاده در[16]و[17]، CORLP ²⁶، ایجاد یال با مفاهیم مثبت و منفی درنظر گرفته شده است. به این معنی که پسندیدن یا نپسندیدن یک قلم، به طور جداگانه لحاظ شده است[18]. [19] با استفاده از اندیس‌هاي اطلاعات محلی²⁷، روش‌های اطلاعات مسیر و دانش زمینه‌ای روشی ارائه کرده‌است. [20]نیز بر مبنای دانش زمینه‌ای درمورد بخشی از گره‌ها روش خود را ارائه کرده‌است. [21] با ترکیب معیارهای پیش‌بینی پیوند و استفاده از شناسایی جوامع، روش خود را برای پیش‌بینی پیوند در گراف‌های چند لایه معرفی کرده‌است.

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

۳ روش پیشنهادی

ایده روش پیشنهادی، استفاده از معیارهای شناخته‌شده و کلاسیک پیش‌بینی پیوند است که برای انطباق با شبکه دوبخشی تغییر یافته و متناسب با شبکه دوبخشی تعریف شده‌اند. با توجه به اهمیت معیارهای پایه، معیار تعریف‌شده جدید به ترکیب معیارهای کلاسیک می‌پردازد. در این روش به دلیل جامعیت و دامنه استفاده بیشتر، تمرکز روی معیارهای مبتنی بر همسایه است. معیارهای مبتنی بر همسایه، اصلی‌ترین گروه معیارهای پیش‌بینی پیوند هستند و در اکثر مسائل پیش‌بینی پیوند، به نوعی مورد استفاده قرار می‌گیرند. به منظور بهره‌گیری از دیدگاه‌های متفاوت به دست‌آمده با استفاده از این معیارها، تعریف و محاسبه یک معیار جامع و جدید مبتنی بر همسایه پیشنهاد می‌شود. تمرکز اصلی روش پیشنهادی، بر اساس اهمیت گره‌های پردرجه است. در این راستا، از میان معیارهای گروه مبتنی بر همسایه، شاخص‌هایی مورد استفاده قرار گرفته‌اند که امتیاز بالاتری را به گره‌های با درجه بالاتر اختصاص می‌دهند. در کنار این شاخص‌ها، شاخص‌های شباهت‌سنجی نیز به منظور محاسبه شباهت بین گره‌ها از دیدگاه‌های مختلف و بدون درنظر گرفتن درجه گره‌ها استفاده شده‌است. شاخص‌های مورد نظر در این پژوهش، ضریب ژاکارد، شباهت کسینوسی سالتون²⁸، انضمام ترجیحی، Hub Depressed و لیخت-هولم-نرمن²⁹ هستند. معیارهای نام‌برده، همگی از نوع معیارهای بر پایه همسایه هستند. بین این معیارها، ضرایب ژاکارد و شباهت کسینوسی سالتون، شباهت بین دو گره را محاسبه می‌کنند. با توجه به اهمیت درجه گره‌ها در شبکه‌هایی که مدل رشد آنها از قانون انضمام ترجیحی پیروی می‌کند، معیارهای انضمام ترجیحی، HD و LHN برای به کارگیری در معیار جدید انتخاب شده‌اند. در این معیارها، گره‌های پردرجه از اهمیت بیشتری برخوردارند. بسیاری از اتفاقات طبیعی از قاعده انضمام ترجیحی پیروی می‌کنند. با وجود اینکه تمامی معیارهای نام‌برده برای هر نوع توزیع داده قابل به کار‌گیری هستند، با توجه به اهمیت گره‌های پردرجه در اکثر این معیارها، به نظر می‌رسد به منظور استفاده در توزیع‌ های لگاریتمی و کشیده به راست³⁰ مناسب‌تر باشند. فرایند کلی این پژوهش در نمودارمفهومی شکل ۲ نشان داده شده است.

شکل 2. نمودار مفهومی روش پیشنهادی

با توجه به اینکه بخشی از اطلاعات ضمنی که در برخی موارد بسیار مهم هستند، در تبدیل شبکه دوبخشی به یک بخشی از دست می‌رود[22]، از استفاده از گراف نگاشت‌شده امتناع شده و به تعریف مجدد معیارهای پیش‌بینی پیوند روی شبکه دوبخشی پرداخته شده‌است. این معیارها در شبکه دوبخشی با جایگزینی «همسایه» با «همسایه همسایه» در ادامه تعریف می‌شوند. در این تعاریف، مجموعه همسایه‌های گره x، مجموعه همسایه‌های همسایه‌های گره x و تعداد همسایه‌های گره x را نشان می‌دهد.

ضریب ژاکارد(JC): ضریب ژاکارد، یک معیار مبتنی بر شباهت است که تعداد همسایه‌های مشترک را نرمال‌سازی می‌کند و بنابراین، اطلاعات مفیدتری به نسبت تعداد همسایه های مشترک ارائه می‌دهد[23]. این شاخص، ارزش بالاتری برای زوج گره‌هایی درنظر می‌گیرد، که نسبت تعداد همسایه‌های مشترک آنها به کل تعداد همسایه‌های آنها، مقدار بیشتری باشد. این معیار جزو اصلی‌ترین معیارهای مورد استفاده به منظور شباهت‌سنجی است و به طور خاص در پیش‌بینی پیوند به کار گرفته‌ می‌شود. ضریب ژاکارد در شبکه دوبخشی با استفاده از رابطه ۱ محاسبه می‌شود:

شباهت کسینوسی سالتون(SC): این شاخص یک معیار کسینوسی جامع، پرکاربرد و پایه در مبحث پیش‌بینی پیوند است که مانند ضریب ژاکارد، به اندازه‌گیری میزان شباهت بین دو گره می‌پردازد و با استفاده از رابطه ۲ محاسبه می‌شود:

(۱)

انضمام ترجیحی(PA): این معیار بیان می‌کند که یال‌های جدید، با احتمال بالاتری به گره‌هایی متصل می‌شوند که درجه بالاتری دارند و این احتمال متناسب با اندازه همسایگی گره است[24]. ضرب تعداد همسایه‌های دو گره، اندازه همسایگی آنها را مشخص می‌کند و با رابطه ۳ محاسبه می‌شود:

(۲)

Hub Depressed (HD): با درنظر داشتن گره‌های پر درجه، این معیار امتیاز بین یک زوج گره را هم‌پوشانی توپولوژیک دو گره تعریف می‌کند[25] که از طریق رابطه ۴ محاسبه می‌گردد:

(۳)

لیخت-هولم-نرمن(LHN): این معیار، ارزش بیشتری به زوج گره‌هایی اختصاص می‌دهد که تعداد همسایه‌های مشترک بیشتری به نسبت تعداد مورد انتظار این همسایه‌ها دارند(رابطه ۵)[26]:

(۴)

با توجه به دامنه متفاوت و اختلاف مقادیر این معیارها، به منظور اثرگذاری یکسان در محاسبه معیار جدید، مقادیر پارامترهای برگزیده بین ۰ و ۱ با استفاده از مقیاس کردن ویژگی³¹ یا نرمال‌سازی کمینه و بیشینه (رابطه ۶)، نرمال‌سازی می‌شوند.

(۵)

معیار پیشنهادی برای پیش‌بینی پیوند در شبکه دوبخشی تحت عنوان ضریب مبتنی بر همسایهNBC)³²)، به منظور استفاده از اطلاعات به دست‌آمده از هر معیار با توجه به مفاهیم متفاوت آنها، استفاده از جمع مقادیر نرمال‌شده امتیازات این معیارها را پیشنهاد می‌کند. این معیار با استفاده از رابطه ۷ محاسبه می‌شود که در آن JC’ ، PA’ ، SC’ ، HD’ و LHN’ مقادیر نرمال‌شده این معیارها هستند.

(۶)

۴ تحلیل داده و شبکه

در این پژوهش از دو سری مجموعه داده فروشگاهی استفاده شده‌است. مجموعه اول مربوط به فروشگاه و شبکه اجتماعی آریو³³ است که یک وب‌سایت داخلی خرید و فروش بازی‌های کامپیوتری‌ است که از طرف این فروشگاه در دسترس نویسندگان قرار گرفته‌است. مجموعه دوم مربوط به یک فروشگاه خرده‌فروشی آنلاین است. این مجموعه داده از انبار یادگیری ماشین دانشگاه ارواین کالیفرنیا³⁴ برداشته شده و برای عموم در اینجا ³⁵ قابل دسترسی است. در پیش‌پردازش هر دو مجموعه داده، داده‌های پرت و خارج از محدوده³⁶ شناسایی و حذف شده‌اند. داده‌های پرت در هر دو مورد، داده‌هایی هستند که فاصله و اختلاف زیادی با دیگر داده‌ها دارند و تنها یک بار اتفاق افتاده اند و به همین دلیل قابل استناد نیستند. این داده‌ها به عنوان نویز در داده درنظر گرفته می‌شوند و با حذف آنها، روند تغییرات داده تغییر نمی‌کند.

در مجموعه داده اول، داده‌ها مربوط به تراکنش‌های خریدهای انجام شده، شامل کاربر خریدار و کالای خریداری شده‌است. پس از انجام پیش پردازش روی داده ها، مجموعه دادگان منتخب شامل ۴۵۹۱ خرید، ۱۰۶۱ کاربر و ۲۸۳ کالاست. شکل ۳ هیستوگرام ترسیم شده برای تعداد خریدهاست. در این نمودار محور افقی نشان‌دهنده تعداد خرید و محور عمودی نشان‌دهنده تعداد افراد است. به دلیل تجمع داده در سمت چپ نمودار و اختلاف مقادیر، به منظور نمایش بهتر از مقیاس لگاریتمی استفاده شده‌است.

شکل 3. نمودار هیستوگرام تعداد خرید در مجموعه داده Ario

در مجموعه داده دوم نیز داده‌های خرید وجود دارد که مانند بخش قبل، داده‌های مربوط به کاربر خریدار و کالای خریداری‌شده مورد استفاده هستند. پس از پیش‌پردازش و پاکسازی داده‌ها، ۱۲۴۳۸۰ خرید، ۲۶۸۰ کاربر و ۳۵۵۰ کالا در مجموعه قرار دارد. شکل ۴ نمودار هیستوگرام این مجموعه داده در راستای تعداد خرید کاربران است.

شکل 4. نمودار هیستوگرام تعداد خرید در مجموعه داده UK Retailer

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

جدول 1. توصیف آماری مجموعه داده‌ها

(۷)

معیار	مجموعه داده Ario	مجموعه داده UK Retailer
تعداد	۱۰۶۱	۲۶۸۰
میانگین	۵/۴	۴۵
انحراف ‌از معیار	۵/۶	۵۱
مینیمم	۱	۱
چارک اول	۲	۱۴
میانه	۳	۲۹
چارک سوم	۴	۵۷
ماکزیمم	۱۲۲	۵۵۳

ابتدا از روی این مجموعه داده‌ها، شبکه دوبخشی دادگان ساخته می‌شود. در این شبکه گره‌ها کاربران و کالاها هستند. درصورتی که کاربری کالایی را خریداری کرده باشد، بین آن دو گره، یال ترسیم می گردد. به منظور انجام پیش‌بینی پیوند و پیاده‌سازی روش پیشنهادی، از برنامه نویسی پایتون و کتابخانه‌های آن از جمله pandas، numpy، networkx، sklearn و statistics استفاده شده‌است. خروجی برنامه، یال‌های پیش‌بینی شده توسط هر روش است. نتایج پیاده‌سازی در بخش بعد بررسی شده‌است.

۵ آزمایش و ارزیابی

در بخش ارزیابی، از ۳ شاخص شناخته‌شده و مرجع در داده‌کاوی تحت عناوین Precision، Recall و F1 Score، که دو معیار اول در آن درنظر گرفته شده‌است، استفاده شده است. مجموعه دادگان به صورت تصادفی با نسبت ۷/۰ به ۳/۰، به مجموعه دادگان آموزش و آزمون تقسیم می‌شود. لازم به ذکر است با توجه به اهمیت همبند بودن گراف در تحلیل آن، این تقسیم‌بندی تا زمانی که گراف به دست‌آمده از مجموعه آموزش همبند باشد، ادامه پیدا می‌کند. نتایج به دست آمده از تحلیل و بررسی مجموعه آموزش، با مجموعه آزمون مقایسه و شاخص‌های ارزیابی از روی آن محاسبه می‌شود. به منظور ارزیابی، معیار پیشنهادی با معیارهای تشکیل‌دهنده آن و همچنین ضریب آدامیک-آدار[27]، که میزان شباهت دو گره را با توجه به همسایه‌های مشترک آنها محاسبه می‌کند، مقایسه می‌شود. ضریب آدامیک-آدار به دلیل اهمیت دادن به گره‌های کم‌درجه، در معیار پیشنهادی استفاده نشده‌است. به منظور جلوگیری از جهت‌دار بودن داده‌های انتخابی در هر مجموعه و به دست‌آوردن مجموعه داده عادلانه، این آزمایش ۱۰ بار تکرار می‌گردد و میانگین مقدار شاخص‌های ارزیابی به عنوان مقادیر نهایی درنظر گرفته می‌شوند. جدول ۲ و جدول ۳، پیچیدگی محاسباتی و مقادیر شاخص‌های ارزیابی به درصد را درهر روش به ترتیب برای مجموعه داده‌های اول و دوم نشان می‌دهد.

جدول 2. نتایج ارزیابی معیارهای پیش‌بینی پیوند روی مجموعه داده Ario

F1 Score (%)	Recall (%)	Precision (%)	Time Complexity	Type
62.15	61.43	62.89	O(n2)	JC
61.38	59.09	63.86	O(n2)	AA
62.48	61.89	63.07	O(n2)	SC
57.02	53.34	61.25	O(n)	PA
62.31	61.58	63.05	O(n2)	HD
60.09	58.78	61.46	O(n2)	LHN
63.23	62.98	63.47	O(n2)	NBC

جدول 3. نتایج ارزیابی معیارهای پیش‌بینی پیوند روی مجموعه داده UK Retailer

F1 Score (%)	Recall (%)	Precision (%)	Time Complexity	Type
43.23	27.57	99.56	O(n2)	JC
42.31	26.83	99.80	O(n2)	AA
65.58	48.80	96.66	O(n2)	SC
31.59	18.77	98.96	O(n)	PA
43.15	27.51	99.87	O(n2)	HD
74.78	63.92	92.47	O(n2)	LHN
77.54	65.13	93.69	O(n2)	NBC

در بحث پیش‌بینی پیوند، علاوه بر F1 Score، Precision نیز شاخصی پراهمیت است. همان‌طور که مشاهده می‌شود، معیار پیشنهادی از نتایج مطلوبی برخوردار است. در هر دو مجموعه داده، معیار پیشنهادی در شاخص‌های F1 Score و Recall، بالاترین مقادیر میان روش‌ها را دارد. برتری روش پیشنهادی به نسبت دیگر روش‌ها در مجموعه داده UK Retailer که ابعاد بزرگتری دارد، بیشتر مشهود است. تمامی روش‌ها از Precision بالا و مطلوبی برخوردار هستند. اما نکته قابل توجه، کم بودن مقادیر Recall و درنتیجه F1 Score برای دیگر روش‌هاست که باعث می‌شود روش پیشنهادی روشی مؤثرتر برآورد شود. نتایج ارزیابی معیار پیشنهادی برای مجموعه داده اول Precision ۴۷/۶۳٪، Recall ۹۸/۶۲٪ و F1 Score ۲۳/۶۳٪ و برای مجموعه داده دوم Precision ۶۹/۹۳٪، Recall ۱۳/۶۵٪ و F1 Score ۵۴/۷۷٪ به‌دست آمده است. در مجموعه داده اول، ضریب آدامیک-آدار دارای مقدار Precision بالاتری است اما اختلاف دقت این معیار و معیار پیشنهادی، ۳۹/۰ درصد و بسیار ناچیز است. در مجموعه داده دوم، با وجود اینکه دیگر روش‌ها مقادیر Precision بالاتری دارند، اما همانطور که ذکر شد به دلیل عملکرد پایین در دیگر شاخص‌های ارزیابی، این موضوع برتری زیادی را به دنبال ندارد. پیچیدگی محاسباتی این روش‌ها عمدتا از نوع O(n2) است. با توجه به اینکه پیچیدگی روش پیشنهادی نیز از همین نوع است، در مجموع، معیار پیشنهادی برای استفاده در پیش‌بینی پیوند شبکه دوبخشی عملکرد بهتری به نسبت دیگر روش‌ها نشان داده‌است. نکته مهم دیگر، درنظر گرفتن جنبه‌های مختلف همسایگی و شباهت در این روش است که در این صورت، مسئله از دیدگاهی گسترده‌تر مورد بررسی قرار می‌گیرد.

۶ جمع‌بندی

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

مراجع

M. Newman, Networks. Oxford university press, 2018.	[1]
A. Alamsyah, “Social network data analytics for market segmentation in indonesian telecommunications industry,” 2017, pp. 1–5.	[2]
O. Allali, C. Magnien, and M. Latapy, “Link prediction in bipartite graphs using internal links and weighted projection,” 2011, pp. 936–941.	[3]
P. Wang, B. Xu, Y. Wu, and X. Zhou, “Link prediction in social networks: the state-of-the-art,” Science China Information Sciences, vol. 58, no. 1, pp. 1–38, 2015.	[4]
V. Martínez, F. Berzal, and J.-C. Cubero, “A survey of link prediction in complex networks,” ACM computing surveys (CSUR), vol. 49, no. 4, pp. 1–33, 2016.	[5]
E. Gündoğan and B. Kaya, “A recommendation method based on link prediction in drug-disease bipartite network,” 2017, pp. 125–128.	[6]
E. Gündoğan and B. Kaya, “A link prediction approach for drug recommendation in disease-drug bipartite network,” 2017, pp. 1–4.	[7]
S. Aslan, B. Kaya, and M. Kaya, “Predicting potential links by using strengthened projections in evolving bipartite networks,” Physica A: Statistical Mechanics and its Applications, vol. 525, pp. 998–1011, 2019.	[8]
S. Aslan and B. Kaya, “Time-aware link prediction based on strengthened projection in bipartite networks,” Information Sciences, vol. 506, pp. 217–233, 2020.	[9]
Y.-J. Chang and H.-Y. Kao, “Link prediction in a bipartite network using wikipedia revision information,” 2012, pp. 50–55.	[10]
S. Xia, B. Dai, E.-P. Lim, Y. Zhang, and C. Xing, “Link prediction for bipartite social networks: The role of structural holes,” 2012, pp. 153–157.	[11]
M. Medo, M. S. Mariani, and L. Lü, “Link prediction in bipartite nested networks,” Entropy, vol. 20, no. 10, p. 777, 2018.	[12]
C. Zhang, E. Chan, and A. Abdulhamid, “Link prediction in bipartite venture capital investment networks,” CS224-w report, Stanford, 2015.	[13]
W. Wang, X. Chen, P. Jiao, and D. Jin, “Similarity-based regularized latent feature model for link prediction in bipartite networks,” Scientific reports, vol. 7, no. 1, pp. 1–12, 2017.	[14]
X. Chen, D. Xie, L. Wang, Q. Zhao, Z.-H. You, and H. Liu, “BNPMDA: bipartite network projection for MiRNA–disease association prediction,” Bioinformatics, vol. 34, no. 18, pp. 3178–3186, 2018.	[15]
D. Zhao, L. Zhang, and W. Zhao, “Genre-based link prediction in bipartite graph for music recommendation,” Procedia Computer Science, vol. 91, pp. 959–965, 2016.	[16]
F. Xie, Z. Chen, J. Shang, X. Feng, and J. Li, “A link prediction approach for item recommendation with complex number,” Knowledge-Based Systems, vol. 81, pp. 148–158, 2015.	[17]
Y. Cui, L. Zhang, Q. Wang, P. Chen, and C. Xie, “Heterogeneous network linkage-weight based link prediction in bipartite graph for personalized recommendation,” Procedia Computer Science, vol. 91, pp. 953–958, 2016.	[18]
Y. Luo, Q. Liu, W. Wu, F. Li, and X. Bo, “Predicting drug side effects based on link prediction in bipartite network,” 2014, pp. 729–733.	[19]
L. Zhang, J. Li, Q. Zhang, F. Meng, and W. Teng, “Domain knowledge-based link prediction in customer-product bipartite graph for product recommendation,” International Journal of Information Technology & Decision Making, vol. 18, no. 01, pp. 311–338, 2019.	[20]
M. Koptelov, A. Zimmermann, B. Crémilleux, and L. Soualmia, “Link prediction via community detection in bipartite multi-layer graphs,” 2020, pp. 430–439.	[21]
D. B. Larremore, A. Clauset, and A. Z. Jacobs, “Efficiently inferring community structure in bipartite networks,” Physical Review E, vol. 90, no. 1, p. 012805, 2014.	[22]
G. Salton and J. Michael, “McGill,” Introduction to modern information retrieval, vol. 1, no. 4.1, pp. 4–1, 1986.	[23]
A.-L. Barabâsi, H. Jeong, Z. Néda, E. Ravasz, A. Schubert, and T. Vicsek, “Evolution of the social network of scientific collaborations,” Physica A: Statistical mechanics and its applications, vol. 311, no. 3–4, pp. 590–614, 2002.	[24]
T. Zhou, L. Lü, and Y.-C. Zhang, “Predicting missing links via local information,” The European Physical Journal B, vol. 71, no. 4, pp. 623–630, 2009.	[25]
E. A. Leicht, P. Holme, and M. E. Newman, “Vertex similarity in networks,” Physical Review E, vol. 73, no. 2, p. 026120, 2006.	[26]
L. A. Adamic and E. Adar, “Friends and neighbors on the web,” Social networks, vol. 25, no. 3, pp. 211–230, 2003.	[27]

[1] Visualization

[2] Structural analysis

[3] Community detection

[4] Small-world networks

[5] Motif analysis

[6] Link Prediction

[7] Diffusion

[8] Path

[9] Random walk

[10] Common Neighbors(CN)

[11] Jaccard’s Coefficient(JC)

[12] Adamic-Adar Coefficient(AA)

[13] Preferential Attachment(PA)

[14] Resource Allocation(RA)

[15] Local Path(LP)

[16] Katz

[17] Relation Strength Similarity(RSS)

[18] Hitting Time(HT)

[19] Commute Time(CT)

[20] Cosine Similarity Time(CST)

[21] Rooted PageRank(RPR)

[22] Co-authorship

[23] Projected graph

[24] Dynamic complex networks

[25] Nested networks

[26] Complex Representation-based Link Prediction

[27] Local information index

[28] Salton Cosine Similarity(SC)

[29] Leicht-Holme-Nerman(LHN)

[30] Right-skewed

[31] Feature scaling

[32] Neighbor-Based Coefficient (NBC)

[33] Ario (https://ariogames.ir)

[34] UCI’s Machine Learning Repository

[35] https://archive.ics.uci.edu/ml/datasets/online+retail

[36] Outlier

A Neighbor-based Link Prediction Method for Bipartite Networks

Abstract:

Keywords: Graph theory, Social network analysis, bipartite network, link prediction, link prediction in bipartite networks.

Share To

Article Url

A Neighbor-based Link Prediction Method for Bipartite Networks

Rimag

Links

Related Centers

Technical Support

Official pages