Коэффициент кластеризации

Коэффициент кластеризации — это показатель того, насколько сильно вершины в графе склонны группироваться. Имеющиеся данные свидетельствуют о том, что в большинстве реальных сетей, особенно в социальных сетях, вершины имеют тенденцию образовывать тесно связанные группы с относительно высокой плотностью связей. Эта вероятность, как правило, выше средней вероятности случайного установления связи между двумя узлами (Холланд и Лейнхардт, 1971^[1]; Уоттс и Строгац, 1998^[2]).

Существует две версии этой меры — глобальная и локальная. Глобальная версия была разработана для общего указания на кластеризацию в сети, тогда как локальная указывает на степень «кластеризации» отдельной вершины.

Локальный коэффициент кластеризации вершины (узла) графа определяет, насколько близки её соседи к образованию клики (полного графа). Дункан Уоттс и Стивен Строгац ввели этот показатель в 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 v_{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 {\tfrac {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}={\tfrac {\lambda _{G}(v)}{\tau _{G}(v)}}.}$

Легко показать, что два определения совпадают, поскольку

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

Показатель равен 1, если любой сосед соединён дугой с любым другим соседом, и 0, если любой сосед не имеет дуги ни с каким другим соседом.

Поскольку любой граф полностью задаётся его матрицей смежности A, локальный коэффициент кластеризации для простого неориентированного графа может быть выражен в терминах A как^[3]:

${\displaystyle C_{i}={\tfrac {1}{k_{i}(k_{i}-1)}}\sum _{j,k}A_{ij}A_{jk}A_{ki}}$

где:

${\displaystyle k_{i}=\sum _{j}A_{ij}}$

и C_i=0, когда k_i нуль или единица. В приведенном выражении числитель отражает удвоенное количество полных треугольников, в которых участвует вершина i. В знаменателе k_i² отражает число пар рёбер, связанных с вершиной i, плюс число одиночных ребер, пройденных дважды. k_i является число рёбер, связанных с вершиной i. Вычитая k_i мы исключаем последнее слагаемое, оставляя лишь набор пар ребер, которые потенциально могут быть соединены в треугольники. Поскольку для каждой такой пары ребер существует другая пара, способная образовать тот же треугольник, знаменатель в итоге также отражает удвоенное количество возможных треугольников, в которых может участвовать вершина i.

Глобальный коэффициент кластеризации основан на тройках узлов. Тройка — это три вершины, соединенные двумя (открытая тройка) или тремя (замкнутая тройка) неориентированными рёбрами. Таким образом, треугольный граф включает три замкнутые тройки, по одной для каждой вершины (это означает, что три тройки в треугольнике образуются из пересекающихся выборок узлов). Глобальный коэффициент кластеризации равен отношению числа закрытых троек (или 3 x число треугольников) и полного числа троек (открытых и закрытых). Первая попытка измерить его была предпринята Люсом и Перри (1949)^[4]. Этот показатель указывает на кластеризацию во всей сети (глобально) и может применяться как к неориентированным, так и к ориентированным сетям (часто называемым транзитивностью, см. Вассерман и Фауст , 1994, стр. 243^[5]).

Глобальный коэффициент кластеризации определяется как

${\displaystyle C={\frac {\mbox{число закрытых троек}}{\mbox{число всех троек (открытых и закрытых)}}}}$.

Число закрытых троек встречается также в литературе как 3 × число треугоьников, так что

${\displaystyle C={\frac {3\times {\mbox{число треугольников}}}{\mbox{число всех троек}}}}$.

Обобщение для сетей с весами предложили Опсал и Панцараза (2009)^[6], а переопределение для двумодальных сетей (как бинарных, так и взвешенных) — Опсалом (2009)^[7].

Поскольку любой простой граф полностью определён его матрицей смежности A, глобальный коэффициент кластеризации для неориентированного графа может быть выражен в терминах A как:

${\displaystyle C={\frac {\sum _{i,j,k}A_{ij}A_{jk}A_{ki}}{{\frac {1}{2}}\sum _{i}k_{i}(k_{i}-1)}}}$

где:

${\displaystyle k_{i}=\sum _{j}A_{ij}}$

и C=0, если знаменатель равен нулю.

В качестве альтернативы глобальному коэффициенту кластеризации общий уровень кластеризации в сети измеряется Уоттсом и Строгацем^[2] как среднее значение локальных коэффициентов кластеризации всех вершин ${\displaystyle n}$^[8]:

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

Данный показатель придает больший вес узлам с низкой степенью, в то время как коэффициент транзитивности уделяет большее внимание узлам с высокой степенью.

Обобщение для сетей с весами было предложено Барраттом и др. (2004)^[9], а переопределение для двудольных графов (также называемых двумодальными сетями) было предложено Латапи и др. (2008)^[10] и Опсалом (2009)^[7].

Альтернативное обобщение для взвешенных и ориентированных графов предложил Фаджиоло (2007)^[11] и Клементе и Грасси (2018)^[12].

Эта формула по умолчанию не определена для графов с изолированными вершинами (см. Кайзер (2008)^[13] и Бармпутис и др.^[14]). Сети с максимально возможным средним коэффициентом кластеризации имеют модульную структуру и, в то же время, наименьшее возможное среднее расстояние между различными узлами^[14].

Для случайной древовидной сети без корреляции степеней вершин можно показать, что сеть может иметь гигантскую компоненту, а порог протекания (вероятность передачи) определяется как ${\displaystyle p_{c}={\frac {1}{g_{1}'(1)}}}$, где ${\displaystyle g_{1}(z)}$ — производящая функция, соответствующая распределению избыточной степени.

В сетях с низкой кластеризацией, ${\displaystyle 0<C\ll 1}$, критическая точка масштабируется множителем ${\displaystyle (1-C)^{-1}}$, так что

${\displaystyle p_{c}={\frac {1}{1-C}}{\frac {1}{g_{1}'(1)}}.}$^[15]

Это указывает на то, что для заданного распределения степеней кластеризация приводит к более высокому порогу протекания, в основном по причине, что при фиксированном числе связей кластерная структура укрепляет ядро сети, но ценой размывания глобальных связей. Для сетей с высокой кластеризацией, сильная кластеризация может порождать структуру «ядро–периферия», в которой ядро и периферия могут перколировать в различных критических точках и вышеупомянутое приближенное рассмотрение становится неприменимым^[15].

Для изучения устойчивости кластеризованных сетей разработан подход на основе теории протекания^[16][17].

• Ориентированный граф
• Теория графов
• Теория сетей
• Наука о сетях
• Теория перколяции
• Безмасштабная сеть
• Мир тесен