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

В исследованиях графов и сетей: степенью узла сети называют число его связей с другими узлами. Распределение степеней (узлов, вершин) - это распределение вероятностей степеней во всей сети.

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

Определение

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

Распределение степеней P(k) графа определяется как доля узлов, имеющих степень k. Таким образом, если есть в общей сложности n узлов в сети и из них n_k имеют степень k, то P(k) = 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). Тем не менее, распределения степеней большинства сетей реального мира существенно отличаются от вышеуказанных. У многих из них распределение существенно скошено вправо, что означает, что значительное большинство узлов имеют малую степень, но небольшое число узлов, известных как "хабы", имеют высокую степень. В некоторых сетях, среди которых заслуживают особого упоминания Интернет, Всемирная паутина, а также некоторые социальные сети, обнаружены распределения степеней, приблизительно соответствующие степенному распределению: P(k) ~ k^−γ, где γ - это константа. Такие сети называются безмасштабными и привлекают особое внимание из-за своих структурных и динамических свойств.^[1][2][3][4]

См. также

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