WikiSort.ru - Не сортированное

Наука о сетях

Теория

Граф Комплексные сети Распространение Мир тесен Безмасштабная сеть Сообщества Перколяция Эволюция Управляемость Визуализация Социальный капитал Анализ связей Оптимизация Взаимность Триадное закрытие Гомофилия Транзитивность Предпочтительное присоединение Теория когнитивного баланса Сетевой эффект Влияние

Типы сетей

Вычислительная Коммуникационная Транспортная Социальная Научное сотрудничество Биологическая Искусственная нейронная Взаимосвязанная Семантическая Пространственная Граф зависимостей Граф потоков На чипе

Графы

Термины Клика Компонента связности Разрез Цикл Структура данных Ребро Петля Окрестность Путь Вершина Список / матрица смежности Список, матрица инцидентности Типы Двудольный Полный Ориентированный Гипер Мульти Случайный Взвешенный

Метрики Алгоритмы

Центральность Степень Посредничество Близость PageRank Мотив Кластеризация Распределение степеней Ассортативность Расстояние Модульность Эффективность

Модели

Топология Случайный граф Эрдёша-Реньи Барабаши — Альберт Фитнес Уоттса-Строгатца ERGM Случайный геометрический Гиперболический Иерархический Стохастический блок Максимум энтропии Гибкая конфигурация LFR Динамика Булева сеть Агентное моделирование Эпидемическая/SIR

Списки Категории

Темы ПО Учёные Теория сетей Теория графов

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

Определение

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

Распределение степеней 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]

См. также

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

Ссылки

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