Python Developer
0,0
рейтинг
14 ноября 2014 в 13:41

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

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

Начнем с того, что просто скачать все id пользователей достаточно легко, список валидных id можно найти в Каталоге пользователей Вконтакте. Наша же задача — получить список друзей выбранного нами id пользователя, их друзей и рекурсивно сколь угодно глубоко, в зависимости от указанной глубины.

Код, опубликованный в статье, будет меняться с течением времени, поэтому более свежую версию можно найти в том же проекте на Github.

Как будем реализовывать:
  • Задаем нужную нам глубину
  • Отправляем исходные данные либо те id, которые надо исследовать на данной глубине
  • Получаем ответ

Что будем использовать:
  • Python 3.4
  • Хранимые процедуры в ВКонтакте

Задаем нужную нам глубину


Что нам потребуется в начале — это указать глубину (deep), с которой мы хотим работать. Сделать это можно сразу в settings.py:

deep = 2 # такая строчка там уже есть

deep равное 1 — это наши друзья, 2 — это друзья наших друзей и так далее. В итоге мы получим словарь, ключами которого будут id пользователей, а значениями — их список друзей.

Не спешите выставлять большие значения глубины. При 14 моих исходных друзьях и глубине равной 2, количество ключей в словаре составило 2427, а при глубине, равной 3, у меня не хватило терпения дождаться завершения работы скрипта, на тот момент словарь насчитывал 223 908 ключей. По этой причине мы не будем визуализировать такой огромный граф, ведь вершинами будут ключи, а ребрами — значения.

Отправление данных


Добиться нужного нам результата поможет уже известный метод friends.get, который будет расположен в хранимой процедуре, имеющей следующий вид:

var targets = Args.targets;
var all_friends = {};
var req;
var parametr = "";
var start = 0;
// из строки с целями вынимаем каждую цель
while(start<=targets.length){
    if (targets.substr(start, 1) != "," && start != targets.length){
        parametr = parametr + targets.substr(start, 1);
    }
    else {
        // сразу делаем запросы, как только вытащили id
        req = API.friends.get({"user_id":parametr});
        if (req) {
            all_friends = all_friends + [req];
        }
        else {
            all_friends = all_friends + [0];
        }
        parametr = "";
    }
    start = start + 1;
}
return all_friends;

Напоминаю, что хранимую процедуру можно создать в настройках приложения, пишется она на VkScript, как и execute, документацию можно прочесть здесь и здесь.

Теперь о том, как она работает. Мы принимаем строку из 25 id, разделенных запятыми, вынимаем по одному id, делаем запрос к friends.get, а нужная нам информация будет приходить в словаре, где ключи — это id, а значения — список друзей данного id.

При первом запуске мы отправим хранимой процедуре список друзей текущего пользователя, id которого указан в настройках. Список будет разбит на несколько частей (N/25 — это и число запросов), связано это с ограничением количества обращений к API ВКонтакте.

Получение ответа


Всю полученную информацию мы сохраняем в словаре, например:

{1:(0, 2, 3, 4), 2: (0, 1, 3, 4), 3: (0, 1, 2)}

Ключи 1, 2 и 3 были получены при глубине, равной 1. Предположим, что это и были все друзья указанного пользователя (0).

Если глубина больше 1, то далее воспользуемся разностью множеств, первое из которых — значения словаря, а второе — его ключи. Таким образом, мы получим те id (в данном случае 0 и 4), которых нет в ключах, разобьем их опять на 25 частей и отправим хранимой процедуре.

Тогда в нашем словаре появятся 2 новых ключа:

{1:(0, 2, 3, 4), 2: (0, 1, 3, 4), 3: (0, 1, 2), 0: (1, 2, 3), 4:(1, 2, ….)}

Сам же метод deep_friends() выглядит следующим образом:

