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

Мера того, насколько связен и кластеризован узел в его графе.

В теории графов коэффициент кластеризации — это мера степени, в которой узлы графа имеют тенденцию группироваться вместе. Имеющиеся данные свидетельствуют о том, что в большинстве реальных сетей, и в частности в социальных сетях , узлы имеют тенденцию создавать тесно связанные группы, характеризующиеся относительно высокой плотностью связей; эта вероятность, как правило, превышает среднюю вероятность связи, случайно установленной между двумя узлами (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}}$ ${\displaystyle v_{i}}$

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

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

Глобальный коэффициент кластеризации основан на тройках узлов. Тройка — это три узла, соединенные либо двумя (открытая тройка), либо тремя (закрытая тройка) ненаправленными связями. Таким образом, треугольный граф включает в себя три замкнутых тройки, по одной в центре каждого из узлов ( это означает, что три тройки в треугольнике возникают в результате перекрывающихся выборок узлов). Глобальный коэффициент кластеризации — это количество закрытых троек (или 3 треугольников) по отношению к общему количеству троек (как открытых, так и закрытых). Первую попытку измерить его сделали Люси и Перри (1949). ^[4] Эта мера дает представление о кластеризации во всей сети (глобальной) и может применяться как к ненаправленным, так и к направленным сетям (часто называемая транзитивностью, см. Wasserman and Faust, 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}}}}$.

Обобщение на взвешенные сети было предложено Опсалом и Панзарасой (2009), ^[6] , а переопределение двухрежимных сетей (как двоичных, так и взвешенных) Опсалом (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}.}$

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

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

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

Эта формула по умолчанию не определена для графов с изолированными вершинами; см. Kaiser (2008) ^[13] и Barmpoutis et al. ^[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]

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

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

Смотрите также

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

Рекомендации

1. PW Holland и С. Лейнхардт (1971). «Транзитивность в структурных моделях малых групп». Сравнительные групповые исследования . 2 (2): 107–124. дои : 10.1177/104649647100200201. S2CID  145544488.
2. DJ Watts и Стивен Строгац (июнь 1998 г.). «Коллективная динамика сетей «маленького мира». Природа . 393 (6684): 440–442. Бибкод : 1998Natur.393..440W. дои : 10.1038/30918. PMID  9623998. S2CID  4429113.
3. Ван, Ю; Гумаре, Эшвар; Ванденберге, Рик; Дюпон, Патрик (2017). «Сравнение различных обобщений коэффициента кластеризации и локальной эффективности для взвешенных неориентированных графов». Нейронные вычисления . 29 (2): 313–331. дои : 10.1162/NECO_a_00914 . PMID  27870616. S2CID  11000115. Архивировано из оригинала 10 августа 2020 г. . Проверено 8 августа 2020 г.
4. Р.Д. Люс и А.Д. Перри (1949). «Метод матричного анализа групповой структуры». Психометрика . 14 (1): 95–116. дои : 10.1007/BF02289146. hdl : 10.1007/BF02289146 . PMID  18152948. S2CID  16186758.
5. Стэнли Вассерман , Кэтрин Фауст, 1994. Анализ социальных сетей: методы и приложения. Кембридж: Издательство Кембриджского университета.
6. Торе Опсал и Пьетро Панзараса (2009). «Кластеризация во взвешенных сетях». Социальные сети . 31 (2): 155–163. doi :10.1016/j.socnet.2009.02.002. Архивировано из оригинала 1 июля 2019 г. Проверено 11 июня 2009 г.
7. Торе Опсал (2009). «Кластеризация в двухрежимных сетях». Конференция и семинар по двухрежимному социальному анализу (30 сентября – 2 октября 2009 г.) . Архивировано из оригинала 21 марта 2016 года . Проверено 11 сентября 2009 г.
8. Кемпер, Андреас (2009). Оценка сетевых эффектов на рынках программного обеспечения: комплексный сетевой подход. Спрингер. п. 142. ИСБН 9783790823660.
9. Баррат, А.; Бартелеми, М.; Пастор-Саторрас Р.; Веспиньяни, А. (2004). «Архитектура комплексно-взвешенных сетей». Труды Национальной академии наук . 101 (11): 3747–3752. arXiv : cond-mat/0311416 . Бибкод : 2004PNAS..101.3747B. дои : 10.1073/pnas.0400087101 . ПМЦ 374315 . ПМИД  15007165. 
10. Латапи, М.; Маньен, К.; Дель Веккио, Н. (2008). «Основные понятия анализа больших двухрежимных сетей» (PDF) . Социальные сети . 30 (1): 31–48. doi :10.1016/j.socnet.2007.04.006.
11. Фаджиоло, Г. (2007). «Кластеризация в сложных направленных сетях». Физический обзор E . 76 (2 Pt 2): 026107. arXiv : физика/0612169 . CiteSeerX 10.1.1.262.1006 . doi : 10.1103/PhysRevE.76.026107. PMID  17930104. S2CID  2317676. 
12. Клементе, врач общей практики; Грасси, Р. (2018). «Направленная кластеризация во взвешенных сетях: новая перспектива». Хаос, солитоны и фракталы . 107 : 26–38. arXiv : 1706.07322 . Бибкод : 2018CSF...107...26C. дои :10.1016/j.chaos.2017.12.007. S2CID  21919524.
13. Кайзер, Маркус (2008). «Средние коэффициенты кластеризации: роль изолированных узлов и листьев в мерах кластеризации для сетей маленького мира». Новый журнал физики . 10 (8): 083042. arXiv : 0802.2512 . Бибкод : 2008NJPh...10h3042K. дои : 10.1088/1367-2630/10/8/083042. S2CID  16480565.
14. Бармпутис, Д.; Мюррей, РМ (2010). «Сети с наименьшим средним расстоянием и наибольшей средней кластеризацией». arXiv : 1007.4031 [q-bio.MN].
15. Берченко, Якир; Артзи-Рандруп, Яэль; Тейчер, Мина; Стоун, Леви (30 марта 2009 г.). «Появление и размер гигантской компоненты в кластерных случайных графах с заданным распределением степеней». Письма о физических отзывах . 102 (13): 138701. doi :10.1103/PhysRevLett.102.138701. ISSN  0031-9007. PMID  19392410. Архивировано из оригинала 04 февраля 2023 г. Проверено 24 февраля 2022 г.
16. Берченко, Якир; Артзи-Рандруп, Яэль; Тейчер, Мина; Стоун, Леви (30 марта 2009 г.). «Появление и размер гигантской компоненты в кластерных случайных графах с заданным распределением степеней». Письма о физических отзывах . 102 (13): 138701. doi :10.1103/PhysRevLett.102.138701. ISSN  0031-9007. PMID  19392410. Архивировано из оригинала 04 февраля 2023 г. Проверено 24 февраля 2022 г.
17. МЭД Ньюман (2009). «Случайные графы с кластеризацией». Физ. Преподобный Летт . 103 (5): 058701. arXiv : 0903.4009 . doi : 10.1103/PhysRevLett.103.058701. PMID  19792540. S2CID  28214709.
18. А. Хакетт; С. Мельник и Дж. П. Глисон (2011). «Каскады в классе кластеризованных случайных сетей». Физ. Преподобный Е. 83 (5, часть 2): 056107. arXiv : 1012.3651 . doi : 10.1103/PhysRevE.83.056107. PMID  21728605. S2CID  18071422.

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

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