КабинетПоиск
Графы и сети

Graph Basics

Основы графов

актуальноТекущий рабочий стандарт

Направления: Прикладные направления · Графовый ML

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

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

  • Плотный удобно хранить , разреженный — списком смежности; выбор влияет на всё остальное.
  • Обходы в ширину и глубину дают компоненты связности, расстояния и циклы.
  • Двудольные описывают взаимодействия «пользователь — товар» и лежат в основе рекомендаций.

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

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

СтруктураПамятьБыстроМедленно
смежностипроверка ребраобход соседей разреженного
Список смежностиобход соседейпроверка конкретного ребра
Список рёберпотоковая обработкалюбые локальные запросы
CSRвекторизованные операцииизменение структуры
На практике

Реальные почти всегда разрежены: у миллиона вершин обычно десятки миллионов рёбер, а не . Поэтому смежности материализуют редко.

  • Степень вершины, число треугольников, коэффициент .
  • Размер компоненты связности и расстояние до известных «плохих» вершин.
  • и персонализированный PageRank относительно множества меток.
  • Агрегаты по соседям: средний возраст аккаунта соседей, доля заблокированных.
На практике

Эти считаются один раз и подаются в . На практике такой подход часто обыгрывает графовую — при несопоставимо меньшей сложности.

Тема также относится к главам:Алгоритмы и структуры данныхГрафы

Видеолекции

Записи университетских курсов, где эта тема звучит. Где у записи есть тайм-коды, ссылка открывает её с нужной секунды; где их не проставили — с начала.

21:38Анализ графа вычислений в Spark HistoryБольшие данные · Семинар «Spark Streaming завершение» · 40 мин7:11Обсуждение вариантов хранения графа подписокБольшие данные · Лекция «Проектирование таблиц в HBase» · 1 ч 25 мин1:08:40Построение графа обхода на основе признаковКомпьютерное зрение 3D · Лекция «Развитие многовидовых трансформеров» · 2 ч 18 минс началаОсновы теории графов. Алгоритмы обхода в глубину и в ширинуАлгоритмы и структуры данных · Лекция · 2 ч 40 минс началаГрафы. DFS, BFS, алгоритмы на основе обходовАлгоритмы и структуры данных · Лекция · 2 ч 48 минс началаПоиск пути в графеАлгоритмы и структуры данных · Лекция · 2 ч 42 мин

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

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

Centrality98%

Центральности · Графы и сети

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

PageRank98%

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

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

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%

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

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

Network Motifs85%

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

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

Clustering85%

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

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

Eigenvector85%

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

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

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

Спрашивают на собеседовании: Газпромбанк — Корпоративные риски, Лаборатория Касперского — Поведенческий анализ и исследования, СКБ Контур — Проверка контрагентов.

Добавить в учебную программу
Следующий шагДальше по связи: CentralityМеры важности вершины: по числу связей, по посредничеству, по близости и по влиянию соседей.Перейти →
Centrality →

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