یک روش آیندهنگر برای بخشبندی جریانی گرافهای بزرگ

گرافها ساختارهایی هستند که برای مدل کردن طیف گستردهای از مسایل در حوزه علوم کامپیوتر،فنآوری اطلاعات وسایر حوزهها مورداستفاده قرارگرفته و در بسیاری از مباحث مهم ازجمله:پردازش موازی، پردازش تصویر و کلان دادهکاربرد دارند. بخشبندی جریانی گراف یک مسیله کلیدی برای انجام محاسبات کارآمد و مقیاسپذیر رویدادههای گرافهای بزرگی همچون گراف شبکه اینترنت و شبکههای اجتماعی است.افزایش اندازه گراف باعث ایجاد چالشهایی درانجام محاسبات و استخراج دانش از گراف موردنظر میگردد، از طرفی مسیله بخشبندی گراف یک مسیله ان پی سخت است که ارایه یک روش ابتکاری کارآمد و بهینه برای حل آن از اهمیت بسیار بالایی برخوردار است. لذا در این پژوهشتلاش کردهایم با ارایه یک روش جدید نتایج بهتری نسبت به کارهایی که قبلا در این حوزه انجامشده به دست آوریم.تمرکز ما بر روی درجات ریوس گراف بوده است با دستهبندی ریوس به سه گروه: ریوس با درجه بالا، ریوس با درجه پایین و سایر ریوس، هنگام تخصیص آنها به بخشهای مختلف از سیاست متناسب با وضعیت آنها استفاده میشود بهاینترتیبکه ریوس درجه پایین را برای ایجاد تعادل بین بخشها و از سایر ریوس بهجز ریوس درجه بالا برای دستیابی به میزان یال برش خورده کمتر استفاده میکنیم. ریوس با درجه بالا نیز سعی میشود با اولویت بروز کمترین یال برش خورده بهطور مساوی بین بخشها توزیع گردند. برای توزیع ریوس درجه بالا نیاز به یک ایده آیندهنگر داشته و باید بر اساس مشاهداتیکه تا هر مرحله از دادههای رسیده از گراف داشتهایم تعداد این ریوس در کل گراف را تخمین بزنیم. نتایج حاصل از آزمون این روش بر روی چندین مجموعه داده نشان داده است که در مقایسه با بهترین روشها در گرافهای بزرگ کاهش ده درصدی ) 10 ٪( در شاخص یال برش خورده با حفظ تعادل مناسب داشتهایم.

Keywords:

بخشبندی گراف , بخشبندی جریانی , الگوریتمهای جریانی , بخشبندی متعادل , رایانش توزیعشده