تشخیص شبکه‌های چگال از شبکه‌های شبه‌درختی برای پیش‌بینی لینک بر مبنای معیارهای همگنی و ناهمگنی

چکیده مقاله

پیش‌بینی لینک، وجود یا عدم وجود ارتباط بین دو موجودیت را بر اساس ویژگی¬های موجودیت¬ها و دیگر لینک¬های مشاهده شده در گراف بررسی می‌کند. الگوریتم¬های پیش¬بینی لینک متفاوتی تا بحال معرفی شده‌اند. این مقاله دو نوع الگوریتم پیش¬بینی لینک را برای شبکه¬های خلوت و چگال بررسی می‌کند؛ در ریاضیات، یک گراف چگال گرافی است که تعداد یال‌های آن نزدیک به بیشینه تعداد یال‌ها باشد و در مقابل یک گراف با کمینه‌ی تعداد یال‌ها یک گراف خلوت است. در این مقاله مقدار ضریب خوشگی برای گراف¬ها با ساختار همگنی و ناهمگنی متفاوت محاسبه شد. سپس بهترین الگوریتم پیش‌بینی لینک برای آن گراف‌ها مشخص شد. در نتیجه، مقداری از ضریب خوشگی بدست آمد که با استفاده از آن می¬توان الگوریتم مناسب برای پیش¬بینی لینک در شبکه را تشخیص داد. به این دلیل که تعداد گراف کافی برای بدست آوردن مقدار مناسب ضریب خوشگی وجود نداشت، روشی را برای تولید گراف تصادفی معرفی کردیم و با استفاده از آن، نقطه مرزی برتری الگوریتم¬های مبتنی بر همسایه مشترک و الگوریتم¬های مبتنی بر درجه نود گراف را بدست آوردیم.