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