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

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