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

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