Степень узла в сети (иногда неправильно называемая связностью ) — это количество соединений или ребер, которые узел имеет с другими узлами. Если сеть направлена , что означает, что ребра направлены в одном направлении от одного узла к другому узлу, то узлы имеют две разные степени: входную степень, которая представляет собой количество входящих ребер, и исходящую степень, которая представляет собой число исходящих ребер.
Распределение степеней P ( k ) сети затем определяется как доля узлов в сети со степенью k . Таким образом, если всего в сети n узлов и n k из них имеют степень k , мы имеем
.
Та же информация иногда представляется в виде кумулятивного распределения степеней , доли узлов со степенью меньше k , или даже дополнительного кумулятивного распределения степеней , доли узлов со степенью больше или равной k (1 - C ) если рассматривать C как кумулятивное распределение степеней ; т.е. дополнение C .
Наблюдаемые распределения степеней
Распределение степеней очень важно при изучении как реальных сетей, таких как Интернет и социальные сети , так и теоретических сетей. Простейшая сетевая модель, например, случайный граф (модель Эрдеша–Реньи) , в котором каждый из n узлов независимо связан (или нет) с вероятностью p (или 1 − p ), имеет биномиальное распределение степеней k :
(или Пуассона в пределе больших n , если средняя степень фиксирована). Однако большинство сетей в реальном мире имеют распределение степеней, сильно отличающееся от этого. Большинство из них сильно смещены вправо , что означает, что подавляющее большинство узлов имеют низкую степень, но небольшое количество, известное как «концентраторы», имеет высокую степень. Утверждалось , что некоторые сети, особенно Интернет, Всемирная паутина и некоторые социальные сети, имеют распределение степеней, которое приблизительно соответствует степенному закону : , где γ — константа. Такие сети называются безмасштабными сетями и привлекают особое внимание своими структурными и динамическими свойствами. [1] [2] [3] [4] Однако исследование широкого спектра реальных сетей показывает, что безмасштабные сети встречаются редко, если оценивать их с использованием статистически строгих мер. [5] Некоторые исследователи оспаривают эти результаты, утверждая, что определения, использованные в исследовании, являются неоправданно строгими, [6] в то время как другие утверждают, что точная функциональная форма распределения степеней менее важна, чем знание того, является ли распределение степеней толстым хвостом . или нет. [7] Чрезмерная интерпретация конкретных форм распределения степеней также подвергалась критике за неспособность принять во внимание, как сети могут развиваться с течением времени. [8]
Распределение избыточной степени
Распределение избыточной степени — это распределение вероятностей для узла, достигнутого путем следования по ребру, количества других ребер, присоединенных к этому узлу. [9] Другими словами, это распределение исходящих ссылок от узла, достигнутого при переходе по ссылке.
Предположим, что сеть имеет распределение степеней , выбирая один узел (случайно или нет) и переходя к одному из его соседей (при условии, что у него есть хотя бы один сосед), тогда вероятность того, что у этого узла есть соседи, не определяется выражением . Причина в том, что всякий раз, когда в гетерогенной сети выбирается какой-либо узел, более вероятно достичь концентраторов, следуя за одним из существующих соседей этого узла. Истинная вероятность того, что такие узлы будут иметь степень, называется избыточной степенью этого узла. В модели конфигурации , в которой корреляции между узлами игнорируются и предполагается, что каждый узел связан с любыми другими узлами в сети с той же вероятностью, распределение избыточной степени можно найти как: [ 9]
где – средняя степень (средняя степень) модели. Отсюда следует, что средняя степень соседа любого узла больше средней степени этого узла. В социальных сетях это означает, что у ваших друзей в среднем больше друзей, чем у вас. Это известно как парадокс дружбы . Можно показать, что сеть может иметь гигантскую компоненту , если ее средняя степень избытка больше единицы:
Имейте в виду, что последние два уравнения предназначены только для модели конфигурации , и для получения избыточного распределения степеней реальной сети мы также должны добавить во внимание корреляции степеней. [9]
Метод производящих функций
Производящие функции можно использовать для расчета различных свойств случайных сетей. Учитывая распределение степеней и избыточное распределение степеней некоторой сети и соответственно, можно записать два степенных ряда в следующих формах:
и
также можно получить из производных :
Если мы знаем производящую функцию распределения вероятностей, мы можем восстановить значения путем дифференцирования:
Некоторые свойства, например моменты, можно легко вычислить на основе их производных:
И вообще: [9]
Для распределенных по Пуассону случайных сетей, таких как ER-граф , , именно по этой причине теория случайных сетей этого типа особенно проста. Распределения вероятностей для 1-го и 2-го ближайших соседей генерируются функциями и . В более широком смысле распределение -th соседей генерируется следующим образом:
, с итерациями функции , действующей на саму себя. [10]
Среднее количество первых соседей , равно, а среднее количество вторых соседей равно:
Распределение степеней для направленных сетей
В направленной сети каждый узел имеет некоторую входную и некоторую выходную степень , которые представляют собой количество ссылок, которые соответственно входили в этот узел и выходили из него. Если это вероятность того, что случайно выбранный узел имеет входящую и исходящую степень, то производящую функцию, присвоенную этому совместному распределению вероятностей , можно записать с двумя значениями и как:
Поскольку каждое звено в направленной сети должно покинуть один узел и войти в другой, среднее число звеньев, входящих в узел, равно нулю. Поэтому,
,
из чего следует, что функция генерации должна удовлетворять:
где - средняя степень (как входа, так и выхода) узлов сети;
Используя функцию , мы снова можем найти порождающую функцию для распределения степени входа/выхода и распределения степени входа/выхода, как и раньше. могут быть определены как производящие функции для количества прибывающих ссылок в случайно выбранный узел и могут быть определены как количество прибывающих ссылок в узел, достигнутый при следовании по случайно выбранной ссылке. Мы также можем определить производящие функции и для числа, выходящего из такого узла: [10]
Здесь среднее количество 1-х соседей, или, как ранее было введено как , равно , а среднее количество 2-х соседей, достижимых из случайно выбранного узла, определяется как: . Это также номера 1-го и 2-го соседей, из которых можно попасть в случайный узел, поскольку эти уравнения явно симметричны по и . [10]
Распределение степеней для подписанных сетей
В подписанной сети каждый узел имеет положительную и отрицательную степень , которые представляют собой положительное количество ссылок и отрицательное количество ссылок, подключенных к этому узлу соответственно. Так и обозначают распределение отрицательной степени и распределение положительной степени подписанной сети. [11] [12]
^ Барабаши, Альберт-Ласло; Альберт, Река (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.
^ Альберт, Река; Барабаши, Альберт-Ласло (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 г.
^ Дороговцев, С. Н.; Мендес, 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.
^ Пачон, Анжелика; Сасердот, Лаура; Ян, Шуи (2018). «Безмасштабное поведение сетей при наличии преимущественных и единых правил присоединения». Физика D: Нелинейные явления . 371 : 1–12. arXiv : 1704.08597 . Бибкод : 2018PhyD..371....1P. doi :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 .
^ Фалькенберг, Макс; Ли, Чон Хек; Амано, Сюн-ичи; Огава, Кен-итиро; Яно, Кадзуо; Мияке, Ёсихиро; Эванс, Тим С.; Кристенсен, Ким (18 июня 2020 г.). «Определение временной зависимости роста сети». Обзор физических исследований . 2 (2): 023352. arXiv : 2001.09118 . doi : 10.1103/PhysRevResearch.2.023352 .
^ abcd Ньюман, Марк (18 октября 2018 г.). Сети. Том. 1. Издательство Оксфордского университета. дои : 10.1093/oso/9780198805090.001.0001. ISBN978-0-19-880509-0. Архивировано из оригинала 15 апреля 2020 г. Проверено 19 апреля 2020 г.
^ abc Ньюман, MEJ; Строгац, С.Х.; Уоттс, ди-джей (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 . 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.