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

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

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

${\displaystyle 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}}}.}$

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

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

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

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

окіл ${\displaystyle N_{i}}$ для вершини <математика> ${\displaystyle v_{i}}$ визначається за допомогою її сусідів, що пов'язані наступним чином:

${\displaystyle N_{i}=\{v_{j}:e_{ij}\in E\lor e_{ji}\in E\}.}$

Визначимо ${\displaystyle k_{i}}$ як число вершин, ${\displaystyle |N_{i}|}$, як околицю, ${\displaystyle N_{i}}$, як вершину.

Локальний коефіцієнт кластеризації ${\displaystyle C_{i}}$ для вершини ${\displaystyle v_{i}}$ далі визначається як зв'язки між вершинами в межах його околиць, розділені на кількість посилань, які могли б існувати між ними. Для орієнтованого графу, ${\displaystyle e_{ij}}$ відрізняється від ${\displaystyle e_{ji}}$, і, отже, для кожної околиці ${\displaystyle N_{i}}$ є ${\displaystyle k_{i}(k_{i}-1)}$ посиланнь, які можуть існувати серед вершин в околиці (${\displaystyle k_{i}}$ це число сусідів вершини). Таким чином, Локальний коефіціент кластеризації для орієнтованих графів задається як[2]

${\displaystyle C_{i}={\frac {|\{e_{jk}:v_{j},v_{k}\in N_{i},e_{jk}\in E\}|}{k_{i}(k_{i}-1)}}.}$

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

${\displaystyle C_{i}={\frac {2|\{e_{jk}:v_{j},v_{k}\in N_{i},e_{jk}\in E\}|}{k_{i}(k_{i}-1)}}.}$

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

${\displaystyle C_{i}={\frac {\lambda _{G}(v)}{\tau _{G}(v)}}.}$

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

${\displaystyle \tau _{G}(v)=C({k_{i}},2)={\frac {1}{2}}k_{i}(k_{i}-1).}$

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

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