متد همسایگان مشترک 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