Перевірка теорії шести рукостискань



Хочу розповісти про свій експеримент по перевірці «Теорії шести рукостискань». На написання цього матеріалу мене надихнула стаття «Аналіз дружніх зв'язків 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.

friend for 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 friend in['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('виконати', [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('виконати', [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 — як би на краю кожної гілки дерева.



Я змоделював всю зв'язку з використанням веб-фреймворку СһеггуРу і результат мене задовольнив, хоча і довелося все одно ввести обмеження для відображуваних даних (в залежності від типу і кількості знайдених зв'язків). Я навмисно опустив підготовку даних для візуалізації, так як ця процедура не представляє інтересу і відрізняється в залежності від обраного методу. Мій варіант коду доступний на репозиторії GitHub, де також описана підготовка даних для використання з бібліотекою D3.js на прикладі шаблону «Radial Reingold–Tilford Tree».

Ще було б цікаво відобразити взаємозв'язки між списком друзів ось таким чином (див. малюнок нижче), так що можете експериментувати. Цей приклад взятий також з D3.js і називається він D3 Dependencies.



Що стосується перевірки теорії, то в масштабах України схема з трьома рукостисканнями працює в 90% випадків. Винятки становлять користувачі з дуже маленькою кількістю друзів.

Дякую за увагу.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.