0,0
рейтинг
15 декабря 2015 в 17:15

Разработка → Проверка теории шести рукопожатий из песочницы



Хочу рассказать о своем эксперименте по проверке «Теории шести рукопожатий». На написание этого материала меня вдохновила статья «Анализ дружеских связей VK с помощью Python» (чтобы избежать повторений, в дальнейшем я буду ссылаться на нее). Так как в целом задача мной была поставлена по-другому, да и использованные методы тоже отличаются, то я решил что это может быть интересно.


Формулировка задачи: визуализировать все связи между двумя пользователями внутри одной социальной сети. При этом связи не должны дублироваться, например если Ваня знает Петю через Олю, то Оля в дальнейших итерациях по поиску общих друзей не участвует. Чтобы попрактиковаться в API, я выбрал “Вконтакте”.

Отталкиваясь от ограничений API и функциональности методов, было решено, что оптимальным количеством «рукопожатий» с позиции времени получения информации будет 3. Так что проверять все-таки будем «Теорию трех рукопожатий», пока что. Таким образом при среднем количестве друзей 200, мы получаем выборку из 8 млн. человек. Например, в масштабах Украины я практически всегда находил связи.

 Структурно задачу можно разбить на следующие этапы:



  1. Поиск общих друзей между исходным пользователем 1 (user_1) и исходным пользователем 2 (user_2).
  2. Поиск общих друзей между user_2 и друзьями user_1.
  3. Поиск общих друзей между друзьями user_2 и друзьями user_1.
  4. Получение детальной информации о найденных связях.
  5. Визуализация.

Итак, что нам понадобится:

import requests
import time
from threading import Thread
from tokens import *


Requests — распространенная HTTP библиотека для Python, описана в статье «Библиотека для упрощения HTTP-запросов».
Time — базовый модуль, название которого говорит само за себя. Будем использовать для введения задержек во времени.
Threading — базовый модуль для работы с потоками. Хорошо описан в статье «Учимся писать многопоточные и многопроцессные приложения на Python».
Tokens — файл tokens.py будет содержать OAuth токены для авторизации в API. Как получить токен описано в исходной статье, а также на странице API «Вконтакте».

Прежде чем приступать к первому этапу, тезисно остановлюсь на функциональности API и некоторых ограничениях:

  • Для обращения к методу API используется POST или GET запрос.
  • Список использованных мной методов: users.get, friends.get, friends.getMutual, execute.
  • Метод execute позволяет запускать до 25 методов одним запросом.
  • В секунду можно осуществить не более 3 запросов (используя один токен).
  • Ограничение для параметра target_uids метода friends.getMutual — 300. Об этом более подробно остановлюсь ниже.

Таким образом глобально схема сводится к отправке GET запросов на сервер «Вконтакте» и анализу ответов от сервера в формате json. При этом для оптимизации времени мы используем метод execute и многопоточность.

Ремарка к исходной статье, которая меня вдохновила. Автор статьи STLEON использует метод friends.getMutual в режиме “один к одному”, используя параметр target_uid. Я полагаю, что это было вызвано отсутствием параметра target_uids в прошлой версии API. Я же использую этот метод в режиме “один к многим”, что значительно экономит время. Параметр target_uids имеет ограничение на длину строки, о котором я ничего не нашел в документации. Экспериментально было установлено, что максимальная длина составляет порядка 310-330 UID в зависимости от длины каждого идентификатора. Я округлил этот показатель до 300.

Все выше сказанное подытожим объявлением следующих констант:

f_1_max = 300
f_2_max = 24
t = 0.35

Почему f_2_max = 24, а не 25, будет ясно позже.

Этап 1. Поиск общих друзей между user_1 и user_2




Напишем функцию, с помощью которой мы будем общаться с сервером «Вконтакте» посредствам GET запроса:

def vk (method, parameters, token):
	return requests.get('https://api.vk.com/method/%s?%s&access_token=%s' % (method, '&'.join(parameters), token)).json()

У этой функции есть три аргумента:

  • method — название метода, к которому мы обращаемся через API.
  • parameters — параметры этого метода (можно найти в описании каждого метода).
  • token — строка, которая авторизирует Вас на сервере. Повторюсь, что получение токена подробно описано здесь и здесь.

Далее для сохранения всей собранной информации мы будем использовать множества. Инициализируем множества для каждого из трех “рукопожатий”.

