14876

14876

ارائه‌ي روشي جهت شناسايي اجزاي همبند گراف‌هاي بزرگ به صورت توزيع‌شده

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

نرم افزار

اسفندماه 1393

اسفندماه 1393

دكتر حسن نادري

كامپيوتر

چكيده به لحاظ غناي اطلاعاتي موجود در سايت‌هايي نظير شبكه‌هاي اجتماعي و سايت‌هاي خريد و فروش اينترنتي، تحليل اطلاعات حاصل از اين سايت‌ها در حوزه‌هاي گوناگون داراي كاربرد مي باشد. به واسطه‌ي ذات اين شبكه‌ها، يكي از رهيافت‌هاي تحليل آن‌ها، تبديل ساختار آن‌ها به ساختار گرافي مي‌باشد. با توسعه‌ي روز‌افزون استفاده از اين شبكه‌ها گراف حاصل از آنها بسيار حجيم (از لحاظ تعداد گره و يال) شده است. به همين جهت پردازش و تحليل گراف‌هاي بسيار بزرگ امروزه به عنوان يك ضرورت تبديل شده است. شناسايي اجزاي همبند گراف از جمله تحليل‌هاي گراف مي‌باشد كه به عنوان زيربخش بسياري از الگوريتم‌هاي گرافي نظير خوشه‌بندي، بخش‌بندي، رنگ‌آميزي استفاده قرار مي‌گيرد. در اين پايان‌نامه هدف شناسايي اجزاي همبند گراف‌هاي بسيار حجيم به صورت توزيع‌شده مي‌باشد. كارهاي صورت گرفته در اين پژوهش را سه بخش مي‌توان تشريح نمود: در بخش اول هدف افزايش مقياس‌پذيري روش Hash-to-all در مواجهه با گراف‌هاي بسيار بزرگ مي‌باشد. اين روش حجم ترافيك شبكه‌ي بسيار بالايي دارد. بهينه‌سازي‌هايي بر مبناي شناسايي زودهنگام همگرايي الگوريتم، حذف ارسال اطلاعات غيرضروري در شبكه، تعامل اطلاعات تنها با همسايه‌هاي جديد به جاي تمام همسايه‌ها بر روي اين روش ارائه گرديد. در بخش دوم يك روش پيش‌پردازش به منظور كاهش اندازه‌ي گراف ورودي (گره و يال) به الگوريتم‌هاي شناسايي اجزاي همبند ارائه گرديده است. اين روش با يك مقايسه‌ي كم‌هزينه، تكليف جزء همبندي بسياري از گره‌هاي گراف را تعيين مي‌نمايد. در نتيجه با حذف اين گره‌ها (و يال‌هاي مربوطه) از گراف اصلي، اندازه‌ي گراف ورودي بسيار كاهش مي‌يابد. در بخش سوم روشي جديد به منظور شناسايي اجزاي همبند گراف ارائه شده است. اين روش اولين روشي است كه قادر است در تعداد ثابتي مرحله‌ي مپ-رديوس (2 مرحله) اجزاي همبند گراف را محاسبه نمايد. ارزيابي صورت گرفته بر روي مجموعه گراف‌هاي واقعي بزرگ نشان داد كه پيش‌پردازش معرفي شده قادر است 99 درصد از سايز گراف را كاهش دهد كه اين امر منجر به افزايش سرعت 3 تا 8 برابر در محاسبه‌ي اجزاي همبند گراف شده است. به علاوه روش پيشنهادي دو مرحله‌اي شناسايي اجزاي همبند افزايش سرعت 20 تا 25 برابر نسبت به روش pegasus و افزايش سرعت 5 تا 10 برابر نسبت به روش ccmr داشته است. واژه‌هاي كليدي:مدل برنامه‌نويسي مپ-رديوس، گراف‌هاي بزرگ، اجزاي همبند، روش توزيع‌شده