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