Структурное отсечение

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

Определение

Структурное ограничение — это ограничение максимальной степени, возникающее из структуры сети конечного размера.

Позволять $E_{kk'}$ — количество ребер между всеми вершинами степени $k$ и $k'$ если $k\neq k'$ , и удвоенное число, если $k=k'$ .Учитывая, что несколько ребер между двумя вершинами не допускаются, $E_{kk'}$ ограничено максимальным количеством ребер между двумя классами степеней $m_{kk'}$ .

Тогда соотношение можно записать

r_{kk'}\equiv {\frac {E_{kk'}}{m_{kk'}}}={\frac {\langle k\rangle P(k,k')}{\min\{kP(k),k'P(k'),NP(k)P(k')\}}}

,

где $\langle k\rangle$ - средняя степень сети, $N$ общее количество вершин, $P(k)$ вероятность того, что случайно выбранная вершина будет иметь степень $k$ , и $P(k,k')=E_{kk'}/\langle k\rangle N$ это вероятность того, что случайно выбранное ребро с одной стороны соединит вершину со степенью $k$ с вершиной степени $k'$ .

Чтобы находиться в физическом регионе, $r_{kk'}\leq 1$ должен быть удовлетворен.

Структурное отсечение $k_{s}$ затем определяется $r_{k_{s}k_{s}}=1$ . ^[1]

Структурное отключение для нейтральных сетей

Структурное отсечение играет важную роль в нейтральных (или некоррелированных) сетях, которые не проявляют никакой ассортативности. Отрезок принимает вид

k_{s}\sim (\langle k\rangle N)^{1/2}

которое конечно в любой реальной сети.

Таким образом, если вершины степени $k\geq k_{s}$ существуют, физически невозможно соединить между ними достаточное количество ребер, чтобы сохранить нейтральность сети.

Структурная дисассортативность в безмасштабных сетях

В безмасштабной сети распределение степеней описывается степенным законом с характеристическим показателем $\gamma$ , $P(k)\sim k^{-\gamma }$ .В свободной сети конечного масштаба максимальная степень любой вершины (также называемая естественной обрезкой) масштабируется как

k_{\text{max}}\sim N^{\frac {1}{\gamma -1}}

.

Тогда сети с $\gamma <3$ , который является режимом большинства реальных сетей, будет иметь $k_{\text{max}}$ расходится быстрее, чем $k_{s}\sim N^{1/2}$ в нейтральной сети. Это имеет важное значение: нейтральная в остальном сеть может демонстрировать дисассортативные корреляции по степени, если $k_{\text{max}}>k_{s}$ .Эта диссортативность не является результатом каких-либо микроскопических свойств сети, а обусловлена исключительно структурными ограничениями сети. При анализе сетей, чтобы корреляция по степени была значимой, необходимо убедиться, что корреляции не имеют структурного происхождения.

Влияние структурного ограничения

Сгенерированные сети

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

Разрешить несколько ребер между одними и теми же двумя вершинами. Хотя это означает, что сеть больше не является простой сетью, она позволяет иметь достаточное количество ребер для поддержания нейтральности.
Просто удалите все вершины со степенью $k>k_{s}$ . Это гарантирует, что ни одна вершина не подвержена структурным ограничениям на своих ребрах, а сеть свободна от структурной дисассортативности.

Реальные сети

В некоторых реальных сетях также могут использоваться те же методы, что и для сгенерированных сетей. Однако во многих случаях может не иметь смысла рассматривать несколько ребер между двумя вершинами, или такая информация недоступна. Вершины высокой степени (концентраторы) также могут быть важной частью сети, которую нельзя удалить без изменения других фундаментальных свойств.

Чтобы определить, имеет ли ассортативность или неассортативность сети структурное происхождение, сеть можно сравнить с сохраняющей степень рандомизированной версией самой себя (без кратных ребер).Тогда любая мера ассортативности рандомизированной версии будет результатом структурного отсечения. Если реальная сеть демонстрирует какую-либо дополнительную ассортативность или дисассортативность помимо структурной дисассортативности, то это является значимым свойством реальной сети.

другие величины, которые зависят от степени корреляции, например некоторые определения коэффициента богатого клуба Структурное отсечение также повлияет на . ^[3]

См. также

Ссылки

^ Богуна, М.; Пастор-Саторрас Р.; Веспиньяни, А. (1 марта 2004 г.). «Обрезки и эффекты конечного размера в безмасштабных сетях». Европейский физический журнал Б. 38 (2): 205–209. arXiv : cond-mat/0311650 . Бибкод : 2004EPJB...38..205B . дои : 10.1140/epjb/e2004-00038-8 .
^ Катандзаро, Микеле; Богунья, Мариан; Пастор-Саторрас, Ромуальдо (февраль 2005 г.). «Генерация некоррелированных случайных безмасштабных сетей». Физический обзор E . 71 (2). arXiv : cond-mat/0408110 . Бибкод : 2005PhRvE..71b7103C . дои : 10.1103/PhysRevE.71.027103 .
^ Чжоу, С; Мондрагон, Р.Дж. (28 июня 2007 г.). «Структурные ограничения в сложных сетях». Новый журнал физики . 9 (6): 173–173. arXiv : физика/0702096 . Бибкод : 2007NJPh....9..173Z . дои : 10.1088/1367-2630/9/6/173 .

[1] Богуна, М.; Пастор-Саторрас Р.; Веспиньяни, А. (1 марта 2004 г.). «Обрезки и эффекты конечного размера в безмасштабных сетях». Европейский физический журнал Б. 38 (2): 205–209. arXiv : cond-mat/0311650 . Бибкод : 2004EPJB...38..205B . дои : 10.1140/epjb/e2004-00038-8 .

[2] Катандзаро, Микеле; Богунья, Мариан; Пастор-Саторрас, Ромуальдо (февраль 2005 г.). «Генерация некоррелированных случайных безмасштабных сетей». Физический обзор E . 71 (2). arXiv : cond-mat/0408110 . Бибкод : 2005PhRvE..71b7103C . дои : 10.1103/PhysRevE.71.027103 .

[3] Чжоу, С; Мондрагон, Р.Дж. (28 июня 2007 г.). «Структурные ограничения в сложных сетях». Новый журнал физики . 9 (6): 173–173. arXiv : физика/0702096 . Бибкод : 2007NJPh....9..173Z . дои : 10.1088/1367-2630/9/6/173 .

[1]

[2]

[3]