ضریب خوشگی

در نظریه گراف‌ها، یک ضریب خوشگی (انگلیسی: Clustering coefficient) معیاری است که درجه که گره‌ها در یک گراف تمایل به ایجاد یک خوشه با هم دارند را اندازه می‌گیرد. شواهد حاکی از آن است که در اکثر شبکه‌های دنیای واقعی، و به خصوص در شبکه‌های اجتماعی، گره‌ها تمایل به ایجاد گروه‌های بافتی که توسط ارتباط نسبتاً پرتراکم مشخص می‌شوند دارد و این احتمال بیش از احتمال میانگین احتمال اتصال‌های تصادفی تشکیل شده بین دو گره است.

دو نسخه از این معیار وجود دارد: عمومی و محلی. نسخهٔ عمومی برای دادن معیار کلی از خوشگی در شبکه طراحی شده‌است در حالی که نسخهٔ محلی میزانی از جاسازی‌شدگی گره‌های مستقل می‌دهد.

ضریب خوشگی سراسری

ضریب خوشگی سراسری بر پایهٔ یک سه تایی از گره‌ها تعریف می‌شود. یک سه تایی متشکل از سه گرهٔ متصل به هم. بنابراین یک مثلث شامل سه سه‌تایی است. که هریک به مرکزیت یکی از گره هاست. ضریب خوشگی نسبت تعداد کل سه‌تایی‌های بسته (یا سه برابر تعداد کل مثلث ها) به تعداد کل سه‌تایی هاست (سه‌تایی‌های باز و بسته). اولین تلاش برای اندازه‌گیری آن توسط لوسی و پری در سال ۱۹۴۹ بوده‌است. این اندازه‌گیری نشانه ای از خوشه‌بندی در تمام شبکه‌های سراسری، چه شبکه‌های جهت دار و چه بدون جهت است.

ضریب خوشگی به صورت زیر تعریف می‌شود:

C={\frac {3\times {\mbox{number of triangles}}}{\mbox{number of connected triplets of vertices}}}={\frac {\mbox{number of closed triplets}}{\mbox{number of connected triplets of vertices}}}

ضریب خوشگی محلی

ضریب خوشگی محلی یک گره نشان می‌دهد که همسایه‌های یک گره چه میزان به یکدیگر برای ساختن یک گراف کامل متصلند.

منابع

↑ R. D. Luce and A. D. Perry (1949). "A method of matrix analysis of group structure". Psychometrika. 14 (1): 95–116. doi:10.1007/BF02289146. PMID 18152948.

[1] R. D. Luce and A. D. Perry (1949). "A method of matrix analysis of group structure". Psychometrika. 14 (1): 95–116. doi:10.1007/BF02289146. PMID 18152948.