Centrality

Меры важности вершины: по числу связей, по посредничеству, по близости и по влиянию соседей.

Ключевые тезисы

Degree centrality — просто число связей; быстро считается и часто уже информативна.
Betweenness находит «мосты», через которые проходит трафик; дорого считается на больших .
Eigenvector centrality учитывает важность соседей — идея, из которой вырос .

Подробный разбор

2 подтемы — объяснения, формулы, примеры и интерактивные графики.

Мера	Отвечает на вопрос	Стоимость
Degree	у кого больше всего связей	$O (m)$
Closeness	кто ближе ко всем остальным	$O (nm)$
Betweenness	через кого проходят пути	$O (nm)$
Eigenvector /	у кого важные соседи	итерации по $O (m)$

В антифроде обычно работают degree и ; betweenness ценна для анализа инфраструктуры и логистики, но её редко считают на больших целиком — используют сэмплирование.

Высокая степень часто означает лишь техническую вершину: колл-центр, платёжный шлюз, общий IP.
Значения имеют тяжёлый хвост — перед подачей в линейную модель логарифмируйте.
Центральность зависит от : неполные данные систематически искажают картину.

вершин60

рёбер117

средняя степень3.9

максимальная степень19

хаб / среднее4.9×

Модель роста

Число вершин60Связей у новой вершины2

Хабы выделены цветом: в безмасштабной сети несколько вершин собирают непропорционально много связей

Связанные темы

Алгоритмы на графах · Машинное обучение на графах · Структура реальных сетей

Graph Basics98%

Основы графов · Графы и сети

Вершины, рёбра, веса и направления. Матрица смежности и список рёбер — два способа хранить одно и то же.

PageRank98%

PageRank · Графы и сети

Стационарное распределение случайного блуждания по графу с телепортацией. Классический алгоритм ранжирования, который до сих пор используется как признак.

Network Motifs97%

Мотивы и триады · Графы и сети

Маленькие повторяющиеся подграфы, встречающиеся чаще, чем в случайной сети. Хорошие признаки для классификации вершин.

Graph Traversal85%

Обходы графа: семейство · Алгоритмы и структуры данных

Зонтичная тема: что общего у обоих обходов, как увидеть граф в задаче, где он не назван, и по каким двум вопросам выбирается обход. Сами обходы разобраны отдельно.

Breadth-First Search85%

Поиск в ширину · Алгоритмы и структуры данных

Обход слоями: сначала всё, до чего один шаг, потом — два. Первое посещение вершины оказывается кратчайшим путём, если все переходы равноценны.

Depth-First Search85%

Поиск в глубину · Алгоритмы и структуры данных

Идти вглубь до упора и возвращаться. Порядок завершения вершин даёт топологическую сортировку, три цвета — обнаружение циклов, откат состояния — перебор с возвратом.

Shortest Paths85%

Кратчайшие пути · Алгоритмы и структуры данных

Дейкстра для неотрицательных весов, Беллман — Форд для отрицательных, A* — когда есть оценка расстояния до цели.

Community Detection85%

Поиск сообществ · Графы и сети

Разбиение графа на плотно связанные группы: клиенты одного круга, связанные аккаунты, тематические кластеры документов.

Graph Embeddings85%

Графовые эмбеддинги · Графы и сети

Векторные представления вершин, в которых близость отражает связанность в графе.

Graph Neural Networks85%

Графовые нейросети · Графы и сети

Нейросети, работающие прямо на структуре графа: представление вершины обновляется по представлениям соседей.

Message Passing85%

Передача сообщений · Графы и сети

Единая схема, к которой сводятся почти все архитектуры GNN: собрать сообщения от соседей, агрегировать, обновить состояние.

Link Prediction85%

Предсказание связей · Графы и сети

Задача «появится ли ребро между вершинами»: рекомендации друзей и товаров, достройка графов знаний.

Knowledge Graphs85%

Графы знаний · Графы и сети

Факты в виде троек «субъект — предикат — объект». Структурированная память, которую всё чаще подключают к языковым моделям.

Clustering85%

Кластеризация · Обучение без учителя

Разбиение объектов на группы похожих без заранее известных меток.

Eigenvector85%

Собственный вектор · Математический справочник

Направление, сохраняющееся при линейном преобразовании с точностью до масштаба.

Scale-free Networks80%

Безмасштабные сети · Графы и сети

Сети, в которых распределение степеней вершин подчиняется степенному закону: немного «хабов» и очень много слабо связанных вершин.

Small World80%

Феномен малого мира · Графы и сети

Короткие пути между любыми двумя вершинами при высокой локальной кластеризации.

Power Law80%

Степенное распределение · Теория вероятностей и распределения

Плотность убывает как степень: редкие события встречаются намного чаще, чем предсказывает нормальный закон. Распределения Парето и Ципфа — его классические формы.

Complex Systems80%

Сложные системы · Динамические системы и фракталы

Системы из множества взаимодействующих элементов, где коллективное поведение не сводится к сумме частей.

Кому эта тема нужна

Спрашивают на собеседовании: СКБ Контур — Проверка контрагентов.

Добавить в учебную программу

Следующий шагДальше по связи: Graph BasicsВершины, рёбра, веса и направления. Матрица смежности и список рёбер — два способа хранить одно и то же.Перейти →

Глава «Графы и сети» последний раз правилась 26 августа 2026 г.. Нашли ошибку — напишите.