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

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

Keywords:

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