روشی نوین برای خوشه‌بندی نیمه‌نظارتی شبکه‌های پیچیده‎ ‎مبتنی بر معیار پیمانگی

خوشه‌بندی، ابزاری پرکاربرد جهت تحلیل اطلاعات شبکه‌های پیچیده ‏است که برای مدل‌سازی سامانه‌های پیچیده بکار می‌رود. پیمانگی ، ‏معیاری پایه و فراگیر جهت ارزیابی و صحت‌سنجی خوشه‌بندی شبکه‌ها ‏است که دارای چالش‌هایی چون ان‌پی-سخت بودن مسئله و عدم‎ ‎امکان ‏استفاده از دانش اولیه در خوشه‌بندی می‌باشد. لذا، خوشه‌بندی‌ مبتنی بر ‏معیار پیمانگی، قابلیت تعمیم به خوشه‌بندی‌های نیمه‌نظارتی را ندارد. از ‏طرفی، یکی از روش‌های خوشه‌بندی نیمه‌نظارتی، روش خوشه‌بندی مبتنی ‏بر تجزیه نامنفی ماتریسی (‏nmf‏) می‌باشد. اما این روش، ویژگی‌های ‏خاص شبکه‌ها را در نظر نمی‌گیرد. در این مقاله، برای غلبه بر چالش‌های ‏نام‌برده‌ و با ارائه‌ی اثباتی جدید، برای خوشه‌بندی مبتنی بر معیار پیمانگی، ‏ساختاری مشابه با خوشه‌بندی مبتنی بر تجزیه نامنفی ماتریسی نامتقارن ‏ارائه می‌شود که در آن، امکان بهره‌گیری از دانش اولیه و حل به روش ‏تکراری میسر می‌گردد. سپس، روش خوشه‌بندی نیمه‌نظارتی نوینی به نام ‏تجزیه نیمه‌نظارتیِ نامنفی ماتریس‌های متقارن مبتنی بر معیار پیمانگی ‏‏(‏ssnmf-q‏) با بهره‌گیری از مزیت دانش اولیه و روش حل تکراری، ‏به‌جای حل مسئله ان‌پی-سخت ارائه می‌گردد. برای ارزیابی روش ‏پیشنهادی، از پنج مجموعه داده واقعی استفاده‌شده که نتایج، بیانگر عملکرد ‏بهتر‎ ssnmf-qدر مقایسه با سایر خوشه‌بندی‌های نیمه‌نظارتی مبتنی بر ‏nmf‏ می‌باشد.‏

a novel semi-supervised clustering method for complex network based ‎on modularity

clustering or community detection is a powerfrul tool for ‎analayzing complex networks which is widely used for ‎modeling complex systems. modularity is a ‎comprehensive criterion for evaluating the quality of ‎clusters (or communities). however, it has some ‎limitations and challenges such as being a np-hard ‎problem and not using prior information. so, modularity-‎based community detection cannot be extended as a ‎semi-supervised community detection method. on the ‎other hand, one of the most common semi-supervised ‎methods which can use prior knowledge for clustering is ‎community detection based on non negative matrix ‎factorization (nmf). but, this method is not able to ‎consider the features of the networks. therefore, in this ‎paper to overcome the mentioned limitations and ‎challenges and by presenting a new proof, a structure ‎similar to community detection based on nmf is ‎presented for modularity-based community detection ‎which can employ prior knowledge and iterative ‎solution. therefore, a novel semi-supervised community ‎detection based on modularity (ssnmf-q) criteria is ‎developed by utilizing prior information and iterative ‎solution instead of solving a np-hard problem. to ‎evaluate ssnmf-q, five real world networks are used ‎and it is shown that the ssnmf-q had better ‎performance compared to other semi-supervised ‎community detection methods based on nmf.‎