Коефіцієнт кластеризації

Шаблон:Автопереклад В теорії графів коефіцієнт кластеризації є мірою ступеня, в якій вузли в графі мають тенденцію групуватися разом. Наявні дані свідчать про те, що в більшості реальних мереж, і, зокрема, в соціальних мережах, вузли, як правило, створюють тісно пов'язані групи, що характеризуються відносно високою щільністю зв'язків; ця ймовірність більше ніж середня ймовірність випадкового зв'язку між двома вузлами (Holland і Leinhardt, 1971; Watts and Strogatz, 1998).

Існують два варіанти цього терміна: глобальний і локальний. Глобальний варіант було створено для загального уявлення про кластеризацію в мережі, в той час як локальний описує вкладеність окремих вузлів.

Глобальний коефіцієнт кластеризації

Глобальний коефіцієнт кластеризації заснований на трійках вузлів. Трійка складається з трьох з'єднаних вузлів. Тому трикутник включає в себе три замкнуті трійки, по одній по центру на кожному з вузлів (n.b. це означає, що три трійки в трикутнику відбуваються водночас з перекриттям вибору вузлів). Глобальний коефіцієнт кластеризації — це число замкнутих трійок (або 3-х трикутників) над загальним числом трійок (відкритих і закритих). Перша спроба виміряти цей коефіцієнт була зроблена Луче і Перрі (1949). Цей термін дає вказівку на кластеризацію у всій мережі (глобальну), і може бути застосований до обох типів мереж: ненаправлених і спрямованих(часто званих транзитивними див. Вассерман і Фауст, 1994, стор. 243).

Глобальний коефіцієнт кластеризації визначається наступним чином:

$C=\frac{3\times \text{number of triangles}}{\text{number of connected triplets of vertices}}=\frac{\text{number of closed triplets}}{\text{number of connected triplets of vertices}}.$

У цій формулі, зв'язана трійка визначається як зв'язний підграф, що складається з трьох вершин і двох ребер. Таким чином, кожен трикутник утворює три з'єднаних трійки, пояснюючи множення на три у формулі. Узагальнення на Шаблон:Не перекладено було запропоноване Опсахлем і Панзарасою (2009), і перевизначення, двох режимів мереж(як бінарних так і вагових) було запропоноване Опсахлем (2009).

Локальний коефіціент кластеризації

Приклад локального коефіціенту кластеризації на неорієнтованому графі. Локальний коефіцієнт кластеризації синього вузла обчислюється як частка зв'язків між сусідами, які фактично реалізовані за допомогою порівняння з числом всіх можливих з'єднань. На малюнку, синій вузол має трьох сусідів, які можуть мати максимум 3 зв'язки між собою. У верхній частині малюнка всі три можливі зв'язки є реалізованими (товсті чорні сегменти), що дає нам локальний коефіцієнт кластеризації рівний 1. У середній частині малюнка тільки одне з'єднання є реалізованим (товста чорна лінія) і 2 з'єднання відсутні (пунктирні червоні лінії), що дає нам локальний коефіцієнт кластера рівний 1/3. І, нарешті, жоден з можливих зв'язків між сусідами синього вузла не буде реалізованим, що дає локальне значення коефіцієнта кластеризації рівне 0.

Локальний коефіціент кластеризації з вершиною (вузлом) в графі рахує, наскільки близько його сусіди повинні бути угруповані (повний граф). Шаблон:Не перекладено і Стівен Строгац ввели цей термін в 1998 році, щоб визначити, чи є граф графом «Світ тісний».

Граф $G=(V,E)$ формально складається з безлічі вершин $V$ і набору ребер $E$ між ними. Ребро $e_{ij}$ з'єднує вершину $v_i$ з вершиною $v_j$.

окіл $N_i$ для вершини <математика> $v_i$ визначається за допомогою її сусідів, що пов'язані наступним чином:

$N_i=\{v_j:e_{ij}\in E\vee e_{ji}\in E\}.$

Визначимо $k_i$ як число вершин, $|N_i|$, як околицю, $N_i$, як вершину.

