تعریف مسئله

تعریف مسئله :

اگر G´(V´,E´) را به عنوان یک گراف بدون جهت در نظر بگیریم،احتمالا یک گراف وزن دار که نشان

 دهنده شبکه ای که مشاهده شده است می باشد.حال کل شبکه را با علامت گذاری G(V,E)

 نمایش می دهیم.سپس G´ را به عنوان یک زیر گراف از G در نظر می گیریم که خود شامل مجموعه

ای از یال های گم شده است.

E-E´ ، با E* علامت گذاری می شود. برای یک ضلع e Ɇ E* ،این کار ما برای تخمین زدن است که آیا

شبیه e E E* است یا نه.

e E E* نمره یال نامیده می شود و با S x,y علامتگذاری می شود.بک نمره می تواند محاسبه برای

تمامی یال های V´ * V´-E´ انجام میشود که در گراف مشاهده شده گم شده اند.توجه داشته

باشید که عملکرد امتیازذهی خاص با روش مورد بحث انجام می شود ، و به این نکته بایدتوجه داشت

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

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

برای شبکه اجتماعی ما با مشخصه گراف G´(V´,E´) راهی را برای محاسبه آن بررسی می کنیم.به

عنوان مثال می توانیم تمام یال های گم شده در شبکه فیسبوک را محاسبه کنیم،تنها راهی که

همیشه می توان از درست بودن یک یال مطمـُن شد این است که از دو کاربر دو طرف یال بپرسیم

 که چه کسی نقطه پایانی یال است.و بعضی مواقع ،ممکن است که آنها وجود خارجی نداشته

باشند ،یا شاید نخاهند در فیسبوک با هم دوست باشند ،یا شاید به عنوان دو همکار بخاهند بین

زندگی شخصی و حرفه ای خود فاصله ایجاد کنند ،یا شاید یکی از آنها به خاطر دزدیده شده متد

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

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

خیلی دقیق باشند.

اما، فیسبوک شرایط مالی جذابی را در نظر گرفته تا مردم را ترغیب کند که با هم دوست شوند. و این

بدان معناست که کسانی که اطلاعات بیشتری در مورد دوستی خود در اختیار فیسبوک قرار دهند

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

کمک شایانی میکند.

این امر یعنی پرسش در مورد روابط دوستانه از کاربران در طول یک بازه زمانی میتواند خیلی پرهزینه

باشد.به عنوان مثال شما بخواهید از یک کاربر سوال کنید که از بین میلیاردها نفر زیر آیا کسی را

میشناسد یا نه. بنابراین به نفع فیسبوک است که سعی کند محدوده ای را که می خواهد در مورد

روابط دوستانه آنها تحقیق کند را کوچک تر کند.و این امر به معنای همان Snapshot با عکس فوری

است که از یک ناحیه شبکه بزرگ پیچیده میگیریم.

                                 

                                                                                                 (   الف    )                                                                                                                                                                             (  ب )                               

شکل (الف ) یک گراف متراکم با 2 یال برای پیشبینی

شکل (ب )  یک گراف کم تراکم با 58 یال برای پیشبینی

تفاوت پیشبینی یال صحیح در یک گراف کم تراکم در مقابل یک نمودار متراکم:

نمودار متراکم 50 درصد شانس این را دارد که لینک صحیح را انتخاب کند در حالیکه گراف کم تراکم تنها

7/1 درصد شانس انتخاب یال صحیح را دارد.

Anne Gatchell -Andy McEvoy     CSL - Link Prediction     Link Prediction in Social Networks

April 29, 2013

    https://www.cs.cornell.edu/home/kleinber/link-pred.pdf