پیش بینی پیوند شبکه براساس تعداد مثلث مبتنی بر زیرگراف

Abstract

با رشد روزافزون شبکه‌های اجتماعی، مساله پیش¬بینی پیوند مورد توجه قرار گرفته است. پیش¬بینی پیوند به منزله پیش¬بینی ارتباطات جدید بین افراد، براساس ارتباطات موجود و ویژگی‌های شبکه است. احتمال ایجاد ارتباط بین افرادی که شباهت‌های بیشتری به یکدیگر دارند، بالاتر است. روش‌های متفاوتی برای پیش¬بینی پیوند ارائه شده، که بعضی از آن‌ها بر روی ویژگی‌های ساختاری شبکه متمرکز هستند. برای رسیدن به ویژگی‌های ساختاری مشابه، گره‌ها به همراه گره‌های همسایه در یک زیرگراف درنظر گرفته می‌شوند. یکی از ویژگی‌های ساختاری مهم در شبکه، تعداد مثلث‌های ایجاد شده است. مثلث نشان‌دهنده‌ی کوچکترین و قوی‌ترین اجتماع در شبکه است که در رشد و تکامل شبکه نقش مهمی دارد. در این مقاله، روش¬های مبتنی بر شباهت با در نظر گرفتن زیرگراف و استفاده از مفهوم مثلث بازنویسی شده است. برای ارزیابی کارآیی این دو بازنویسی پیشنهادی، روش ژاکارد به دو صورت مبتنی بر زیرگراف و مبتنی بر مثلث در زیرگراف بازنویسی شده و آزمایش‌هایی بر روی گراف¬های تصادفی و شبکه‌های واقعی انجام شده است. آزمایش‌ها نشان می‌دهد که هر دو روش بازنویسی پیشنهادی از ژاکارد استاندارد عملکرد بهتری دارند. به عنوان نمونه، در آزمایش انجام شده بر روی گراف‌های تصادفی، معیار ژاکارد بازنویسی شده مبتنی بر زیرگراف به‌طور میانگین 3/3 درصد و معیار ژاکارد بازنویسی شده مبتنی بر مثلث در زیرگراف به‌طور میانگین 7/6 درصد بهبود نسبت به ژاکارد استاندارد داشته است. همچنین نتایج بر روی شبکه‌های واقعی نشان می¬دهد که معیار ژاکارد بازنویسی شده مبتنی بر زیرگراف به‌طور میانگین 6/3 و معیار ژاکارد بازنویسی شده مبتنی بر مثلث در زیرگراف به‌طور میانگین 45/7 درصد بهبود داشته است.