Локальний коефіцієнт кластеризації $C_i$ для вершини $v_i$ далі визначається як зв'язки між вершинами в межах його околиць, розділені на кількість посилань, які могли б існувати між ними. Для орієнтованого графа, $e_{ij}$ відрізняється від $e_{ji}$, і, отже, для кожної околиці $N_i$ є $k_i(k_i-1)$ посиланнь, які можуть існувати серед вершин в околиці ($k_i$ це число сусідів вершини). Таким чином, Локальний коефіціент кластеризації для орієнтованих графів задається як

$C_i=\frac{|\{e_{jk}:v_j,v_k\in N_i,e_{jk}\in E\}|}{k_i(k_i-1)}.$

Неорієнтовані граф володіє такою властивістю, що $e_{ij}$ і $e_{ji}$ вважаються однаковими. Тому, якщо вершина $v_i$ має $k_i$ сусідів, $\frac{k_i(k_i-1)}{2}$ ребер може існувати серед вершин в межах околиці. Таким чином, Локальний коефіціент кластеризації для неорієнтованих графів може бути визначений як

$C_i=\frac{2|\{e_{jk}:v_j,v_k\in N_i,e_{jk}\in E\}|}{k_i(k_i-1)}.$

Нехай ${\lambda }_G(v)$ — це кількість трикутників на множині вершин $v\in V(G)$ для неорієнтованого графа $G$. Тобто, ${\lambda }_G(v)$ це число підграфів $G$ з 3-ма ребрами і 3-ма вершинами, одна з яких $v$. Нехай ${\tau }_G(v)$ — це число трійок на $v\in G$. Тобто,${\tau }_G(v)$ — це число підграфів (не обов'язково інддукованих) з 2-ма ребрами і 3-ма вершинами, одна з яких є $v$ і таке, що $v$ інцидентна на обох краях. Тоді ми можемо визначити коефіцієнт кластеризації як

$C_i=\frac{{\lambda }_G(v)}{{\tau }_G(v)}.$

Легко показати, що два попередніх визначення є однаковими, так як

${\tau }_G(v)=C(k_i,2)=\frac{1}{2}{k}_i(k_i-1).$

Ці міри є рівними 1, якщо кожен сусід зв'язаний із $v_i$ також пов'язаний з будь-якою іншою вершиною в околиці, і ці міри дорівнюють 0, якщо жодна з вершин, що пов'язана з $v_i$ зв'яжеться з будь-якою іншою вершиною, що пов'язана з $v_i$.

Мережевий середній коефіцієнт кластеризації

Як альтернатива глобального коефіцієнта кластеризації, загальний рівень кластеризації в мережі був виміряний Уоттсом та Строгацом як середнє значення локальних коефіцієнтів кластеризації всіх вершин $n$ :

$\overline{C}=\frac{1}{n}\sum _{i=1}^n{C}_i.$

Варто зазначити, що ця метрика розміщує більше ваги на низьких вузлів ступеня, в той час як співвідношення транзитивності поміщає більше ваги на високих вузлах ступеня. Насправді, зважене середнє, де кожна локальна оцінка кластеризації зважуються по $k_i(k_i-1)$ збігається з глобальним коефіцієнтом кластеризації.

Граф вважається графом «Світ тісний», якщо його середній локальний коефіцієнт кластеризації $\overline{C}$ значно вище, ніж у випадкового графа, побудованого на той самій множині вершин, а також якщо граф має приблизно таку ж відстань- найбільш коротку довжину шляху як і відповідний випадковий граф.

Узагальнення терміну Шаблон:Не перекладено було запропоновано Барратом та ін. (2004), і перевизначення до двочасткових графів S (названих також дворежимними мережами) було запропоноване Латапу та ін. (2008) і Опсахлем (2009).

Ця формула не є визначеною для графів з ізольованими вершинами; див. Кайзер (2008) та Бармпотіусом та ін.. Мережі з максимально можливим середнім коефіцієнтом кластеризації мають модульну структуру, і в той же час, вони мають найменшу можливу середню відстань між різними вузлами.

Перколяції кластерних мереж

Для вивчення стійкості кластерних мереж був розроблений перколяційний підхід.