2. Отсекать голоса виртуалов и аккаунтов, созданных для одного раза, алгоритм топа умеет. Манипуляция ведется со стороны клаки юзеров, давно ведущих дневник и сделавших себе репутацию. Надо уметь локализовать подобные клаки, и аннулировать накрученные голоса. Это можно делать, анализируя конфигурацию графа, образованного юзерами и ссылками.
Граф этот не очень большой (тысяч двадцать вершин, тысяч двести ребер) и математические операции с ним много не потребуют.
Клака есть кластер в этом графе. Пусть у нас задано какое-то количество кластеров (к примеру: нашисты, ДПНИ, Ф18, антифа, КБ, крокодилы). Это группы авторитетных пользователей, усвоивших технику накрутки, и целеустремленно ею пользующихся для своих групповых нужд. Кластеров будет штук 10-20, я думаю. Как определять кластеры, я напишу чуть ниже.
Поскольку юзер может принадлежать сразу многим кластерам, либо принадлежать им частично, имеет смысл зафиксировать какое-то количество кластеров, и каждой паре (юзер, кластер) присвоить число ("кластерный коэффициент"), обозначающее степень принадлежности кластеру. Назовем этот набор чисел "кластерным профилем".
Каждому кластеру K выделим квоту a(K) - процент записей из данного кластера, "безнакруточно" попавших в топ. От балды, более-менее.
При появлении в топе новой записи, усреднением из кластерных профилей сославшихся юзеров составляется кластерный профиль записи. Если коэффициент, соответствующий кластеру K, больше, чем у (100-a(K))% записей, попавших в топ, запись считается спонсируемой этим кластером.
Обнаружив факт спонсируемости, у всех сославшихся на нее юзеров надо увеличивать число "принадлежность кластеру K" на какую-то небольшую величину. А голоса юзеров, которые в большой степени принадлежат кластеру K, не учитывать. Для радикальной борьбы с накрутками - учитывать эти голоса со знаком минус. Тогда лишняя ссылка от фашистов будет выталкивать фашицкую запись из топа. Тут требуется доводка по конкретным числам.
Для нахождения кластеров в графах есть специальная наука. Я на нее не ссылаюсь. Вот вместо этого простой алгоритм, который для топа Яндекса будет наверное адекватен.
Рассмотрим возрастающую функцию v(N) (брать можно любую, но для наших целей хорошо пойдет N^2 - потом можно посмотреть, с какой функцией оно лучше работает).
Длиной ребра от юзера к юзеру назовем 1/v(N), где N есть число записей, на которые эти два юзера сослались совместно. Это задает метрику на графе. Метрический граф, составленный из юзеров (вершин) и ребер (совместно сосланных записей) с метрикой (числом таких записей) есть источник всей работы кластер-анализатора, никаких других данных он не использует.
Я расскажу два метода нахождения кластеров: один из них чисто математический, но требует доводки, другой более априорный.
АЛГОРИТМ 1. Будем считать, что у кластера есть n_1 лидеров, n_2 участников, n_3 сочувствующих, а общее число лидеров равно n_0 (5, 20 и 50 и 100 для ситуации, сложившейся в топе).
Рассмотрим граф как метрическое пространство (с длиной ребра, заданной выше). Для каждой вершины x найдем число a(x), которое есть радиус минимального метрического шара, содержащего n_3 вершин графа. Это число, характеризующее интегрированность юзера в блогосферу и в топ Яндекса в частности (чем меньше, тем лучше он интегрирован).
Потенциальные лидеры клаки есть люди с минимальным a(x). Выберем n_0 из них. Пусть A есть максимальный a(x) для таких юзеров. Если у n_1 (или больше) человек шары с радиусом A в пересечении содержат n_2 вершин, это клака. Таким образом составляется список кластеров. Его придется доводить вручную, убивая дубликаты. Но задача обозримая, ибо речь идет о примерно 100 вершинах графа. Возможно, придется поиграть с коэффициентами n_i.
Фиксируем убывающую положительнозначную функцию V, стремяющуюся к \infty в нуле. V(x)=1/x например.
Кластерный коэффициент юзера положим равным V(z), где z есть сумма расстояний от юзера до всех лидеров кластера. Чем ближе пользователь к лидерам, тем больше его коэффициент.
АЛГОРИТМ 2. (Возможно, имеет смысл сначала запустить алгоритм 1, и посмотреть, с чем мы примерно имеем дело).
Список кластеров составляется от балды, человеком, хорошо знакомым с блогосферой. Каждому кластеру изначально присваивается, например, 5 лидеров. Тоже от балды - есть люди, которые в состоянии составить этот расклад вручную.
Теперь, изначальный кластерный коэффициент юзера будет V(z), где z есть сумма расстояний от юзера до всех лидеров клаки, а V определено выше.
Неидеально, но после автоматической доводки из пункта 3 должно работать.
* * *
6. Практическая ценность сего метода несомненна - Яндекс экономит на девочках, которые следят за топом и убивают неподходящие записи; со временем эту технологию можно лицензировать, ибо она нужна в совершенно разных ситуациях. Наконец, мы получим относительно приличный, нескучный и репрезентативный топ, не прибегая к цензурным механизмам.
Топ Яндекса есть модель прямой демократии в миниатюре, и в интересах всех демократически мыслящих товарищей, чтоб она хорошо работала.
