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

редактировать

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

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

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

Содержание

1 Коэффициент локальной кластеризации
2 Коэффициент глобальной кластеризации
- 2.1 Средний сетевой коэффициент кластеризации
3 Перколяция кластеризованных сетей
4 См. Также
5 Ссылки
6 Внешние links

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

Пример коэффициента локальной кластеризации на неориентированном графе. Коэффициент локальной кластеризации синего узла вычисляется как доля фактически реализованных соединений между его соседями по сравнению с количеством всех возможных соединений. На рисунке синий узел имеет трех соседей, между которыми может быть максимум 3 соединения. В верхней части рисунка реализованы все три возможных соединения (толстые черные сегменты), что дает коэффициент локальной кластеризации, равный 1. В средней части рисунка реализовано только одно соединение (толстая черная линия) и 2 соединения отсутствуют ( пунктирные красные линии), что дает коэффициент локального кластера 1/3. Наконец, ни одно из возможных соединений между соседями синего узла не реализуется, в результате чего значение коэффициента локальной кластеризации равно 0.

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

Граф $G = (V, E) {\ displaystyle G = (V, E)}$ $G = (V, E)$ формально состоит из набора вершин $V {\ displaystyle V}$ $V$ и набора ребер $E {\ displaystyle E}$ $E$ между ними. Ребро $eij {\ displaystyle e_ {ij}}$ $e_ {ij}$ соединяет вершину $vi {\ displaystyle v_ {i}}$ $v_ {i}$ с вершиной $vj {\ displaystyle v_ {j}}$ $v_ {j}$ .

окрестность $N i {\ displaystyle N_ {i}}$ $N_ {i}$ для вершины $vi {\ displaystyle v_ {i}}$ $v_ {i}$ определяется как его непосредственно связанные соседи следующим образом:

N i = {vj: eij ∈ E ∨ eji ∈ E}. {\ displaystyle N_ {i} = \ {v_ {j}: e_ {ij} \ in E \ lor e_ {ji} \ in E \}.}

{\ displaystyle N _ {i} = \ {v_ {j}: e_ {ij} \ in E \ lor e_ {ji} \ in E \}.}

Мы определяем $ki {\ displaystyle k_ {i }}$ $k_ {i}$ как количество вершин, $| N i | {\ displaystyle | N_ {i} |}$ $| N_ {i } |$ , в окрестности, $N i {\ displaystyle N_ {i}}$ $N_ {i}$ , вершины.

Локальный коэффициент кластеризации $C i {\ displaystyle C_ {i}}$ $C_ {i}$ для вершины $vi {\ displaystyle v_ {i}}$ $v_ {i}$ тогда задается пропорцией связей между вершинами в его окрестности, деленной на количество связей, которые могут существовать между ними. Для ориентированного графа $eij {\ displaystyle e_ {ij}}$ $e_ {ij}$ отличается от $eji {\ displaystyle e_ {ji}}$ $e _ {{ji}}$ , и, следовательно, для каждой окрестности $N i {\ displaystyle N_ {i}}$ $N_ {i}$ есть $ки (ki - 1) {\ displaystyle k_ {i} (k_ {i} -1)}$ $k_ {i} (k_ {i} -1)$ ссылок, которые могут существовать между вершинами в пределах окрестности ( $ki {\ displaystyle k_ {i}}$ $k_ {i}$ - количество соседей вершины). Таким образом, коэффициент локальной кластеризации для ориентированных графов задается как

C i = | {e j k: v j, v k ∈ N i, e j k ∈ E} | к я (к я - 1). {\ displaystyle C_ {i} = {\ frac {| \ {e_ {jk}: v_ {j}, v_ {k} \ in N_ {i}, e_ {jk} \ in E \} |} {k_ { i} (k_ {i} -1)}}.}

C_ {i} = {\ frac {| \ {e _ {{jk}}: v_ {j}, v_ {k} \ in N_ {i}, e _ {{jk}} \ в E \} |} {k_ {i} (k_ {i} -1)}}.

Неориентированный граф имеет свойство $eij {\ displaystyle e_ {ij}}$ $e_ {ij}$ и $eji {\ displaystyle e_ {ji}}$ $e _ {{ji}}$ считаются идентичными. Следовательно, если вершина $vi {\ displaystyle v_ {i}}$ $v_ {i}$ имеет $ki {\ displaystyle k_ {i}}$ $k_ {i}$ соседей, $ki (ki - 1) 2 {\ displaystyle {\ frac {k_ {i} (k_ {i} -1)} {2}}}$ ${\ frac {k_ {i} (k_ {i} -1)} {2}}$ ребер могут существовать среди вершин в пределах окрестности. Таким образом, коэффициент локальной кластеризации для неориентированных графов можно определить как

