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

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

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

Определение

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

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

См. также

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

Ссылки

• Albert, R.; Barabasi, A.-L. Statistical mechanics of complex networks (англ.) // Reviews of Modern Physics : journal. — 2002. — Vol. 74. — P. 47—97. — doi:10.1103/RevModPhys.74.47. — . — arXiv:cond-mat/0106096.
• Dorogovtsev, S.; Mendes, J. F. F. Evolution of networks (англ.) // Advances in Physics : journal. — 2002. — Vol. 51, no. 4. — P. 1079—1187. — doi:10.1080/00018730110112519. — . — arXiv:cond-mat/0106144.
• Newman, M. E. J. The structure and function of complex networks (неопр.) // SIAM Review. — 2003. — Т. 45, № 2. — С. 167—256. — doi:10.1137/S003614450342480. — . — arXiv:cond-mat/0303516. (недоступная ссылка)
• Shlomo Havlin; Reuven Cohen. Complex Networks: Structure, Robustness and Function (англ.). — Cambridge University Press, 2010.