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

خوشه‌بندی گره‌های گراف از جنبه ساختاری یا محتوایی، همواره موردتوجه پژوهشگران حوزه داده‌کاوی بوده است؛ اما به خوشه‌بندی گراف بر مبنای ساختار و محتوا به‌طور ترکیبی کمتر توجه شده است. با توجه به نیاز خوشه‌بندی ساختاریمحتوایی در شبکه‌های اطلاعاتی که شبکه‌های اجتماعی نمونه‌ای از آن‌هاست، در این مقاله الگوریتم خوشه‌بندی icscluster ارائه‌شده که هر دو جنبه ساختار و محتوا را به‌صورت هم‌زمان در نظر می‌گیرد. هدف این روش، رسیدن به خوشه‌هایی با ساختار درونی منسجم (ساختاری) و مقادیر ویژگی (محتوایی) همگن در گراف است. در این روش ابتدا گراف اولیه به یک گراف ساختاریمحتوایی تبدیل می‌شود که در آن وزن هر یال (ارتباط) بیانگر شباهت ساختاریمحتوایی دو گره (موجودیت) است. خوشه‌بندی با توجه به وزن یال‌ها به‌صورت افزایشی انجام می‌شود بدین معنا که گره‌های یالِ با وزن بالا به‌عنوان خوشه در نظر گرفته می‌شوند و وزن یال‌های متصل به خوشه با یکدیگر ادغام‌شده و به‌صورت یک یال متصل به خوشه در نظر گرفته می‌شوند، این مراحل تا زمانی که الگوریتم به تعداد خوشه موردنظر کاربر برسد، ادامه خواهد یافت. الگوریتم       icscluster به هر تعداد خوشه که مدنظر کاربر است، گراف را خوشه‌بندی می‌کند. مقایسه الگوریتم مطرح‌شده با سه الگوریتم خوشه‌بندی ساختاری محتوایی ارائه‌شده، بر اساس معیارهای شش‌گانه سنجش کیفیت خوشه، بیانگر عملکرد مناسب روش icscluster است. این معیارها معیارهای ساختاریِ تراکم خوشه، خطای یال و پیمانگی، معیار محتواییِ میانگین شباهت، معیار ساختاریمحتوایی csmeasure و زمان اجرای روش‌ها است.

An Incremental Solution for ContentStructural Graph Clustering

Researchers have always been interested in graph nodes clustering based on content or structure. But less attention has been paid to clustering based on both structure and content. But a contentstructural clustering is needed in information networks like social networks. In this paper, the ICSCluster algorithm is proposed which takes into consideration both the structure and content aspects of the nodes. The purpose of this approach is to gain a coherent internal structure (structural aspect) and homogeneous attribute values (content aspect) in the graph. In this approach firstly the graph is converted into a contentstructural graph which edges’ weight show similarity between the connected nodes. Incremental clustering is done based on edges’ weight in this process the edges with the most weight is considered as clusters then the weight of connected edge to the cluster is aggregated and they’ll be one edge, the process is repeated until the algorithm reaches the number of clusters that indicated by the user. ICSCluster algorithm number of cluster is indicated by the user. Comparing ICSCluster with other content structural algorithm based on six criteria for measuring cluster quality shows that ICSCluster has good performance. These criteria contain structural criteria (Modularity, Error Link, and Density), content criterion (Average Similarity), contentstructural criterion (CSMeasure) and the run time.