15184

15184

بخش بندي تطبيق پذير گراف هاي بزرگ مقياس

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

نرم افزار

اسفند ماه 1393

اسفند ماه 1393

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

كامپيوتر

چكيده گراف يك مدل تأثيرگذار در نمايش روابط بين موجوديت¬ها است. گراف براي نمايش و مدل كردن ارتباطات شبكه¬اي، روابط اجتماعي، پيوندهاي وب¬ و كانال¬هاي حمل‌ونقل بين مكان¬ها استفاده مي¬شود. در دهه اخير ما شاهد رشد قابل‌توجهي در توانايي ذخيره¬سازي حجم بالايي از اطلاعات بوديم. اين اطلاعات باعث به وجود آمدن گراف¬هايي شده است كه تعداد رأس و يال آن‌ها به ميليون و يا حتي بيليون مي¬رسد. به دست آوردن دانش از اين گراف¬هاي حجيم، به يك چالش تبديل شده است. يك راهكار استاندارد براي به دست آوردن دانش از اين گراف¬هاي حجيم پردازش توزيع‌شده اين گراف¬ها است. به همين جهت سيستم¬هاي پردازش گرافي توزيع‌شده متعددي معرفي شده¬اند. يكي از عواملي كه مي¬تواند بر روي كارايي اين سيستم¬ها تأثيرگذار باشد، چگونگي بخش¬بندي گراف در سيستم¬ پردازش توزيعي است. بخش¬بندي مطلوب گراف در سيستم¬هاي پردازش گراف مي¬تواند به افزايش سرعت انجام محاسبات، كاهش بار شبكه و افزايش موازي¬سازي كمك كند. سيستم¬هاي پردازش گراف با توجه به مدل محاسباتي خود معيارهاي متفاوتي براي بخش¬بندي ارائه داده¬اند. ارائه يك روش بخش¬بندي با توجه به معيارهاي يك سيستم پردازش گراف مي¬تواند تأثير بسزايي در كارايي آن سيستم داشته باشد. در اين پايان¬نامه يك روش¬ بخش-بندي براي دسته¬اي از سيستم¬هاي پردازشي گراف ارائه‌شده است. روش پيشنهادي باتوجه به مدل محاسباتي اين سيستم¬ها معيار¬هايي براي بخش¬بندي گراف معرفي مي¬كند. در اين روش گراف به‌صورت محلي بخش¬بندي مي¬شود و هر قسمت از گراف به صورت جرياني به سيستم بخش¬بندي وارد شده و آن قسمت با توجه به اطلاعاتي كه از بخش¬بندي گراف تا اين لحظه بدست آمده تمام و يا قسمتي از آن به يك بخش اختصاص مي يابد. هدف اين بخش¬بندي كاهش زمان پردازش در سيستم پردازش گراف دارد. اين روش با ورود تغييرات به گراف با استفاده از اطلاعاتي كه از بخش¬بندي اوليه نگه داشته، بخش¬بندي را به روز رساني مي¬كند و نياز به بخش¬بندي از ابتدا ندارد. واژه‌هاي كليدي: گراف، بخش¬بندي، گراف جرياني، خوشه¬بندي، گراف پويا