متد کاتز Katz
متد کاتز (katz):
میخواهیم به ایده جهان کوچک و ایده های موجود در همسایگان مشترک رویکرد دیگری داشته باشیم،اگر یک مسیر کوتاه بین دو گره نشان می دهد که ممکن است یک لینک مناسب بین آن دو وجود داشته باشد،بنابراین اگر تعدادزیادی مسیر کوتاه بین دو گره وجود داشته باشد احتمال قوی تری برای وجود ارتباط بین این دو گره وجود دارد.آزمایش بر روی گراف G´ در شکل زیر نشان داد که مسیرهایی بین شما و گره های B و C وجود دارد.
این مشاهدات در جدول زیر برای نمایش جزییات طول مسیرهای مختلف و همچنین نشان ارزش کمتر طول مسیرهای بلند تر نمایش داده
شده است :
|
طول مسیر |
فاصله های شما و گره B |
فاصله های شما و گره C |
تعدیل |
|
2 |
2 |
1 |
2/1 |
|
3 |
2 |
1 |
4/1 |
|
4 |
0 |
1 |
8/1 |
محاسبه امتیاز بر اساس همه مسیرهایی که بین شما و گره B و C در گراف G´ وجود دارد.
با استفاده از این جدول میتوانیم یک امتیازی را برای هر یال ممکن محاسبه کنیم که در دو معادله زیر نشان داده شده است:
و اگر بخواهیم بطور رسمی تر عنوان کنیم،از تابع زیر استفاده می کنیم:
جاییکه β فاکتور وزن است و معمولا انتخاب به گونه ای انجام می شود که مسیرهای دیگر نمی توانند تحت تاثیر احتمال یک لینک بین
دو گره قرار گیرند.
به معنای وزن همه مسیرهای بین x و y در طول L است .این متد می تواند برای استفاده از فرم
عمق اولین جستجو Depth
first search))
پیاده سازی شود.
هر یال به عنوان یک درخت شناخته می شود،یال های عقب ،جلو و یا یال هایی که یکدیگر را قطع می کنند ،شما می توانید از این طریق تعداد مسیر هایی که به هر گره می رسد را بدست آورید و همچنین می توانید طول این مسیر ها را نیز بدست آورید.
Anne Gatchell -Andy McEvoy CSL - Link Prediction Link Prediction in Social Networks
April 29, 2013
متد همسایگان مشترک 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
متدهای پیشبینی لینک:
درمورد پیشبینی لینک در زمینه پیشبینی لینک هایی از یک منبع که می توانیم از آن به عنوان گره x یاد کنیم به گره های دیگر که نام آن ها را گره y میگذاریم می باشد.بنابراین،روش هایی که در اینجا در مورد آن بحث می کنیم ،روش هایی هستند که می توانند به عنوان راس ɤEV نامیده شوند.در زمان اجرا هر متد با فرض اینکه گراف ´G پراکنده و غیر متراکم است و متوسط مقدار اتصالات هر گره N است،پیش میرود. lᵐᵃᵡ به عنوان حداکثر طول مسیر بین دو گره که احتمالا می تواند یک یال را تحت تاثیر قرار دهد تعریف می شود.مسیرهای طولانی تر را اینگونه فرض خواهیم کرد که احتمال نفوذ آنها در یال های موجود صفر است.
الگوریتم زیر یک آزمایش تجربی کوچک در مورد کشف یک متد است و شکل زیر همان الگوریتم را به صورت ویژوال به تصویر می کشد.
در شکل زیر V´² می تواند یک یال درʺG باشد . E´ شامل هر دو Eʺ و یال هایی است که ما خذف کرده ایم.Eᶰᵉᵚ نشان دهنده یال هایی است که با بالاترین امتیاز در اثر اجرای یک روش جدید کشف شده پیشبینی لینک بدست آمده است. در محل تقاطع بین E´-Eʺ و Eᶰᵉᵚ نشان دهنده مجموعه ای از پیشبینی یال های موفق است و هدف به حد اکثر رساندن اندازه این مجموعه است.حد بالای این مجموعه موفق برابر است با |E´-Eʺ|