TY - JOUR ID - 162420 TI - الگوریتم موازی برای کاوش زیرگراف های منسجم در گراف های حجیم JO - علوم رایانش و فناوری اطلاعات JA - JCSIT LA - fa SN - 2676-5438 AU - عالمی, مهدی AU - حقیقی, حسن AD - دانشکده مهندسی و علوم کامپیوتر، دانشگاه شهید بهشتی، تهران Y1 - 2018 PY - 2018 VL - 16 IS - 1 SP - EP - KW - اجتماعات منسجم KW - شبکه های اجتماعی KW - پردازش موازی KW - شمارش مثلث KW - k-Truss DO - N2 - یافتن زیرگراف های منسجم در بسیاری از کاربردها از جمله موتورهای جستجو، شبکه های اجتماعی و شبکه های بیولوژی جایگاه ویژه ای دارد. در این بین، زیرگراف K-Truss به دلیل سادگی و کاربردهایی مانند یافتن نقاط پرچگال و ترسیم گراف کاربرد اهمیت دارد. با توجه به حجم زیاد گراف ها، توسعه ی الگوریتم های موازی برای افزایش سرعت در پاسخدهی نیازی اساسی است. برای این منظور، در این مقاله یک الگوریتم موازی برای کاوش زیرگراف های منسجم در گراف های حجیم در 2 فاز ارائه شده است؛ در فاز اول، ابتدا با یک الگوریتم موازی مثلث های گراف یافت می شوند و خروجی ها در یک ساختار جدید با نام رأسهای مثلثی برای نگهداری مجموعه رأسهایی که با هر یال تشکیل یک مثلث می دهند، تولید می شود. در فاز دوم، در یک حلقه به صورت موازی یالهای نامعتبر به تدریج از مجموعه یالهای موجود حذف میگردند تا زمانی که هیچ یالی که خصوصیت K-Truss را نقض می کند، پیدا نشود. کارایی روش پیشنهادی در مقایسه با دیگر روش ها و مقیاس پذیری آن، با انجام آزمایش هایی بر روی یک ماشین 12 هستهای با استفاده از مجموعه گرافهای استاندارد نشان داده شده است. UR - http://jcsit.ir/article_162420.html L1 - ER -