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

چکیده

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

مقدمه

شبکه های اجتماعی شبکه های پویایی اند که همواره اعضا و ارتباطات و پیوندهای بین آنها رو به افزایش است. زنجیره این پیوندها گاهی به دلیل فرآیند ایجاد ناقص یا به دلیل اینکه هنوز در این شبکه ها انعکاس نیافته اند (برای مثال، دوستان دنیای واقعی که یک ارتباط اجتماع ی مجاز ی ایجاد نکرده اند)، پاره شده و از دست می روند (فایر و دیگران، 2011 )، لذا یکی از مسائل مهم درشبکه های اجتماعی، مسئله پیش گویی پیوند  است.مسئله پیشگویی، یکی از جنبه های مهم داده کاوی است. داده کاوی پیشگویی کننده، مدلی ازسیستم ارائه می کند که این مدل را مجموعه ای از داد ه های مشخص، پیش بینی می کنند و هدف کلی آن ایجاد الگویی برای طبقه بندی، پیش بینی و تخمین داده ها است. پیشگویی پیوند، به معنای وجود و عدم وجود یک پیوند یا ارتباط در آینده بین دو رأس یک شبکه اجتماعی است و یک ابزار مهم برای تحلیل شبکه های اجتماعی به شمار می رود که کاربردهای زیادی نیز در حوزه های دیگری چون، بازیابی اطلاعات، بایوانفورماتیک و تجارت الکترونیک دارد. به علاوه در حوزة علم وب و اینترنت، می تواند در کارهایی مانند ایجاد ابرپیوند خودکار وب و پیش بینی ابرپیوند سایت های وب کاربرد داشته باشد یکی از مهمترین کاربردهای پیشگویی پیوند در تجارت الکترو نیک ، ایجاد سیستم های پیشنهاد دهنده است. این پیشنهادها می توانند شامل پیشنهاد کالا یا پیشنهاد دوست باشند. ازجمله فواید پیشگویی پیوند اینکه با پیشنهادهای مناسب در زمینة کالا، می توان ضریب خرید اینترنتی افراد جامعه را بالا برد. عمل خرید تحت تأثیر بسیاری از خصایص مشتریان ، مانند ویژگی های شخصیتی، سبک زندگی، دانش و مهارت ها، عوامل اجتماعی، عوامل روانی و عوامل جمعیتی قرار دارد .خرید اینترنتی براساس تجربه واقعی از خرید کالا صورت نمی گیرد، بلکه براساس ظواهری مانند تصویر، شکل، اطلاعات کیفی و تبلیغات از کالا استوار است؛ به همین دلیل جلب اعتماد مشتری برای انجام مبادلات ازطریق اینترنت، مورد توجه بسیاری از سازمان ها و مشتریان قرار گرفته است .یکی از را ههای جلب اعتماد مشتری، به واسطه اعتماد به افرادی حاصل می شود که با وی دریک شبکه اجتماعی در ارتباط بوده و از کالای مورد نظر استفاده می کنند . به همین دلیل ،هم پیوندی به معنی تمایل اعضا برای پیوند و ارتباط با یکدیگر، به منزله ویژگی مهمی برای یکپارچه سازی اطلاعات یاد شده است که موجب پایداری کسب وکارها می شود.در این زمینه پیشگویی پیوند با تحلیل ارتباطات موجود در شبکه های اجتماعی، می تواند فرآیند پیشنهاد کالا و خدمات را تسهیل کند.از جنبه دوست یابی نیز، شبکه های اجتماعی برخطی مانند فیس بوک دارای حجم انبوهی ازداده هستند که می توانند با جست وجو در میان آنها و تحلیل اطلاعات موجود، در این مورد که چه کسی ممکن است بخواهد با دیگری دوست شود، پیشگویی کنند و بر اساس این پیشگویی ها به کاربران پیشنهادهای مناسبی ارائه دهند.ساختار شبکه های اجتماعی، به صورت گرافی مدل می شود که رأس های گراف همان کاربران شبکه هستند و ارتباطات بین این کاربران، یال های گراف را شکل میدهند. برای ارائه پیشنهاد در این شبکه ها دو رویکرد کلی وجود دارد. رویکرد اول که مبتنی بر ویژگی های محلی ساختارگراف شبکه است، روشی است که معمولاً در شبکه های اجتماعی برخط مورد استفاده قرارمی گیرد. این شبکه ها معمولاً پیشگویی های خود را بر اساس تعداد دوستان مشترکی که دو کاربردارند، انجام می دهند؛ زیرا احتمال بسیار زیادی وجود دارد که دو کاربری که دوستان مشترک زیادی دارند، تمایل داشته باشند با یکدیگر چه در دنیای مجازی و چه در دنیای واقعی دوست شوند. اشکالی که به این روش ها وارد است، به در نظر گرفتن حداکثر فاصلة 2 بین هر دو کاربر در گراف شبکه برمی گردد که ممکن است از دقت کافی برخوردار نباشند.در مقابل روش های با رویکرد محلی ، مانند روش دوست  دوست یا دوستان مشترک روش های سراسری نیز وجود دارند که برای یافتن میزان شباهت بین دو فرد ، کل گراف شبکه را پیمایش می کنند. از آنجایی که این روش ها کل اطلاعات شبکه را در نظرمی گیرند، ممکن است از دقت زیادی برخوردار باشند، ولی بار محاسباتی بالایی دارند و طبیعتاً برای شبکه های اجتماعی برخط مناسب نیستند. از جمله رو شهایی که مبتنی بر این رویکردمعیار کاتز گام تصادفی با شروع مجدد نام برد. در این نوشتار روشی ارائه خواهد شد که با استفاده از رویکردی محلی، در تهیه یک معیارجدید برای پیشنهاد دوست و پیشگویی پیوند، در کنار بهره مندی از مزیت سرعت رو شهای محلی، از کارایی مناسبی نسبت به سایر رو شهای موجود، برخوردار است.

