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

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

Определение [ править ]

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

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

P(k)={\frac {n_{k}}{n}}

.

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

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

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

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

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

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

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

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

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

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

$\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]

Метод порождающих функций [ править ]

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

$G_{0}(x)=\textstyle \sum _{k}\displaystyle P(k)x^{k}$ и $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}$

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

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

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

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

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

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

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

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

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

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

Среднее количество 1-х соседей, $c_{1}$ , является ${\langle k\rangle }={dG_{0}(x) \over dx}|_{x=1}$ а среднее количество вторых соседей равно: $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)$

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

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

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

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

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

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

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

${\partial {\mathcal {G}} \over \partial x}\vert _{x,y=1}={\partial {\mathcal {G}} \over \partial y}\vert _{x,y=1}=c,$

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

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

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

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

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

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

См. также [ править ]

Ссылки [ править ]

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

Альберт, Р.; Барабаси, А.-Л. (2002). «Статистическая механика сложных сетей». Обзоры современной физики . 74 (1): 47–97. arXiv : cond-mat/0106096 . Бибкод : 2002РвМП...74...47А . дои : 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 .

[BA-1] Барабаши, Альберт-Ласло; Альберт, Река (15.10.1999). «Появление масштабирования в случайных сетях». Наука . 286 (5439): 509–512. arXiv : cond-mat/9910332 . Бибкод : 1999Sci...286..509B . дои : 10.1126/science.286.5439.509 . ISSN 0036-8075 . ПМИД 10521342 . S2CID 524106 .

[AB-2] Альберт, Река; Барабаши, Альберт-Ласло (11 декабря 2000 г.). «Топология развивающихся сетей: локальные события и универсальность» (PDF) . Письма о физических отзывах . 85 (24): 5234–5237. arXiv : cond-mat/0005085 . Бибкод : 2000PhRvL..85.5234A . дои : 10.1103/physrevlett.85.5234 . hdl : 2047/d20000695 . ISSN 0031-9007 . ПМИД 11102229 . S2CID 81784 . Архивировано (PDF) из оригинала 21 июля 2018 г. Проверено 25 сентября 2019 г.

[Doro-3] Дороговцев С.Н.; Мендес, JFF; Самухин, АН (21 мая 2001 г.). «Распределение степеней безмасштабной растущей сети в зависимости от размера». Физический обзор E . 63 (6): 062101. arXiv : cond-mat/0011115 . Бибкод : 2001PhRvE..63f2101D . дои : 10.1103/physreve.63.062101 . ISSN 1063-651X . ПМИД 11415146 . S2CID 119063903 .

[PSY-4] Пашон, Анжелика; Сасердот, Лаура; Ян, Шуйи (2018). «Безмасштабное поведение сетей при наличии преимущественных и единых правил присоединения». Физика D: Нелинейные явления . 371 : 1–12. arXiv : 1704.08597 . Бибкод : 2018PhyD..371....1P . дои : 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 .

[:0-9] Jump up to: ^а ^б ^с ^д Ньюман, Марк (18 октября 2018 г.). Сети . Том. 1. Издательство Оксфордского университета. дои : 10.1093/oso/9780198805090.001.0001 . ISBN 978-0-19-880509-0 . Архивировано из оригинала 15 апреля 2020 г. Проверено 19 апреля 2020 г.

[:1-10] Jump up to: ^а ^б ^с Ньюман, МЭЖ; Строгац, С.Х.; Уоттс, ди-джей (24 июля 2001 г.). «Случайные графы с произвольными распределениями степеней и их приложения» . Физический обзор E . 64 (2): 026118. arXiv : cond-mat/0007235 . дои : 10.1103/PhysRevE.64.026118 . ISSN 1063-651X . ПМИД 11497662 .

[10.1038/s41598-021-81767-7-11] Сабери М., Хосровабади Р., Хатиби А., Мисич Б., Джафари Г. (январь 2021 г.). «Топологическое влияние отрицательных связей на стабильность сети мозга в состоянии покоя» . Научные отчеты . 11 (1): 2176. doi : 10.1038/s41598-021-81767-7 . ПМЦ 7838299 . ПМИД 33500525 .

[10.1016/j.physa.2014.11.062-12] Чиотти V (2015). «Степень корреляции в подписанных социальных сетях» . Физика А: Статистическая механика и ее приложения . 422 : 25–39. arXiv : 1412.1024 . дои : 10.1016/j.physa.2014.11.062 . S2CID 4995458 . Архивировано из оригинала 2 октября 2021 г. Проверено 10 февраля 2021 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]