متد Simrank
متد Simrank :
Simrank یک متد است برای رتبه بندی درجه شباهت اشیاء.این متد بر این اصل استوار است که اکر دو جسم به اشیاء مشابه مرتبط باشند آن دو جسم مشابه هستند.ما می توانیم از این اصل برای پیش بینی لینک استفاده کنیم. بدین صورت که بگوییم دو گره مشابه هستند اگر همسایه مشابه داشته باشند.بنابراین ، a و b مشابه هستند اگر متصل باشند c و d ،به شرطی که c و d خود مشابه باشند. اساس کر این است که شیء شبیه به خود باشد. به عنوان مثال a کاملا مشابه a است.
ما می توانیم شباهت را در مقیاس [0,1] اندازه گیری کنیم، هنگامی که 1 ماکزیمم شباهت باشد و 0 کاملا غیر مشابه باشد. یک گره که به هیچ یک از گره های دیگر متصل نیستند با دیگر گره های موجود در شبکه دارای شباهت 0 است.
به عنوان مثال چگونگی شباهت در یک حالت انتشار پایه در شکل زیر نشان داده شده است.این شکل یک شبکه بین چند دوست است.لسلی دارای بیشترین شباهت با خودش است ، بنابراین ما میتوانیم به این موضوع پی ببریم که آپریل و رون شاید با یکدیگر شباهت داشته باشند ،اما با میزان کمتر.به طور مشابه ، آپریل و رون مشابه هستند ، سپس ما میتوانیم استنباط کنیم که آنها با یکدیگر دوستان نسبی هستند، اندی و سپاستین نیز با یکدیگر مشابه هستند اما به میزان کمتر از آپریل و رون.البته این سری از شباهت به صورت n² جفت از افراد در شبکه گسترش میابد، و جفت های مشابه دیگر تحت تاثیر گره های بیرونی لسلی قرار می گیرند.
در شکل بالا نشان داده شده است که لسلی بیشترین شباهت را به خودش دارد s(Lesley,Lesley)=1 ،شباهت از دوستان او منتشر می شود همچنین از دوستان دوستان.
این ایده بر اساس شباهت هاست و بر اساس این نظریه که شباهت ها به شباهت های بین همسایگان بستگی دارد، که بستگی به شباهت های همسا یه ای که به صورت برگشتی به خود تعریف می شود.
برای اندازه گیری شباهت بین دو گره با اشاره به s(a,b) :
(1)
ما به گونه ای امتیاز بین دو گروه را برای هدف اکتشافی خود تعریف می کنیم که شباهت بین دو گره برابر باشد با:
در معادله (1) مورد اصلی تعریف شده شباهت یک گره به خودش است، مورد بازگشتی تکرار همه جفت های همسایه (z,z´) از (a,b) است،خلاصه شباهت s(z,z´) بین هر یک از این جفت ها وجود دارد.سپس تقسیم بر تعداد کل جفت های همسایه می کنیم.
|Γ(a)||Γ(b)| ،برای نرمالسازی جمع انجام می شود. بنابراین ، این اساس معدل گیری شباهت های همسایه های a و همسایگان b است.باید توجه داشت که به معنای تقارن است یعنی s(a,b)=s(b,c)
ثابت c را می توان به عنوان یک فاکتور تعدیل یا فاکتور اعتماد در نظر گرفت.به عنوان مثال ،در مثال قبل از شکل 4 ،هنگامی که ما آپریل و رون را مشابه هم در نظر گرفتیم و در حقیقت لسلی با آنها دوست است ،در این حال ما میتوانیم بگوییم s(april,ron)=s(leslie,leslie)=1 ،اما چیزی که خیلی می توان از آن اطمینان داشت درجه شباهت بین آپریل و رون در این مدت است.
بنابراین بهتر است ما بوسیله یک ثابت شرایط را بهبود ببخشیم.بطوریکه:
s(april,ron)=c.s(leslie,leslie) برای c=[0,1] . ولی در حقیقت افراد اغلب از c=0.8 استفاده میکنند.
Anne Gatchell -Andy McEvoy CSL - Link Prediction Link Prediction in Social Networks
April 29, 2013