Распределение степеней - Degree distribution

Сетевая наука
Теория
График Комплексная сеть Заражение Маленький мир Без накипи Структура сообщества Перколяция Эволюция Управляемость Рисование графика Социальный капитал Анализ ссылок Оптимизация Взаимность Закрытие Гомофилия Транзитивность Предпочтительная привязанность Теория баланса Сетевой эффект Влияние общества
Типы сетей
Информационная (вычислительная) Телекоммуникации Транспорт Социальное Научное сотрудничество Биологические Искусственный нейрон Взаимозависимый Семантический Пространственный Зависимость Поток на чипе
Графики
Функции Клика Компонент Резать Цикл Структура данных Край Петля Район Дорожка Вершина Список смежности  / матрица Список заболеваемости  / матрица Типы Двудольный Полный Режиссер Гипер Мульти Случайный Взвешенный
Метрики Алгоритмы
Центральность Степень Близость Близость PageRank Мотив Кластеризация Распределение степеней Ассортативность Расстояние Модульность Эффективность
Модели
Топология Случайный график Эрдеш – Реньи Барабаши – Альберт Фитнес модель Уоттс-Строгац Экспоненциальный случайный (ERGM) Случайный геометрический (RGG) Гиперболический (HGN) Иерархический Стохастический блок Максимальная энтропия Мягкая конфигурация Тест LFR Динамика Логическая сеть агент на основе Эпидемия /СЭР
Списки Категории
Темы Программного обеспечения Сетевые ученые Категория: Теория сетей Категория: Теория графов

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

Определение

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

Распределение степеней п(k) сети определяется как доля узлов в сети со степенью k. Таким образом, если есть п узлов всего в сети и п_k из них имеют степень k, у нас есть ${ displaystyle P (k) = { frac {n_ {k}} {n}}}$.

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

Наблюдаемое распределение степеней

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

${ Displaystyle P (k) = {n-1 выберите k} p ^ {k} (1-p) ^ {n-1-k},}$

(или же Пуассон в пределе большого п, если средняя степень ${ Displaystyle langle к rangle = п (п-1)}$ фиксируется). Однако в большинстве сетей в реальном мире распределение степеней сильно отличается от этого. Большинство очень наклоненный вправо, что означает, что подавляющее большинство узлов имеют низкую степень, но небольшое количество, известное как «концентраторы», имеет высокую степень. Некоторые сети, в частности Интернет, Всемирная паутина, и утверждалось, что в некоторых социальных сетях распределение степеней примерно соответствует сила закона: ${ Displaystyle Р (к) сим к ^ {- гамма}}$, куда γ является константой. Такие сети называются безмасштабные сети и привлекли особое внимание своими структурными и динамическими свойствами.^[1][2][3][4] Однако в последнее время были проведены некоторые исследования, основанные на реальных наборах данных, которые утверждали, что, несмотря на то, что большинство наблюдаемых сетей имеют жирно-хвостовые степени распределения, они отклоняются от того, чтобы быть безмасштабный.^[5]

Распределение избыточной степени

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

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

${ Displaystyle д (к) = { гидроразрыва {к + 1} { langle k rangle}} P (k + 1),}$

куда ${ Displaystyle { langle к rangle}}$ это средний градус (средняя степень) модели. Из этого следует, что средняя степень соседа любого узла больше, чем средняя степень этого узла. В социальных сетях это означает, что у ваших друзей в среднем больше друзей, чем у вас. Это известно как парадокс дружбы. Можно показать, что сеть может иметь гигантский компонент, если его средняя степень превышения больше единицы:

${ displaystyle sum _ {k} kq (k)> 1 Rightarrow { langle k ^ {2} rangle} -2 { langle k rangle}> 0}$

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

Метод производящих функций

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

${ displaystyle G_ {0} (x) = textstyle sum _ {k} displaystyle P (k) x ^ {k}}$ и ${ displaystyle G_ {1} (x) = textstyle sum _ {k} displaystyle q (k) x ^ {k} = textstyle sum _ {k} displaystyle { frac {k} { langle k rangle}} P (k) x ^ {k-1}}$

${ Displaystyle G_ {1} (х)}$ также могут быть получены из производных ${ Displaystyle G_ {0} (х)}$:

${ displaystyle G_ {1} (x) = { frac {G '_ {0} (x)} {G' _ {0} (1)}}}$

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

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

Некоторые свойства, например моменты, можно легко вычислить из ${ Displaystyle G_ {0} (х)}$ и его производные:

• ${ displaystyle { langle k rangle} = G '_ {0} (1)}$
• ${ displaystyle { langle k ^ {2} rangle} = G '' _ {0} (1) + G '_ {0} (1)}$

И вообще:^[6]

• ${ displaystyle { langle k ^ {m} rangle} = { Biggl [} {{ bigg (} operatorname {x} { operatorname {d} ! over operatorname {dx} !} { biggl)} ^ {m}} G_ {0} (x) { Biggl]} _ {x = 1}}$

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

${ Displaystyle G_ {0} { bigl (} G_ {1} (... G_ {1} (x) ...) { bigr)}}$, с ${ displaystyle m-1}$ итерации функции ${ displaystyle G_ {1}}$ действует на себя.^[7]

Среднее количество первых соседей, ${ displaystyle c_ {1}}$, является ${ displaystyle { langle k rangle} = {dG_ {0} (x) over dx} | _ {x = 1}}$ и среднее количество вторых соседей: ${ displaystyle c_ {2} = { biggl [} {d over dx} G_ {0} { big (} G_ {1} (x) { big)} { biggl]} _ {x = 1 } = G_ {1} '(1) G' _ {0} { big (} G_ {1} (1) { big)} = G_ {1} '(1) G' _ {0} (1 ) = G '' _ {0} (1)}$

Распределение степеней для направленных сетей

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

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

${ displaystyle { mathcal {G}} (x, y) = sum _ {k_ {in}, k_ {out}} displaystyle P ({k_ {in}, k_ {out}}) x ^ {k_ {in}} y ^ {k_ {out}}.}$

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

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

${ displaystyle langle {k_ {in} -k_ {out}} rangle = sum _ {k_ {in}, k_ {out}} displaystyle (k_ {in} -k_ {out}) P ({k_ {in}, k_ {out}}) = 0}$,

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

${ Displaystyle { partial { mathcal {G}} over partial x} vert _ {x, y = 1} = { partial { mathcal {G}} over partial y} vert _ { х, у = 1} = с,}$

куда ${ displaystyle c}$ - средняя степень (как входящих, так и исходящих) узлов в сети; ${ displaystyle langle {k_ {in}} rangle = langle {k_ {out}} rangle = c.}$

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

• ${ Displaystyle G_ {0} ^ {in} (х) = { mathcal {G}} (х, 1)}$
• ${ displaystyle G_ {1} ^ {in} (x) = { frac {1} {c}} { partial { mathcal {G}} over partial x} vert _ {y = 1}}$
• ${ displaystyle G_ {0} ^ {out} (y) = { mathcal {G}} (1, y)}$
• ${ displaystyle G_ {1} ^ {out} (y) = { frac {1} {c}} { partial { mathcal {G}} over partial y} vert _ {x = 1}}$

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

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

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

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

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