C i = 2 | {e j k: v j, v k ∈ N i, e j k ∈ E} | к я (к я - 1). {\ displaystyle C_ {i} = {\ frac {2 | \ {e_ {jk}: v_ {j}, v_ {k} \ in N_ {i}, e_ {jk} \ in E \} |} {k_ {i} (k_ {i} -1)}}.}

C_ {i} = { \ frac {2 | \ {e _ {{jk}}: v_ {j}, v_ {k} \ in N_ {i}, e _ {{jk}} \ in E \} |} {k_ {i} (k_ {i} -1)}}.

Пусть $λ G (v) {\ displaystyle \ lambda _ {G} (v)}$ $\ lambda _ {G} (v)$ будет количеством треугольники на $v ∈ V (G) {\ displaystyle v \ in V (G)}$ $v \ in V (G)$ для неориентированного графа $G {\ displaystyle G}$ $G$ . То есть $λ G (v) {\ displaystyle \ lambda _ {G} (v)}$ $\ lambda _ {G} (v)$ - это количество подграфов $G {\ displaystyle G}$ <66.>с 3 ребрами и 3 вершинами, одна из которых - $v {\ displaystyle v}$ $v$ . Пусть $τ G (v) {\ displaystyle \ tau _ {G} (v)}$ $\ tau _ {G} (v)$ будет количеством троек на $v ∈ G {\ displaystyle v \ in G}$ $v \ in G$ . То есть $τ G (v) {\ displaystyle \ tau _ {G} (v)}$ $\ tau _ {G} (v)$ - количество подграфов (не обязательно индуцированных) с 2 ребрами и 3 вершинами, одна из которых - это $v {\ displaystyle v}$ $v$ и такое, что $v {\ displaystyle v}$ $v$ касается обоих краев. Тогда мы также можем определить коэффициент кластеризации как

C i = λ G (v) τ G (v). {\ displaystyle C_ {i} = {\ frac {\ lambda _ {G} (v)} {\ tau _ {G} (v)}}.}

C_ {i} = {\ frac {\ lambda _ {G} (v)} {\ tau _ {G } (v)}}.

Несложно показать, что два предыдущих определения то же самое, поскольку

τ G (v) = C (ki, 2) = 1 2 ki (ki - 1). {\ displaystyle \ tau _ {G} (v) = C ({k_ {i}}, 2) = {\ frac {1} {2}} k_ {i} (k_ {i} -1).}

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

Эти меры равны 1, если каждый сосед, подключенный к $vi {\ displaystyle v_ {i}}$ $v_ {i}$ , также подключен ко всем остальным вершинам в окрестности, и 0, если нет вершин, подключенных к $vi {\ displaystyle v_ {i}}$ $v_ {i}$ соединяется с любой другой вершиной, которая связана с $vi {\ displaystyle v_ {i}}$ $v_ {i}$ .

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

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

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

где:

ki = ∑ j A ij {\ displaystyle k_ {i} = \ sum _ {j} A_ {ij}}

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

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

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

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

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

C = количество закрытых триплетов, количество всех триплетов (открытых и закрытых) {\ displaystyle C = {\ frac {\ t_dv {количество закрытых триплетов}} {\ t_dv {количество всех троек (открытых и закрытых)}}}}

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

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

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

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

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

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

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

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

где:

k i = ∑ j A i j {\ displaystyle k_ {i} = \ sum _ {j} A_ {ij}}

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

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

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

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

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

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

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

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

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

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

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

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

Для изучения устойчивости кластерных сетей разработан перколяционный подход. Устойчивость к локальным атакам изучалась с помощью локальной перколяции. Также изучалась локализация волн в кластерных сложных сетях.

См. Также

Ссылки

