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

چکیده مقاله

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