Распределение по степеням

При изучении графиков и сетей, степень узла в сети - это количество подключений, которые он имеет к другим узлам, а распределение степеней - это распределение вероятностей этих степеней по всей сети.

• 1 Определение
• 2 Наблюдаемые распределения степеней
• 3 Распределение избыточных степеней
• 4 Метод генерирующих функций
• 5 Распределение степеней для направленных сетей
• 6 См. Также
• 7 Ссылки

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

Затем определяется степень распределения P (k) сети как доля узлов в сети со степенью k. Таким образом, если в сети всего n узлов и n k из них имеют степень k, мы имеем P (k) = n k / n.

Та же самая информация также иногда представлена ​​в форме распределения кумулятивных степеней, доли узлов со степенью меньше k или даже дополнительного распределения кумулятивной степени, доли узлов со степенью больше или равной до k (1 - C), если рассматривать C как совокупное распределение степеней; то есть дополнение C.

Распределение степеней очень важно при изучении как реальных сетей, таких как Интернет и социальные сети и теоретические сети. Простейшая сетевая модель, например (модель Эрдеша – Реньи) случайный граф, в котором каждый из n узлов независимо связан (или нет) с вероятностью p (или 1 - p), имеет биномиальное распределение степеней k:

$P\; (k)\; =\; (n\; -\; 1\; k)\; pk\; (1\; -\; p)\; n\; -\; 1\; -\; k,\; \{\backslash \; displaystyle\; P\; (k)\; =\; \{n-1\; \backslash \; выберите\; k\}\; p\; ^\; \{k\}\; (1-p)\; ^\; \{n-1-k\},\}$

(или Пуассон в пределе большого n, если средняя степень $⟨\; к⟩\; знак\; равно\; п\; (n\; -\; 1)\; \{\backslash \; displaystyle\; \backslash \; langle\; k\; \backslash \; rangle\; =\; p\; (n-1)\}$фиксируется). Однако в большинстве сетей в реальном мире распределение степеней сильно отличается от этого. Большинство из них сильно наклонено вправо, что означает, что подавляющее большинство узлов имеют низкую степень, но небольшое количество, известное как «концентраторы», имеет высокую степень. Утверждалось, что некоторые сети, в частности Интернет, всемирная паутина и некоторые социальные сети, имеют распределение степеней, которое приблизительно соответствует степенному закону : $P\; (k)\; \sim \; k\; -\; \gamma \; \{\backslash \; displaystyle\; P\; (k)\; \backslash \; sim\; k\; ^\; \{-\; \backslash \; gamma\}\}$, где γ - постоянная. Такие сети называются безмасштабными сетями и привлекают особое внимание своими структурными и динамическими свойствами. Однако в последнее время были проведены некоторые исследования, основанные на реальных наборах данных, в которых утверждается, что, несмотря на то, что большинство наблюдаемых сетей имеют распределение степеней с толстыми хвостами, они отклоняются от безмасштабных.

Распределение избыточных степеней - это распределение вероятности для узла, достигнутого при следовании за ребром, количества других ребер, прикрепленных к этому узлу. Другими словами, это распределение исходящих ссылок от узла, достигнутого при переходе по ссылке.

Предположим, что сеть имеет распределение степеней $P\; (k)\; \{\backslash \; displaystyle\; P\; (k)\}$, выбирая один узел (случайно или нет) и переходя к одному из его соседей (предполагается, что у этого узла есть хотя бы один сосед), тогда вероятность того, что этот узел будет иметь $k\; \{\backslash \; displaystyle\; k\}$соседей, не определяется как $P\; (k)\; \{\backslash \; displaystyle\; P\; (k)\}$. Причина в том, что всякий раз, когда какой-либо узел выбирается в неоднородной сети, более вероятно достичь хобов, следуя за одним из существующих соседей этого узла. Истинная вероятность таких узлов иметь степень $k\; \{\backslash \; displaystyle\; k\}$равна $q\; (k)\; \{\backslash \; displaystyle\; q\; (k)\}$, что называется избыточная степень этого узла. В модели конфигурации , в которой корреляции между узлами были проигнорированы, и предполагается, что каждый узел связан с любыми другими узлами в сети с той же вероятностью, распределение избыточных степеней может быть найдено как:

$Q\; (К)\; знак\; равно\; К\; +\; 1\; ⟨К⟩\; п\; (к\; +\; 1),\; \{\backslash \; Displaystyle\; д\; (к)\; =\; \{\backslash \; гидроразрыва\; \{к\; +\; 1\}\; \{\backslash \; langle\; к\; \backslash \; rangle\}\}\; п\; (к\; +\; 1),\; \}$