def deep_friends(self, deep):
		result = {}

		def fill_result(friends):
			for i in VkFriends.parts(friends):
				r = requests.get(self.request_url('execute.deepFriends', 'targets=%s' % VkFriends.make_targets(i))).json()['response']
				for x, id in enumerate(i):
					result[id] = tuple(r[x]["items"]) if r[x] else None

		for i in range(deep):
			if result:
				# те айди, которых нет в ключах + не берем id:None
				fill_result(list(set([item for sublist in result.values() if sublist for item in sublist]) - set(result.keys())))
			else:
				fill_result(requests.get(self.request_url('friends.get', 'user_id=%s' % self.my_id)).json()['response']["items"])

		return result

Конечно, это быстрее, чем кидать по одному id в friends.get без использования хранимой процедуры, но времени все равно занимает порядочно много.

Если бы friends.get был похож на users.get, а именно мог принимать в качестве параметра user_ids, то есть перечисленные через запятую id, для которых нужно вернуть список друзей, а не по одному id, то код был бы намного проще, да и количество запросов было в разы меньше.

Слишком медленно


Возвращаясь к началу статьи, могу снова повторить — очень медленно. Хранимые процедуры не спасают, решение alxpy с многопоточностью (спасибо ему за вклад и участие хоть кому-то было интересно, кроме меня) ускоряло на несколько секунд работу программы, но хотелось большего.

Мудрый совет получил от igrishaev — нужен какой-то мап-редьюс.

Дело в том, что ВКонтакте разрешает 25 запросов к API через execute, из этого следует, что если делать запросы с разных клиентов, то мы можем увеличить количество допустимых запросов. 5 тачек — это уже 125 запросов в секунду. Но и это далеко не так. Забегая вперед, скажу, что можно и еще быстрее, примерно будет выглядеть следующим образом (на каждой машине):

while True:
	r = requests.get(request_url('execute.getMutual','source=%s&targets=%s' % (my_id, make_targets(lst)),access_token=True)).json()
	if 'response' in r:
		r = r["response"]
		break
	else:
		time.sleep(delay)

Если нам приходит сообщение об ошибке, то мы делаем запрос снова, спустя заданное количество секунд. Такой прием работает какое-то время, но затем ВКонтакте начинает присылать во всех ответах None, поэтому после каждого запроса честно будем ждать 1 секунду. Пока что.

Далее нам надо выбрать новые инструменты или же написать свои, чтобы реализовать задуманное. В итоге у нас должна получиться горизонтально масштабируемая система, принцип работы видится мне следующим образом:

  • Главный сервер получает от клиента его id ВКонтакте и код операции: либо вытащить всех общих друзей, либо рекурсивно прогуляться по списку друзей с указанной глубиной.
  • Далее в обоих случаях сервер делает запрос к API ВКонтакте — нам нужен список всех друзей пользователя.
  • Поскольку все сделано для того, чтобы мы пользовались по-максимуму возможностями хранимых процедур — здесь надо будет разделить список друзей на части, по 25 контактов в каждой. На самом деле по 75. Об этом чуть ниже.
  • У нас получится много частей, используя брокер сообщений будем доставлять каждую часть определенному получателю (producer-consumer).
  • Получатели будут принимать контакты, сразу делать запросы, возвращать результат поставщику. Да, вы правильно подумали про RPC.

А если вы видели эту картинку, то понимаете, на какой брокер сообщений я намекаю.


Как только все ответы приняты, объединяем их в один. Далее результат можно будет вывести на экран или вовсе сохранить, об этом позже.

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

В качестве брокера сообщений будем использовать RabbitMQ, асинхронной распределенной очереди заданий — Celery.

Для тех, кто никогда с ними не сталкивался, вот несколько полезных ссылок на материалы, которые советую вам прочитать:



Не надо бояться понять, хоть и говорят, что можно конкретно повернуть свою голову, когда начинаешь «думать не одним компьютером, а несколькими», но это вовсе не так.

