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

В теории графов коэффициент кластеризации — это мера степени, в которой узлы графа имеют тенденцию группироваться вместе. Имеющиеся данные свидетельствуют о том, что в большинстве реальных сетей, и в частности в социальных сетях , узлы имеют тенденцию создавать тесно связанные группы, характеризующиеся относительно высокой плотностью связей; эта вероятность обычно превышает среднюю вероятность связи, случайно установленной между двумя узлами (Holland and Leinhardt, 1971; Уоттс и Строгац, 1998 г. ).

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

локальной

Пример коэффициента локальной кластеризации на неориентированном графе. Коэффициент локальной кластеризации синего узла вычисляется как доля фактически реализованных соединений между его соседями по сравнению с количеством всех возможных соединений. На рисунке синий узел имеет трех соседей, между которыми может быть максимум 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\lor e_{ji}\in E\}.$

Мы определяем $k_{i}$ как количество вершин, $|N_{i}|$, по соседству, $N_{i}$, вершины $v_{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}$.

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

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

где:

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

и C _i =0, когда k _i равно нулю или единице. В приведенном выше выражении числитель подсчитывает удвоенное количество полных треугольников, в которых участвует вершина i . В знаменателе k _i ² подсчитывает количество пар ребер, в которых участвует вершина i, плюс количество одиночных ребер, пройденных дважды. k _i — количество ребер, соединенных с вершиной i, и вычитание k _i затем удаляет последнюю, оставляя только набор пар ребер, которые предположительно можно соединить в треугольники. Для каждой такой пары ребер найдется еще одна пара ребер, которая может образовать тот же треугольник, поэтому знаменатель учитывает в два раза больше мыслимых треугольников, вершина i в которые может входить .

Глобальный

Глобальный коэффициент кластеризации основан на тройках узлов. Тройка — это три узла, соединенные либо двумя (открытая тройка), либо тремя (закрытая тройка) ненаправленными связями. Таким образом, треугольный граф включает в себя три замкнутых тройки, по одной в центре каждого из узлов ( это означает, что три тройки в треугольнике возникают в результате перекрывающихся выборок узлов). Глобальный коэффициент кластеризации — это количество закрытых троек (или 3 треугольников) по отношению к общему количеству троек (как открытых, так и закрытых). Первую попытку измерить его сделали Люси и Перри (1949). Эта мера дает представление о кластеризации во всей сети (глобальной) и может применяться как к ненаправленным, так и к направленным сетям (часто называемая транзитивностью, см. Wasserman and Faust, 1994, стр. 243). ).

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

$C={\frac {\mbox{number of closed triplets}}{\mbox{number of all triplets (open and closed)}}}$.

Число замкнутых троек в литературе также называют треугольниками 3 ×, поэтому:

$C={\frac {3\times {\mbox{number of triangles}}}{\mbox{number of all triplets}}}$.

Обобщение на взвешенные сети было предложено Опсалом и Панзарасой (2009): и переопределение двухрежимных сетей (как двоичных, так и взвешенных) Опсалом (2009).

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

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

где:

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

и C = 0, когда знаменатель равен нулю.

сети

В качестве альтернативы глобальному коэффициенту кластеризации общий уровень кластеризации в сети измеряется Уоттсом и Строгацем. как среднее значение локальных коэффициентов кластеризации всех вершин $n$ :

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

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

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

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

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

Проникновение кластерных сетей

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

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

$p_{c}={\frac {1}{1-C}}{\frac {1}{g_{1}'(1)}}.$

Это указывает на то, что для данного распределения степеней кластеризация приводит к большему порогу перколяции, главным образом потому, что для фиксированного числа связей структура кластеризации усиливает ядро ​​сети ценой размывания глобальных связей. Для сетей с высокой степенью кластеризации сильная кластеризация может вызвать структуру ядро-периферия, в которой ядро ​​и периферия могут находиться в разных критических точках, и приведенная выше приблизительная трактовка неприменима.

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

См. также

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

Внешние ссылки

• СМИ, связанные с коэффициентом кластеризации, на Викискладе?