محسن سعادتپورمقدم - دانشجوی کارشناسی ارشد، دانشگاه شهیدبهشتی
سیدکامیار ایزدی - عضو هیئت علمی، دانشگاه شهیدبهشتی
رحیم هاشمی شهرکی - دانشجوی کارشناسی ارشد، دانشگاه شهیدبهشتی

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

گراف کاوی، جریان گراف، خوشه بندی، جریان داده ها، خوشه بندی راس های گراف