Если у вас Mac, как и у автора, то RabbitMQ шикарно ставится через Homebrew:

brew update
brew install rabbitmq

Celery же ставится еще легче, используем третью ветку Python:

pip3 install Celery

У меня Celery установлен на Linux Mint, а RabbitMQ — на Mac. С виндой, как обычно, проблемы — тяжело найти, легко потерять она почему-то все время не хотела возвращать response моему Mac.

Далее создадим virtual host, пользователя и дадим ему права:

rabbitmqctl add_vhost vk_friends
rabbitmqctl add_user user password
rabbitmqctl set_permissions -p vk_friends user ".*" ".*" ".*"

В конфигурации RabbitMQ надо указать ip хоста, на котором он установлен:

vim /usr/local/etc/rabbitmq/rabbitmq-env.conf
NODE_IP_ADDRESS=192.168.1.14 // конкретно мой вариант

Вот несколько возможных конфигураций, какую выбрать — решать вам.



Если у вас роутер или еще что-то, полезно будет знать, что RabbitMQ использует 5672 порт, ну и сделать переадресацию в настройках вашего устройства. Скорее всего, если будете тестировать, то воркеров раскидаете по разным машинам, а им нужно будет использовать брокер, и, если не правильно настроите сеть, Celery до RabbitMQ так и не достучится.

Очень хорошей новостью является то, что ВКонтакте разрешает делать по 3 запроса в секунду с одного id. Умножим эти запросы на количество возможных обращений к API ВКонтакте (25), получим максимальное число обрабатываемых контактов в секунду (75).


Если у нас будет много воркеров, то настанет момент, когда начнем переходить за дозволенный лимит. Поэтому переменная tokensettings.py) теперь будет кортежем, содержащим в себе несколько токенов с разных id. Скрипт же будет при каждом запросе к ВКонтакте API выбирать один из них рандомным образом:

def request_url(method_name, parameters, access_token=False):
	"""read https://vk.com/dev/api_requests"""

	req_url = 'https://api.vk.com/method/{method_name}?{parameters}&v={api_v}'.format(
		method_name=method_name, api_v=api_v, parameters=parameters)

	if access_token:
		req_url = '{}&access_token={token}'.format(req_url, token=random.choice(token))

	return req_url 

В этом плане у вас не должно возникнуть сложностей, если есть несколько аккаунтов в ВКонтакте (можно напрячь друзей, родных), у меня не было проблем с 4 токенами и 3 воркерами.

Нет, вам никто не мешает использовать time.sleep(), или пример выше с while, но тогда готовьтесь получать сообщения об ошибках (возможны вообще пустые ответы — id:None), или подольше ждать.

Самое интересное из файла call.py:

def getMutual():
	all_friends = friends(my_id)
	c_friends = group(mutual_friends.s(i) for i in parts(list(all_friends[0].keys()), 75))().get()
	result = {k: v for d in c_friends for k, v in d.items()}
	return cleaner(result)

def getDeep():
	result = {}
	for i in range(deep):
		if result:
			# те айди, которых нет в ключах + не берем id:None
			lst = list(set([item for sublist in result.values() if sublist for item in sublist]) - set(result.keys()))
			d_friends = group(deep_friends.s(i) for i in parts(list(lst), 75))().get()
			result = {k: v for d in d_friends for k, v in d.items()}
			result.update(result)
		else:
			all_friends = friends(my_id)
			d_friends = group(deep_friends.s(i) for i in parts(list(all_friends[0].keys()), 75) )().get()
			result = {k: v for d in d_friends for k, v in d.items()}
			result.update(result)

	return cleaner(result)

Как видите, в 2 функциях мы используем groups(), который параллельно запускает несколько заданий, после чего мы «склеиваем» ответ. Помните, как deep_friends() выглядел вначале (там уж очень старый пример — даже без многопоточности)? Смысл остался тем же — мы используем разность множеств.

И, наконец, tasks.py. Когда-нибудь эти замечательные функции объединятся в одну:

