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

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

مهدی عالمی, حسن حقیقی

چکیده

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

کلمات کلیدی

اجتماعات منسجم, شبکه های اجتماعي, پردازش موازی, شمارش مثلث, k-Truss