Наука о сетях
Граф Комплексные сети Мир тесен Безмасштабная сеть Перколяция Визуализация Социальный капитал Анализ связей Оптимизация Гомофилия Транзитивность Теория когнитивного баланса Сетевой эффект Социальное влияние
Типы сетей
Вычислительная Коммуникационная Социальная Биологическая Нейронная Семантическая Граф потоков
Графы
Термины Клика Компонента связности Разрез Цикл Структура данных Ребро Петля Окрестность Путь Вершина Список / матрица смежности Список, матрица инцидентности Типы Двудольный Полный Ориентированный Гипер Мульти Случайный Взвешенный
Центральность Степень Посредничество Близость PageRank Ассортативность Расстояние
Модели
Топология Случайный граф Эрдёша-Реньи Барабаши — Альберт Динамика Агентное моделирование /
Списки Категории
Теория сетей Теория графов

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

Определение

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

Распределение степеней 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 ^{− γ} , где γ - это константа. Такие сети называются безмасштабными и привлекают особое внимание из-за своих структурных и динамических свойств.

См. также

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

Ссылки

• Albert, R.; Barabasi, A.-L. Statistical mechanics of complex networks (англ.) // Reviews of Modern Physics : journal. — 2002. — Vol. 74 . — P. 47—97 . — doi : . — Bibcode : . — arXiv : .
• Dorogovtsev, S.; Mendes, J. F. F. Evolution of networks (англ.) // (англ.) ( : journal. — 2002. — Vol. 51 , no. 4 . — P. 1079—1187 . — doi : . — Bibcode : . — arXiv : .
• Newman, M. E. J. (неопр.) // SIAM Review. — 2003. — Т. 45 , № 2 . — С. 167—256 . — doi : . — Bibcode : . — arXiv : . (недоступная ссылка)
• Shlomo Havlin ; Reuven Cohen. (англ.) . — Cambridge University Press , 2010.