@app.task
def mutual_friends(lst):
	"""
	read https://vk.com/dev/friends.getMutual and read https://vk.com/dev/execute
	"""
	result = {}
	for i in list(parts(lst, 25)):
		r = requests.get(request_url('execute.getMutual', 'source=%s&targets=%s' % (my_id, make_targets(i)), access_token=True)).json()['response']	
		for x, vk_id in enumerate(i):
			result[vk_id] = tuple(i for i in r[x]) if r[x] else None
	return result

@app.task
def deep_friends(friends):
	result = {}
	for i in list(parts(friends, 25)):
		r = requests.get(request_url('execute.deepFriends', 'targets=%s' % make_targets(i), access_token=True)).json()["response"]
	
		for x, vk_id in enumerate(i):
			result[vk_id] = tuple(r[x]["items"]) if r[x] else None

	return result

Когда все настроено, запускаем RabbitMQ командой:

rabbitmq-server

Затем переходим в папку проекта и активируем воркера:

celery -A tasks worker --loglevel=info

Теперь, чтобы получить и сохранить список общих или «глубинных» друзей, достаточно скомандовать в консоли:

python3 call.py

О результатах измерений


Напомню, что у автора статьи, которая вдохновила меня на первую часть, 343 друга (запрос на общих друзей) «обрабатывались» за 119 секунд.

Мой вариант из предыдущей статьи делал то же самое за 9 секунд.

Сейчас у того автора другое число друзей — 308. Что же, придется сделать один лишний запрос для последних восьми id, потратить на него драгоценную секунду, хотя за ту же секунду можно обработать 75 id.

С одним воркером работа скрипта заняла 4.2 секунды, с двумя воркерами — 2.2 секунды.

Если 119 округлим до 120, а 2.2 до 2, то мой вариант работает в 60 раз быстрее.

Что касается «глубинных друзей» (друзья моих друзей и так далее + тестируем на другом id, чтобы ждать меньше) — при глубине, равной 2, количество ключей в словаре составило 1 251.

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

Одним воркером время выполнения скрипта — 15.1 секунды, с двумя воркерами — 8.2 секунды.

Таким образом, deep_friends() стал быстрее примерно в 2.18 раза.

Да, не всегда результат такой радужный, иногда ответа на один запрос в ВКонтакте приходится ждать и по 10, и по 20 секунд (хотя частое время выполнения одного задания 1.2 — 1.6 секунд), скорее всего, это связано с нагрузкой на сервис, ведь мы не одни во вселенной.


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

Сохранение результата


Да, есть много графо-ориентированных БД. Если в дальнейшем (а оно так и будет), мы захотим анализировать полученные результаты, то все равно их надо будет где-то хранить до самого анализа, потом эти же результаты выгружать в память и производить с ними какие-нибудь действия. Не вижу смысла использовать какую-нибудь субд, если проект был бы коммерческим и нас интересовало, например, что происходит с графом конкретного пользователя на протяжении времени — то да, тут обязательна графо-ориентированная бд, но, поскольку заниматься анализом будем в «домашних условиях», pickle нам хватит вполне.

Перед сохранением словарей логично будет удалять из них ключи, значения которых None. Это заблокированные или удаленные аккаунты. Проще говоря, эти id будут присутствовать в графе, потому что они есть у кого-то в друзьях, ну а мы сэкономим на количестве ключей в словаре:

def cleaner(dct):
	return {k:v for k, v in dct.items() if v != None}

def save_or_load(myfile, sv, smth=None):
	if sv and smth:
		pickle.dump(smth, open(myfile, "wb"))
	else:
		return pickle.load(open(myfile, "rb"))

Как видно, если мы где-то сохранили результат, то где-то и должны его загрузить, дабы заново не собирать id.

Анализ графа


Чтобы не писать свой велосипед, воспользуемся довольно известным networkx, который сделает за нас всю грязную работу. Больше узнать про networkx вы можете из этой статьи.

