Pull to refresh

Анализ дружеских связей VK с помощью Wolfram Mathematica

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


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

https://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.

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

Все это доступно вот тут
Tags:wolframwolfram mathematicaсоциальные сетивконтактевконтакте api
Hubs: Programming
Total votes 33: ↑31 and ↓2 +29
Views41.7K

Popular right now

Programming Manager (C++)
from 250,000 ₽Game InsightRemote job
Разработчик нейронных сетей
from 75,000 to 75,000 ₽ДельтаинкомКазаньRemote job
QA специалист (API/Web/Mobile)
from 90,000 to 106,000 ₽Почта БанкМоскваRemote job
Senior Control Plane Developer
from 3,600 to 4,700 $DataDirect Networks Inc. (DDN)Remote job

Top of the last 24 hours