LINUX.ORG.RU
ФорумTalks

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


0

1

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

В итоге можно построить полную карту всех социальных связей связей внутри этой социальной сети.

Так вот есть ли хотя бы возможность достать полный граф (не парся миллионы страниц своим кривым питон-скриптом), а ещё лучше вот эти самые инструменты автоматического анализа?

★★★
Ответ на: комментарий от Tark

Хотя даты установления связей конечно стоит держать отдельно.

Tark ★★
()
Ответ на: комментарий от Tark

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

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

который выполнит ОС, ибо считывание будет идти страницами. А тебе надо объяснять, сколько в страницу памяти влезет списков таких в нашем случае?

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

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

ты сам понял, что сказал хоть?

К слову БД для графов нужны как раз для этих вещей. Это все выглядит

Я еще раз повторю: БД для графов не нужны, БД для графов не нужны, БД для графов не нужны, БД для графов не нужны.

К слову у них 100к операций чтения и 20к записи в секунду. Но это к делу не относится.

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

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

Если это держать в свопе, то работа с такой структурой данных будет Ъ ад.

Я еще раз повторяю: свойства вершин и ребер можешь держать где угодно и как угодно. Но для _самого_ графа БД никаким раком не впирается.

dikiy ★★☆☆☆
()
Ответ на: комментарий от Tark

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

Я так понял. Это относилось не к тому, что это за граф, а к способу его хранения.

тогда я в упор не понимаю, что ты имеешь в виду.

dikiy ★★☆☆☆
()
Ответ на: комментарий от dikiy

>который выполнит ОС, ибо считывание будет идти страницами. А тебе надо объяснять, сколько в страницу памяти влезет списков таких в нашем случае?
Который ОС выполнит неправильно, так как вершины френдов хранятся совсем в других местах. Если распределение френдов в памяти равномерное, то размер страницы чем меньше, тем лучше.

Я еще раз повторю: БД для графов не нужны, БД для графов не нужны, БД для графов не нужны, БД для графов не нужны.

Еще раз повторю, вы не отличаете разные модели данных в БД и путаете все с реляционной.

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

Но там именно граф. Суть здесь в том, что ИМЕННО для того, чтобы работать удобно работать с данными, в том числе обеспечивать репликацию и параллельную обработку хоть на сотне компьютеров - нужны специальные БД.

Я еще раз повторяю: свойства вершин и ребер можешь держать где угодно и как угодно. Но для _самого_ графа БД никаким раком не впирается.

Про свойства я уже написал чуть позже. Но итак будет 100 Гб структура, которая должна будет висеть в памяти.

тогда я в упор не понимаю, что ты имеешь в виду.

На это можно забить тогда, там была разница чисто формальная и важного ничего нет.

Tark ★★
()
Ответ на: комментарий от Tark

>>который выполнит ОС, ибо считывание будет идти страницами. А тебе надо объяснять, сколько в страницу памяти влезет списков таких в нашем случае?

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

вершина - это не более чем цифра. Загрузив список, ОС автоматически сразу загрузит и вершины френдов. Ибо это одно и то же.

с такой скоростью использование алгоритмов для графов сразу >становится просто чисто теоретической возможностью. (просисью: это просто фатально медленно для такого большого графа).

Но там именно граф. Суть здесь в том, что ИМЕННО для того, чтобы работать удобно работать с данными, в том числе обеспечивать репликацию и параллельную обработку хоть на сотне компьютеров - нужны специальные БД.

Хорошо, приведу пример: поиск кратчайшего пути от одной вершины к другой - O(n+m) примерно будет O(n) в нашем случае = 50e6. Поделив на 100k, как ты говоришь, получим как минимум 500 секунд. Некисло, правда?

На всякий случай, вот список ненужных имплементаций ненужного. http://en.wikipedia.org/wiki/Graph_database

это базы данных основынные на графах, но не базы данных _для_ графов.

dikiy ★★☆☆☆
()
Ответ на: комментарий от dikiy

>вершина - это не более чем цифра. Загрузив список, ОС автоматически сразу загрузит и вершины френдов. Ибо это одно и то же.
Ну тут уже глубина на которую грузить выбирается программистом.