pip3 install networkx

Прежде чем начнем анализировать граф, нарисуем его. networkx для этого понадобится matplotlib:

pip3 install matplotlib

Далее нам надо создать сам граф. Вообще, есть 2 пути.

Первый сожрет много оперативной памяти и вашего времени:

def adder(self, node):
	if node not in self.graph.nodes():
		self.graph.add_node(node)

self.graph = nx.Graph()
	for k, v in self.dct.items():
		self.adder(k)
		for i in v:
			self.adder(i)
			self.graph.add_edge(k, i)

И это не автор выжил из ума, нет. Подобный пример приводится на странице университета Райса (Rice University), под заголовком Convert Dictionary Graph Representation into networkx Graph Representation:

def dict2nx(aDictGraph):
    """ Converts the given dictionary representation of a graph, 
    aDictGraph, into a networkx DiGraph (directed graph) representation.   
    aDictGraph is a dictionary that maps nodes to its 
    neighbors (successors):  {node:[nodes]}
    A DiGraph object is returned.
    """
    g = nx.DiGraph()
    for node, neighbors in aDictGraph.items():
        g.add_node(node)  # in case there are nodes with no edges
        for neighbor in neighbors:
            g.add_edge(node, neighbor)
    return g 

Можете поверить мне на слово, граф строился целый вечер, когда в нем было уже более 300 000 вершин, мое терпение лопнуло. Если вы прошли курс на Сoursera по Python от этого университета, то понимаете, о чем я. А я всем на курсе говорил, что не так людей учат, ну да ладно.

Да, приводится пример для ориентированного графа, но суть остается той же — сначала добавляем ключи, делая их вершинами, потом делаем вершинами значения, и то если их еще нет в графе, а потом соединяем их ребрами (в моем варианте).

А второй способ сделает все за секунды:

self.graph = nx.from_dict_of_lists(self.dct)

Код лежит в файле graph.py, чтобы нарисовать граф общих друзей достаточно запустить этот скрипт или же где-нибудь создать экземпляр класса VkGraph(), а затем вызвать его метод draw_graph().

Это граф общих друзей, всего 306 вершин и 2096 ребер. К сожалению, я ни разу не дизайнер (практически все настройки стандартные), но вы всегда сможете стилизовать граф «под себя». Вот пара ссылок:


А сам метод выглядит так:

def draw_graph(self):
	plt.figure(figsize=(19,19), dpi=450,)
	nx.draw(self.graph, node_size=100, cmap=True)
	plt.savefig("%s graph.png" % datetime.now().strftime('%H:%M:%S %d-%m-%Y'))

В итоге вы получаете картинку date graph.png в папке проекта. Не советую рисовать граф для глубинных друзей. При 308 друзьях и глубиной равной 2, в словаре оказалось более 145 000 ключей. А есть ведь еще и значения — кортежи с id, которых вряд ли будет мало.

Долго искал самый малосодержащий друзей профиль в ВКонтакте, хотя тут важнее — друзья-друзей. 10 начальных друзей (1 из них заблокированный и автоматически удалится), при нашей стандартной глубине (2), в словаре насчитывалось 1234 ключа и 517 174 id (из значений). Примерно 419 друзей у одного id. Да, там есть и общие друзья, когда построим граф, мы это поймем:

deep_friends = VkGraph(d_friends_dct)
print('Количество вершин:', deep_friends.graph.number_of_nodes())
print('Количество ребер:', deep_friends.graph.number_of_edges())

Вернет:

Количество вершин: 370341
Количество ребер: 512949

С такими большими данными было бы неплохо поиграться. У networkx очень большой список алгоритмов, которые можно применять к графам. Разберем некоторые из них.

Связный граф

Для начала определим, связный ли у нас граф:

print('Связный граф?', nx.is_connected(deep_friends.graph))