edges_1, edges_2, edges_3 = set(), set(), set()

Для выполнения условия, чтобы связи не дублировались и Оля не фигурировала как общий друг Пети и Вани во всех трех “рукопожатиях”, а только в первом, необходимо ввести фильтры. Сразу же добавляем в фильтр первого “рукопожатия” исходных пользователей.

filter_1, filter_2 = set(), set()
filter_1.update([user_1, user_2])

Находим друзей user_1 с помощью вызова метода friends.get. После выполнения обращения к методу API, вводим необходимую задержу во времени t = 0.35. Заметьте, что одним из параметров является версия API (v=5.4 в моем случае). Очень важно везде ее указывать, потому что могут появиться несоответствия. Параметры метода order и count — использовать опционально.

friends_1 = set(vk('friends.get', ['user_id=%s' % user_1, 'order=hints', 'count=900', 'v=5.4'], token_1)['response']['items'])
time.sleep(t)

Далее переходим непосредственно к поиску общих друзей между user_1 и user_2 с помощью вызова метода friends.getMutual.

mutual_friends = vk('friends.getMutual', ['source_uid=%s' % user_1, 'order=hints', 'target_uid=%s' % user_2, 'v=5.4'], token_1)['response']
time.sleep(t)

И последний пункт первого этапа — сохранение информации в множество edges_1, обновление filtr_1 и удаление найденных общих друзей из списка друзей user_1, чтобы избежать повторений в будущем.

for user in mutual_friends:
	edges_1.update([(user_1, user), (user, user_2)])
	friends_1.remove(user)
	filter_1.update([user])

Этап 2. Поиск общих друзей между user_2 и друзьями user_1 (friends_1)




Глобально второй этап повторяет первый, вся разница в том, что вместо поиска общих друзей в режиме “один к одному”, мы используем режим “один к многим”, что требует несколько лишних строк кода.
Инициализируем список, в который будем сохранять добытых друзей, а также некоторые переменные, которые нам понадобятся в промежуточных вычислениях.

user_1_mutual_friends, temp_users, j = [], [], 0

Далее, отсчитывая порции (не самое подходящее слово) из друзей user_1 по 300 UID, мы поочередно отправляем запросы к серверу об общих друзьях между user_2 и порцией UID, которые записываются в параметр target_uids метода friends.getMutual.

for i, friend in enumerate(friends_1):
		temp_users += [friend]
		j += 1
		if j == f_1_max:
			user_1_mutual_friends += vk('friends.getMutual', ['source_uid=%s' % user_2, 'order=hints', 'target_uids=%s' % str(temp_users)[1:-1], 'v=5.4'], token_1)['response']
			temp_users, j = [], 0
			time.sleep(t)

		if i == len(friends_1) - 1 and len(friends_1) % f_1_max != 0:
			user_1_mutual_friends += vk('friends.getMutual', ['source_uid=%s' % user_2, 'order=hints', 'target_uids=%s' % str(temp_users)[1:-1], 'v=5.4'], token_1)['response']
			time.sleep(t)

Сохраняем полученную информацию в множество edges_2 и обновляем информацию в фильтре, как было в предыдущем этапе. Здесь могут быть исключения, допустим если UID закрыл доступ к общим друзьям или страница пользователя удалена, поэтому используем конструкцию try-except.

for friend in user_1_mutual_friends:
	if friend['id'] != user_2 and friend['id'] not in filter_1:
		try:
			if friend['common_count'] > 0:
				for common_friend in friend['common_friends']:
					if common_friend != user_1 and common_friend not in filter_1:
						edges_2.update([(user_1, friend['id']), (friend['id'], common_friend), (common_friend, user_2)])
						friends_1.remove(friend['id'])
						filter_2.update([friend['id'], common_friend])
		except:
			continue

Этап 3. Поиск общих друзей между друзьями user_2 и друзьями user_1




Данный этап является наиболее затратным по времени, так как запросов отправить нужно очень много. Именно здесь невозможно обойтись без использования метода execute. Из практики скажу, что без использования многопоточности, время на выполнение данного этапа по этому алгоритму составляет 50 — 120 секунд, а в некоторых случаях еще больше. 
С помощью использования нескольких потоков возможно свести время до выполнения одного запроса execute, который обрабатывается от 5 до 12 секунд.

Объявляем filter_3, объединяя множества filter_1 и filter_2. Преобразуем множество друзей user_1 (friends_1) в список.

filter_3 = filter_1.union(filter_2)
friends_1 = list(friends_1)

Далее последует монстрозный блок кода, в котором мы объявляем функцию для поиска общих друзей между друзьями user_1 и друзьями user_2 и сохранения информации в множество edges_3. Здесь опять-таки весь алгоритм такой же, как и в предыдущих этапах, только используется принцип “многие ко многим”, что еще больше усложняет код, тем более в моей имплементации он явно избыточный, так что вам есть над чем поработать. Ниже я приведу некоторые пояснения к этому многобуквию.

def get_edges_3 (friends_1, token):

	prefix_code = 'code=var friends = API.friends.get({"v": "5.4", "user_id":"%s", "count":"500", "order": "hints"}).items; ' % user_2
	lines, j, k = [], 0, -1
	for i, friend in enumerate(friends_1):
		lines += ['API.friends.getMutual({"v": "5.4", "source_uid": "%s", "count":"500", "target_uids": friends})' % friend] # Generating string for 'execute' request.
		j += 1
		if j == f_2_max:
			code = prefix_code + 'return [' + ','.join(str(x) for x in lines) + '];'
			response = vk('execute', [code, 'v=5.4'], token_1)
			for friends in response['response']:
				k += 1
				if len(edges_3) < max_edges_3:
					try:    
						for one_friend in friends:
							if one_friend['common_count'] > 0:
								for common_friend in one_friend['common_friends']:
									if common_friend not in filter_3 and one_friend['id'] not in filter_3:
										edges_3.update([(user_1, friends_1[k]), (friends_1[k], common_friend), (common_friend, one_friend['id']), (one_friend['id'], user_2)])
					except:
						continue
			lines, j = [], 0
			time.sleep(t)

		if i == len(friends_1) - 1 and len(friends_1) % f_2_max != 0 :
			code = prefix_code + 'return [' + ','.join(str(x) for x in lines) + '];'
			response = vk('execute', [code, 'v=5.4'], token_1)
			for friends in response['response']:
				k += 1
				if len(edges_3) < max_edges_3:
					try:    
						for one_friend in friends:
							if one_friend['common_count'] > 0:
								for common_friend in one_friend['common_friends']:
									if common_friend not in filter_3 and one_friend['id'] not in filter_3:
										edges_3.update([(user_1, friends_1[k]), (friends_1[k], common_friend), (common_friend, one_friend['id']), (one_friend['id'], user_2)])
					except:
						continue
			time.sleep(t)

Сумма строк prefix_code и lines представляет собой код в формате VKScript и является единственным параметром для метода execute. Этот скрипт содержит в себе 25 обращений к методам API.

prefix_code — часть строки, содержащая обращение №1 к методу friends.get. Здесь мы получаем список друзей user_2 и присваиваем его переменной friends.

lines — вторая часть строки, содержащая обращения №№ 2-25 к методу friends.getMutual. Здесь мы получаем список общих друзей между каждым из 24 друзей user_1 и списком друзей user_2. В цикле мы складываем prefix_code и 24 строки lines, таким образом получая строку code, которую используем как параметр к методу execute.

Далее я приведу пример с использованием нескольких потоков, но подробно не буду останавливаться на нем. Всю информацию можно найти в статье «Учимся писать многопоточные и многопроцессные приложения на Python».

t1 = Thread(target=get_edges_3, args=(friends_1[ : len(friends_1) * 1/3], token_1))
t2 = Thread(target=get_edges_3, args=(friends_1[len(friends_1) * 1/3 : len(friends_1) * 2/3], token_2))
t3 = Thread(target=get_edges_3, args=(friends_1[len(friends_1) * 2/3 : ], token_3))

t1.start()
t2.start()
t3.start()

t1.join()
t2.join()
t3.join()

Этап 4. Получение детальной информации о найденных связях


Теперь мы должны сложить все ребра нашего еще непостроенного графа друзей и извлечь из них список вершин. Далее по описанному выше шаблону с помощью метода users.get порциями по 300 UID отправляем запросы на получение данных о фамилии и имени пользователей. На выходе получаем список, в каждой ячейке которого будет UID и словарь с информацией о данном UID. Эти данные в комплексе с множествами ребер в дальнейшем используем для визуализации.

edges = list(edges_1) + list(edges_2) + list(edges_3)
	nodes = []
	for edge in edges:
		nodes += [edge[0], edge[1]]
	nodes = list(set(nodes))
	nodes_info, temp_nodes, j = [], [], 0

	for i, node in enumerate(nodes): 
		temp_nodes += [node]
		j += 1
		if j == f_1_max:
			nodes_info += vk('users.get', ['user_ids=%s' % str(temp_nodes)[1:-1], 'fields=first_name, last_name', 'v=5.4'], token_1)['response']
			temp_nodes, j = [], 0
			time.sleep(t)
		if i == len(nodes) - 1 and len(nodes) % f_1_max != 0:
			nodes_info += vk('users.get', ['user_ids=%s' % str(temp_nodes)[1:-1], 'fields=first_name, last_name', 'v=5.4'], token_1)['response']
			time.sleep(t)

	for i, node in enumerate(nodes_info):
		try:
			nodes[i] = (nodes[i], {'first_name': node['first_name'], 'last_name': node['last_name']})
		except:           
			continue

Этап 5. Визуализация


На технической реализации этого этапа я подробно останавливаться не буду. Опишу лишь кратко свой опыт.

Как и в исходной статье, я пробовал использовать библиотеку networkx для построения графа. Изменял диаметр и цвет вершин в зависимости от пола или количества связей, испробовал много методов визуализации, которые доступны в этой библиотеке, но результат мне не нравился. Беспорядочный граф получался не информативным при среднем и большом количестве ребер и вершин. Информация терялась.

Я пришел к выводу, что необходимо какое-то интерактивное решение. Первым, что я нашел, была библиотека D3.js. Но и здесь в формате обычного графа, несмотря на интерактивность, результат был неудовлетворительным. Затем в той же библиотеке был найден пример древовидного построения “Radial Reingold–Tilford Tree”, который мне показался подходящим. При таком построении в центре оказывается user_1, а user_2 — как бы на краю каждой ветви дерева.



Я смоделировал всю связку с использованием веб-фреймворка СherryPy и результат меня удовлетворил, хотя и пришлось все равно ввести ограничения для отображаемых данных (в зависимости от типа и количества найденных связей). Я намеренно опустил подготовку данных для визуализации, так как эта процедура не представляет интереса и отличается в зависимости от выбранного метода. Мой вариант кода доступен на репозитории GitHub, где также описана подготовка данных для использования с библиотекой D3.js на примере шаблона “Radial Reingold–Tilford Tree”.

Еще было бы интересно отобразить взаимосвязи между списком друзей вот таким образом (см. рисунок ниже), так что можете экспериментировать. Этот пример взят также из D3.js и называется он D3 Dependencies.



Что касается проверки теории, то в масштабах Украины схема с тремя рукопожатиями работает в 90% случаев. Исключения составляют пользователи с очень маленьким количеством друзей.

Спасибо за внимание.
Бражник Владимир @InspiredByData
карма
8,0
рейтинг 0,0
Python developer
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

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

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

  • +1
    Я занимался этим, почти у каждого есть друг или друг друга, который имеет заоблачное число друзей.

    Глючит, но с трудом работает:
    vk.com/app1886758#chain=1=345

    Место 1 и 345 подставьте свои ID.

    Вот пример поинтереснее:
    Взял ПД и почти случайный номер:
    vk.com/app1886758#chain=1=10273191
    Основан на ссылки на эту статью: habrahabr.ru/post/273191

    Работает по ссылке с обновлениями. После верефикации ВК, приложение утратило значение.

  • +2
    тема уже обсуждалось на хабре и не 1 раз:
    http://habrahabr.ru/post/258713/
    http://habrahabr.ru/post/132558/

    p.s. сам занимался этим, но на хабр постеснялся писать, по той же причине
    • +1
      Спасибо за ссылки, я обязательно ознакомлюсь. Дело в том что мне попадалась только статья об анализе дружеских связей, а поскольку я два месяца назад еще не знал что такое Python и вообще программирование в целом, то и этот результат считаю достижением для себя.
      • –1
        Не стоит превращать хабр в «Опубликуй свой Hello World!». Добавьте чего-нибудь научного, какой-нибудь статистический анализ с гугл картами и графиками для визуализации
        • +3
          Если объективно, то ни одна из приведенных выше ссылок не дублирует мой материал. Не стоит думать, что вся статья — это «Hello World», не вникнув в контекст, а прочитав только мой комментарий о том, что у меня нет опыта в разработке. Это не оправдание, а факт.
          • –5
            Объективно, в моем коментарии конструктивная критика, я описал, как сделать лучше. Вы можете либо дальше спорить либо сделать лучше
            • +3
              За критику спасибо, гугл карты — хорошая идея. А спорить — это для слабаков.
      • +3
        Каждому бы писать такой Hello world с визуализацией и многопоточностью) для первой задачи на python впечатляет. Идея визуализации тоже очень понравилась.
  • +1
    Вот моя попытка сделать что-то похожее. У меня получилось диаметр сетки вк если память не изменяет 4.3, так что 6 рукопожатий для социалок это очень завышенная планка.
  • 0
    Когда контакт только появился, ради интереса создал группу, которая для увеличения числа пользователей типа исследовала эту теорию.
    Мы не были первыми, у кого количество членов группы перевалило 10к, но 20к были наши. =)

    Сейчас для того, чтобы найти кратчайший путь до другого человека достаточно у любого рандомного человека открыть список друзей, пройти по первой ссылке, на другой странице то же самое — список друзей, первая ссылка.
    • 0
      Я таким образом могу только путь до жены найти.
  • 0
    Метод users.get доступен без авторизации. Когда я делал что-то схожее, грузил данные в 64 потока. Ответ на запрос приходит с задержкой в доли секунды, а время передачи файлика, имхо, намного меньше. Получалось, если меньше 64 потоков — медленнее, больше — упирался в скорость интернета (или мне так казалось).
    • 0
      Да, вы правы. На такие запросы как users.get, friedns.get, где в параметры не передаются списки значений, ответ от сервера приходит очень быстро. Все изменяется, когда начинаешь использовать execute, в котором 25 методов с комплексными параметрами. Более 10 секунд может быть.
  • 0
    Спасибо, интересно.

    Делал нечто подобное, но хотел построить граф групп френдов для целого города.
    Список френдов получал get-запросом на api.vk.com/method/friends.get, там не требуется токен. Дальше просто в цикле делал запросы, ну и складывал в базу.
    В принципе работало, но получилось слишком долго и медленно — небольшой город на 200тыс «сливался» около 15 часов. На Москву замахиваться с такой скоростью обработки я не рискнул :)

    Вопрос как максимально быстро скачать всех юзеров города для меня пока открытый. Может действительно стоит тупо распараллелить.
    • 0
      Мне кажется, что самый оптимальный вариант — это использование execute в комплексе с мультипоточностью. Сделайте ботов, получите для них токены и вперед. Можно с одного IP, по крайней мере до каких-то пор.
      Кстати, кроме метода execute, возможно еще использовать хранимые процедуры. Это тот же VKscript, но который хранится на сервере. Прироста в производительно я так понимаю никакой не будет, а просто экономия трафика. Поправьте, если я не прав.
      • 0
        Спасибо, попробую.
  • +2
    Кажется, все кому не лень с появлением соц. сетей стали проверять эту теорию. И, надо же, все сходятся во мнении, что она «в общем то работает».

    А по теме, было бы неплохо вытаскивать только людей с количеством связей < 100 (в своей реализации: https://github.com/Sild/vk_chain_friends я использовал ограничение в 300), а ещё лучше брать только топ 30-50 активных друзей.

    Да и надежность этого всего… Добавить в друзяшки человека !== Иметь связь с человеком.

    • 0
      Согласен. По заголовку стало интересно, как же будут проверять. Дочитал до API вконтакте и приуныл. :(
  • 0
    Хочу поддержать — статья очень понравилась, не смотря на то, что раньше уже писали на эту тему.
    Особенно впечатлила визуализация — не думаю, что она информативна, зато очень красивая.

    Идея для улучшения:
    Поставить фильтр на друзей — считать друзьями только тех, кто достаточно часто взаимно лайкает посты друг друга.
    • 0
      Спасибо, интересно. Хотя думаю логику «кого считать друзьями» нужно сделать более гибкой. И об ограничении на количество друзей из предыдущего поста — тоже согласен.

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