где $⟨k⟩\; \{\backslash \; displaystyle\; \{\backslash \; langle\; k\; \backslash \; rangle\}\}$- средний градус (средний градус) модели. Отсюда следует тот факт, что средняя степень соседа любого узла больше, чем средняя степень этого узла. В социальных сетях это означает, что у ваших друзей в среднем больше друзей, чем у вас. Это известно как парадокс дружбы. Можно показать, что сеть может иметь гигантский компонент, если его средняя степень превышения больше единицы:

$\sum \; kkq\; (k)>1\; \Rightarrow \; ⟨k\; 2⟩\; -\; 2\; ⟨k⟩>0\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{k\}\; kq\; (k)>1\; \backslash \; Rightarrow\; \{\backslash \; langle\; k\; ^\; \{2\}\; \backslash \; rangle\}\; -2\; \{\backslash \; langle\; k\; \backslash \; rangle\}>0\}$

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

Генерирующие функции можно использовать для вычисления различных свойств случайных сетей. Учитывая распределение степеней и избыточную степень распределение некоторой сети, $P\; (k)\; \{\backslash \; displaystyle\; P\; (k)\}$и $q\; (k)\; \{\backslash \; displaystyle\; q\; (k)\}$res соответственно, можно записать два степенных ряда в следующих формах:

$G\; 0\; (x)\; =\; \sum \; k\; P\; (k)\; xk\; \{\backslash \; displaystyle\; G\_\; \{0\}\; (x)\; =\; \backslash \; textstyle\; \backslash \; sum\; \_\; \{k\}\; \backslash \; Displaystyle\; P\; (k)\; x\; ^\; \{k\}\}$и $G\; 1\; (x)\; =\; \sum \; kq\; (k)\; xk\; =\; \sum \; kk\; ⟨k⟩\; P\; (k)\; xk\; -\; 1\; \{\backslash \; displaystyle\; G\_\; \{1\}\; (x)\; =\; \backslash \; textstyle\; \backslash \; sum\; \_\; \{k\}\; \backslash \; displaystyle\; q\; (k)\; x\; ^\; \{k\}\; =\; \backslash \; textstyle\; \backslash \; sum\; \_\; \{k\}\; \backslash \; displaystyle\; \{\backslash \; frac\; \{k\}\; \{\backslash \; langle\; k\; \backslash \; rangle\; \}\}\; P\; (k)\; x\; ^\; \{k-1\}\}$

$G\; 1\; (x)\; \{\backslash \; displaystyle\; G\_\; \{1\}\; (x)\}$можно также получить из производных от $G\; 0\; (Икс)\; \{\backslash \; Displaystyle\; G\_\; \{0\}\; (х)\}$:

$G\; 1\; (x)\; =\; G\; 0\; \prime \; (x)\; G\; 0\; \prime \; (1)\; \{\backslash \; displaystyle\; G\_\; \{1\}\; (x)\; =\; \{\backslash \; frac\; \{G\; \text{'}\_\; \{0\}\; (x)\}\; \{G\text{'}\; \_\; \{0\}\; (1)\}\}\}$

Если мы знаем производящую функцию для распределения вероятностей $P\; (k)\; \{\backslash \; displaystyle\; P\; (k)\}$, тогда мы можем восстановить значения $P\; (k)\; \{\backslash \; displaystyle\; P\; (k)\}$путем дифференцирования:

$P\; (k)\; =\; 1\; k!\; d\; k\; G\; d\; x\; k\; |\; x\; =\; 0\; \{\backslash \; displaystyle\; P\; (k)\; =\; \{\backslash \; frac\; \{1\}\; \{k!\}\}\; \{\backslash \; operatorname\; \{d\}\; ^\; \{k\}\; \backslash !\; G\; \backslash \; over\; \backslash \; operatorname\; \{d\}\; \backslash !\; x\; ^\; \{k\}\}\; \{\backslash \; biggl\; \backslash \; vert\}\; \_\; \{x\; =\; 0\}\}$

Некоторые свойства, например моменты, могут быть легко вычислены из $G\; 0\; (x)\; \{\backslash \; displaystyle\; G\_\; \{0\}\; (x)\}$и его производных:

