Стационарное распределение случайного блуждания по графу с телепортацией. Классический алгоритм ранжирования, который до сих пор используется как .
- случайное блуждание по ссылкам: важность перетекает от вершины к её соседям
- телепортация: с вероятностью 1−α прыгаем в случайную вершину. Спасает от тупиков и делает решение единственным
Ключевые тезисы
- Коэффициент затухания (обычно 0.85) задаёт вероятность продолжить блуждание, а не прыгнуть случайно.
- Вычисляется степенным методом: только умножения разреженной на .
- Персонализированный даёт близость к конкретной вершине — рабочий в антифроде.
Подробный разбор
- коэффициент, задающий вес слагаемого или скорость обновления
- число объектов в выборке
- степень вершины — число её связей
- Сходится за 30–50 итераций при — этого хватает для практики.
- Каждая итерация — одно умножение разреженной на , легко распараллеливается.
- Вершины без исходящих рёбер («висячие») требуют отдельной обработки, иначе масса вероятности утекает.
Вместо равномерной телепортации возвращаемся в фиксированное множество вершин — например, в подтверждённые мошеннические аккаунты. Результат читается как «насколько эта вершина близка к известному злу».
Это один из самых сильных графовых в антифроде и рекомендациях: считается быстро, интерпретируется просто, устойчив к шуму.
Связанные темы
Алгоритмы на графах · Машинное обучение на графах
Graph Basics98%
Основы графов · Графы и сетиВершины, рёбра, веса и направления. Матрица смежности и список рёбер — два способа хранить одно и то же.
Centrality98%
Центральности · Графы и сетиМеры важности вершины: по числу связей, по посредничеству, по близости и по влиянию соседей.
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%
Собственный вектор · Математический справочникНаправление, сохраняющееся при линейном преобразовании с точностью до масштаба.
Глава «Графы и сети» последний раз правилась . Нашли ошибку — напишите.