Инструменты для использования vkontakte.ru в (не обязательно) злобных целях

Дурной ты. Попроси в ФСБ админский логин.

список друзей открыт не у всех

Слоупок? Сколько было шума, когда эту фичу вводили. Ну да, можно скрыть до 20 друзей из списка, но мало кто это делает, поэтому влиянием на статистику можно пренебречь.

Я просто зашёл случайно на страницу одного человека, отдалённо знакомого, и увидел в списке «Общие друзья» ровно одного другого человека. И мне стало интересно, каким же образом они связаны. Вручную выбирать общих друзей, просматривать стену абсолютно не интересно, а вот если бы были автоматические инструменты, которые по запросу «связь между X и Y» выдавали бы мне все возможные прямые и косвенные связи (общие друзья, группы, соседние записи на стенах друзей и т.д.).

При этом можно было использовать наличие Y в моём списке друзей, потому что так я вижу больше информации. Из этого вытекает, что инструменты должны работать локально и, желательно, быть свободными, чтобы не стать членом ботнета.

Не знаю насчет вконтакте, вряд-ли там вообще граф хранится в специальной форме какой-то, кроме ссылок на друзей у объекта пользователя. А вообще для хранения и обработки подобных данных у твиттера например используется самописный FlockDB.

>Не знаю насчет вконтакте, вряд-ли там вообще граф хранится в специальной форме какой-то, кроме ссылок на друзей у объекта пользователя.

Ну суть как раз в том, чтобы этот граф каким-нибудь пауком оттуда выгрепать)

Не знаю, возможно ли это за разумное время. Если страничка друзей каждого пользователя весит 20 Кб, то только первый миллион будет 20 Гб весить.
А заполнить в принципе не особо сложно, id - вершина, ребра - id/friend_id, таким образом можно запихивать в любую БД у которой есть нормальный способ хранения графов.

Переделать http://habrahabr.ru/blogs/python/126417/

Полный граф вряд ли интересен ТСу, так как он его не сможет весь просмотреть

Выгрепай) АПИ для этого нет. насколько я знаю. Когда мне нужно было знать насколько честна одна тян, писал скрипт для перебора контактов.

Относительно автоматического определения характера связей сильно сомневаюсь.

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

Можно попробовать написать приложение с использованием API движка.

Собрался проверить теорию шести рукопожатий?

есть такая штука как FOAF - vkontakte.ru ее поддерживает http://www.foaf-project.org/

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

А парсить единственная возможность получить, и это вполне реально. Есть волшебная ссылка чтобы легко получить список друзей.

Я когда озадачивался этим, то у меня парсилка рекурсивно ходила по спискам друзей, и добавляла в очередь новых только если у них вуз из моего города. Использовал berkeley db hash таблицу для хранения id=>friends_list, и berkeley db queue для хранения очереди. На моих 4мбит за ночь обходило 300к идишников. Собственно я 300к только и собрал, потом нашёл приложение о котором писал вначале и забил на сбор. Интересно после какого количества записей bdb стала бы работать непозволительно медленно?

Пока ты думал они список друзей уже закрыли

>Можно попробовать написать приложение с использованием API движка.

Ленивые вы стали. Только LWP! Только хардкор!

> Ну да, можно скрыть до 20 друзей из списка

Сдаётся мне, что ты гонишь. У меня несколько больше чем 20. Зашёл к себе, отлогинился - кроме города и пары последних обновлений аватарки ничего не видно, ни школы-института, ни друзей, ни аудио-видео. Как и должно быть, и как и всегда было. Поэтому какие вы там графы строить собираетесь я хз.

>http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%88%D0%B...

«Специальное приложение («Цепочка друзей — теория шести рукопожатий») позволяет искать цепочки знакомств между пользователями сети»

Пруф? У меня всё как было, можно скрыть только 20.

Можно скрыть отображение страницы друзей ЕМНИП но 6 рандомных друзей на глагне все равно показываться будут. Так что в этом случае может помочь только многократный парсинг глагны

>А заполнить в принципе не особо сложно, id - вершина, ребра - id/friend_id, таким образом можно запихивать в любую БД у которой есть нормальный способ хранения графов.

Нафига графу БД, спрашивается? Можно обычные классические связанные списки использовать. Ну или матрицу. А можно еще GraphBoostLib юзать.

Многократный парсинг одной странички в надежде собрать всех друзей это очень долго.

1. Пишется приложение для вконтакте с доступом к личным данным;

2. Небольшая реклама приложения;

3. ...

4. PROFIT!

http://www.linux.org.ru/jump-message.jsp?msgid=6664038&cid=6664541

ну там, по ссылке, упоминается специально написанное для этого приложение, а я подразумевал что можно собирать «счастливым фермером» или как там оно именуется (мы же злобные цели преследуем)

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

>Нафига графу БД, спрашивается? Можно обычные классические связанные списки использовать. Ну или матрицу. А можно еще GraphBoostLib юзать.
Чтобы его хранить и быстро с ним работать. Социальный граф может занимать пару десятков Гб.

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

