10241

10241

طراحي و پياده‌سازي الگوريتمي براي استخراج توزيع‌شده‌ي شبه- دسته‌هاي گاما از گراف‌هاي عظيم

كارشناسي ارشد

كامپيوتر - نرم‌افزار

اسفند ماه 1390

اسفند ماه 1390

دكتر محسن شريفي

شبكه‌هاي پيچيده همچون شبكه‌هاي اجتماعي و پيوند صفحات وب اغلب در قالب گراف مدل مي‌شوند و مورد تحليل قرار مي‌گيرند. در اين گراف‌ها بخش‌هايي كه متراكم بوده و تعداد اتصالات بالايي دارند داراي اهميت فراواني هستند و الگوريتم‌هاي متعددي براي استخراج اين نقاط ارائه شده است. با توجه به پيچيدگي زماني بالاي اين مسئله، رشد روزافزون حجم داده‌ها و ماهيت توزيعي داده‌هاي امروزي، الگوريتم‌هاي ارائه شده داراي محدوديت‌هاي زيادي همچون حجم محدود حافظه، سرعت پايين استخراج و عدم مقياس‌پذيري هستند. در اين پايان‌نامه، الگوريتمي توزيعي و مبتني بر مدل مپ‌رديوس براي استخراج شبه-دسته‌هاي گاما، به عنوان نوعي از زيرگراف‌هاي متراكم، ارائه مي‌كنيم. الگوريتم پيشنهادي كه به نام دكسي نام‌گذاري شده، ابتدا ليست مجاورت هر يك از رأس‌ها و درجه‌ي آن‌ها را به دست مي‌آورد، سپس گراف ورودي را به بخش‌هاي كوچك‌تر تقسيم نموده و اطلاعات مورد نياز هر بخش را براي پردازش نهايي به يك كامپيوتر جداگانه در سيستم توزيعي منتقل مي‌نمايد. در كامپيوتر مقصد فضاي جست‌و‌جوي نهايي ايجاد شده، شبه-دسته‌هاي گاما استخراج شده و در نهايت ركوردهاي مشابه حذف مي‌گردند. نتايج ارزيابي‌ها نشان مي‌دهد كه پيچيدگي محاسباتي شكستن گراف در الگوريتم دكسي برابر O(n2) و پيچيدگي محاسباتي استخراج شبه-دسته‌هاي گاما O(3n/m) است. كاستن از پيچيدگي محاسباتي استخراج شبه-دسته‌هاي گاما و افزودن پيچيدگي محاسباتي شكستن گراف باعث مي‌شود تا با افزايش اندازه‌ي گراف ورودي و كاهش گاما، دكسي زمان اجرايي كمتري نسبت به الگوريتمي مشابه با نام كوييك داشته باشد. همچنين نتايج ارزيابي مقياس‌پذيري نشان مي‌دهد كه با افزايش تعداد ماشين‌هاي يك سيستم توزيعي، سرعت اجراي الگوريتم دكسي نيز به صورت تقريباً خطي افزايش مي‌يابد. واژه‌هاي كليدي: زيرگرافهاي متراكم، شبه-دسته‌هاي گاما، پردازش توزيعي گراف، گراف‌هاي عظيم