Цепочка общих друзей в ВК

Предположим, необходимо выяснить цепочку общих на друзей от idxxxxxxx до idyyyyyyy. Учитывая, что ВК содержит ~ 140 млн. учетных записей и приблизительно по 100 друзей на каждом аккаунте, то выйдет порядка 14 млрд связей. Такая база займет с учетом сохранения параметров user_id/friend_id порядка 200 Гб дискового пространства, не считая времени затраченного на сбор самой базы.
Дальше, когда база получена можно приступить к поиску взаимосвязей. Но тут нам потребуется строить матрицу 140.000.000х140.000.000 пользователей (связи всех со всеми). Для такой базы потребуется примерно 10к жестких дисков, по 2 Тб. Такое вообще не годится.
Какой вариант будет более-менее подходить для пользовательских мощностей, не прибегая к технике с приставкой "супер"?

 

Я в шоке,это или не чего делать,или жить стало скучно,дядьки я бы хотел на это посмотреть !

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

 

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

 

Ну по крайней мере, если парсить будет по два юзера в секунду, то выходит около двух лет будет идти загрузка.

 

Может облако?
На распределенном кластере с общим виртуальным местом и вычислительной мощностью.

 

А смысл всех парсить? Брать просто два профиля, парсятся только их друзья, и проверяются на общие, потом друзья тех друзей, и так далее. Думаю таких промежутков не будет более 3-4х можно даже ради прикола заказать такую софтину, думаю за пару штук её напишут.

 

ТС, не усложняйте жизнь.
Организуйте онлайн парсинг друзей, определенных ID и будет Вам счастье.

 

как собираешься монитизировать? какие социальные исследования?

была у меня идея сделать такое приложение, но потом увидел что такое уже существует
http://vk.com/fchain
правда сейчас почему то не работает, возможно сервер они отключили, за неуплату к примеру, но работало когда то, пробовал

для поиска все варианты перебирать необязательно, оптимизаций можно придумать множество, первое что на ум приходит
большинство людей в вк будут связаны через людей у которых по 1000-10000 друзей, так что нужно создать базу таких людей, необязательно всех даже брать, можно часть, найти у каждой пары общих друзей, возможно и друзей друзей, а дальше когда нужно выполнить поиск чтобы найти цепочку между 2 ид, искать путь от первого до одного из этих много тысячников, и от второго до много тысячников, скорее всего там путь через одного друга, то есть в друзьях друзей есть такой многотысячник, искать тоже можно на первом шаге у всех друзей, а на втором брать у друзей друзей к примеру по 5 друзей имеющих максимальное количество друзей, так быстрей,

можно использовать то что у людей из одного города чаще всего в друзьях люди из этого города, в рамках города связи довольно короткие, в качестве едра из первого примера использовать не многотысячников, а людей у которых много друзей и в городе А и в городе Б, так бывает когда человек переезжает из одного города в другой, для каждой пары город-город найти таких людей, и уже для 2 искомых ид искать для каждого выход внутри города на одного из них

и ещё если нужно найти общих друзей у 2 человек у которых по 10 000 друзей, то необязательно перебирать все варианты 10 000 х 10 000 = 100 000 000 то есть 100 лямов, можно каждый список разбить на 10 списков в зависимости от последней цифры ид, ид кончающиеся на 1 в первом списке, на 2 во втором и тд. для этого нужен 1 проход списка, сделать его для обоих, и искать общих сравнивая ид кончающиеся на 0 у первого с таким же списком у второго, получается 1000*1000*10=10 000 000 уже 10 лямов, а если разбить на списки в зависимости от двух последних цифр ид, то получится 100 списков, количество вариантов перебора 100*100*100= 1 000 000 уже 1 лям, и так можно перебор сокращать ещё сильно

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

 

да с парсингом ещё не такие огромные проблемы, вот найти все варианты вот это нереальная задача
можно накупить серверов по 5$, там 100мб канал,
или взять 1 гигабит, видел по 100-200 баксов, даже по 50 баксов видел,
чтобы за месяц спарсить нужно парсить по 200млн/30/24/60/60=70 страниц в секунду, незнаю какие там скоростя на гигабитном канале, но если запустить 1000 потоков и каждый будет парсить 1 анкету за 14 сек, то получим 70 анкет в секунду,
по трафику ограничение там в 100 тб, засёк страница со 100 друзьями без картинок весит 50кб, умножаем на 200 млн = 10 тб, тоже влезаем,
будет бан ип скорее всего при таком парсинге, видел некоторые вдс продают по баксу ип до 256 ип, на 1 ип приходится 18 запросов в минуту, вполне нормально,
альтернатива покупка безлимитных авм проксей за 200 баксов (если за них вк не банит), 30000 онлайн (иностранные, поэтому акки брать в виде тел номера), там вообще с запасом нагрузка,
наверное самое трудное найти поставщика акков которые будут нормально жить, если все запросы разделить на 1000 акков, то получится по 4 запроса с акка в минуту, в течении месяца непрерывно, не думаю что за это должны банить, если чередовать активность с акков, просмотр видеороликов с акка больше канал грузит чем это,
но скорее всего такого селлера не найти, вариант активировать самому через сервис активации, но это 10000 руб. можно попробовать сократить количество акков в несколько раз,
есть ещё варинт брать много мелких впс по 100 мбит, по 5 баксов (или бесплатно) и пробовать без прокси,
итого в самом оптимистичном варианте
100$ сервер + 250$ прокси/ип + 200$ акки (авторег)=550$
но сумма может и увеличится в пару раз,
а может и наоборот, если на 100 мбит серве поставить парсинг, и использовать до 350 потоков авм за 100 баксов в месяц, то цена уже падает на 200 баксов, вообщем я не в курсе какой канал сколько подобных потоков может держать,
в любом случае это уже не 10к жестких дисков

базу в таком виде хранить смысла нет, если у тебя 1 или 0 - друг или не друг, у тебя в строчке будет 100 единиц, и 199 999 900 нулей, то есть архивации никакой, все жёсткие диски нулями забьешь
проще для каждого ид хранить список друзей, притом не в виде символов, из 256 значений будешь использовать только 10, а в виде числа, тогда 260 млн помещается в 3.5 байта, а 100 друзей, в 350 байтов, умножаем на 200 млн, итого 70 гигов, это и на ссд влезет,
а вот если найти цепочки от каждого к каждому то действительно места не хватит для хранения, цепочка из 6 друзей весит 6*3.5~20 байтов, 200 млн на 200 млн на 20 байтов 800 000 терабайтов, 400 000 двухтерабайтных дисков, по 100 баксов за штуку 40 млн баксов
я уж не буду считать сколько займет вычисление, мне кажется оно будет на порядки дороже хранения,
возможно что и неосуществимо силами всего человечества,
так что выход только один считать на ходу

 

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

 

Если возможно, дай ссылку на статью.

 

http://habrahabr.ru/post/132558/

 

человек, иди в институт, там тебе расскажут как это сделать незатратно, быстро, и оптимизировано, курсу к 3-4ому, только в нормльный ВУЗ
в москве:
(МИФИ (КиБ факультет), МГУ (ВМК), МФТИ (непомню кафедру), Синергия если бобла много (кафедра интернета))
В спб СПбГУ
Потом будешь просить пощадить

 

а баумана уже не котируется?

а не здесь немного про другое

 

Записная книжка полезных связей ваших друзей
http://vk.com/takepin
http://takepin.com/