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

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

A Hierarchical Method For Content-Structured Graph Clustering

Entities in social networks, in addition to having the relationship with each other, also have content. This type of networks can be modeled by the enriched graph, in which nodes could have text too. Graph clustering is one of the important attempts toward analyzing social networks. Despite these two facts, most of the existing graph clustering methods independently focused on one of the content or structural aspects. ContentStructural graph clustering algorithms simultaneously consider both the structure and the content of the graph. The main aim of this paper is to achieve well connected (structured) clusters while their nodes benefit from homogeneous attribute values (content). The proposed algorithm in this paper socalled RSLCluster performs the clustering by hierarchically removing the edge between nodes which has a weight lower that the average similarity of nodes. This stage continues until reaching the user’s desired number of clusters. Comparing the proposed algorithm with three wellknown contentstructural clustering algorithms represents the proper functioning of the proposed method. The used measures to evaluate our method include structural, content and the contentstructural measures.