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

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