Введение

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

Определение

Степень узла в сети (иногда ошибочно называемая связностью) — это количество соединений или рёбер, которые узел имеет с другими узлами. Если сеть ориентированная, то есть рёбра указывают направление от одного узла к другому, то у узлов существуют две различные степени: входящая степень, представляющая собой количество входящих рёбер, и исходящая степень, представляющая собой количество исходящих рёбер. Распределение степеней P(k) сети определяется как доля узлов в сети со степенью k. Таким образом, если в сети всего n узлов, и nk из них имеют степень k, то… Та же информация иногда представляется в виде кумулятивного распределения степеней — доля узлов со степенью, меньшей k, или даже дополнительного кумулятивного распределения степеней — доля узлов со степенью, большей или равной k (1 – C), если рассматривать C как кумулятивное распределение степеней, то есть как дополнение к C.

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

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

(или распределение Пуассона в пределе больших n, если средняя степень поддерживается постоянной). Однако большинство сетей в реальном мире имеют распределения степеней, сильно отличающиеся от этого. Большинство из них сильно скошены вправо, что означает, что подавляющее большинство узлов имеют низкую степень, но небольшое число, известных как "хабы", имеют высокую степень. Для некоторых сетей, в частности Интернета, Всемирной паутины и некоторых социальных сетей, было показано, что распределения степеней приблизительно следуют степенному закону: , где γ — константа. Такие сети называются масштабно-инвариантными и привлекают особое внимание благодаря своим структурным и динамическим свойствам. Однако обзор широкого спектра реальных сетей показывает, что масштабно-инвариантные сети встречаются относительно редко при использовании статистически строгих методов оценки. Некоторые исследователи оспаривают эти выводы, утверждая, что определения, использованные в исследовании, были излишне строгими, в то время как другие считают, что точная функциональная форма распределения степеней менее важна, чем знание о том, имеет ли распределение степеней "тяжелые хвосты" или нет. Также критикуется излишняя интерпретация конкретных форм распределения степеней за то, что не учитывается эволюция сетей во времени.