[VK.com] Друзья

«Скажи мне, кто твой друг, и я скажу тебе, кто ты» (Еврипид) 

Найдя на Вконтактике человека и просмотрев открытые данные о нем, мы иногда открываем список его друзей (спасибо П. Дурову за открытие почти всех друзей год назад). Скорее всего, увидев там человек 200 (или больше), мы его закрываем :). Ну да — вручную пытаться там найти какие-то связи очень непросто.  Попробуем это сделать, немного автоматизировав процесс.

Задача: в списке друзей человека найти все группы людей, где все друг друга знают (каждый у каждого есть в друзьях).

Условия: обойтись без бана, каптчи и прочих антибот-действий со стороны Вк. Решить задачу за адекватное время (никаких «запустил, оставил на ночь, с утра посмотрел результат»).

Решение:

Человек, для которого решается задача, — cID.

Первое что приходит на ум — это загрузка страницы http://vk.com/friends.php?id=cID. В ее коде скрывается JSON с данными о друзьях cID. Но тут загвоздка. Данные тут только о первых 200 друзьях. Если у cID их больше, то понадобятся дополнительные запросы. Это неприемлемо. Однако, уж очень удобный этот JSON — и id, и ссылка на страницу, и фамилия/имя человека, и даже ссылка на аватарку (которая 50х50) есть. К счастью, есть еще один url, по запросу которого выдается похожий JSON с такими же данными и по всем(!) друзьям человека — http://vk.com/al_friends.php?act=load_friends_silent&al=1&gid=0&id=cID.

Распарсив этот JSON, получаем список друзей cID. Сохраняем его. Надо отметить, что любой человек может скрыть до 30 друзей. В дальнейшем к этому еще вернемся.

Данные о друзьях будут храниться в виде матрицы (M). Так же отдельно создаем массив (V) для всех людей, которые загружаются (cID, его друзья, друзья его друзей). В V хранится id, ФИО, аватарка. По сути, V — это наш эквивалент таблицы users на Вк (если, конечно, у них такая есть). Для каждого из списка друзей cID загружаем его список друзей и записываем соответствующие данные в V и M.

По завершению этого, мы должны получить M, которая симметрична относительно главной диагонали (ведь, если человек А есть в друзьях у Б, то и Б есть у А). Но это не всегда будет так. Человек А может скрыть у себя в списке друзей человека Б, а вот Б может не скрыть у себя А. Что бы избежать такого, проходим по M и делаем ее симметричной.

Так же для удобства вычислений каждого добавляем к себе «в друзья». Теперь матрица M полностью готова.

Переходим к формированию групп, где все друг друга знают. Делается это через два цикла (один вложенный). Каждый шаг внешнего цикла берет список друзей cID и список друзей одного из друзей cID. Находится их (списков) пересечение (P). Если в  P больше двух людей (то есть у cID и его друга есть какие-то общие друзья), то запускается внутренний цикл. В нем берется каждый человек (N) из P и его список друзей (Pn). Рассматривается P  и пересечение P и Pn. Если они не равны, то N «выбрасывается» из P. Если в P осталось больше двух человек, то внутренний цикл продолжается.

По завершению внешнего цикла получится список групп, где все друг друга знают. Однако в этом списке могут быть одинаковые группы и подгруппы (например, есть группа ABC и ABCD — ABC надо убрать). Убираем их и получаем чистый список групп.

Программная реализация:

Небольшой (но местами прожорливый до ресурсов) PHP-скрипт. Авторизация на Вк взята из http://uasc.org.ua/2012/04/клас-авторизації-та-взаємодії-з-vk-authvk/. Скачать скрипт — ссылка (тут класс от UASC немного переработан). Запускать — test.php?cid=######. С короткими ссылками на страницы не работает. Только ID страницы!

Бывает, что скрипт подвисает (очень долго не выдает результатов работы). В таких случаях лучше просто перезапустить его.

Результаты:

Несколько примеров — ссылка1, ссылка2.

Количество запросов к Вк — авторизация (2) + список друзей cID (1) + кол-во друзей cID (N).

Бан, каптча за запросы на al_friends.php не дается.

Чем меньше друзей — тем меньше время обработки.

P.S. Узнать людей стало еще немного проще.

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

UPD 20.07.2012. Обновил метод авторизации. Ссылка на скрипт — скачать.

, , ,

1 комментарий
  1. ULTRA сказал(а):

    Что-то в этом есть)

Оставить комментарий

Top ↑ | Main page | Back