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

از روش های خوشه بندی برای بازیابی ساختار نرم افزار جهت فهم درست آن و همچنین بازسازی نرم افزار استفاده می شود. در ادبیات موضوع، بیشتر الگوریتم های ارایه شده برای خوشه بندی سامانه های نرم افزاری به دو دسته الگوریتم های مبتنی بر جستجو و الگوریتم های سلسله مراتبی طبقه بندی می شوند و الگوریتمی از رده مبتنی بر افراز برای خوشه بندی یک سامانه نرم افزاری ارایه نشده است. این روش ها سعی دارند که گراف وابستگی موجودیت به دست آمده  از کد منبع سامانه نرم افزاری را به چند مجموعه راسی افراز کنند. در سامانه های نرم افزاری، موجودیت می تواند رده، تابع و یا یک فایل باشد. با توجه به چندجمله ای غیر قطعی، سخت بودن مساله خوشه بندی، در سال های اخیر از روش های تکاملی و مبتنی بر جستجو مانند الگوریتم ژنتیک برای این حل این مساله، زیاد استفاده شده است. هر چند این الگوریتم ها در برخی موارد می توانند ساختار مناسبی از نرم افزار را به دست آورند، اما برای نرم افزار های با ابعاد بزرگ، با توجه به زمان اجرا و حافظه مصرفی زیاد، قابل اجرا نیستند؛ همچنین، این روش ها از اطلاعات و دانش گرافی موجود در گراف وابستگی موجودیت استفاده ی چندانی نمی کنند. در این مقاله یک الگوریتم مبتنی بر افراز ارایه شده است که بتوان از آن در خوشه بندی نرم افزار نیز استفاده کرد. همچنین، یک نوع فاصله جدید برای قیاس تشابه و عدم تشابه ارایه شده است. انتظار می رود روش پیشنهادی بتواند در قیاس با سایر روش های موجود، خوشه بندی هایی با کیفیت بالاتر و نزدیک به خوشه بندی فرد خبره، تولید کند. برای بررسی صحت اجرای الگوریتم، آن را بر روی نرم افزار موزیلا فایرفاکس اجرا کرده و نتایج را با الگوریتم های مطرح این حوزه، مقایسه کرده ایم.