Распределение степеней
В исследованиях графов и сетей: степенью узла сети называют число его связей с другими узлами. Распределение степеней (узлов, вершин) - это распределение вероятностей степеней во всей сети.
Определение
Степень узла в сети (иногда некорректно путают со связностью) - это число связей или рёбер между этим узлом и другими узлами. Если граф является ориентированным, т.е. рёбра имеют направления от одного узла к другому, то узлы имеют два значения степени: входящую степень как число входящих рёбер и исходящую степень как число исходящих рёбер.
Распределение степеней P(k) графа определяется как доля узлов, имеющих степень k. Таким образом, если есть в общей сложности n узлов в сети и из них nk имеют степень k, то P(k) = nk/n.
Ту же информацию иногда представляют в форме кумулятивного распределения степеней - это доля узлов со степенью меньше k - или в виде комплементарного кумулятивного распределения степеней - это доля узлов со степенью, большей или равной k (1 - C, если C - это кумулятивное распределение степеней; т.е. дополнение к C).
Наблюдаемые распределения степеней
Распределения степеней очень важны в исследованиях как реальных сетей, таких как Интернет и социальные сети, так и теоретических сетей. Простейшая модель сети, например, случайный граф (Бернулли), в котором каждый из n узлов соединяется (или не соединяется) с другими узлами с независимой вероятностью p (или 1 − p), имеет биномиальное распределение степеней k:
(или распределение Пуассона при росте n к пределу). Тем не менее, распределения степеней большинства сетей реального мира существенно отличаются от вышеуказанных. У многих из них распределение существенно скошено вправо, что означает, что значительное большинство узлов имеют малую степень, но небольшое число узлов, известных как "хабы", имеют высокую степень. В некоторых сетях, среди которых заслуживают особого упоминания Интернет, Всемирная паутина, а также некоторые социальные сети, обнаружены распределения степеней, приблизительно соответствующие степенному распределению: P(k) ~ k−γ, где γ - это константа. Такие сети называются безмасштабными и привлекают особое внимание из-за своих структурных и динамических свойств.[1][2][3][4]
См. также
- Теория графов
- Комплексные сети
- Безмасштабная сеть
- Случайный граф
- Структурный срез
Ссылки
- Barabási, A.-L. and R. Albert, Science 286, 509 (1999).
- R. Albert, and A.L. Barabási, Phys. Rev. Lett. 85, 5234(2000).
- S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhim, cond-mat/0011115.
- Pachon, Angelica; Sacerdote, Laura; Yang, Shuyi. Scale-free behavior of networks with the copresence of preferential and uniform attachment rules (англ.) // Physica D: Nonlinear Phenomena : journal. — 2018. — doi:10.1016/j.physd.2018.01.005. — . — arXiv:1704.08597.
- 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.