Связный граф — это такой граф, в котором любая пара вершин соединена маршрутом.

Кстати, у того же самого id при глубине, равной 1, вот такой красивый граф, содержащий 1268 вершин и 1329 ребер:

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

Правильный ответ
Давайте разберемся. Сначала берется список друзей, и получается так, что есть у нас id X. Из-за которого граф несвязный. Далее мы делаем запрос на друзей этого X (в глубину ведь). Так вот если у X все друзья скрытые, то будет запись в словаре:

{X:(), ...}

Когда будет строится граф, мы честно добавим вершину X, но никаких ребер у нее не будет. Да, чисто теоретически у вершины X должно быть ребро с вершиной, id которой указан в settings.py, но вы же внимательно читали — мы добавляем только то, что находится в словаре. Следовательно, при глубине, равной 2, мы получим в словаре id, указанный в настройках. И тогда у вершины X появятся ребра.

Будем считать, что у вас не будет такой ситуации, то есть скорее всего вы увидите True.

Диаметр, центр и радиус

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

print('Диамерт графа:', nx.diameter(deep_friends.graph))

Центр графа — это любая вершина, такая, что расстояние от нее до наиболее отдаленной вершины минимально. Центром графа может быть одна вершина или несколько вершин. Или проще. Центр графа — вершина, эксцентриситет (расстояние от этой вершины до самой удаленной от нее) которой равен радиусу.

print('Центр графа:', nx.center(deep_friends.graph))

Вернет список вершин, которые являются центром графа. Не удивляйтесь, если центром окажется id, указанный в settings.py.

Радиус графа — это наименьший из эксцентриситетов всех вершин.

print('Радиус графа:', nx.radius(deep_friends.graph))

Авторитетность или Page Rank

Этот тот самый Page Rank, о котором вы подумали. Как правило, алгоритм используется для веб-страничек или иных документов, связанных ссылками. Чем больше ссылок на страницу, тем она важнее. Но никто не запрещает использовать этот алгоритм для графов. Более точное и подходящее определение позаимствуем из этой статьи:
Авторитетность в социальном графе можно анализировать разными способами. Самый простой — отсортировать участников по количеству входящих ребер. У кого больше — тот больше авторитетен. Такой способ годен для небольших графов. В поиске по Интернету Google в качестве одного из критериев для авторитетности страниц использует PageRank. Он вычисляется при помощи случайного блуждания по графу, где в качестве узлов — страницы, а ребро между узлами — если одна страница ссылается на другую. Случайный блуждатель двигается по графу и время от времени перемещается на случайный узел и начинает блуждание заново. PageRank равен доли пребывания на каком-то узле за все время блуждания. Чем он больше, тем узел более авторитетен.

import operator
print('Page Rank:', sorted(nx.pagerank(deep_friends.graph).items(), key=operator.itemgetter(1), reverse=True))

Коэффициент кластеризации

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

print('Коэффициент кластеризации', nx.average_clustering(deep_friends.graph))

Как видите, нет ничего сложного, и networkx предлагает еще много алгоритмов (автор насчитал 148), которые можно применять к графам. Вам остается лишь выбрать нужный вам алгоритм и вызвать соответствующий метод в файле graph.py.

Итог


Мы сделали распределенную систему, позволяющую собирать и строить граф общих друзей в ВКонтакте, которая работает в 60 раз быстрее (в зависимости от количества воркеров), чем предложенный вариант от Himura, также реализовали новую функцию — запрос всех «глубинных друзей», добавили возможность анализа построенных графов.

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

Это вовсе не предел, будут продолжаться работы по увеличению быстродействия программы.

