خوشه‌بندی محتوایی-ساختاری گراف و معیاری جدید جهت ارزیابی آن

نویسندگان

1 دانشگاه علم و صنعت ایران

2 دانشگاه جامع امام حسین (ع)

چکیده

امروزه با گسترش شبکه‌های اجتماعی در بین مردم، تلاش‌های مخالفین برای بدبین کردن ایشان نسبت به حکومت که از آن به عنوان جنگ نرم یاد می‌شود افزایش یافته است، بنابراین توجه به این شبکه‌ها برای ارگان‌های نظامی و امنیتی بیش از پیش اهمیت دارد. خوشه‌بندی گراف از جمله اولین کارهای تحلیلی یک یا چند شبکه اجتماعی است. متأسفانه اکثر خوشه‌بندی‌های گرافی انجام شده بر روی جنبه‌های ساختاری یا محتوایی گره‌های گراف به صورت مستقل تأکید دارند. هدف از این مقاله (پیاده‌سازی شده در قالب الگوریتمCS-Cluster ) رسیدن به خوشه‌هایی با ساختار درونی منسجم و مقادیر ویژگی (محتوایی) همگن در گراف است. از طرفی پس از جستجوهای صورت گرفته در این تحقیق، هیچگونه معیاری جهت ارزیابی الگوریتم‌های خوشه‌بندی که جنبه‌های ساختاری و محتوایی گره‌ها را به صورت هم‌زمان در نظر بگیرد، یافت نشد. به همین دلیل در دومین گام معیاری جدید به نام CS-Measure ارائه شد که قادر است الگوریتم‌های خوشه‌بندی گراف را از هر دو جنبه ساختار و محتوا به صورت هم‌زمان مورد سنجش قرار دهد. مقایسه الگوریتم مطرح شده با دو الگوریتم خوشه‌بندی ساختاری-محتوایی (از سه الگوریتم شناخته شده تاکنون) بر اساس معیارهای میانگین شباهت، خطای یال و معیارِ جدیدِ ساختاری-محتوایی، بیانگر عملکرد بهتر روش ارائه شده است و از نظر معیار تراکم نیز عملکرد نسبتاً خوبی دارد.

کلیدواژه‌ها


عنوان مقاله [English]

Content-Structural Graph Clustering and a New Measure for Its Evaluation

چکیده [English]

Today, with the spread of social networks, the opposition's efforts to chill out people from government (known as “soft war”) are increased. Therefore, dealing with this type of networks is important for military and security organizations. Graph clustering is one of the first attempts toward analyzing social networks which can appropriately be modeled by a content graph. In contrast, most of the existing graph clustering methods independently focused on one of the content or structural aspects of a graph. The aim of this paper (implemented as CS-Cluster algorithm) is to achieve well connected clusters while their nodes benefits from homogeneous attribute values (content). In the second step of our research, after an intensive search, no measure has found which could simultaneously consider content and structural features of clustering algorithms. So to be able to appropriately evaluate our algorithm, a new content-structural measure (so-called “CS-Measure”) is proposed. Our experimentation shows that the proposed clustering algorithm outperforms two other well-known content-structural clustering algorithms, using the new content-structural, average similarity, and Error link measure as well as the previous content and structural measures, And it also performed relatively well in density measure.

کلیدواژه‌ها [English]

  • Clustering
  • content graph
  • content-structural clustering
  • content-structural evaluation