روش شناسی پژوهش

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

که در آن (Cn(u,z تعداد همسایه های مشترک دو رأس z و u است.رابطة بالا برای تعداد بالای دوستان مشترک رأس میانی با دو رأس اصلی، امتیاز مثبت قائل می شود و به همین دلیل، مجموع این تعداد در صورت معادله قرار داده شده است تا میزان شباهت را افزایش دهد. از سوی دیگر، برای درجة رأس میانی امتیاز منفی در نظر گرفته شده ودر مخرج معادله جای می گیرد.در مقایسه هایی که بین این روش و روش های معرفی شده صورت گرفته است، مشاهده می شود که این معیار کارایی قابل قبولی نسبت به روش های دیگر دارد که در ادامه این کارایی اثبات می شود.

یافته های پژوهش

در این بخش الگوریتم پیشنهادی این پژوهش با سیزده ویژگی شرح داده شده، مقایسه می شود وکارایی آن به صورت تجربی اثبات خواهد شد . برای این کار، از دو مجموعه داد ه واقعی Facebook و Epinions استفاده شده است. مجموعه داده های شبکه اجتماعیEpinionsکه یک شبکة اجتماعی به شمار می رود در نظر گرفته شده و از 49 k کاربر و k 487یال بین جفت رأس ها تشکیل شده است مجموعه داده ای Facebook که در 30 اکتبر 2009جمع آوری شده شامل 3/7k کاربر و از  13.7k یال است. برای ارزیابی و مقایسه روش ها و الگوریتم های مختلف پیشگویی پیوند با روش پیشنهادی، از معیار MAP استفاده شده است، تا در بررسی کارایی الگوریتم مورد نظر، روی ترتیب دوستان پیشنهاد داده شده با این رو شها، تأکید بیشتری شود. معادله MAPبه صورت رابطه زیر تعریف می شود:

در این رابطه N تعداد کاربران در مجموعه دادة آزمایشی Rتعداد کاربران مرتبط با کاربر Uمجموعه آزمایشی و precision: مقدار precision در k امین موقعیت فهرست پیشنهادها برای uاست توجه کنید که MAP در واقع هر دو مقدار precisionوrecall را درخود دارد و از نظر هندسی در زیر منحنی precision-recall جای دارد.به منظور ارزیابی روش ها، از هر مجموعه آموزشی به صورتی کاملاً تصادفی، 1000 رأس انتخاب شد و با در نظر گرفتن همه ارتباطات میان آنها، پس از محاسبه و مقایسة مقادیر معیارها، آزمایش های لازم روی آنها انجام گرفت. از آنجایی که با این انتخاب همه رأس ها، حتی رأس هایی که هنوز دوستی ندارند و به اصطلاح افراد تازه وارد این شبکه اجتماعی به شمار میروند نیز انتخاب می شوند، این امکان وجود دارد که در نتایج همه انواع روش های معرفی شده، با دقت پایینی مواجه شویم؛ چراکه این نوع رأس ها، با مشکلی به نام آغاز سرد  برخورد می کنند که یک مشکل رایج در ارائه پیشنهادهای شبکه های اجتماعی محسوب می شود. در این حالت، اطلاعاتی از فرد تازه وارد در دست نیست تا بتوان از این طریق، علایق وی را شناسایی کرد و پیشنهادهای مناسب را به او ارائه داد در شبکه های اجتماعی مشهوری چون Facebook که از روش«  دوست دوست » برای ارائة پیشنهادها استفاده می کنند، این مشکل از راه بررسی اسامی موجود در پست الکترونیکی فرد و تطابق آن با اعضای شبکه اجتماعی و ارائه اسامی تطابق یافته، از بین می رود.در گوگل پلاس نیز برای حل این مشکل، فرد را وادار می کنند که در آغاز ورود به شبکه، ده نفردوست را انتخاب کرده و معرفی کند.برای تفکیک داده های آموزشی و آزمایشی در هر دو مورد از اعتبارسنجی ضربدری ده لایه ای  استفاده شد و الگوریتم ها به کمک زبان نرم افزاری جاوا، به اجرا گذاشته شدند . مقایسه بین الگوریتم های مختلف در رابطه با مجموعه داده ه ای انتخابی و نتایج آن، در جدول 1 نشان داده شده است.

همان طور که در جدول 1 مشاهده می شود، روش جدید در رابطه با مجموعه داده Epinions پس از معیار ضریب خوشه بندی، بهترین جواب را داده است و در مقایسه با سایر معیارها بهتر عمل کرده است. در مورد Facebook نیز به کمک روش پیشنهادی، در مجموع بهترین پاسخ در رابطه با مجموعه دادة انتخابی به دست آمده است؛ در حالیکه در این مجموعه داده، ضریب خوشه بندی دارای کارایی بسیار پایینی بوده است. بنابراین همان گونه که در جدول 1 مشاهده می شود، روش جدید در مورد هر دو مجموعه داده در مقایسه با سایر رو شها، پاسخهای مناسب و قابل قبولی خواهد داشت و پیش بینی های خوبی را ارائه می دهد.

نتیجه گیری  

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

منابع:

ارائة روشی جدید برای پیشگویی پیوند بین رأس های موجود درشبکه های اجتماعی اعظم کی پور مرتضی براری ، حسین شیرازی