تعریف مسئله

تعریف مسئله :

اگر 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

پیشبینی لینک به چه معناست؟

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

با ظهور شبکه های اجتماعی،هر کسی باید با مفهوم شبکه اجتماعی آشنا باشد.شبکه اجتماعی

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

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

حروف نمایش داده میشوند(A,B,C,D,E).هر یال نشان گر یک رابطه بین دو نفر است.به عنوان مثال

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

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

زمانی که ایجاد شده اند کدگذاری شوندیا بر اساس نوع رابطه یا تعداد دفعاتی که یک رابطه بین دو

گروه برقرار شده است.

شکل بالا مثالی است از یک شبکه اجتماعی و اینکه چگونه دیده میشود.

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

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

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

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

پیشبینی این فعالیت ها تجربیات معناداری را برای کاربران خواهد داشت و باعث حفظ آینده شبکه

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

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

میتوانند از متد های پیشبینی لینک استفاده کنند:

نوع شبکه	نوع پیشبینی فعل و انفعالات
اجتماعی	روابط دوستی-روابط همکاری-روابط تبانی
بیولوژیکال	-فعل و انفعالات پروتیُنی در فرآیندهای بیولوژیکال -شبکه های مواد غذایی که نشان می دهد موجودات مختلف چگونه با یکدیگر و محیط پیرامون خود در ارتباط هستند
سیستم های اطلاعاتی	کاربر ها-سیستم های پیشنهاد دهنده

مشکل اصلی در تمام این مثال ها پیدا کردن تعامل معنی دار است که بین دو گره برقرار باشد.

حال اگر بخواهیم مباحثی را تاکنون ذکر شده را به زبان مفهومی بیان کنیم می توان پیش بینی لینک

را اینگونه تعریف کردکه ما با داشتن یک Snapshot یا عکس فوری در زمان T1 وضعیت شبکه را در

زمان آینده T2 تخمین بزنیم و سعی ما بر این است که بر اساس تعاملات میان اعضای موجود در

شبکه پی ببریم که در زمان آینده به احتمال زیاد چه ارتباطاتی به وجود می آید یا چه تعاملاتی از بین

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

بسیاری در انجام و چگونگی این موضوع وجود دارد که در مباحث آینده بیشتر به آن می پردازیم.

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