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

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

Определение

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

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

${\displaystyle P(k)={\frac {n_{k}}{n}}}$.

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

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

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

${\displaystyle P(k)={n-1 \choose k}p^{k}(1-p)^{n-1-k},}$

(или Пуассона в пределе больших n , если средняя степень фиксирована). Однако большинство сетей в реальном мире имеют распределение степеней, сильно отличающееся от этого. Большинство из них сильно смещены вправо , что означает, что подавляющее большинство узлов имеют низкую степень, но небольшое количество, известное как «концентраторы», имеет высокую степень. Утверждалось , что некоторые сети, особенно Интернет, Всемирная паутина и некоторые социальные сети, имеют распределение степеней, которое приблизительно соответствует степенному закону : , где γ — константа. Такие сети называются безмасштабными сетями и привлекают особое внимание своими структурными и динамическими свойствами. ^{[1] [2] [3] [4]} Однако исследование широкого спектра реальных сетей показывает, что безмасштабные сети встречаются редко, если оценивать их с использованием статистически строгих мер. ^[5] Некоторые исследователи оспаривают эти результаты, утверждая, что определения, использованные в исследовании, являются неоправданно строгими, ^{[6] в то время как другие утверждают, что точная функциональная форма распределения степеней менее важна, чем знание того, является ли распределение степеней} толстым хвостом . или нет. ^[7] Чрезмерная интерпретация конкретных форм распределения степеней также подвергалась критике за неспособность принять во внимание, как сети могут развиваться с течением времени. ^[8] ${\displaystyle \langle k\rangle =p(n-1)}$ ${\displaystyle P(k)\sim k^{-\gamma }}$

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

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

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

${\displaystyle q(k)={\frac {k+1}{\langle k\rangle }}P(k+1),}$

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

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

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

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

Производящие функции можно использовать для расчета различных свойств случайных сетей. Учитывая распределение степеней и избыточное распределение степеней некоторой сети и соответственно, можно записать два степенных ряда в следующих формах: ${\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}(x)}$также можно получить из производных : ${\displaystyle G_{0}(x)}$

${\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}(x)}$

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

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

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

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

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

Среднее количество первых соседей , равно, а среднее количество вторых соседей равно: ${\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 _{x,y=1}=c,}$

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

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

• ${\displaystyle G_{0}^{in}(x)={\mathcal {G}}(x,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}}$

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

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

В подписанной сети каждый узел имеет положительную и отрицательную степень , которые представляют собой положительное количество ссылок и отрицательное количество ссылок, подключенных к этому узлу соответственно. Так и обозначают распределение отрицательной степени и распределение положительной степени подписанной сети. ^{[11] [12]} ${\displaystyle k_{+}}$ ${\displaystyle k_{-}}$ ${\displaystyle P(k_{+})}$ ${\displaystyle P(k_{-})}$

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

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

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

1. Барабаши, Альберт-Ласло; Альберт, Река (15 октября 1999 г.). «Появление масштабирования в случайных сетях». Наука . 286 (5439): 509–512. arXiv : cond-mat/9910332 . Бибкод : 1999Sci...286..509B. дои : 10.1126/science.286.5439.509. ISSN  0036-8075. PMID  10521342. S2CID  524106.
2. Альберт, Река; Барабаши, Альберт-Ласло (11 декабря 2000 г.). «Топология развивающихся сетей: локальные события и универсальность» (PDF) . Письма о физических отзывах . 85 (24): 5234–5237. arXiv : cond-mat/0005085 . Бибкод : 2000PhRvL..85.5234A. doi : 10.1103/physrevlett.85.5234. hdl : 2047/d20000695. ISSN  0031-9007. PMID  11102229. S2CID  81784. Архивировано (PDF) из оригинала 21 июля 2018 г. Проверено 25 сентября 2019 г.
3. Дороговцев, С. Н.; Мендес, JFF; Самухин, АН (21 мая 2001 г.). «Распределение степеней безмасштабной растущей сети в зависимости от размера». Физический обзор E . 63 (6): 062101. arXiv : cond-mat/0011115 . Бибкод : 2001PhRvE..63f2101D. doi : 10.1103/physreve.63.062101. ISSN  1063-651X. PMID  11415146. S2CID  119063903.
4. Пачон, Анжелика; Сасердот, Лаура; Ян, Шуи (2018). «Безмасштабное поведение сетей при наличии преимущественных и единых правил присоединения». Физика D: Нелинейные явления . 371 : 1–12. arXiv : 1704.08597 . Бибкод : 2018PhyD..371....1P. doi :10.1016/j.physd.2018.01.005. S2CID  119320331.
5. Бройдо, Анна Д.; Клаузет, Аарон (04 марта 2019 г.). «Безмасштабные сети встречаются редко». Природные коммуникации . 10 (1): 1017. doi : 10.1038/s41467-019-08746-5 . ISSN  2041-1723. ПМК 6399239 . ПМИД  30833554. 
6. Войталов, Иван; ван дер Хорн, Пим; ван дер Хофстад, Ремко; Крюков, Дмитрий (18 октября 2019 г.). «Безмасштабные сети молодцы». Обзор физических исследований . 1 (3): 033034. arXiv : 1811.02071 . doi : 10.1103/PhysRevResearch.1.033034 .
7. Холм, Петтер (04 марта 2019 г.). «Редко и везде: перспективы безмасштабных сетей». Природные коммуникации . 10 (1): 1016. Бибкод : 2019NatCo..10.1016H. дои : 10.1038/s41467-019-09038-8. ISSN  2041-1723. ПМК 6399274 . ПМИД  30833568. 
8. Фалькенберг, Макс; Ли, Чон Хек; Амано, Сюн-ичи; Огава, Кен-итиро; Яно, Кадзуо; Мияке, Ёсихиро; Эванс, Тим С.; Кристенсен, Ким (18 июня 2020 г.). «Определение временной зависимости роста сети». Обзор физических исследований . 2 (2): 023352. arXiv : 2001.09118 . doi : 10.1103/PhysRevResearch.2.023352 .
9. Ньюман, Марк (18 октября 2018 г.). Сети. Том. 1. Издательство Оксфордского университета. дои : 10.1093/oso/9780198805090.001.0001. ISBN 978-0-19-880509-0. Архивировано из оригинала 15 апреля 2020 г. Проверено 19 апреля 2020 г.
10. Ньюман, MEJ; Строгац, С.Х.; Уоттс, ди-джей (24 июля 2001 г.). «Случайные графы с произвольным распределением степеней и их приложения». Физический обзор E . 64 (2): 026118. arXiv : cond-mat/0007235 . дои : 10.1103/PhysRevE.64.026118 . ISSN  1063-651X. ПМИД  11497662.
11. Сабери М., Хосровабади Р., Хатиби А., Мисич Б., Джафари Г. (январь 2021 г.). «Топологическое влияние отрицательных связей на стабильность мозговой сети в состоянии покоя». Научные отчеты . 11 (1): 2176. doi : 10.1038/s41598-021-81767-7. ПМЦ 7838299 . ПМИД  33500525. 
12. Чиотти V (2015). «Степень корреляции в подписанных социальных сетях». Физика А: Статистическая механика и ее приложения . 422 : 25–39. arXiv : 1412.1024 . doi :10.1016/j.physa.2014.11.062. S2CID  4995458. Архивировано из оригинала 02 октября 2021 г. Проверено 10 февраля 2021 г.

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