کنفرانس بین المللی محاسبات نرم

صفحه اصلی / پنجمین کنفرانس بین المللی محاسبات نرم

خوشه‌بندی گراف‌های احتمالاتی مبتنی بر شباهت ساختاری و ویژگی‌های همگن

نویسندگان :

ملیحه دانش¹

1- دانشگاه علم وفناوری مازندران

کلمات کلیدی :

گراف احتمالاتی،خوشه‌بندی،شباهت ساختاری،ویژگی گره‌ها،ماتریس وابستگی

چکیده :

امروزه گراف‌های احتمالاتی در بسیاری از کاربردهای دنیای واقعی توسعه یافته‌اند و تحلیل آنها از اهمیت ویژه‌ای برخوردار است. خوشه‌بندی به عنوان یکی از مهمترین مسائل در تحلیل گراف‌های احتمالاتی است که هدف آن گروه‌بندی متراکم و مطمئنی از داده‌هاست. با توجه به احتمالی بودن اتصالات میان گره‌ها، دستیابی به این هدف دشوار بوده و نیاز به ارائه راهکارهایی جهت پردازش عدم قطعیت در آنهاست. جهت رفع این چالش، ما در این مقاله از مجموعه ویژگی‌ گره‌ها بهره بردیم که این ویژگی‌ها در اکثر شبکه‌های احتمالاتی موجود بوده و به توصیف خصوصیاتی از آنها می‌پردازند. در این راستا ابتدا دو ماتریس شباهت یکی بر اساس اطلاعات ساختاری و دیگری مبتنی بر خصوصیات گره‌ها ساخته می‌شود. در شباهت ساختاری، مجاورت سراسری گره‌ها در کنار مجاورت محلی آنها استفاده شده و به ازای گره‌هایی با همسایه‌های مشترک، شباهت بیشتری به آنها تخصیص می‌یابد. در ماتریس شباهت مبتنی بر ویژگی‌ها، گره‌هایی با ویژگی‌های همگن امتیاز بیشتری داشته و امکان هم‌خوشه بودن آنها بیشتر است. در ادامه ماتریس وابستگی احتمالی از ترکیب ماتریس‌های شباهت فوق ساخته شده و سپس از آن جهت افراز نهایی گره‌ها با استفاده از یکی از الگوریتم‌های خوشه‌بندی گراف‌های احتمالاتی استفاده می‌شود. نتایج حاصل از اجرای روش پیشنهادی بر روی چهار مجموعه داده واقعی از گراف‌های احتمالاتی موجود، نشان دهنده عملکرد مؤثرتر رویکرد پیشنهادی نسبت به روش‌های اخیر خوشه‌بندی این نوع گراف‌هاست.