خوشه بندی گراف

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

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