Теория графов — раздел математики, изучающий графы: множества вершин (узлов), соединённых рёбрами. Инструмент для моделирования связей между объектами. Возникла в 1735, взорвалась с появлением компьютеров и социальных сетей.
Определения
- Граф G = (V, E): V — вершины, E — рёбра
- Ориентированный граф: рёбра имеют направление
- Взвешенный граф: рёбра имеют веса
- Простой граф: без кратных рёбер и петель
- Мультиграф: допускает кратные
- Полный граф: все вершины соединены
Классические задачи
- Кёнигсбергские мосты (Эйлер, 1735): пройти по всем мостам ровно раз. Невозможно, если больше 2 вершин нечётной степени
- Коммивояжёр (TSP): обойти все города, вернуться, минимум расстояние. NP-трудная задача
- Кратчайший путь (Дейкстра, 1956): с одной вершины ко всем другим
- Минимальное остовное дерево (Краскал, Прим)
- Задача о максимальном потоке (Форд-Фалкерсон)
- Раскраска графа (хроматическое число)
Алгоритмы
- Поиск в глубину (DFS): рекурсивно
- Поиск в ширину (BFS): слоями
- Дейкстра: кратчайший путь с неотрицательными весами
- Беллман-Форд: может с отрицательными (но не циклами)
- Флойд-Уоршалл: кратчайшие между всеми парами
- A* (A-star): эвристический поиск пути
Сложность
- BFS/DFS: O(V + E)
- Дейкстра: O(E + V log V) с кучей
- Коммивояжёр: NP-трудная, для точного решения — O(n!)
- Приближения для практики существуют
Малый мир
- Милгрэм, 1967: эксперимент с письмами. Любые два американца связаны через ~6 человек
- Шесть рукопожатий (six degrees of separation)
- Facebook, 2016: в среднем 3,57 шага между любыми двумя пользователями
- Уоттс и Строгатц (1998): модель малого мира
Безмасштабные сети
- Степень вершины = число рёбер к ней
- Во многих реальных сетях распределение степеней — степенной закон
- Небольшое число "хабов" с тысячами связей
- Большинство — с единицами
- Барабаши, 1999
Примеры безмасштабных сетей
- Интернет (WWW): Google, Facebook — хабы
- Социальные сети
- Белково-белковые взаимодействия
- Цитирование научных статей
- Транспортные сети (хабовые аэропорты)
PageRank
- Алгоритм Google для ранжирования страниц
- Вершина важна, если на неё ссылаются важные вершины
- Собственный вектор матрицы переходов
- Дало Google преимущество в начале 2000-х
Применения
- Соцсети: рекомендации друзей, feed-алгоритмы
- Интернет: роутинг, DNS
- Карты и навигация: кратчайшие пути
- Биология: белковые сети, нейронные сети, эволюционные деревья
- Химия: молекулы как графы
- Электросети: моделирование
- Расписания: раскраска графа = распределение
- Компьютерные науки: компиляторы (зависимости), базы данных (joins)
Типы сетей
- Случайные (Эрдёш-Реньи): каждая пара соединена с вероятностью p
- Регулярные (решётки)
- Малый мир
- Безмасштабные
- Иерархические
Кластеризация
- Коэффициент кластеризации: сколько соседей вершины соединены друг с другом
- В соцсетях высокий — друзья друзей обычно тоже друзья
- Community detection: поиск плотных подграфов
- Louvain, Girvan-Newman алгоритмы
Динамика на сетях
- Эпидемии: SIR, SIS модели на графе
- Распространение информации
- Социальное влияние
- Каскадные сбои (перегрузка одного узла — падение соседей)
Инструменты
- NetworkX (Python)
- igraph (R, Python)
- Gephi (визуализация)
- Neo4j (графовая БД)
- Cytoscape (биология)
Гугл, Facebook, LinkedIn
Все крупные соцсети — на графовой логике. Graph-databases, graph-algorithms — основа их бизнеса. Рекомендации "людей, которых вы, возможно, знаете" — классическая графовая задача.
Обсуждение (0)
Войдите, чтобы задать вопрос
Загрузка комментариев…