فا   |   En
ورود به سایت

الگوریتم موازی برای کاوش زیرگراف‌های منسجم در گراف‌های حجیم

نویسنده: مهدی عالمی و حسن حقیقی

یافتن زیرگراف‌های منسجم در بسیاری از کاربردها از جمله موتورهای جستجو، شبکه‌های اجتماعی و شبکه‌های بیولوژی جایگاه ویژه‌ای دارد. در این بین، زیرگراف K-Truss به دلیل سادگی و کاربردهایی مانند یافتن نقاط پرچگال و ترسیم گراف کاربرد اهمیت دارد. با توجه به حجم زیاد گراف‌ها، توسعه‌ی الگوریتم‌های موازی برای افزایش سرعت در پاسخ‌دهی نیازی اساسی است. برای این منظور، در این مقاله یک الگوریتم موازی برای کاوش زیرگراف‌های منسجم در گراف‌های حجیم در 2 فاز ارائه شده است؛ در فاز اول، ابتدا با یک الگوریتم موازی مثلث‌های گراف یافت می‌شوند و خروجی‌ها در یک ساختار جدید با نام رأس‌های مثلثی برای نگهداری مجموعه رأس‌هایی که با هر یال تشکیل یک مثلث می‌دهند، تولید می‌شود. در فاز دوم، در یک حلقه به صورت موازی یال‌های نامعتبر به تدریج از مجموعه یال‌های موجود حذف می‌گردند تا زمانی‌ که هیچ یالی که خصوصیت K-Truss را نقض می‌کند، پیدا نشود. کارایی روش پیشنهادی در مقایسه با دیگر روش‌ها و مقیاس‌پذیری آن، با انجام آزمایش‌هایی بر روی یک ماشین 12 هسته‌ای با استفاده از مجموعه گراف‌های استاندارد نشان داده شده است.

فايل مقاله