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

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