Математика и секс
Октябрь 30th, 2013

VKAnalyzer

Подумал, что хорошо бы повыкладывать в открытый доступ ряд утилит, написанных мной под себя. Таких проектов довольно много, но я никогда не доводил проекты до конца: обычно они возникали для решения сиюминутной задачи, задача решалась, а проект забрасывался. По этой причине у меня накопилась определенная база говнокода, которая совершенна не пригодна для среднего пользователя, но тем не менее вероятно могущая для кого-то представлять интерес.

Сейчас вот залил на GitHub первый образчик: VKAnalyzer на Python3.

Писал я эту программу, когда мне требовалось прижать одного мудака, и я искал до него аккуратные подходы. Программа делает три вещи:

1. Выводит список общих друзей для любой пары пользователей ВКонтатке.

2. Позволяет оценить реальный круг общения пользователя.

3. Отслеживает удалённых и добавленных друзей.

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

Вторая функция анализирует списки друзей всех друзей пользователя, и сортирует их по количеству общих друзей. Например, если пользователь A дружит с пользователями B и C, при этом пользователь B дружит c A и Е, а общих друзей между A и С нет, то логично предположить, что A и B вероятно связывает что-то большее, нежели чем просто случайное знакомство. Программа выведет тогда B как более приоритетного друга, чем C.

Тут есть много оговорок. Например, если у пользователя B всего три друга, и все они общие с A, то это довольно значительный друг. Если у пользователя C при этом 15 общих друзей с A, но при этом у него всего 50000 друзей, то вероятно на самом деле они не такие уж и друзья.

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

Конкретный алгоритм можно выбирать.

Программа ведет внутренний кеш данных пользователей. Если вы проведете анализ сегодня, а затем еще через месяц, то результаты будут такими же, так как программа запомнит все данные. Чтобы обновить информацию на человека, надо ввести соответствующую команду update(), в этом случае будет выведен список изменений в друзьях.

Вот, например, найдём общих друзей между небезызвестным Энтео (Православный фанатик Дмитрий Цорионов), и картавым нацистом Дёмушкиным (можно кликнуть и увеличить, в скобках выводится количество друзей у персоны всего):

spy

Операция вывода круга общения занимает гораздо больше времени. Скажем, у Энтео более восьми тысяч друзей, это значит, что надо запросить информацию о восьми тысячах пользователей у vk.com. Это долго, плюс регулярно будут происходить ошибки связи и простые тормоза. Утилита умеет кешировать уже полученные данные, так что если с первого раза анализ не проходит из-за ошибок связи, то он может пройти со второго или третьего раза. Это может занимать довольно много времени, но если очень надо, то время найдётся. Для того же Энтео программа может работать до часу (включая перезапуски в случае проблем связи).

Круг общения Энтео получается таким:

spy2

В скобках — количество друзей всего и общее количество друзей. Но в общем-то как я уже говорил, программу я писал под себя, под конкретную цель, поэтому во многих местах она неюзабельна, интерфейс не продуман, архитектура нерасширяема, алгоритмы не самые быстрые, оптимизацию не проводил и прочее и прочее.

Энтео тут в общем-то фигурирует лишь для примера — на ком-то надо ставить эксперимент, поэтому, как это принято в науках, я выбрал первое попавшееся животное. Не на людях же ставить опыты.

Если кому-то интересно — заливайте свои обновления, расширяйте и прочее. Здесь простор для фантазии весьма большой. Например, я писал алгоритм, который разбивал всех друзей на кластеры — в один кластер при этом попадали друзья по интересам (опять же подобием метрики выступало общее количество друзей). Этот алгоритм позволял разбить друзей, например, на группы сокурсников, коллег, клубных друзей и группу мутных и очень интересных типов.

Он не входит в эту утилиту, так как написан был изначально отдельным скриптом, работающим с тем же файлом кеша. Возможно, если руки доберутся, я добавлю кластеризацию и сюда. Алгоритм сам по себе очень простой (простейший алгоритм Крускала с ранней остановкой).

Дополнительно были идеи анализировать фейсбук, твиттер, ЖЖ и подобное, но руки не дошли. Руки вообще очень до многого не дошли, так как того что реализовано в своё время мне вполне хватило.

Берите, пользуйтесь. Подробных комментариев по использованию я не оставляю, так как предполагаю, что использовать это всё равно смогут только программисты.

P.S. По непонятной мне причине urllib в Python3 отказывается работать с vk.com под Линуксом. Такое чувство, что из-за отличия в заголовках vk.com отшивает urllib. Наверняка с этим можно разобраться, но, опять же, мне это было не нужно, если кому-то надо — тот доделает.

