(۲-۲۳)
به این صورت است که تعداد جنگل های پوشا با ریشه x که x و y در یک درخت باشند نسبت به تعداد کل جنگل های پوشای ممکن. اگر تعداد جنگل های پوشا با ریشه x که x و y که در یک درخت باشند بیشتر باشد یعنی ارتباطات بیشتری بین x و y برقرار است پس شباهت دو گره بالاتر است.
تفاوت شاخص های محلی و سراسری در این است که متد های محلی بر روی لینک های مجاور دو گره بررسی می کند ولی روش سراسری بر روی کل اطلاعات گراف و توپولوژی شبکه کار می کند. در سراسری شباهت دقیقتر محاسبه می شود ولی محاسبه بسیار زمانبند است و برای شبکه های بزرگ غیر ممکن .
توازن دو روش محلی و سراسری متد های شبه محلی هستند.
۲-۳-۱-۳- شاخص های شباهت شبه محلی[۴۸]
شاخص [۴۹]:
این متد توازن بین دقت و پیچیدگی را برقرار می کند . در این روش پیچیدگی را تا حدی بالا می بریم که به دقت قابل قبولی برسیم. (Lü,L. , Jin, C. , Zhou1, T. , (2009)).
(۲-۲۴)
پارامتری برای وزن دادن به مسیر ها با فاصله های دور و نزدیک است. مسیر های نزدیکتر با ارزشترند. بدیهی است همان متد CN خواهد شد.
(۲-۲۵)
این روش با مقادیر مختلف ، توازنی بین CN و شاخص کتز برقرار میکند.
بر اساس ارزیابی ها متد LP بهتر از RA , CN ,AA عمل می کند. در جدول ۲-۲ مقایسه متد های LP ، Katz و LHN2 نشان داده شده . در روش ارزیابی AUC متد Katz بهترین کارایی و در روش Precision متد LP بهترین کارایی را دارد. در شبکه هایی با میانگین فاصله های کوتاه مثل USAir و PB متد LP به خوبی می تواند پیش بینی مورد نظر را انجام دهد.
جدول ۲-۲- مقایسه متد های katz ، LP و LHN2
روش گام برداشتن تصادفی محلی (LRW)[50] :
(۲-۲۶)
یک بردار که عضو x ام آن برابر ۱ و سایر اعضا برابر صفر است.
بیانگر احتمال حرکت رونده با شروع از گره x با t گام به گره Yبصورت بازگشتی. ماتریس احتمال حرکت است . اگر ارتباط x و y قطع باشد و اگر ارتباط وصل باشد. بنابراین احتمال حرکت از x به y برابر است. که مجموع درجات همه گره هاست. بنابراین احتمال برقراری لینک در دو گره ای که درجه بزرگتری دارند بیشتر خواهد بود.
(۲-۲۷)
روش گام برداشتن تصادفی انطباقی (SRW)[51] :
مانند روش LRW است و محاسبه احتمال حرکت X به Y با حداکثر t گام. SRW با t های مختلف توازنی بین شاخص محلی و شاخص سراسری ایجاد می کند
(۲-۲۸)
این روش بهینه یافته روش LRW است.
همانطور که مشاهده شد روش SWR بیش ترین دقت را در ۵ شبکه با استفاده از معیار ارزیابی AUC دارد.
جدول ۲-۳- مقایسه الگوریتم های مختلف پیش بینی در ۵ شبکه متفاوت
 
۲-۳-۲-متدهای بیشترین احتمال [۵۲]:
این الگوریتم ها فرض می کنند که اصول سازماندهی مشخصی در شبکه وجود دارد . با پارامتر ها و قوانین معین که با استفاده از ماکزیمم کردن احتمال ساختارهای مشاهده شده بدست می آید . بنابراین احتمال هر لینک مشاهده نشده با این قوانین و پارامترها بدست می آید.
مشکل این الگوریتم ها زمانبر بودن آنهاست و با شبکه های بزرگ جزء دقیق ترین متد ها نیست . مزیت این روش ها دیدی است که به ما در مورد شبکه می دهد.
۲-۳-۲-۱-روش های مبتنی بر بیش ترین احتمال[۵۳]
مدل ساختار سلسله مراتبی [۵۴]:
در شکل ۱ ساختار سلسله مراتبی یک شبکه به صورت دندروگرام با N گره برگ ، بیان شده.)متناظر با نود های شبکه).
هر گره داخلی r دارای احتمال است .احتمال اتصال یک جفت برگ است که پایین ترین جد مشترک بین دو گره ، برگ است.) احتمال اتصال۳ و ۵ ، ۰٫۴ است).
دندروگرام d درختی است که از روی گراف شبکه ساخته شده است. تعداد لبه هایی در گراف که نودهای دو سر این لبه ها دارای r مشترک باشند r) پایین ترین جد مشترک گره های انتهایی آن لبه ها در d باشد). به عنوان مثال اگر در گراف شبکه یالی باشد که دو سر آن ۳،۵ و ۳،۴ باشد. یعنی اگر این دو یال باشد مقدار می شود.
تعداد برگ ها در زیر درخت سمت چپ () و تعداد برگ ها در زیر درخت سمت راست ().
 
شکل ۲-۱- دندروگرام شبکه با ۵ نود
ماکزیمم احتمال دندروگرام d با یک مجموعه از :
(۲-۲۹)
(۲-۳۰)
بهینه ترین حالت برای محاسبه احتمال است. یعنی بهینه ترین حالت زمانی است که توازن بین زیر درخت سمت راست و چپ جد مشترک برقرار باشد. در شکل ۲-۲ دو دندروگرام متفاوت از گراف شبکه ترسیم شده است.
 

دانلود متن کامل این پایان نامه در سایت abisho.ir