Я уже этим занимался. Список друзей открыт не у всех. И да, люди у которых френдов более 9000 портят всю статистику.

> Интересно, а на ВК не могут забанить по IP, если слишком часто посылать запросы с информацией?

Если очень быстро запрашивать странички, то вконтактик начинает показывать живительную капчу. На запросы json лимита не обнаружил :3

>>Нафига графу БД, спрашивается? Можно обычные классические связанные списки использовать. Ну или матрицу. А можно еще GraphBoostLib юзать. Чтобы его хранить и быстро с ним работать.

Чтобы быстро с ним работать, достаточно связанных списков. Всякие БД тормозят по определению.

>Чтобы быстро с ним работать, достаточно связанных списков. Всякие БД тормозят по определению.
Допустим я согласился. Как вы планируете быстро работать с где-то 40-50 Гб данных используя связанные списки? Если вы добавите туда индексы и кэширование, то уже выйдет вполне себе БД.

>>Чтобы быстро с ним работать, достаточно связанных списков. Всякие БД тормозят по определению.

Допустим я согласился. Как вы планируете быстро работать с где-то 40-50 Гб данных используя связанные списки? Если вы добавите туда индексы и кэширование, то уже выйдет вполне себе БД.

1. Зачем индексы в графе?

2. Кэшированием может заниматься ОС.

>Зачем индексы в графе?
Есть связанный список из 1000000 элементов. Нужно найти пользователя с id 778434, не бегать же каждый раз по всему списку? А если там миллионов 50 пользователей, то с учетом того, что на проход одного пользователя при том, что весь список в памяти нужно минимум 4 такта(если данные в списке по-порядку и однообразно, иначе в 2 раза больше где-то), то в худшем случае просто поиск i-го элемента будет занимать 200 миллионов тактов. А если все хранится в одном большом списке, то в память оно не влезет и это займет в 100500 раз больше тактов.
Гораздо более козырно в данном случае для хранения указателей на записи в графе использовать обычный массив, который займет пару десятков мегов памяти. А это и есть индекс. При этом рандомное чтение по id с диска будет тоже быстрым.
Поиск друзей по id пользователя конечно не самая частая операция для домашнего анализа, но если использовать на сервере, то она нужна будет часто. Ну и на стадии заполнения искать каждый раз пользователя в связанном списке будет не самым быстрым процессом.
2. Эта не та задача для которой стоит использовать swap файлы.
П.С.
Под БД я подразумеваю не MySQL, а специальные графоориентированые.

>>Зачем индексы в графе? Есть связанный список из 1000000 элементов. Нужно найти пользователя с id 778434, не бегать же каждый раз по всему списку?

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

Для пользователей ты можешь иметь себе обычную БД.

Но граф хранить в виде связанных списков. БД для него никаким боком не вперлась.

>2. Эта не та задача для которой стоит использовать swap файлы.

Что ты вообще подразумеваешь под кэшированием в данном случае?

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

Для пользователей ты можешь иметь себе обычную БД.

Но граф хранить в виде связанных списков. БД для него никаким боком не вперлась.

Имеет, для графов это звучит как поиск соседей для случайного узла в графе.
Это важно во время заполнения графа. У нас есть 2 пользователя №4524532 и №325132, между ними в графе должно быть ребро, как именно определить адреса по которым в памяти лежат эти вершины?

Что ты вообще подразумеваешь под кэшированием в данном случае?

Я подразумеваю способ работы с 10-20 Гб данных таким образом, чтобы как можно больше актуальных данных находилось в памяти.
П.С.
Хватит называть граф списком. Не все структуры данных в которых узел содержит ссылки на другие узлы называются списками.
На всякий случай матрица здесь не катит совершенно, так как оверхед просто гигантский.

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

Для пользователей ты можешь иметь себе обычную БД.
Но граф хранить в виде связанных списков. БД для него никаким боком >>не вперлась.

Имеет, для графов это звучит как поиск соседей для случайного узла в графе.
Это важно во время заполнения графа. У нас есть 2 пользователя №4524532 и №325132, между ними в графе должно быть ребро, как именно определить адреса по которым в памяти лежат эти вершины?

взять из линейного массива вершин 4524532-й элемент (каждый элемент - это вершина связанного списока, который содержит соседствующие вершины с данной). и пройтись по связанному списку в поиске элемента с индексом 325132. Вуаля!

>>Что ты вообще подразумеваешь под кэшированием в данном случае?

Я подразумеваю способ работы с 10-20 Гб данных таким образом, чтобы как можно больше актуальных данных находилось в памяти.

каких актуальных данных? Тех данных, что чаще всего вызываются? Так это ОС отлично сама сделает.

П.С.

Хватит называть граф списком. Не все структуры данных в которых узел содержит ссылки на другие узлы называются списками.

граф можно (и в большинстве случаев нужно) хранить в виде списков.

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

man sparsed matrix.

>взять из линейного массива вершин 4524532-й элемент (каждый элемент - это вершина связанного списока, который содержит соседствующие вершины с данной). и пройтись по связанному списку в поиске элемента с индексом 325132. Вуаля!
Во-первых линейный массив вершин для связанного списка и есть индекс. Если граф будет большой, то там еще будет хранится смещение относительно начала файла. Во-вторых почему во второй раз не брать элемент из массива?