21 комментарий »

  1. >Берите, пользуйтесь

    нахуй это нужно? нет, я серьёзно. нахуй тебе знать чьи-то круги общения, число общих друзей и прочее говно?

    Comment by заебал со своей почтой бля — 30.10.2013 @ 17:18
  2. @ заебал со своей почтой бля:
    В общем случае не нужно совершенно, конечно. Но вот жизненная ситуация: наехали какой-то типы (в реале). Известна страница вконтакте одного из них, но у него 10000 друзей, хочется в этом списке найти тех остальных, которые с ним были, и тогда понять кто это — нацисты, антипедофилы, менты, кремлевская молодежь или еще кто. Ну это один из вариантов, подобного придумать можно много очень. У меня была ситуация, когда мне реально надо было вытащить всю информацию о человеке какую только возможно — такой анализ оказался весьма кстати.

    Comment by Хеллер — 30.10.2013 @ 17:25
  3. Хеллер написал:

    У меня была ситуация, когда мне реально надо было вытащить всю информацию о человеке какую только возможно

    Пили кулстори, хули.

    Comment by Anonymous — 30.10.2013 @ 23:41
  4. @ Anonymous:
    Да это всё та же история, что с прошлого года. Я пилю кулстори, но она длинная, а времени категорически не хватает.

    Comment by Хеллер — 31.10.2013 @ 09:45
  5. Хеллер, хрень какая-то. Нафиг нужны эти парсеры, если есть API вконтакте, которые выдают результат мгновенно?

    А насчёт квадратного корня — хитро придумал

    Comment by Синий (за Русь) — 31.10.2013 @ 13:35
  6. @ Синий (за Русь):
    Ну не мгновенно и не всё, тот же «круг друзей» не определить, изменения в списке друзей не определить. Да и с голыми идентификаторами возиться руками не хочется, составляя запросы.

    Собственно парсера у меня и нет — я напрямую API использую.

    Comment by Хеллер — 31.10.2013 @ 13:38
  7. Нельзя так?

    1. Два массива id (http://vk.com/dev/friends.get)
    2. Для пересечения массивов используешь http://vk.com/dev/users.get
    3. Ассоциативный массив общих друзей у тебя в кармане. Нет?

    Comment by Синий (за Русь) — 31.10.2013 @ 14:18
  8. А, хотя ты так и делаешь, приношу свои извинения =) Начал критиковать, не разобравшись в коде.

    Но почему долго получается, ума не приложу…

    Просто для общих друзей — три запроса.
    Для друзей друзей — несколько сотен (ну, тысяча, максимум). Это же немного

    Comment by Синий (за Русь) — 31.10.2013 @ 14:20
  9. @ Синий (за Русь):
    Контакт ограничивает судя по всему искусственно частоту запросов, поэтому получается довольно долго, часто вообще соединение валится по таймауту. Но опять же это долго, если у человека 8000 друзей, если 100 — то быстро конечно.

    Comment by Хеллер — 31.10.2013 @ 14:35
  10. Спасибо. Недавно как раз понадобилась такая штука.

    Comment by Guest — 31.10.2013 @ 17:29
  11. три запроса в секунду дают по АПИ

    Comment by дао — 31.10.2013 @ 17:36
  12. http://www.yasiv.com/vk
    Enjoy.

    Comment by Pastafarianist — 31.10.2013 @ 18:23
  13. @ Pastafarianist:
    Очень круто, но немного не то — мне нужны не мои друзья, а чужие (тем более на данный момент у меня вообще нет аккаунта вконтакте).

    Comment by Хеллер — 31.10.2013 @ 18:30
  14. Опасный вы друг, Роман!

    Comment by Иннокентий — 01.11.2013 @ 22:45
  15. Попробуй import threading.Thread. Тогда 8000 запросов будут выполняться не намного дольше, чем 100 (если, конечно, vk не забанит).

    Comment by igor — 02.11.2013 @ 07:53
  16. @ igor:
    Да, хорошее дело. Это я так понимаю ты закомитил? Получилось конечно намного круче.

    К сожалению, с тредами в Питоне я не работал, и не думал, что всё так просто — привык к WinAPI и С++, поэтому было лениво сразу правильно делать. Python изящный конечно.

    Comment by Хеллер — 05.11.2013 @ 11:50
  17. Я сам с тредами не слишком много работал, особенно под WinAPI и C++ (может, как раз потому и не привык их считать чем-то сложным:))
    А для подобных скриптов они очень хорошо подходят.

    Comment by igor — 07.11.2013 @ 02:30
  18. @ igor:
    Я к своему стыду не знал, что в Python все контейнеры потокобезопасные. В C++ каждую строчку надо было бы обложить мьютексом, предварительно 10 раз подумав, что именно обкладывать, либо подключать потокобезопасную библиотеку, что часто еще хуже в плане простоты использования. И это еще относится к C++11, до него в самом С++ вообще потоков не было, надо было дергать функции WinAPI и для мьютексов и для тредов. То есть гемор большой. Ну и по привычке я без нужды их не использую, хотя конечно как этот пример показывает — совершенно зря.

    Comment by Хеллер — 07.11.2013 @ 02:47
  19. Программу для взлома соседского вайфая можно замутить, сенсей Хеллер? Хотя бы теоритически, а?

    Comment by smesh — 02.01.2014 @ 20:12
  20. @ smesh:
    Теоретически наверное да, на практике как я понимаю вряд ли. Ну пожалуй кроме перебора всех паролей, хотя я не уверен, что это осуществимая задача (есть простые способы защиты от таких атак). Вообще я по этим делам не спец, но вообще сегодня очень многие усилия вкладываются в безопасность, особенно в безопасность технологий более-менее стандартных, поэтому маловероятно, что кому-то легко удастся обыграть большое количество экспертов в области сетей и криптографии, которые это всё разрабатывали. Раньше это было несколько проще, когда бизнес не сильно осознавал ценности информационной безопасности, сейчас какие-то проблемы находятся сравнительно редко в технологиях подобного масштаба и очень быстро исправляются.

    Comment by Хеллер — 13.01.2014 @ 16:57
  21. @ igor:
    С тредами не выйдет, Vk палит по ip же, ну и банит. прокси спасут. много проксей)

    Comment by Glop — 02.10.2015 @ 11:33

RSS feed for comments on this post. TrackBack URI

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

This work is licensed under GPL - 2009 | Powered by Wordpress using the theme aav1
SEO Powered by Platinum SEO from Techblissonline