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

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

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

Коэффициент локальной кластеризации [ править ]

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

Коэффициент локальной кластеризации для вершины тогда определяется пропорцией связей между вершинами в ее окрестности, деленной на количество связей, которые могут существовать между ними. Для ориентированного графа, отличен от , и поэтому для каждой окрестности существуют связи, которые могут существовать между вершинами в пределах окрестности ( количество соседей вершины). Таким образом, коэффициент локальной кластеризации для ориентированных графов задается как ^[2]${\ displaystyle C_ {i}}$${\ displaystyle v_ {i}}$${\ displaystyle e_ {ij}}$${\ displaystyle e_ {ji}}$${\ displaystyle N_ {i}}$${\ Displaystyle к_ {я} (к_ {я} -1)}$${\ displaystyle k_ {i}}$

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

Позвольте быть количество треугольников на для неориентированного графа . То есть это количество подграфов с 3 ребрами и 3 вершинами, одна из которых есть . Позвольте быть количество троек на . То есть, это число подграфов (не обязательно индуцируется) с 2 - мя ребрами и вершинами 3, один из которых является и такое , что падает на обоих краях. Тогда мы также можем определить коэффициент кластеризации как${\ displaystyle \ lambda _ {G} (v)}$${\ Displaystyle v \ in V (G)}$${\ displaystyle G}$${\ displaystyle \ lambda _ {G} (v)}$${\ displaystyle G}$${\ displaystyle v}$${\ Displaystyle \ тау _ {G} (v)}$${\ displaystyle v \ in G}$${\ Displaystyle \ тау _ {G} (v)}$${\ 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, если каждый подключенный сосед также подключен к любой другой вершине в пределах окрестности, и 0, если ни одна из подключенных вершин не соединяется с какой-либо другой вершиной, с которой связана .${\displaystyle v_{i}}$${\displaystyle v_{i}}$${\displaystyle v_{i}}$

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

${\displaystyle C_{i}={\frac {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 .

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

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

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

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

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

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

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

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

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

куда:

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

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

Средний сетевой коэффициент кластеризации [ править ]

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

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

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

Граф считаются малым миром , если граф имеет небольшую среднюю-короткую длину пути , что весы с натуральным логарифмом числа узлов в сети, . ^[9] Например, случайный граф - это маленький мир, а решетка - нет, а графы без масштабирования часто считаются сверхмалыми мирами, так как их длина среднего кратчайшего пути масштабируется с .${\displaystyle \ln {N}}$${\displaystyle \ln {\ln {N}}}$

Обобщение на взвешенные сети было предложено Barrat et al. (2004), ^[10] и новое определение двудольных графов (также называемых двухмодовыми сетями) Latapy et al. (2008) ^[11] и Opsahl (2009). ^[7]

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

Эта формула по умолчанию не определена для графов с изолированными вершинами; см. Kaiser (2008) ^[14] и Barmpoutis et al. ^[15] Сети с максимально возможным средним коэффициентом кластеризации имеют модульную структуру и в то же время имеют минимально возможное среднее расстояние между различными узлами. ^[15]

Перколяция кластерных сетей [ править ]

Для исследования устойчивости кластерных сетей разработан перколяционный подход. ^{[16] [17] [18]} Устойчивость к локальным атакам была изучена с использованием локальной перколяции. ^[19] Также изучалась локализация волн в кластерных сложных сетях. ^[20]

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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