متد کاتز 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