По-прежнему жду от вас вкусных пулл-реквестов, особенно если вы занимаетесь визуализированием данных. Спасибо за внимание!
Лев Тонких @STLEON
карма
13,0
рейтинг 0,0
Python Developer
Реклама помогает поддерживать и развивать наши сервисы

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

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

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

  • 0
    Лучше уж не pickle, а jsonpickle. После него хотя-бы можно будет данные куда-нибудь выгрузить, например в javaScript какой-нибудь. Или вообще из этого сервис организовать.
    • 0
      Я не против, если есть конкретные предложения — давайте обсудим
      • –1
        Предложения, скорее, на уровне диванного анализа :) Замена pickle на jsonpickle особого труда не составит (но я пока не смогу этим заняться), а уже с json-ом можно творить что угодно.
        • 0
          Спасибо! Обязательно учту.
          • 0
            Пожалуйста! Если будут какие-то вопросы, обращайтесь :)
  • 0
    Неделю назад хотел сделать подобное для расчета закона n-рукопожатий, но раз пишу коммент, а не пост, значит передумал ;)
    Хорошая работа.
    • 0
      Спасибо. Очень приятно.
  • 0
    Мне очень нравится graph-tool.skewed.de/ для анализа графов. Рекомендую.
  • 0
    Я писал подобное приложение на php, закон 7 рукопожатий это закон 5 рукопожатий уже)
    • 0
      Есть люди, не входящие в vk/fb, обычно из-за них продлевают цепочку на два звена в обе стороны.
  • 0
    Такие большие графы возможно удобно было бы анализировать интерактивно, если построить их с помощью d3js. Правда, не уверен, какая будет скорость при тысячах узлов, но на сотнях работает нормально. Там есть зум и прочие вкусности.
  • +1
    Спасибо за интересную статью, взял на вооружение готовые библиотеки что вы советовали :)
    А мы в прошлом семестре подобное на octave/matlab писали (правда реализацию того же PageRank и прочего требовали писать с нуля, матричными операциями и считая eigenvalue/vectors).
    В этом семестре планируем взяться за hadoop, ибо сети для научных исследований будут большими, на одной машине все не просчитать. Хотя я честно говоря фанат пайтона, потому сегодня начал читать как подружить hadoop и python. Или использовать какой нибудь pig latin.
  • 0

    Потратил вечер на то чтобы заюзать этот код. Разочаровался. Проблемы возникли следующие:


    • При установке rabbitmq, он автоматически стартует сервер, а Celery при этом (при незапущенном vhost?) ругается на отсутствие django, что ни разу не способствует дебагу. Но это быстро решилось, хотя и подпортило настрой.
    • Первый запуск упал с каким-то эксепшном. Когда подписал try/catch, выяснилось что VK возвращает ошибки "Too many requests" (может всё-таки стоило допустить возможность такого ответа и выводить что-то типа "нужно больше токенов"?)
    • Запустил celery с ограничением в 2 воркера. Не помогло
    • Запустил celery с ограничением в 1 воркер. Безрезультатно, два запроса getFriends всё равно валятся. В этот момент я понял, что вообще ничего не понимаю.

    Я не понимаю главного — Как во всей этой супер распределенной системе выдерживается интервал между запросами? Может это где-то в rabbitmq или в celery должно настраиваться? Может где-то не хватает time.wait() или "while request_failed: retry()"? У меня всё валится и я не понимаю почему не должно… Ну нету у меня четырех токенов, я готов подождать, но блин, не работает же. Вернуться на первую версию — да, можно, но речь о том что ЭТА не работает. Да, возможно, я не совсем по назначению использую её, но если там всё Настолько Вероятностно и без всякой защиты, есть немалый шанс словить такой вот "Too many requests" на супер масштабном и дофига распределенном запросе, который длится уже долго. И потерять кучу данных.


    И последний пункт, вызывающий у меня негодование. Нет, может я чо не понимаю, но кажется, вы кроме ID в крутом распределенном виде ничего не запрашиваете. То есть собственно информативность вершин графа стремится к нулю. И при этом вы сравниваете быстродействие своей системы с быстродействием моей (у которой в вершинах АВАТАРКА, а алгоритм абсолютно линеен и без хранимых процедур). Короче, ящитаю, что AkelPad качается и устанавливается в 100500 раз быстрее, чем ваш этот TeX Live. Утрировано, но всё-таки, без аватарок (и ДАЖЕ без банального plaintext имени), мой код будет работать никак не в 60 раз медленнее. А если заюзать хранимые процедуры, то и того быстрее будет. Попахивает грязным маркетингом. Фу фу фу.


    Ни разу не хочу сказать, что методы увеличения быстродействия не крутые — они очень крутые и очень перспективны для выкачивании аватарок, но при сравнении, пожалуйста, решайте аналогичные задачи. Немного неприятно когда бесконечно крутые технологии Wolfram представляют тормозными, хотя я в своем исследовании ни строчки не написал для увеличения быстродействия, потому что цель была не в быстродействии, а в результате. Я хотел получить ВИЗУАЛЬНО ИНФОРМАТИВНЫЙ граф, а не получить хоть какие-то данные быстро.


    И я даже хочу отправить няшные пул-реквесты (потому что тоже обожаю Python), но мне мешает непонимание, описанное выше. Я не представляю себе как через эти очереди гарантированно добиться двух запросов в секунду… Вот. А если нельзя, так надо дальше думать же! Плохие инструменты, код небезопасен. Хотя бы костыль вставить какой-нибудь, типа "while request_failed: retry()"...

    • 0
      Привет

      При установке rabbitmq, он автоматически стартует сервер, а Celery при этом (при незапущенном vhost?) ругается на отсутствие django, что ни разу не способствует дебагу. Но это быстро решилось, хотя и подпортило настрой.


      Может у тебя какая-то другая Celery?)

      Первый запуск упал с каким-то эксепшном. Когда подписал try/catch, выяснилось что VK возвращает ошибки «Too many requests» (может всё-таки стоило допустить возможность такого ответа и выводить что-то типа «нужно больше токенов»?)
      Запустил celery с ограничением в 2 воркера. Не помогло
      Запустил celery с ограничением в 1 воркер. Безрезультатно, два запроса getFriends всё равно валятся. В этот момент я понял, что вообще ничего не понимаю.


      Нужно много токенов, об этом было написано. Иначе все равно можно упереться в ограничения от ВК.

      Как во всей этой супер распределенной системе выдерживается интервал между запросами? Может это где-то в rabbitmq или в celery должно настраиваться?


      Не выставлял интервал, но инфу можно найти в манах.

      И при этом вы сравниваете быстродействие своей системы с быстродействием моей (у которой в вершинах АВАТАРКА, а алгоритм абсолютно линеен и без хранимых процедур)


      Аватарку получить — не думаю, что произойдет большая просадка по perfomance. Про хранимки тебе писали в комментах, никто не мешал их заюзать.

      Я хотел получить ВИЗУАЛЬНО ИНФОРМАТИВНЫЙ граф, а не получить хоть какие-то данные быстро.


      Опять же, получить аватарку не проблема

      Ничего не имею против Wolfram, он очень крут, и спасибо за коммент и время
  • 0

    А запарился я, потому что мне показали https://gephi.org
    Давайте всё-таки сделаем нормальную качалку друзей друзей? Я прям очень хочу потыкать этот граф в Gephi

    • 0
      Мне тоже показывали Gephi

      Давайте всё-таки сделаем нормальную качалку друзей друзей?


      Уже давно в планах все переписать и сделать еще быстрее)
  • 0

    Ого, перечитал свою статью, оказывается, 119 секунд — это действительно только getMutural с чистыми ID. У меня было подозрение, что на хабре не бывает негатива, но как-то не щёлкнуло… Моя любовь к необдуманным действиям не знает границ…
    Приношу глубочайшие извинения за наезд, задачи решаются аналогичные. Прошу игнорировать абзацы n-2 и n-1 в сообщении i-2

    • 0
      Ничего, всякое бывает

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