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

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

Keywords:

خوشه بندی گراف , خوشه بندی ساختاری- محتوایی , گراف خصوصیت , استخراج خوشه