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

Совсем недавно на Хабре появилась статья о реализации дружеских связей в ВКонтакте с помощью Wolfram Mathematica. Идея мне понравилась, и, естественно, захотелось сделать такой же граф, используя Python и d3. Вот, что из этого получилось.

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

Разобьем задачу по элементам:

• Создание и авторизация приложения.
• Получение данных.
• Визуализация графа.

Что для этого нам понадобится:

• Python 3.4
• requests
• d3
• Mozilla FireFox, так как в Chrome нельзя использовать XMLHttpRequest для загрузки локальных файлов (никто не мешает сделать python -m http.server 8000)

Создание и авторизация приложения

Чтобы получить доступ к API ВКонтакте, нам необходимо создать Standalone-приложение, после чего мы сможем использовать нужные нам методы API, которые будут описаны далее. Приложение создается здесь — выберем Standalone-приложение. Нас попросят ввести код-подтверждения, высланный на мобильный, после чего мы попадем на страницу управления приложением. На вкладке Настройки нам пригодится ID приложения для получения access_token.
Далее нам надо авторизовать наше приложение. Этот процесс состоит из 3х этапов.

Аутентификации пользователя на сайте ВКонтакте

Для этого сформируем url, как показано ниже:

https://oauth.vk.com/authorize?client_id=IDприложения&scope=friends,offline&redirect_uri=https://oauth.vk.com/blank.html&display=page&v=5.21&response_type=token

Цитируя vk.com/dev/auth_mobile:

APP_ID – идентификатор Вашего приложения;
PERMISSIONS – запрашиваемые права доступа приложения;
DISPLAY – внешний вид окна авторизации, поддерживаются: page, popup и mobile.
REDIRECT_URI – адрес, на который будет передан access_token.
API_VERSION – версия API, которую Вы используете.

В нашем случае PERMISSIONS — это доступ к друзьям и к API в любое время со стороннего сервера (бессрочный токен). Если адрес сформирован правильно, нам предложат ввести логин и пароль.

Разрешение доступа к своим данным

Далее разрешаем приложению доступ к необходимой информации:

Получение access_token

После авторизации приложения клиент будет перенаправлен на REDIRECT_URI. Нужная нам информация будет заключена в ссылке.

https://oauth.vk.com/blank.html#access_token=ACCESS_TOKEN&expires_in=0&user_id=USER_ID

Редактируем файл settings.py, вставляя туда полученные access_token и user_id. Теперь мы можем осуществлять запросы к API ВКонтакте.

Получение данных

Для начала разберем методы, которые будем использовать для данной цели.

Поскольку нужна хоть какая-то информация об id пользователя, по которому будет строиться граф, нам пригодиться users.get. Он принимает как один id, так и несколько, список полей, информация из которых нам необходима, а также падеж, в котором будет склоняться фамилия и имя. Мой метод base_info() получает список id и возвращает информацию о пользователе с фотографией.

def base_info(self, ids):
		"""read https://vk.com/dev/users.get"""
		r = requests.get(self.request_url('users.get', 'user_ids=%s&fields=photo' % (','.join(map(str, ids))))).json()
		if 'error' in r.keys():
			raise VkException('Error message: %s. Error code: %s' % (r['error']['error_msg'], r['error']['error_code']))
		r = r['response']
		# Проверяем, если id из settings.py не деактивирован
		if 'deactivated' in r[0].keys():
			raise VkException("User deactivated")
		return r

Это может быть важно для тех, кто захочет отправлять в него id из friends.getMutual, таким образом произведя на свет огромное число запросов. Об этом позже.
Теперь нам надо получить информацию о друзьях пользователя, в чем нам и поможет метод friends.get. Из всех его параметров, перечисленных в документации, используем user_id, который находится в нашем setting.py и fields. Дополнительными полями будут id друзей, их имена, фамилии и фотографии. Ведь хочется, чтобы в узлах были миниатюры их фотографий.

def friends(self, id):
		"""
		read https://vk.com/dev/friends.get
		Принимает идентификатор пользователя
		"""
		r = requests.get(self.request_url('friends.get',
				'user_id=%s&fields=uid,first_name,last_name,photo' % id)).json()['response']
		#self.count_friends = r['count']
		return {item['id']: item for item in r['items']}

Далее наступает самое интересное.
Список id общих друзей между двумя пользователями возвращает метод friends.getMutual. Это хорошо, потому что мы получаем только id, а более расширенная информация у нас уже есть, благодаря friends.get. Но никто не запрещает сделать вам лишнюю сотню-другую запросов, используя users.get. Схемы расположены чуть-чуть пониже.
Теперь определимся, как будем использовать friends.getMutual. Если у пользователя N-друзей, то надо сделать N-запросов, чтобы по каждому другу мы получили список общих друзей. К тому же нам надо будет делать задержки, чтобы у нас было допустимое количество запросов в секунду.
Предположим, что у сканируемого нами id есть 25 друзей.

