Как Google выявляет ссылочный спам (Link Farms и Web Rings), анализируя чувствительность PageRank к изменениям в структуре ссылок

Термины и определения

Clique Attack / Web Ring (Кликовая атака / Веб-кольцо)

Тип ссылочного спама. Набор узлов, которые преимущественно ссылаются друг на друга, чтобы создать ложное впечатление авторитетности и взаимно повысить свой ранг, удерживая его внутри группы.

Coupling Factor (c) (Коэффициент связности)

Параметр (от 0 до 1), определяющий, насколько сильно ранг узла зависит от структуры ссылок. При c=1 ранг полностью зависит от ссылок; при c=0 все узлы имеют равный ранг (только случайные переходы). Аналог Damping Factor в классическом PageRank.

Derivative Value (Значение производной)

Производная функции важности узла по отношению к coupling factor (x'(c)). Показывает скорость изменения ранга узла при изменении веса ссылок в алгоритме.

Inflation Detector (Детектор инфляции)

Компонент системы, который анализирует структуру ссылок и PageRanks для выявления узлов с искусственно завышенным рангом.

Link Farm (Ссылочная ферма)

Тип ссылочного спама. Структура, где большое количество узлов (обычно с низким рангом) ссылаются на один центральный узел, чтобы искусственно повысить его ранг.

Node Importance Function (Функция важности узла)

Функция, вычисляющая важность или ранг узлов на основе структуры ссылок (например, PageRank). Обозначается как x(c).

Normalized Derivative Value / Spam Likelihood Value (S)

Нормализованное значение производной (часто x'(c)/x(c)). Используется как количественная мера вероятности того, что ранг узла искусственно завышен из-за ссылочного спама.

Transition Probability Matrix (A(c))

Матрица NxN, представляющая структуру вероятностей переходов в направленном графе. Зависит от coupling factor c.

Ключевые утверждения (Анализ Claims)

Claim 1 (Независимый пункт): Описывает общий метод идентификации узлов, являющихся бенефициарами ссылок, завышающих важность узла.

1. Вычисление для подмножества узлов величины, соответствующей производной функции важности узла (derivative of a node importance function).
2. Сравнение этой вычисленной величины с пороговым значением (threshold).
3. Идентификация узлов, для которых сравнение дает предопределенный результат (например, превышение порога).

Claim 3 (Зависимый от 1): Уточняет, что производная функции важности вычисляется по отношению к коэффициенту связности (coupling factor).

Claim 36 (Зависимый от 1): Детализирует процесс вычисления с использованием матричной алгебры (Метод 1).

1. Расчет матрицы A(c), представляющей направленный граф и зависящей от коэффициента связности c.
2. Расчет главного собственного вектора A(c), обозначенного x(c) (это вектор рангов, например, PageRank).
3. Расчет производной x(c) по c, обозначенной x'(c).
4. Расчет значения вероятности инфляции (inflation likelihood value S) на основе x'(c) и ранга узла.

Claim 39 (Зависимый от 37): Определяет точную формулу для вычисления производной x'(c): $x'(c) = (I-cP^T)^{-1}(P-E)^T x(c)$.

Claim 48 (Независимый пункт): Описывает альтернативный метод идентификации ссылочного спама (Метод 2, аппроксимация производной).

1. Расчет матрицы A(c).
2. Расчет главного собственного вектора для двух различных значений коэффициента c (a и b): x(a) и x(b). (Т.е. расчет PageRank дважды с разными coupling factors).
3. Расчет значения вероятности спама (spam likelihood value S) для узла на основе компонентов x(a) и x(b), соответствующих этому узлу.

Где и как применяется

Изобретение применяется в бэкенд-системе поисковой машины (Search Engine Back End System) на этапах, связанных с анализом ссылок и расчетом рангов.

INDEXING – Индексирование и извлечение признаков
Основное применение патента происходит на этом этапе или в связанных с ним офлайн-процессах анализа данных. Система использует Link Map(s) (карты ссылок) для расчета PageRanks. Затем Inflation Detector (Детектор инфляции) анализирует Link Map(s) и рассчитанные PageRanks для вычисления производных и определения Spam Likelihood Values.

RANKING – Ранжирование
Результаты работы Inflation Detector используются на этапе ранжирования. Если узел идентифицирован как бенефициар ссылочного спама, система может предпринять контрмеры: скорректировать (понизить) его важность (adjusted importance) или удалить узел из графа/индекса.

Входные данные:

• Link Map(s): Структура направленного графа (кто на кого ссылается).
• PageRanks (x(c)): Рассчитанные значения важности узлов (если используется Метод 1).

Выходные данные:

• Spam Likelihood Values (S) для узлов.
• Скорректированные значения важности или флаги спама для идентифицированных узлов.

На что влияет

• Конкретные типы сайтов: Наибольшее влияние оказывается на сайты, использующие искусственные схемы линкбилдинга: ссылочные фермы, PBN (Private Blog Networks), которые функционируют как веб-кольца, и другие сети сайтов, созданные для манипуляции ранжированием.
• Конкретные ниши или тематики: Наибольшее влияние оказывается на конкурентные и коммерческие ниши, где техники ссылочного спама применяются наиболее активно.

Когда применяется

• При каких условиях работает алгоритм: Алгоритм применяется в процессе расчета или обновления глобальных метрик важности узлов (PageRank).
• Триггеры активации и пороговые значения: Узел идентифицируется как спам, если его Normalized Derivative Value превышает определенный порог (threshold) по модулю, или если он попадает в предопределенный процент узлов с самыми экстремальными (высокими положительными или низкими отрицательными) значениями.
• Частота применения: Расчеты производятся периодически в офлайн-режиме по мере обновления ссылочного графа.

Пошаговый алгоритм

Патент описывает два основных метода реализации.

Метод 1: Прямой расчет производной

1. Подготовка данных: Создание направленного графа. Формирование матрицы вероятностей переходов $A(c) = [cP + (1-c)E]^T$.
2. Вычисление важности: Расчет функции важности узлов (PageRank, x(c)) для заданного значения coupling factor c.
3. Вычисление производной: Расчет производной функции важности x'(c) по формуле из Claim 39. Поскольку матрица большая и разреженная, используются итеративные методы, такие как Jacobi relaxation или Gauss-Seidel.
4. Нормализация: Вычисление Normalized Derivative Value (Spam Likelihood Value S). Часто путем деления производной на ранг узла (x'(c)/x(c)).
5. Идентификация спама: Сравнение S с пороговыми значениями.
   • Если S сильно положительное (выше порога) — вероятно Web Ring.
   • Если S сильно отрицательное (ниже порога) — вероятно Link Farm.
6. Применение действий: Выполнение действий над идентифицированными узлами (например, понижение ранга, удаление узла).

Метод 2: Аппроксимация производной (Averaging)

Этот метод используется, если прямой расчет производной слишком ресурсоемок.

1. Вычисление важности для разных C: Расчет PageRank для двух разных значений coupling factor: x(a) и x(b).
2. Расчет Spam Likelihood Value: Вычисление среднего нормализованного значения производной в интервале [a, b] по формуле: