0,0
рейтинг
24 марта 2014 в 11:32

Разработка → Анализ дружеских связей VK с помощью Wolfram Mathematica из песочницы

Не так давно, в Москве прошел семинар Wolfram Research Эра технологий Wolfram, на котором рассказывали много интересного про одну из самых мощных и определенно самую удобную систему компьютерных исследований Wolfram Mathematica. В частности, были представлены результаты исследования данных социальной сети facebook научно-исследовательской группой «Конструктивная Кибернетика». А чуть ранее, я наткнулся на новые возможности Wolfram|Alpha по всестороннему анализу странички в facebook. И после всего этого, у меня засела в голове безумная идея: «Я хочу узреть граф дружеских связей той соцсети, в которой живу (а именно, ВКонтатке)». И я все-таки нашел время на то чтобы ее реализовать. Добро пожаловать под кат.


Взаимодействие с VK API начинается с создания Standalone-приложения на https://vk.com/dev (там же можно будет редактировать уже созданное приложение). После нескольких кликов и долгих раздумий над названием, система выдает ID приложения, который будет использоваться для получения Access Token.
Чтобы получить Access Token, необходимо проследовать по ссылке ниже, заменив решеточки на ID приложения. О том, как формируется строчка, можно почитать тут.

oauth.vk.com/authorize?client_id=######&scope=friends&redirect_uri=https://oauth.vk.com/blank.html&display=page&v=5.16&response_type=token

После этого, в строке адреса появится много полезной информации, в частности, access_token и user_id. Эти два значения необходимо сохранить. Я назвал переменные myID(Integer||String) и token(String).
Следующим этапом будет написание базовой функции, взаимодействующей с API. Стандартный формат ответа от VK API — это JSON, который без труда парсится в списки и правила внутренними средствами Mathematica.



Список методов, которые теперь доступны ограничен только значением параметра scope, которое было передано при формировании Access Token. Чтобы проверить работоспособность системы, можно узнать, как вас зовут



Вывод VK API содержит много лишнего, поэтому, чтобы выделить только полезные данные, необходимо сначала отсечь лишнее



А, потом, применить правила замены (а это список правил замены) к тем параметрам, которые интересны. Остальные правила автоматически игнорируются.



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



Обратите внимание, что параметр для API называется user_ids, а не user_id. Это позволит получить информацию о целом списке пользователей за один запрос (ID должны разделяться запятыми и их должно быть меньше 1000).

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



Но в силу моего стремления к идеализму и желания хоть чуть-чуть приблизиться по продуманности к встроенным функциям Mathematica, у меня VKFriends вырос вот в это



Однако, для построения графа будет использоваться именно "Clean" версия. Тут интересно следующее — если параметр fields убрать, то ответом от API будет являться список ID и больше ничего. А если fields хоть чему-то, да равен, в ответ автоматически включается имя пользователя. Поэтому, для версии без аватарок, применяется значение fields=sex просто потому что sex — красивое слово. Практически, правило замены для пола в конечном варианте не реализуется. Хотя всегда можно добавить поля, которые вам интересно исследовать у своих друзей и строить из них красивые гистограммы, но тогда код вырастет еще во много раз и его структуру нужно будет менять (если, конечно, стремиться к массовости).

Последняя функция, которая нужна от API для сбора данных — это общие друзья. С их помощью, можно будет исследовать связи только внутри вашего круга общения, не получая и не обрабатывая мегабайты лишней информации о том кого знают ваши друзья из тех, кого вы не знаете. Для приведения синтаксиса и возможностей в соответствие с VKFriends, пришлось немного попотеть. Дело в том, что friends.getMutual умеет возвращать только чистый список ID, а это не наглядно (если вдруг кому-то понадобится наглядность)



Всё! На этом интеграция с VK API для данной задачи окончена (и так намного больше чем необходимо сделали). Пора брать быка за рога списки за хвосты. Поехали!



Получаем список друзей, описываем связи. Все они связаны только с Вами. Скорость исполнения — мгновение ока.



Но не огорчайтесь, время сходить за чаем и даже его испить у вас будет. Сам по себе friends.getMutual не особенно скоростной, так он еще и для каждого из ваших друзей выполняться должен. На моих 333 друзьях это заняло 119 секунд. Сие есть самая длительная операция за все исследование. Пока работает эта функция, можно поставить чайник и выбрать чай. DeleteCases возник в процессе отладки, когда глубина полученного массива оказалась внезапно равна 7. А все потому что в друзьях есть пользователи, для которых по каким-то причинам недоступны общие друзья. И сообщение об ошибке представлено в виде правил. Поэтому, удалив все правила, глубина массива станет нормальной, а тип данных станет Integer (представленный как String).
В результате выполнения кода, в переменной friendsOfFriends будет двумерный список, размером Length[myFriends]. И каждому элементу myFriends (другу) будет соответствовать список ваших общих друзей с этим другом. Теперь надо соединить каждого друга из myFriends со всеми соответствующими ему друзьями из friendsOfFriends. Фух. Объяснить словами вроде получилось, но если применять для этого вложенный Map, получится совершенно нечитабельно. Поэтому, похулиганим немного в процедурном стиле (убедительная просьба не повторять самостоятельно. Это очень плохой стиль для Mathematica. Ассемблер базировался на goto и в процедурном программировании стал плохим стилем, а Wolfram Language же позволяет решать всё аналитически, и здесь плохим стилем являются явные циклы [чисто формально это делает его языком нового поколения])



Далее, можно попытаться построить сей граф, но ничего не выйдет. Неориентированные графы со степенью вершин больше единицы добавлены только в еще не вышедшей Mathematica 10. Степень всех вершин не-орграфа равна двум, ибо каждый пользователь, находящийся в друзьях у другого пользователя, также находится в друзьях у первого. Проще говоря, мы нашли общего друга B с пользователем A, а когда смотрели страничку B, пользователь A так же оказывается в общих друзьях. И после исследования всей сети, все пользователи стали соединяться двумя ребрами. Чтобы на это посмотреть, замените UndirectedEdge на DirectedEdge по всем вхождениям. Но орграф избыточен ровно в 2 раза, так что от повторных ребер необходимо избавляться и строить неориентированный граф.



Пришлось писать свою функцию проверки, ибо нету такой. И, за одно, соединим графы воедино. Как ни странно, работает довольно долго… В результате, количество связей должно уменьшится чуть менее чем вдвое, потому что связи от gMyFriends не дублированы.
Ну все, можно строить! Только ничего непонятно будет. Так что продолжаем кодить пока не станет понятно.

Для того чтобы стало понятно, необходимо поменять вид вершин графа. Это можно сделать опцией VertexShape функции Graph. VertexShape принимает список правил замены названий на любые объекты. Названия вершин в данном случае представляют собой список gMyFriends, расширенный всего одним элементом — пользователем myID. Таким образом, необходимо получить информацию для всех элементов списка Append[myFriends, myID] и сделать из этого правила. Помните о вскипевшем чайнике? Самое время. У вас есть пара минут чтобы попить чай.



Что классно, так это то, что вся инфа запрашивается сразу в одном запросе. Только надо из ToString@Append[myFriends, myID] убрать скобки и пробелы.
Теперь мы имеем массив того, что надо заменять и массив того, на что надо заменять. Но нет, пока еще нЕ на что. Нужно чтобы всё было красиво.



Сначала, конструируются прямоугольные рамочки с именем и аватаркой, потом они помещаются в трех-уровневый список рядом с соответствующими ID, а потом в каждом элементе списка из списков, подменяется заголовок функции с List на Rule. В итоге, получаем список правил из списка списков. (Ну разве Wolfram Language не прекрасен?)

Вот теперь точно всё!



Можно насладиться результатом. Лично у меня получилось экспортировать эту красоту только в PDF, однако при этом пропадает кириллица, так что если на вашей странице стоит русский язык, добавьте в функцию VK "&lang=en" после "&v=5.16". Мой результат выглядит как-то так




Впечатляюще. Глобально. Особенно когда контакт является основным средством общения.

Блокнот скачать тут. Больше 300 человек в одном запросе уже не проходят, необходимо делить и об этом далее.


(прошла неделя)

Сегодня мне доказали, что себя на графе рисовать бесполезно, ибо в любом случае вы связаны с каждым из своих другов одной связью. Следовательно, эта связь избыточна. Я перестроил свои графы и они изменились. Так же, я добавил механизм автоматического разбиения списка друзей на части и сбора результата. Теперь он даже показывает прогресс выполнения — после каждого запроса печатает строку и когда напечатанных строк станет столько же, сколько частей в разделенном списке друзей, это 100%.



Экспериментально определено, что если в одном запросе больше 200 человек, начинаются проблемы. Оптимальное количество — 100. А вообще, чем меньше, тем надежнее. У меня 50 потому что всего друзей 300.

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

Все это доступно вот тут
Владислав Глаголев @Himura
карма
20,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (32)

  • +5
    Для получения необходимых вам данных нет необходимости в создание приложения, токенах и авторизациях. Всё без проблем добывается GETом (CURLом)
    api.vk.com/method/friends.get?user_id=2

    А графы впечатляют. Красиво.
    • 0
      Для друзей в токенах действительно нет необходимости, но вот друзья друзей не будут работать vk.com/pages?oid=-1&p=friends.getMutual
      Вообще сомнительная конечно производительность от этого, но так возможностей для расширения больше намного чем без авторизации
      • +1
        Что мешает собрать всех друзей, и запулить их по очереди тем же способом?
        Да, производительность таким образом хромает. Но тут уже дело алгоритмов, как оптимизировать.
        • 0
          Можно так сделать, но логичнее через друзей друзей. Если бы эта функция не была тормознутой, прирост производительности был бы ощутимым, так как у меня есть друзья у которых больше тысячи друзей
          • 0
            А если в pipelining запросов пачку на друзей друзей? Он же держит http/1.1, хотя поддержку пайпа надо проверить(
  • 0
    Спасибо большое, красиво! Теперь можно будет более подробо проверить теорию 5-ти рукопожатий.
    А не могли бы вы куда-нибудь выложить mathematica sheet? Поиграться) (чтобы не перебивать)
    • +1
      Теория шести рукопожатий. Насколько я проверял (самопальное приложение) — и правда работает
    • 0
      Мне habrastorage сказал что только картинки понимает. ВК есть предыдущая версия, как домой доберусь (к вечеру), обновлю
  • +1
    Так, а ссылка-то где? )
    • 0
  • +1
    почему бы не выложить готовый вариант в котором достаточно заменить входные данные?
  • +1
    Не могли бы вы подписать получившиеся у вас компоненты сильной связности? Ну, чтобы было понятно, как эти вершины связались в клубки. Например, одноклассники, однокурсники и т.д.
    • 0
      Вообще сообщества графа выделяются чисто математически последней строчкой. Но реально, в них можно узреть смысл и это невероятно круто. Для каждого смысл будет свой. Вот например мелкий апендикс слева — это народ, который со мной знаком по программе Кадры Будущего — прошлым летом я в Дубну ездил и кроме меня и моего друга их никто не знает. И Mathematica на раз их вычислила это круто!
  • +6
    Такой проект был ещё года 2-3 назад.
    www.yasiv.com/vk
    • +2
      :) Спасибо что помните! Я очень надеюсь выложить в этом году обновленную версию с гораздо более продвинутым функционалом, и полностью в открытом коде (включая веб интерфейс)
  • +1
    Ого, а вы не ищете легких путей. www.yasiv.com/vk Может потому, что вконтакт «является основным средством общения».
    • 0
      А не подскажете, почему этот сервис может показывать связь между 2 людьми, но эти люди друг о друге не знают?
      • 0
        Очень любопытно! Либо вы наткнулись на баг, либо же эти люди таки знают друг друга. Можете дать ссылки на них?
        • 0
          Таки они знают друг друга. Подружились буквально за час до того, как я воспользовался этим сервисом
          • 0
            :) тесный мир
    • 0
      IE11 — не заработало. Белый фон, но на мышку реагирует и рандомных друзей показывает при перемещении. И связей у них меньше чем у меня
      Эти люди, кстати, сурсов не выкладывали.
      А не ищу я легких путей по жизни, а не потому что как люблю общаться через удобные социальные сети с умными людьми.
      • +1
        Хабражитель anvaka выложил свою жс-реализацию ещё 2 года назад.
      • 0
        Привет!

        Я думаю у вас классная версия! Очень здорово видно кластеры когда ребра связываются воедино.

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

        А вот сам укладчик графов очень даже публично доступен под BSD 3: github.com/anvaka/VivaGraphJS и за него мне не стыдно :). Следующая итерация укладчика доступна тут github.com/anvaka/ngraph — очень надеюсь что тоже включу edge bundling со временем.
        • 0
          О, так они и правда не выложены =)
          По-моиму у вас очень классно получилось, при том что все это без использования всемогущих функций Mathematica.
          • 0
            Спасибо! У меня лишь веб интерфейс статикой хостится — за него стыдно :). Но если хочется — можно правой кнопкой и посмотреть исходники :). Правда, они очень страшные :)…

            Зная oauth и vk api легко можно воспроизвести мою визуалзиацию :).
            • 0
              делал такую же штуку. По видео видно, что работает получение общих друзей очень медленно. Я использовал написанный на VKScript скрипт через метод execute, что позволило поднять скорость получения общих друзей в ~20 раз. Будете допиливать свою версию — подумайте над этим :)
              • 0
                Т.е. VKScript реально быстрей работает, чем обычные запросы, например при получении друзей тысячи друзей?
                • 0
                  нет, дело в другом. у контакта есть ограничение в 3 запроса к апи в секунду, через метод execute вы в один запрос можете включить 20 вызовов апи, таким образом увеличив скорость на долгих задачах примерно в 20 раз
  • 0
    В коде нашлась ошибка в ходе тестирования на других людях! Кто найдет, тот няшка ))
  • 0
    Обновил блокнот, теперь он содержит примерный путь как можно избежать ошибки слишком длинного URL если друзей больше 400. На самом деле процесс можно автоматизировать, но влом. Правда если у вас больше 1000 друзей, придется, наверно, автоматизировать…
  • 0
    Обновления в конце основного поста

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