Всего 52 запроса — это слишком многовато, поэтому вспомним, что users.get может принимать список id:

25 друзей — 28 запросов, но как писалось выше, информация у нас уже имеется, благодаря friends.get.

И тут нам пригодится execute, который позволит запустить последовательность методов. У него есть единственный параметр code, он может содержать до 25 обращений к методам API.
То есть в итоге код в VKScript будет примерно таким:

return {
“id": API.friends.getMutual({"source_uid":source, "target_uid":target}), // * 25
...
};

Найдитесь те, кто напишет, как сократить данный код, не используя все время API.friends.getMutual.
Теперь нам надо всего лишь отправлять партиями id друзей по 25 в каждой. На нашем примере схема будет выглядеть так:

А ведь мы могли с помощью for отправлять каждого друга в friends.getMutual, а потом еще узнавать более детальную информацию через users.get.
Далее составим человеко понятную структуру, где уже вместо id друга и списка id ваших общих друзей, будет информация из friends.get. В итоге получим нечто вроде:

[({Ваш друг}, [{общий друг}, {еще один общий друг}]),({Ваша подруга}, None)]

В словарях находится id, имя, фамилия, фото, в списках — словари общих друзей, если общих друзей нет, то None. Кортежами все это разделяется.

def common_friends(self):
		"""
		read https://vk.com/dev/friends.getMutual and read https://vk.com/dev/execute
		Возвращает в словаре кортежи с инфой о цели и списком общих друзей с инфой
		"""
		def parts(lst, n=25):
			""" разбиваем список на части - по 25 в каждой """
			return [lst[i:i + n] for i in iter(range(0, len(lst), n))]

		result = []
		for i in parts(list(self.all_friends.keys())):
			# Формируем code (параметр execute)
			code = 'return {'
			for id in i:
				code = '%s%s' % (code, '"%s": API.friends.getMutual({"source_uid":%s, "target_uid":%s}),' % (id, 
								self.my_id, id))
			code = '%s%s' % (code, '};')

			for key, val in requests.get(self.request_url('execute', 'code=%s' % code)).json()['response'].items():
				if int(key) in list(self.all_friends.keys()):
					# берем инфу из уже полного списка
					result.append((self.all_friends[int(key)], [self.all_friends[int(i)] for i in val] if val else None))

		return result

Итак, если хочется посмотреть свой список друзей и общих с ними друзей, запускаем:

python main.py

Визуализация графа

Выбор пал на d3, а именно на Curved Links. Для этого надо сгенерировать json, который будет примерно такого содержания:

{ 
"nodes": [ 
        {"name":"Myriel","group":1, "photo": "path"}, 
        {"name":"Napoleon","group":1, "photo": "path"}, 
        {"name":"Mlle.Baptistine","group":1, "photo": "path"} 
        ], 
"links":[ 
        {"source":1,"target":0,"value":1}, 
        {"source":2,"target":0,"value":8} 
        ] 
}

Немного видоизменяя index.html, узлами становятся фотографии друзей.

Если хочется сразу визуализировать граф:

python 2d3.py

В папке web появится файл miserables.json. Не забываем открывать index.html в Mozilla FireFox или используем python -m http.server 8000 и открываем в Chrome.

Визуализация подтормаживает при большом количестве друзей, поэтому на будущее я думаю об использовании WebGL.

Так выглядит граф дружеских связей одного из моих друзей. Связи — это все.

Конечно, мне было интересно, у кого работает быстрее.

В статье, которая меня вдохновила, написано:

На моих 333 друзьях это заняло 119 секунд.

На момент написания этой статьи, у Himura в ВКонтакте был 321 друг. У меня это заняло 9 секунд (работа всей программы, а не одного friends.getMutual).

В заключение

Всю необходимую информацию об использованных методах можно найти в щедро написанной документации ВКонтакте, однако мной была обнаружена пара ошибок: не была описана ошибка с кодом 15 ('error_msg': 'Access denied: user deactivated', 'error_code': 15), догадаться можно, что она значит, и uid вместо user_id в документации к методу friends.get. Спустя 2 дня:

Как говорилось вначале, проект можно найти на GitHub, буду рад, если он понравится ещё кому-то и я получу много вкусных пулл реквестов…

UPD (27.05.2014):
Как мне подсказал WTFRU7, я добавил возможность использования хранимых процедур. Для этого нужно перейти по ссылке.
Создаем хранимую процедуру getMutual. Копируем содержимое execute_getMutual.js в форму и сохраняем. Не забываем скачать более новую версию. Финальный вид нашей схемы будет таким:

UPD (16.06.2014):
Получаем бессрочный токен.
UPD (11.07.2014):
Добавлены схемы-пояснения.
UPD (14.11.2014):
Продолжение