متد همسایگان مشترک Common neighbors
متد همسایگان مشترک (Common neighbors) :
بسط و گسترش الگوریتم جهان کوچک ، این تصویر کلی را برای ما پدیدار می سازد که همسایگان بدون واسطه یک گره اطلاعات با ارزش درباره یال های احتمالی گره X را نگهداری می کنند، بنابراین x))Γ را به عنوان مجموعه ای از همسایگان گره x علامت گذاری میکنیم.
اگر مفهوم homophily در بحث خوشه بندی را مد نظر بگیریم ،منافع بین دو نفر ، نظیر x ,y همانند روابط دوستی بین دو آن دو نفر است.
اگر به این مقوله از منظر پیشبینی لینک نگاه کنیم ، اگر دو نفر به عنوان مثال x و y ، دوستان مشترک زیادی دارند ، احتمال بسیار زیاد وجود دارد که x و y نیز با هم دوست باشند.این مفهوم پایه و اساس متد همسایگان مشترک و پیشبینی لینک است.
با بررسی میزان همپوشانی دو گروه همسایه ، ما میتوانیم احتمال وجود لینک بین دو گروه را بررسی کنیم:
اگر نمودار G´ به عنوان یک لیست مجاورت ذخیره شده است ، به سادگی می تواند به عنوان یک لیست عملیات مقایسه بین هر یک از گره های لیست استفاده شود و می تواند o(n lg n) بارانجام شود چنانچه دو لیست ذخیره شده باشد،یا o(n) بار انجام شود اگر لیست ها حالت مخلوط داشته باشند.
با بررسی گراف شکل زیر میتوانیم ببینیم که شما همسایگان مشترک بیشتری با گره B دارید تا گره C ،بنابراین لینک بین شما و B با احتمال بیشتری پیشبینی می شود تا لینک بین شما و گره C .
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
متد کوتاهترین مسیر
متد کوتاهترین مسیر:
الگوریتم جهان کوچک را در نظر بگیرید . میلگرام در آزمایشی افراد مختلفی را از نبراسکا و کانزاس انتخاب کرد و برای آنها نامه ای فرستاد.در این نامه او از این افراد خواسته بود که در آزمایش او شرکت کنند.از آنها خواسته شد که نامه ای را به فرد خاص در بوستون بفرستند ،تنها با استفاده از افرادی که آنها را بر اساس نام کوچکشان می شناسند .هنگامی که میلگرام به نتایج نگاه کرد ،منوجه شد که هر کدام از افراد با حدود شش نفر تماس گرفته اند تا به هدف برسند ،به طور متوسط مردم ایالات متحده آمریکا توسط 6 نفر جدا می شوند(یا به عبارتی ارتباط بین دو نفر توسط 6 نفر برقرار می شود) که به آن قانون 6درجه جدایی (six degrees of separation) می گویند.
بنابراین در روش کوتاهترین مسیر ما به فاصله بین دو گره نگاه میکنیم و احتمال اینکه یک لینک به عنوان منفی کوتاهترین فاصله بین دو گروه باشد را تخمین میزنیم:
پیاده سازی اولیه این استراژی میتواند فضای جستجو را برای اولین بار و فرض اینکه هر گره به طور متوسط دارای n همسایه است،o(v´.nˡ) زمان پیش بینی بر آورد را بر روی گراف ورودی G´ انجام میشود.در مثال گراف G´ که در شکل زیر نمایش داده شده است،هم B و هم C در فاصله 2 از شما واقع شده اند ، به طوریکه می توانند با احتمال برابر پیشبینی شوند.
Anne Gatchell -Andy McEvoy CSL - Link Prediction Link Prediction in Social Networks
April 29, 2013
متدهای پیشبینی لینک
متدهای پیشبینی لینک:
درمورد پیشبینی لینک در زمینه پیشبینی لینک هایی از یک منبع که می توانیم از آن به عنوان گره x یاد کنیم به گره های دیگر که نام آن ها را گره y میگذاریم می باشد.بنابراین،روش هایی که در اینجا در مورد آن بحث می کنیم ،روش هایی هستند که می توانند به عنوان راس ´ɤEV نامیده شوند.در زمان اجرا هر متد با فرض اینکه گراف ´G پراکنده و غیر متراکم است و متوسط مقدار اتصالات هر گره N است،پیش میرود. lᵐᵃᵡ به عنوان حداکثر طول مسیر بین دو گره که احتمالا می تواند یک یال را تحت تاثیر قرار دهد تعریف می شود.مسیرهای طولانی تر را اینگونه فرض خواهیم کرد که احتمال نفوذ آنها در یال های موجود صفر است.
الگوریتم زیر یک آزمایش تجربی
کوچک در مورد کشف یک متد است و شکل زیر همان الگوریتم را به صورت ویژوال به تصویر
می کشد.
در شکل زیر V´² می تواند یک یال درʺG باشد . E´ شامل هر دو Eʺ و یال هایی است که ما خذف کرده ایم.Eᶰᵉᵚ نشان
دهنده یال هایی است که با بالاترین امتیاز در اثر اجرای یک روش جدید کشف شده
پیشبینی لینک بدست آمده است. در محل تقاطع بین E´-Eʺ و Eᶰᵉᵚ نشان دهنده مجموعه ای از پیشبینی یال های موفق است و هدف به حد
اکثر رساندن اندازه این مجموعه است.حد بالای این مجموعه موفق برابر است با E´-Eʺ| |
Anne Gatchell -Andy McEvoy CSL - Link Prediction Link Prediction in Social Networks
April 29, 2013