PageRank

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

P R = α M P R + \frac{1 - α}{N} 1

Что означает каждый компонент

$α M P R$ случайное блуждание по ссылкам: важность перетекает от вершины к её соседям
$\frac{1 - α}{N}$ телепортация: с вероятностью 1−α прыгаем в случайную вершину. Спасает от тупиков и делает решение единственным

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

Коэффициент затухания (обычно 0.85) задаёт вероятность продолжить блуждание, а не прыгнуть случайно.
Вычисляется степенным методом: только умножения разреженной матрицы на вектор.
Персонализированный PageRank даёт близость к конкретной вершине — рабочий признак в антифроде.

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

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

Алгоритм и вычисление

Степенной метод на разреженной матрице.

P R_{k + 1} = α M P R_{k} + \frac{1 - α}{N} 1

Обозначения

$α$ коэффициент, задающий вес слагаемого или скорость обновления
$n$ число объектов в выборке
$k$ степень вершины — число её связей

Сходится за 30–50 итераций при $α = 0.85$ — этого хватает для практики.
Каждая итерация — одно умножение разреженной матрицы на вектор, легко распараллеливается.
Вершины без исходящих рёбер («висячие») требуют отдельной обработки, иначе масса вероятности утекает.

Персонализированный PageRank

Близость к заданному множеству вершин.

Вместо равномерной телепортации возвращаемся в фиксированное множество вершин — например, в подтверждённые мошеннические аккаунты. Результат читается как «насколько эта вершина близка к известному злу».

На практике

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

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

Машинное обучение на графах

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

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

Алгоритм и вычисление

Персонализированный PageRank

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

Graph Basics85%

Centrality85%

Community Detection85%

Graph Embeddings85%

Graph Neural Networks85%

Message Passing85%

Link Prediction85%

Knowledge Graphs85%

Network Motifs85%

Clustering85%

Eigenvector85%