^и (1971). «Транзитивность в структурных моделях малых групп». Сравнительные групповые исследования. 2 (2): 107–124. doi : 10.1177 / 104649647100200201.
^ D. Дж. Уоттс и Стивен Строгац (июнь 1998 г.). «Коллективная динамика сетей« маленького мира »». Природа. 393 (6684): 440–442. Bibcode : 1998Natur.393..440W. DOI : 10.1038 / 30918. PMID 9623998.
^Ван Юй; Гумаре, Эшвар; Ванденберге, Рик; Дюпон, Патрик (2017). «Сравнение различных обобщений коэффициента кластеризации и локальной эффективности для взвешенных неориентированных графов». Нейронные вычисления. 29 (2): 313–331. doi : 10.1162 / NECO_a_00914. Проверено 8 августа 2020 г.
^R. Д. Люс и (1949). «Метод матричного анализа структуры группы». Психометрика. 14 (1): 95–116. DOI : 10.1007 / BF02289146. PMID 18152948.
^Стэнли Вассерман, Кэтрин Фауст, 1994. Анализ социальных сетей: методы и приложения. Кембридж: Издательство Кембриджского университета.
^и (2009). «Кластеризация во взвешенных сетях». Социальные сети. 31 (2): 155–163. DOI : 10.1016 / j.socnet.2009.02.002.
^ (2009). «Кластеризация в двухрежимных сетях». Конференция и семинар по двухрежимному социальному анализу (30 сентября - 2 октября 2009 г.)
^Кемпер, Андреас (2009). Оценка сетевых эффектов на рынках программного обеспечения: комплексный сетевой подход. Springer. п. 142. ISBN 9783790823660.
^http://networksciencebook.com/4#ultra-small
^Barrat, A.; Barthelemy, M.; Pastor-Satorras, R.; Веспиньяни, А. (2004). «Архитектура сложных весовых сетей». Труды Национальной академии наук. 101 (11): 3747–3752. arXiv : cond-mat / 0311416. Bibcode : 2004PNAS..101.3747B. doi : 10.1073 / pnas.0400087101. PMC 374315. PMID 15007165.
^Latapy, M.; Magnien, C.; Дель Веккьо, Н. (2008). «Основные понятия для анализа больших двухрежимных сетей». Социальные сети. 30 (1): 31–48. doi : 10.1016 / j.socnet.2007.04.006.
^Фаджиоло, Г. (2007). «Кластеризация в сложных направленных сетях». Physical Review E. 76 (2 Pt 2): 026107. CiteSeerX 10.1.1.262.1006. doi : 10.1103 / PhysRevE.76.026107. PMID 17930104.
^Clemente, G.P.; Грасси, Р. (2018). «Направленная кластеризация в взвешенных сетях: новая перспектива». Хаос, солитоны и фракталы. 107 : 26–38. arXiv : 1706.07322. Bibcode : 2018CSF... 107... 26C. doi : 10.1016 / j.chaos.2017.12.007.
^Кайзер, Маркус (2008). «Средние коэффициенты кластеризации: роль изолированных узлов и листьев в мерах кластеризации для сетей малого мира». Новый журнал физики. 10 (8): 083042. arXiv : 0802.2512. Bibcode : 2008NJPh... 10h3042K. doi : 10.1088 / 1367-2630 / 10/8/083042.
^ Barmpoutis, D.; Мюррей, Р. М. (2010). «Сети с наименьшим средним расстоянием и наибольшей средней кластеризацией». arXiv : 1007.4031 [q-bio.MN ].
^M. Э. Дж. Ньюман (2009). «Случайные графы с кластеризацией». Phys. Rev. Lett. 103 : 058701.
^А. Хакетт, С. Мельник и Дж. П. Глисон (2011). «Каскады по классу сгруппированных случайных сетей». Phys. Ред. E. 83 : 056107. CS1 maint: дополнительная пунктуация (ссылка ) CS1 maint: несколько имен: список авторов (ссылка )
^S. Shao, X. Huang, HE Stanley, S. Havlin (2014). «Устойчивость частично взаимозависимой сети, сформированной из кластерных сетей». Phys. Rev. E. 89 : 032812. CS1 maint: несколько имен: список авторов (ссылка )
^, Fan Wang, Ruijin Du, Lixin Tian, Shuai Shao, H Eugene Stanley, Shlomo Havlin (2019). «Локализованная атака на сети с кластеризацией Huifang Hao». New Journal of Physics. 21 : 013014. CS1 maint: несколько имен: список авторов (ссылка )
^L. Jahnke, JW Kantelhardt, R. Berkovits, S. Havlin Phys (2008). «Локализация волн в сложных сетях с высокой кластеризацией». Phys. Rev. Lett. 101 : 175702. CS1 maint: несколько имен: список авторов (ссылка )

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

СМИ, относящиеся к коэффициент кластеризации на Wikimedia Commons