Хорошо, приведу пример: поиск кратчайшего пути от одной вершины к другой - O(n+m) примерно будет O(n) в нашем случае = 50e6. Поделив на 100k, как ты говоришь, получим как минимум 500 секунд. Некисло, правда?

Ничего не понял, я говорил, про 100k операций в секунду. Но вообще, необязательно искать на полную глубину, иногда достаточно поиск на 4-5 уровней, а это уже вполне разумное время.

это базы данных основынные на графах, но не базы данных _для_ графов.

General graph databases that can store any graph are distinct from specialized graph databases such as triplestores and network databases.


Ну и вообще их именно для этого и применяют. Кроме твиттера, тот же гугл еще например, у него есть такой параметр page rank который определяет вес страницы и он зависит от ссылок на эту страницу, поэтому эти данные у него хранятся в виде распределенного(при том, что у них за трллион страниц перевалило уже 3 года назад, по другому нельзя) графа.

Tark ★★
()
Ответ на: комментарий от Tark

>>вершина - это не более чем цифра. Загрузив список, ОС автоматически сразу загрузит и вершины френдов. Ибо это одно и то же.

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

ну и на какую грузить? А главное, зачем?

Хорошо, приведу пример: поиск кратчайшего пути от одной вершины к другой - O(n+m) примерно будет O(n) в нашем случае = 50e6. Поделив на 100k, как ты говоришь, получим как минимум 500 секунд. Некисло, правда?

Ничего не понял, я говорил, про 100k операций в секунду. Но вообще, необязательно искать на полную глубину, иногда достаточно поиск на 4-5 уровней, а это уже вполне разумное время.

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

Ну и вообще их именно для этого и применяют. Кроме твиттера, тот же гугл еще например, у него есть такой параметр page rank который определяет вес страницы и он зависит от ссылок на эту страницу, поэтому эти данные у него хранятся в виде распределенного(при том, что у них за трллион страниц перевалило уже 3 года назад, по другому нельзя) графа.

и причем здесь сам этот граф?

Можно ли на этом графе с помощью этой БД провести стандартные алгоритмы за вменяемое время? Если нет, то тогда это не БД для графов, а БД, _некоторым образом_ использующая графы.

dikiy ★★☆☆☆
()
Ответ на: комментарий от dikiy

>обязательно. Ибо иначе нельзя найти пути между двумя узлами. А если ты хочешь строить дерево длинной в пять ребер, то вычисление того, что надо подгружать _уже_ будет этим алгоритмом => избыточно.
Не всегда нужен путь между двумя узлами, и тем более не всегда нужен точный. Чтобы просто вывести список людей, кого вы возможно знаете, достаточно глубины в 3-4 слоя. Чтобы определить в какой группе сидит больше всего членов этой группы надо вообще 1 слой.

и причем здесь сам этот граф?

При том, что он как раз и хранится в этой БД, как у твиттера в FlockDB.

Можно ли на этом графе с помощью этой БД провести стандартные алгоритмы за вменяемое время? Если нет, то тогда это не БД для графов, а БД, _некоторым образом_ использующая графы.

А если текст 10Гб и на нем нельзя использовать стандартный алгоритм поиска наибольшей общей подстроки, то это что, не текст чтоли?
Гугловская БД находит все кратчайшие пути из одного источника при 1 миллиарде вершин и 80 миллиарде граней за 200 секунд при распараллеливании на 480 многоядерных компьютеров.

Tark ★★
()
Ответ на: комментарий от Tark

>Гугловская БД находит все кратчайшие пути из одного источника при 1 миллиарде вершин и 80 миллиарде граней за 200 секунд при распараллеливании на 480 многоядерных компьютеров.

Что может говорит о том, что граф хранится отдельно от БД.

и причем здесь сам этот граф?

При том, что он как раз и хранится в этой БД, как у твиттера в FlockDB.

ну хранится и что?

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

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

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

dikiy ★★☆☆☆
()
Ответ на: комментарий от dikiy

>Что может говорит о том, что граф хранится отдельно от БД.
Кхм. Это БД нужна именно и только для графа. Для других данных есть BigTable.

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

FlockDB вообще использует в качестве бэкэнда mysql. Специальная БД поверх нужна для того, чтобы с этим быстро и эффективно работать. Шардинг там всякий, хождение по графу и прочее.

Tark ★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.