در خوشه بندی گره ها به گروه های کوچکی به نام خوشه تقسیم می شوند. در هر خوشه سر خوشه انتخاب می شود. در مبحث خوشه بندی گراف، گروه بندی رأس های گراف به خوشه ها با در نظر گرفتن ساختار یالهای گراف، به گونه ای است که باید یالهای درون هر خوشه ماکزیمم و بین خوشه ها حداقل تعداد یال موجود باشد. خوشه بندی گراف به معنای گروهبندی گرههای گراف ورودی به خوشه ها است.
در محیط (فضای) گراف، هر خوشه باید مستقیماً متصل باشد، باید حداقل یک مسیر چندگانه متصل برای هر جفت از گره ها درون یک خوشه وجود داشته باشد. اگر رأس از رأس قابل دسترس نباشد، آن ها نباید در خوشه های یکسان (مشابه) قرار بگیرند.
هدف خوشه بندی یافتن خوشه های مشابه می باشد معیار تعیین بهترین خوشه بندی را می توان نشان داد که هیچ معیار مطلقی برای بهترین خوشه بندی وجود ندارد بلکه این بستگی به مسئله و نظر کاربر دارد که باید تصمیم بگیرد که آیا نمونه ها به درستی خوشه بندی شده اند یا خیر. بااین حال معیارهای مختلفی برای خوب بودن یک خوشه بندی ارائه می شود که می تواند کاربر را برای رسیدن به یک خوشه بندی مناسب راهنمایی کند یکی از مسائل مهم در خوشه بندی انتخاب تعداد خوشه ها می باشد. در بعضی از الگوریتم ها تعداد خوشه ها از قبل مشخص می شود و در بعضی دیگر خود الگوریتم تصمیم می گیرد که داده ها به چند خوشه تقسیم شوند.
ضریب خوشه بندی
به دنبال مطرح شدن اصل بستار سه تایی و تراکم بالای مثلث ها، معیارهایی برای اندازه گیری چگالی این سه تاییها در شبکه های اجتماعی معرفی شد. ضریب خوشه بندی، یکی از معروف ترین این معیارهاست. همچنین ضریب خوشه بندی معیاری است که مشخص می کند گره های یک شبکه تا چه حد تمایل دارند باهم تشکیل یک خوشه دهند. شواهد نشان می دهد که در شبکه های واقعی و پیچیده و به خصوص در شبکه های اجتماعی گره ها تمایل دارند با برخی گره های دیگر، گروه هایی
تشکیل دهند، به طوری که گره های داخل یک گروه شباهت زیادی به یک گراف کامل دارند.
تعریف ضریب خوشه بندی
این خصوصیت بیان می کند که دو گره در شبکه اجتماعی که همسایه یک گره دیگر هستند نسبت به دو گره که به طور تصادفی از کل گره های موجود در شبکه اجتماعی انتخاب شوند با احتمال بیشتری با یکدیگر در ارتباط هستند .این خصوصیت بر اساس ضریب خوشه بندی قابل اندازه گیری است.
روش های خوشه بندی
روش های خوشه بندی را می توان از چندین جنبه تقسیم بندی کرد:
1 . خوشه بندی انحصاری و خوشه بندی با هم پوشی
در روش خوشه بندی انحصاری پس از خوشه بندی هر داده دقیقاً به یک خوشه تعلق می گیرد مانند K-Means
ولی در خوشه بندی با همپوشی پس از خوشه بندی به هر داده یک درجه تعلق به ازای هر خوشه نسبت داده می شود. به عبارتی یک داده می تواند با نسبت های متفاوتی به چندین خوشه تعلق داشته باشد. نمونه ای از آن خوشه بندی فازی است.
2 .خوشه بندی سلسله مراتبی و خوشه بندی مسطح
در روش خوشه بندی سلسله مراتبی، به خوشه های نهایی بر اساس میزان عمومیت آن ها ساختاری سلسله مراتبی نسبت داده می شود؛ مانند روش Single Link ولی در خوشه بندی مسطح تمامی خوشه های نهایی دارای یک میزان عمومیت هستند مانند K-Means به ساختار سلسله مراتبی حاصل از روش های خوشه بندی سلسله مراتبی دندوگرام گفته می شود