Меню
Главная
Случайная статья
Настройки
|
В исследованиях графов и сетей: степенью узла сети называют число его связей с другими узлами. Распределение степеней (узлов, вершин) - это распределение вероятностей степеней во всей сети.
Содержание
Определение
Степень узла в сети (иногда некорректно путают со связностью) - это число связей или рёбер между этим узлом и другими узлами. Если граф является ориентированным, т.е. рёбра имеют направления от одного узла к другому, то узлы имеют два значения степени: входящую степень как число входящих рёбер и исходящую степень как число исходящих рёбер.
Распределение степеней 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]
См. также
Ссылки
- Barabsi, A.-L. and R. Albert, Science 286, 509 (1999).
- R. Albert, and A.L. Barabsi, 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.
|
|