ضریب خوشگی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به ناوبری پرش به جستجو

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

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

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

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

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

ضریب خوشگی محلی[ویرایش]

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

منابع[ویرایش]

  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.