• $⟨k⟩\; =\; G\; 0\; \prime \; (1)\; \{\backslash \; displaystyle\; \{\backslash \; langle\; k\; \backslash \; rangle\}\; =\; G\; \text{'}\_\; \{0\}\; (1)\}$
• $⟨k\; 2⟩\; =\; G\; 0\; ″\; (1)\; +\; G\; 0\; \prime \; (1)\; \{\backslash \; displaystyle\; \{\backslash \; langle\; k\; ^\; \{2\}\; \backslash \; rangle\}\; =\; G\; \text{'}\text{'}\; \_\; \{0\}\; (1)\; +\; G\; \text{'}\_\; \{0\}\; (1)\}$

И вообще:

• $⟨km⟩\; =\; [(x\; \; d\; dx)\; m\; G\; 0\; (x)]\; x\; =\; 1\; \{\backslash \; displaystyle\; \{\backslash \; langle\; k\; ^\; \{m\}\; \backslash \; rangle\}\; =\; \{\backslash \; Biggl\; [\}\; \{\{\backslash \; bigg\; (\}\; \backslash \; operatorname\; \{x\}\; \{\backslash \; operatorname\; \{d\}\; \backslash !\; \backslash \; Over\; \backslash \; operatorname\; \{dx\}\; \backslash !\}\; \{\backslash \; biggl)\}\; ^\; \{m\}\}\; G\_\; \{0\}\; (x)\; \{\backslash \; Biggl]\}\; \_\; \{x\; =\; 1\}\}$

Для с распределением по Пуассону случайные сети, такие как график ER, $G\; 1\; (x)\; =\; G\; 0\; (x)\; \{\backslash \; displaystyle\; G\_\; \{1\}\; (x)\; =\; G\_\; \{0\}\; (x)\}$, поэтому теория случайных сетей этого типа особенно проста. Распределения вероятностей для 1-го и 2-го ближайших соседей генерируются функциями $G\; 0\; (x)\; \{\backslash \; displaystyle\; G\_\; \{0\}\; (x)\}$и $G\; 0\; (G\; 1\; (х))\; \{\backslash \; Displaystyle\; G\_\; \{0\}\; (G\_\; \{1\}\; (x))\}$. В более широком смысле, распределение $m\; \{\backslash \; displaystyle\; m\}$-го соседа генерируется следующим образом:

$G\; 0\; (G\; 1\; (...\; G\; 1\; (x)..))\; \{\backslash \; displaystyle\; G\_\; \{0\}\; \{\backslash \; bigl\; (\}\; G\_\; \{1\}\; (...\; G\_\; \{1\}\; (x)...)\; \{\backslash \; bigr)\}\}$, с $m\; -\; 1\; \{\backslash \; displaystyle\; m-1\}$итераций функции $G\; 1\; \{\backslash \; displaystyle\; G\_\; \{1\}\}$, действующей на себя.

Среднее число первых соседей, $c\; 1\; \{\backslash \; displaystyle\; c\_\; \{1\}\}$, равно $⟨k⟩\; =\; d\; G\; 0\; (x)\; dx\; |\; x\; =\; 1\; \{\backslash \; displaystyle\; \{\backslash \; langle\; k\; \backslash \; rangle\}\; =\; \{dG\_\; \{0\}\; (x)\; \backslash \; over\; dx\}\; |\; \_\; \{x\; =\; 1\}\}$, а среднее количество вторых соседей: $c\; 2\; =\; [ddx\; G\; 0\; (G\; 1\; (x))]\; x\; =\; 1\; =\; G\; 1\; \prime \; (1)\; G\; 0\; \prime \; (G\; 1\; (1))\; =\; G\; 1\; \prime \; (1)\; G\; 0\; \prime \; (1)\; Знак\; равно\; G\; 0\; ″\; (1)\; \{\backslash \; displaystyle\; c\_\; \{2\}\; =\; \{\backslash \; biggl\; [\}\; \{d\; \backslash \; over\; dx\}\; G\_\; \{0\}\; \{\backslash \; big\; (\}\; G\_\; \{1\}\; (x)\; \{\backslash \; big)\}\; \{\backslash \; biggl\; ]\}\; \_\; \{x\; =\; 1\}\; =\; G\_\; \{1\}\; \text{'}(1)\; G\text{'}\; \_\; \{0\}\; \{\backslash \; big\; (\}\; G\_\; \{1\}\; (1)\; \{\backslash \; big)\}\; =\; G\_\; \{1\}\; \text{'}(1)\; G\; \text{'}\_\; \{0\}\; (1)\; =\; G\text{'}\; \text{'}\_\; \{0\}\; (1)\}$

Распределение степени входа / выхода для графа гиперссылок Википедии (логарифмические шкалы)

В направленном сети, каждый узел имеет некоторую внутреннюю степень $kin\; \{\backslash \; displaystyle\; k\_\; \{in\}\}$и некоторую внешнюю степень $kout\; \{\backslash \; displaystyle\; k\_\; \{out\}\}$которые представляют собой количество ссылок, которые должным образом входили и выходили из этого узла. Если $P\; (kin,\; kout)\; \{\backslash \; displaystyle\; P\; (k\_\; \{in\},\; k\_\; \{out\})\}$- это вероятность того, что случайно выбранный узел имеет внутреннюю степень $kin\; \{\backslash \; displaystyle\; k\_\; \{in\}\}$и out-degree $kout\; \{\backslash \; displaystyle\; k\_\; \{out\}\}$, затем производящая функция, назначенная этому совместному распределению вероятностей можно записать с двумя значениями $x\; \{\backslash \; displaystyle\; x\}$и $y\; \{\backslash \; displaystyle\; y\}$как:

$G\; (x,\; y)\; =\; \sum \; кин,\; коут\; П\; (кин,\; коут)\; xkinykout.\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{G\}\}\; (x,\; y)\; =\; \backslash \; sum\; \_\; \{k\_\; \{in\},\; k\_\; \{out\}\}\; \backslash \; displaystyle\; P\; (\{k\_\; \{in\},\; k\_\; \{out\}\})\; x\; ^\; \{k\_\; \{in\}\}\; y\; ^\; \{k\_\; \{out\}\}.\}$

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

узел, равно нулю. Следовательно,

$⟨кин\; -\; коут⟩\; =\; \sum \; кин,\; коут\; (кин\; -\; коут)\; P\; (кин,\; коут)\; =\; 0\; \{\backslash \; displaystyle\; \backslash \; langle\; \{k\_\; \{in\}\; -k\_\; \{out\}\}\; \backslash \; rangle\; =\; \backslash \; sum\; \_\; \{k\_\; \{in\},\; k\_\; \{out\}\}\; \backslash \; displaystyle\; (k\_\; \{in\}\; -k\_\; \{out\})\; P\; (\{k\_\; \{in\},\; k\_\; \{out\}\})\; =\; 0\}$,

что означает, что поколение функция должна удовлетворять:

$\partial \; G\; \partial \; x\; |\; x,\; y\; =\; 1\; =\; \partial \; G\; \partial \; y\; |\; Икс,\; Y\; знак\; равно\; 1\; знак\; равно\; с,\; \{\backslash \; Displaystyle\; \{\backslash \; partial\; \{\backslash \; mathcal\; \{G\}\}\; \backslash \; over\; \backslash \; partial\; x\}\; \backslash \; vert\; \_\; \{x,\; y\; =\; 1\}\; =\; \{\backslash \; partial\; \{\backslash \; mathcal\; \{G\}\}\; \backslash \; over\; \backslash \; partial\; y\}\; \backslash \; vert\; \_\; \{x,\; y\; =\; 1\}\; =\; c,\}$

где $c\; \{\backslash \; displaystyle\; c\}$- средняя степень (как внутри, так и снаружи) узлов. в сети; $k\; i\; n⟩\; =\; ⟨k\; o\; u\; t⟩\; =\; c.\; \{\backslash \; displaystyle\; \backslash \; langle\; \{k\_\; \{in\}\}\; \backslash \; rangle\; =\; \backslash \; langle\; \{k\_\; \{out\}\}\; \backslash \; rangle\; =\; c.\}$

Использование функции $G\; (x,\; y)\; \{\backslash \; displaystyle\; \{\backslash \; mathcal\; \{\; G\}\}\; (x,\; y)\}$, мы снова можем найти функцию генерации для распределения внутренних / исходящих степеней и распределения входных / выходных степеней, как и раньше. $G\; 0\; in\; (x)\; \{\backslash \; displaystyle\; G\_\; \{0\}\; ^\; \{in\}\; (x)\}$можно определить как производящие функции для количества поступающих ссылок на случайно выбранный узел, а $G\; 1\; in\; (x)\; \{\backslash \; displaystyle\; G\_\; \{1\}\; ^\; \{in\}\; (x)\}$можно определить как количество входящих ссылок на узел, достигнутый при переходе по случайно выбранной ссылке. Мы также можем определить производящие функции $G\; 0\; out\; (y)\; \{\backslash \; displaystyle\; G\_\; \{0\}\; ^\; \{out\}\; (y)\}$и $G\; 1\; out\; (y)\; \{\backslash \; displaystyle\; G\_\; \{1\}\; ^\; \{out\}\; (y)\}$для числа, выходящего из такого узла:

• $G\; 0\; in\; (x)\; =\; G\; (x,\; 1)\; \{\backslash \; displaystyle\; G\_\; \{0\}\; ^\; \{\; in\}\; (x)\; =\; \{\backslash \; mathcal\; \{G\}\}\; (x,\; 1)\}$
• $G\; 1\; in\; (x)\; =\; 1\; c\; \partial \; G\; \partial \; x\; |\; y\; =\; 1\; \{\backslash \; displaystyle\; G\_\; \{1\}\; ^\; \{in\}\; (x)\; =\; \{\backslash \; frac\; \{1\}\; \{c\}\}\; \{\backslash \; partial\; \{\backslash \; mathcal\; \{G\}\}\; \backslash \; over\; \backslash \; partial\; x\}\; \backslash \; vert\; \_\; \{y\; =\; 1\}\}$
• $G\; 0\; out\; (y)\; =\; G\; (1,\; y)\; \{\backslash \; displaystyle\; G\_\; \{0\}\; ^\; \{out\}\; (y)\; =\; \{\backslash \; mathcal\; \{G\}\}\; (1,\; y)\}$
• $G\; 1\; out\; (y)\; =\; 1\; c\; \partial \; G\; \partial \; y\; |\; Икс\; =\; 1\; \{\backslash \; Displaystyle\; G\_\; \{1\}\; ^\; \{out\}\; (y)\; =\; \{\backslash \; frac\; \{1\}\; \{c\}\}\; \{\backslash \; partial\; \{\backslash \; mathcal\; \{G\}\}\; \backslash \; over\; \backslash \; partial\; y\}\; \backslash \; vert\; \_\; \{x\; =\; 1\}\}$

Здесь среднее количество первых соседей, $c\; \{\backslash \; displaystyle\; c\}$, или, как ранее было указано, $c\; 1\; \{\backslash \; displaystyle\; c\_\; \{1\}\}$, равно $\partial \; G\; \partial \; x\; |\; x,\; y\; =\; 1\; =\; \partial \; G\; \partial \; y\; |\; х,\; у\; знак\; равно\; 1\; \{\backslash \; Displaystyle\; \{\backslash \; partial\; \{\backslash \; mathcal\; \{G\}\}\; \backslash \; over\; \backslash \; partial\; x\}\; \{\backslash \; biggl\; \backslash \; vert\}\; \_\; \{x,\; y\; =\; 1\}\; =\; \{\backslash \; partial\; \{\backslash \; mathcal\; \{G\}\}\; \backslash \; over\; \backslash \; partial\; y\}\; \{\backslash \; biggl\; \backslash \; vert\}\; \_\; \{x,\; y\; =\; 1\}\}$, а среднее количество 2-х соседей, достижимых из случайно выбранного узла, равно: $c\; 2\; =\; G\; 1\; \prime \; (1)\; G\; 0\; \prime \; (1)\; =\; \partial \; 2\; G\; \partial \; x\; \partial \; y\; |\; Икс,\; Y\; =\; 1\; \{\backslash \; Displaystyle\; c\_\; \{2\}\; =\; G\_\; \{1\}\; \text{'}(1)\; G\text{'}\; \_\; \{0\}\; (1)\; =\; \{\backslash \; partial\; ^\; \{2\}\; \{\backslash \; mathcal\; \{G\}\}\; \backslash \; over\; \backslash \; partial\; x\; \backslash \; partial\; y\}\; \{\backslash \; biggl\; \backslash \; vert\}\; \_\; \{x,\; y\; =\; 1\}\}$. Это также номера 1-го и 2-го соседей, из которых может быть достигнут случайный узел, поскольку эти уравнения явно симметричны в $x\; \{\backslash \; displaystyle\; x\}$и $y\; \{\backslash \; displaystyle\; y\; \}$.

• Теория графов
• Сложная сеть
• Безмасштабная сеть
• Случайный граф
• Структурное отсечение

• Albert, R.; Барабаши, А.-Л. (2002). «Статистическая механика сложных сетей». Обзоры современной физики. 74 (1): 47–97. arXiv : cond-mat / 0106096. Bibcode : 2002RvMP... 74... 47A. doi : 10.1103 / RevModPhys.74.47.
• Дороговцев, С.; Мендес, Дж. Ф. Ф. (2002). «Эволюция сетей». Успехи физики. 51 (4): 1079–1187. arXiv : cond-mat / 0106144. Bibcode : 2002AdPhy..51.1079D. doi : 10.1080 / 00018730110112519.
• Ньюман, М. Э. Дж. (2003). «Структура и функции сложных сетей». SIAM Обзор. 45 (2): 167–256. arXiv : cond-mat / 0303516. Bibcode : 2003SIAMR..45..167N. doi : 10.1137 / S003614450342480.
• Шломо Хэвлин и Реувен Коэн (2010). Сложные сети: структура, надежность и функции. Cambridge University Press.