استخراج جوامع در شبکه های اجتماعی براساس خوشه بندی سلسله مراتبی QCM ودرنظرگرفتن میزان افت چگالی

خوشه بندی یا استخراج جوامع در شبکه های اجتماعی یک مسأله مهم و کاربردی در حوزه داده کاوی است. یکی ازرویکردهای مطرح برای این منظور استفاده از الگوریتم های خوشه بندی سلسله مراتبی است. این الگوریتم ها مجموعه ایاز خوشه های تودرتو در یک ساختار سلسله مراتبی تولید و در قالب یک خروجی به صورت دندوگرام ارائه می کنند. اماانتخاب خوشه های نهایی از دندوگرام مستلزم تصمیم گیری بهینه یا نزدیک به بهینه در مورد برش یال های دندوگراماست که این موضوع مسأله ای مشکل محسوب می شود.در این مقاله راهکار جدیدی برای استخراج جوامع در شبکه های اجتماعی معرفی می شود. در راهکار پیشنهادی ابتدا بااستفاده از الگوریتم QCM دندوگرامی تولید می شود که هر گره آن یک زیرگراف از گراف اصلی است. در مرحله بعد برمبنای مقایسه چگالی هر گره با میانگین چگالی فرزندان آن در مورد برش یالهای خارجشده از آن تصمیم گیریمیشود. برای محاسبه چگالی، رابطه پارامتریک جدیدی ارائه شده است تا زیرگراف هایی به عنوان خوشه های نهاییتولید شوند که هم شباهت داخلی گره های آنها زیاد باشد و هم این که تعداد این خوشه ها بیش از حد زیاد نشود.راهکار پیشنهادی هم بر روی گراف های تولیدشده به صورت تصادفی و هم برروی مجموعه داده های واقعی مورد ارزیابیقرار گرفته و با برخی الگوریتم های مطرح در این حوزه مقایسه شده است که نشان دهنده برتری راهکار پیشنهادی ازنظر دقت خوشه بندی است.

کلیدواژه ها:

استخراج جامعه ، شبکه های اجتماعی ، خوشه بندی سلسله مراتبی ، الگوریتم QCM ، چگالی گراف