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

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

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

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

Глобальний коефіцієнт кластеризації заснований на трійках вузлів. Трійка складається з трьох з'єднаних вузлів. Тому трикутник включає в себе три замкнуті трійки, по одній по центру на кожному з вузлів (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}}}.}$

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

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

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

Локальний коефіціент кластеризації з вершиною (вузлом) в графі рахує, наскільки близько його сусіди повинні бути угруповані (повний граф). Дункан Уоттс^[en] і Стівен Строгац ввели цей термін в 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}}$.

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

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

${\displaystyle {\bar {C}}={\frac {1}{n}}\sum _{i=1}^{n}C_{i}.}$

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

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

Узагальнення терміну зважені мережі^[en] було запропоновано Барратом та ін. (2004),^[8] і перевизначення до двочасткових графів S (названих також дворежимними мережами) було запропоноване Латапу та ін. (2008)^[9] і Опсахлем (2009).^[6]

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

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

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