متد کوتاهترین مسیر
متد کوتاهترین مسیر:
الگوریتم جهان کوچک را در نظر بگیرید . میلگرام در آزمایشی افراد مختلفی را از نبراسکا و کانزاس انتخاب کرد و برای آنها نامه ای فرستاد.در این نامه او از این افراد خواسته بود که در آزمایش او شرکت کنند.از آنها خواسته شد که نامه ای را به فرد خاص در بوستون بفرستند ،تنها با استفاده از افرادی که آنها را بر اساس نام کوچکشان می شناسند .هنگامی که میلگرام به نتایج نگاه کرد ،منوجه شد که هر کدام از افراد با حدود شش نفر تماس گرفته اند تا به هدف برسند ،به طور متوسط مردم ایالات متحده آمریکا توسط 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