каких актуальных данных? Тех данных, что чаще всего вызываются? Так это ОС отлично сама сделает.

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

граф можно (и в большинстве случаев нужно) хранить в виде списков.

Нет, граф нужно хранить в виде графа, в котором у каждой вершины есть указатели на соседние. И иметь массив с адресами всех вершин для индексирования. Именно этим и еще всякими умными штуками типа репликации и транзакций и замимаются БД для графов.

man sparsed matrix.

Не катят, слишком разряженная получится, не будет особой разницы между такой матрицей и просто графом.

>>взять из линейного массива вершин 4524532-й элемент (каждый элемент - это вершина связанного списока, который содержит соседствующие вершины с данной). и пройтись по связанному списку в поиске элемента с >индексом 325132. Вуаля! Во-первых линейный массив вершин для связанного списка и есть индекс. Если граф будет большой, то там еще будет хранится смещение относительно начала файла. Во-вторых почему во второй раз не брать элемент из массива?

а как ты определишь, есть ли ребро?

каких актуальных данных? Тех данных, что чаще всего вызываются? Так это ОС отлично сама сделает.

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

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

памяти программа будет постоянно подгружать в память новые страницы из свопа и выгружать старые.

они будут в свопе, если редко будут использоваться. Что и надо.

граф можно (и в большинстве случаев нужно) хранить в виде списков.

Нет, граф нужно хранить в виде графа, в котором у каждой вершины есть указатели на соседние.

это и будет связанный список.

И иметь массив с адресами всех вершин для индексирования. Именно этим и еще всякими умными штуками типа репликации и транзакций и замимаются БД для графов.

вершина - это индекс. Какой может быть адрес у индекса?

man sparsed matrix.

Не катят, слишком разряженная получится, не будет особой разницы между такой матрицей и просто графом.

как раз отлично катят. Пойди еще раз man sparsed matrix прочти.

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

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

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

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

они будут в свопе, если редко будут использоваться. Что и надо.

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

вершина - это индекс. Какой может быть адрес у индекса?

Это было мое недопонимание вашего способа хранения.

как раз отлично катят. Пойди еще раз man sparsed matrix прочти.

Если 1-й юзер добавит себе друга, то это вызовет довольно много пересчетов.

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

нет. Смотри:

Есть четыре списка, на каждый узел по списку:

a->b

b->a->c->d

c->d

d

это говорит о том, что есть ребро (a,b). Так же есть ребра (b,a) (b,c) (b,d). И есть (c,d). А из d вообще никаких ребер нет.

> b->a->c->d
На самом деле же это будет не такой список, а граф b->n1(->a)->n2(->b)->n3(->c)

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

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

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

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

Если тебе полегчает, можешь сразу загружать с диска весь связанный список к вершине. Но к кэшированию это отношения не имеет никакого. Это называется preread.

они будут в свопе, если редко будут использоваться. Что и надо.

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

а ты что хотел? Если все редко используются :)

как раз отлично катят. Пойди еще раз man sparsed matrix прочти.

Если 1-й юзер добавит себе друга, то это вызовет довольно много пересчетов.

с чего это вдруг?

Есть куча методов реализации таких матриц. Один из них - это список списков, что собсно я имею в виду :) Но есть и другие, которые работают не хуже.

>> b->a->c->d

На самом деле же это будет не такой список, а граф b->n1(->a)->n2(->b)->n3(->c)

Перечитай еще раз. Ты опять не так понял. Вот этот граф:


d<-b<->a
↖ ↓
c

форматирование съезжает, но думаю, что понятно.

>не имеет смысла, ибо непонятно на какую глубину надо подгружать. К примеру для поиска пути между двумя вершинами вычисление того, что надо подгружать _уже_ эквивалентно шагу алгоритма.
Вряд-ли, так как подгруа

Если тебе полегчает, можешь сразу загружать с диска весь связанный список к вершине. Но к кэшированию это отношения не имеет никакого. Это называется preread.

Preread это такой вид кэша если что.

с чего это вдруг?

Есть куча методов реализации таких матриц. Один из них - это список списков, что собсно я имею в виду :) Но есть и другие, которые работают не хуже.

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

К слову БД для графов нужны как раз для этих вещей. Это все выглядит просто на маленьких объемах, но у Twitter, которые для этих целей используют вышеупомянутую FlockDb, еще год назад было 13 миллионов связей, если каждая из них - даже 8-х байтный указатель(64-бита система), то эта структура будет занимать 100 Гб. С учетом того, что для такого графа еще желательно знать даты установления связей, то памяти оно отожрет в разы больше.
Если это держать в свопе, то работа с такой структурой данных будет Ъ ад.
П.С.
К слову у них 100к операций чтения и 20к записи в секунду. Но это к делу не относится.

13 миллионов = 13 миллиардов

>Перечитай еще раз. Ты опять не так понял. Вот этот граф:
Я так понял. Это относилось не к тому, что это за граф, а к способу его хранения.