Очередная попытка доказать что мир тесен

[ainu]

Добровольцев нет? Или в контакте никто не сидит?

[Ex3NDR]

а у меня всего два рукопожатия))))

[torVALd]

а меня можно потестить?
id7848

[romy4]

клёва, заходите, тестьте: id3710341
ещё бы, если можно, выложите свой JS-ник, хотелось бы его к ФФ прикрутить-погонять. :)

[ainu]

Принято, спасибо, начинаем эксперимент!

[romy4]

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

[paly4]

кстати, может под хабракат?

[Zivaka]

id288968 — интересно :)
вообще пару месяцев назад у меня с Дуровым был общий друг, потом он удалился из контакта…

[ainu]

Готово=) см. Апдейт в посте=) До Дурова не довёл, но доведу обязательно, а вот нас с Вами разделяет 4 рукопожатия. Кстати, до Дурова — уже есть цепочка, но длинноватая, через 10 рукопожатий. Сраните с графом.

[Zivaka]

Если я не ошибаюсь, то до Дурова у мну 3 или 4 рукопожатия.
Прикольно, так как мы с Женей Глазыриным (474078) работали вместе, а Леонид Калентьев также работал когда то в той компании :)

[ainu]

Если порыть глубже, я уверен, есть и более короткие цепочки. Просто сроки у меня сжатые)

[bishop3000]

А почему без автоматического скрипта? Ведь вроде несложно его написать.
Мой: id3624179

[ainu]

Я в курсе. Но это не есть хорошо, такие вещи писать. За это и забанить могут.

[bishop3000]

Забанить? У них вроде правило — не чаще раза в секунду заходить на новую страницу. Если скрипт будет это правило выполнять — разве забанят?
Можно в техподдержку написать — спросить :)

[ainu]

Готово) 4 «рукопожатия» до Дурова.

[bishop3000]

Ого! А путь?

[bishop3000]

А, всё, нашел, что вы его в пост запихали

[anka]

и меня, пожайлуста:) id6798242

[ainu]

Анка Partyzanka Заика(6798242) — Ксения Кондрашова(7855546) — Леся ॐ Pyromancy(1635334) — Сергей Алхимик Невзоров(5046973) — Александр Conqueror Ярошенко(6931374) — Андрей Лопатин(11191) — Павел Дуров(1)
Анка Partyzanka Заика(6798242) — Коля Наумов(11182297) — Persona Grata(4822233) — Максим Чеботаев(11146947) — Александр «SAleX» Сидоров(62691) — Андрей Лопатин(11191) — Павел Дуров(1)

[anka]

Таки с Украиной связь есть:)

[kiroru]

а меня можно еще id48437

[ainu]

Готово… Ко мне Вы ближе, чем к Дурову. По имеющимся связям.

[MindiveR]

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

Только «контакт» не лучший выбор для опытов, нередко «в друзья» добавляют людей, вообще их не зная. Вот для теста очередного скрипта, повышения программерского скилла или составления списка пользователей (а вот с последним будьте аккуратнее, можно попасть) — это можно ;)

з.ы. если не трудно, id674210 :)

[ainu]

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

[ainu]

Ваш список друзей закрыт, извините.

[kiroru]

и ооочень хотелось бы потестить скриптик. Думаю самому написать, но зачем делать одно и тоже, предлагаю вам посильную помощь…

[ainu]

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

[kiroru]

нет, я больше по программированию готов помочь.

[bishop3000]

Кстати, я — программист игр бывший, на поиске путей собаку съел. С удовольствием помогу :)

[leave]

Дейкстра — лучший друг? ;)

[bishop3000]

Не лучший, но пару алгоритмов подкинул :)

[quark]

id7379963

[ainu]

Извините, не вышло

[antyrat]

id5958359

[ainu]

Извините, не получилось. Львов — это далеко.

[lgyanf]

id7490373 :)

[ainu]

Иван Громов(7490373) — Александр dant1st Горбатов(1958232) — Андрей Лопатин(11191) — Павел Дуров(1)

[Lukin]

id633454

[GreenAngel]

Начинание интересное и полезное.
Полезное в том, что поднимает людям настроение и сообщает им полезную информацию.

Но нет необходимости пытаться доказать аксиому)

[Kolger]

Отличный эксперемент! Тоже недавно ломал голову над таким, но к действиям так и не перешел :)

[Kolger]

id210630

[ainu]

Готово) См. апдейт поста.

[to_Okie]

id399912
зы надеюсь опровергну вашу гипотезу)

[ainu]

Извините, список друзей закрыт

[Razdelim_com]

Хороший топик- и главное все остались довольны- и автор и комментаторы, судя по плюсам.
Вот все бы темы так гармонично шли!

[Taxup]

id1516701
буду благодарен)

[ainu]

Готово. 4 рукопожатия

[Taxup]

фигасе… не ожидал… рахмат)

[Xelaan]

id2856612
Очень сомневаюсь, но вдруг…
P.S. Заранее спасибо :)

[ainu]

Александр Наймушин(2856612) — Михаил ]netmisch[ Черных(1479019) — Дмитрий Гозман(1718621) — Андрей Лопатин(11191) — Павел Дуров(1)
Александр Наймушин(2856612) — Алексей Склёмин(4265315) — Наташа Minority Дрыганец(1230612) — Мария Павленко(7543286) — Андрей Лопатин(11191) — Павел Дуров(1)

[Ranedo]

id5355398

[ainu]

Список друзей закрыт

[Lex85]

id5491025

[ainu]

Хмм… Не вышло, извините.

[Lex85]

наверное у меня маловато знакомых((

[tinkk]

id888570 Если до меня дело дойдёт :)

[ainu]

И до Вас дело дошло :)
Нашлась связь между Вами и Rchee (id241410).
Хоть что-то.

[ainu]

Эльвира *Рыжая_Вельха* Хабибулина (можно найти на графе) — Павел Тутубалин — Игорь Hellsing666 Рыбаков — Елизавета Likogra Кондакова — Аня — Леди Лиса — Хурхулу — Даша *without_me* Шевлякова — Сергей t1nkk… Пономаренко
Извините за отсутствие id номеров, времени в обрез, да и бета сырая=)
Смоделировано алгоритмом номер 2, спасибо хабрачеловеку eigrad. Думало 300 секунд.
ОДнако сам факт нахождения цепочки длиной в 9 рукопожатий предполагает возможность создания универсально публичного (вернее, персонального для каждого) скрипта поиска.

[rozboris]

id738345

Попробуйте — у меня достаточно узкий круг друзей(правда, есть среди них и рекордсмены в 500+ френдов)

[ainu]

Получилось, всего три рукопожатия. (см. апдейт)

[rozboris]

Ничего себе! Спасибо за исследование, интересно. Жалко, что это всё-таки «не по правилам» и нельзя нарисовать ОченьБольшойГраф всех пользователей(читай, нельзя сливать всю базу)

[ainu]

Нет. Всё по-честному. Всё на клиенте.
Извините, Ваш список друзей закрыт.

[mberkut]

И меня, и меня тоже :)
id253875

[ainu]

Бектур Мамбетов(253875) — Александр Коломиец(238989) — Света Буйнова(3368) — Полина Богуш(334) — Павел Дуров(1)

[MVM]

Если не сложно..) id6181
спасибо)).

[ainu]

Максим Матвеев(6181) — Сергей Тимошенко(1839656) — Александр «SAleX» Сидоров(62691) — Андрей Лопатин(11191) — Павел Дуров(1)
Максим Матвеев(6181) — Инна Степанова(9451) — Светлана Климичева(822) — Анастасия Желудкова(59) — Павел Дуров(1)

[nrg3]

А как насчёт такого же, но только уже на Хабре и его друзьях ?:) я думаю было б интересно.А так експеремент меня очень удивил, класно вышло :) спасибо за то, что изменили некоторые мои взгляды.

[ainu]

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

[Suomi]

Ну чтож, попробуйте.
id829436

[ainu]

Ваш список друзей закрыт

[Suomi]

Ой, извините, открыл.

[romy4]

инетресно, сколько у кого новых друзей появилось теперь в контакте?

[mzaharenkov]

id175 — одно рукопожатие до Павла Дурова

[maddogrts]

увидел маленький id решил посмотреть, и что вы думаете, у нас есть общие знакомые :))), тесный мир (Мария Воробьева)

[putnik]

Хех. И у меня с вами тоже есть общие знакомые. =)

[VasilioRuzanni]

Интересная тема)
id427647

[ainu]

Готово)
Благодаря Вам обнаружился баг в скрипте (кавычки в нике + кривоватый SQL запрос = ошибка)

[VasilioRuzanni]

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

[DREAM1N]

id842053?25858

[Spirit_Fenix]

интересно стало… только вот народу уже много. надеюсь не обойдете меня стороной)
id5776045

[Devgru]

354639
спасибо, интересно :)

[keatlon]

вот статейка пробегала

www.techcrunch.com/2008/09/03/six-degrees-of-separation-is-now-three/

если вкратце — мир теснее, чем 6 рукопожатий. всего 3

[steck]

Хм, странно.
У нас пусть около 7*10⁹
если мы извлечем корень третьей степени, то получим число знакомых, которых минимально необходимо иметь для покрытия всего земного шара.
У меня получилось 1913 людей. Имхо это несколько больше, чем в среднем количество людей, с которыми нормально общается человек.

[eigrad]

но вполне правдоподобно что с таким количеством людей мы производим хотябы одно рукопожатие за всю жизнь…

[slovar2003]

id1405401

[Elected]

id6721642

[Ingolmo]

id277926

интересно :)

[mishenin]

id6949
Если будет время :)

[ZDN]

vkontakte.ru/id9477

Умираю от любопытства

[maxk]

Мда… Хоть для что-то Вконтакте полезен…

[atreen]

moikrug.ru/ — социальная сеть, основанная на теории о 3 рукопожатиях.
А во вконтакте, да, порой нехватает видения «кругов».

[tauron]

id404582

[lifeforweb]

id575175

[ainu]

Готово)

[lifeforweb]

Спс, пошел писать Тарасу (второй в цепочке) ;-)

[Rchee]

id241410

[ainu]

Хмм… Связь нашлась, но она длиннее, чем 6 человек. Если мне кто-нибудь поможет с алгоритмом, покажу.

[ainu]

Есть путь в 7 рукопожатий до хабрчеловека tinkk (id888570).
Я уверен, есть пути покороче, но на их поиски необходимо время.

[n0s]

Ооо… имя «Дамир» знакомо. Это не тот, про которого на башорге писали?
цитата:
:) ща на форуме нашем человек зарегился, Дамир зовут. e-mail: yesworld@…

[EvilFaeton]

Можно не считать — два рукопожатия до ПВД.
Но, господи, смотрю на хабратопик, вижу знакомые имена/фамилии и втупляю не могу понять чего они на хабре делают. :))

[VEG]

Классная тема :)
id4625479

[sgnppv]

id2551971.

На самом деле такую штуку бы — да вконтакт встроить. Жалкое подобие есть на одноклассниках — там максимум 3(?) «рукопожатия». С другой стороны, это приватность как-то нарушает…

[Sabiko]

Жаль, вас уже так завалили заявками, вручную такой объём вряд ли возьмётесь обрабатывать, а палить вконтакт впустую не хочется. Всё же (надеяться не вредно): id23959.

Интересно, на фейсбуке подобного функционала нет?

[ainu]

Как раз и вручную=) в свободное от работы время.

[tuprikov]

id1562664

[glazs]

Я звезда! Я там два раза!
Смотрите, у меня никнейм в xml-комментарии!

[igeek]

да, чувак, ты крут!

[Trave]

Если дадите структуру БД завтра-послезавтра могу набросать скриптик для поиска кратчайшего пути в графе.

[ainu]

Слил slil.ru/26134283 кусок таблицы (но она должна называться не friends_copy, как в дампе, а friends)

[Trave]

На сколько я разбираюсь в БД то вам крайне желательно удалить ключевое поле(зачем оно?) и создать индекс по myid. так же name можно вынести в отдельную таблицу чтоб не было дублирующихся данных и таблица связей работала быстрей.

мой скриптик:
протестировал на 4000000 базе с рандомными значениями. цепочку глубиной в 10 и общим количеством участников ~350 прошло за 0.07 секунды на моем сервере.
Количество запросов к БД = количеству просматриваемых уровней.
Если не заработает буду рад разобраться и помочь. критика, вопросы, советы — велком!

[ainu]

myid и frid повторяются, нельзя их делать ключевыми.
А насчёт name — это правильно, спасибо. Небольшой минус в том, что просто при просмотре страницы контакта проводится запись в базу, и на страницах размером в 500 контактов чувствуются ощутимые тормоза. При таком подходе они удвоятся.
А скриптик сейчас посмотрим, спасибо.

[Trave]

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

[ainu]

Честно говоря, удивлён скоростью работы, спасибо!
Чудеса просто.
2-3 секунды на моей 200 000 базе.
Есть 2 пожелания, если сумеете реализовать (я тоже попробую, надеюсь, сумею сделать, не испортив скорости).
1. Список друзей человека это не только все frid одного myid, но и все myid одного frid. Это важно, например, чтобы друзей Дурова находить (а список его друзей закрыт, например, 888570->1 работает на «ура», а наоборот, 1->888570 вылетает с предупреждением о пустом результате (mysql_fetch_array(): supplied argument is not a valid MySQL result resource in Z:\home\priem\www\graf3.0.php on line 83).
2. Надо уметь закрывать пути через определённых людей, запрещая их.

[ainu]

1-й пункт сделал сам.

[Trave]

второй пункт не понял что вы имеете в виду. привидите пример.
2-3 секунды это очень много на такой базе(или цепочка была очень длинная?). сделайте индекс на frid и myid и вынесете имя в отдельную таблицу — уверен скорость увеличиться в разы. добавление новых записей будет немного медленне, но если у вас не граббер который делает это в режиме постоянного сканирования, то вы этого не ощутите.

[ainu]

2-й тоже. Вероятно, кривовато, но на скорости сказывается слабо:
После загрузки списка друзей,
for($i=0;$i<=count($zapret)-1;$i++)
{
unset ($friends[$zapret[$i]]);
}

[Trave]

foreach($zapret as $key) {
unset ($friends[$key]);
}

[uzurpator]

а я через одного друга знаком
id1019587

[neon4ig]

id2415323

[ainu]

Закрыт список друзей и страница. Извиняйте.

[Timon]

Готов стать добровольцем :)

id222737

[ainu]

Готово. Правда, только 8 шагов.

[Timon]

Спасибо.

[ainu]

Альтернатива
Тимур Timurka Тазетдинов(222737) — Мария Чернышева(14335577) — Татьяна Яикина(1072856) — Наталья Ульянкова(119648) — Андрей Gottfried Белоус(696) — Анастасия Желудкова(59) — Павел Дуров(1)

[vadimz]

Готов вступить в ряды. id5415769

[chip]

Надо скрипт в общее использование, с веб-интерфейсом, вводишь id от кого, и id до кого, скрипт считает и выводит граф) красота была б)

[ainu]

Будет алгоритм — будет и скрипт.

[ainu]

Вот текущий алгоритм (только 4 рукопожатия): ramainen.ru/i/download/graf.php.txt

[Barefoot]

очень круто!
id1795320

[DobroeZlo]

а кто такой Павел Дуров? о_О

[DobroeZlo]

anyway 71428

[DobroeZlo]

ошибся
id3549759

[ainu]

Самая последняя ссылка (внизу любой страницы контакта)

[DobroeZlo]

хехехе… не знал =)

[Alder]

добровольцы++ :)
id3981543

[alias]

Поставьте апдейты под хабракат, чтоли…

[ainu]

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

[vat]

id2245179
:)

[eigrad]

Поиск пути на невзвешанном графе в 20млн вершин эт простой поиск волной:

N вершин (N < 20 млн. — допустим у нас стока народу вконтакте)

Есть очередь вершин в которые мы собираемся идти и массив из N элементов где отмечаем в каких вершинах были. Изначально массив забит нулями, единицей отмечена только начальная вершина, а в очереди только начальная вершина.

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

Массив из 20млн. байт — 20 МБ. Очередь (каждая вершина побывает в очереди <= 1 раза) <= 20Мб…

Помоему работает за t(N)…

Собственно всё…

[eigrad]

Кстати предположив что у каждого примерно по 100-200 друзей и с каждым из них от 10 до 50 общих друзей можно оценить диаметр нашего графа… Только, извините, мне лень)))

[eigrad]

vkontakte.ru/id1174706

[ainu]

Андрей GrAd Григорьев(1174706) — Витя «Царь_Овощей» Кудрявцев(31839) — Вячеслав Евгеньевич _S Швед(1693471) — Андрей Лопатин(11191) — Павел Дуров(1)

[ainu]

Идея, безусловно, красивая, да вот на практик уж очень туго работает. Долго.
Каждое t (которых N) делает запрос к базе данных. К приличной базе данных.

[eigrad]

Можно распараллелить и запросы к базе данных слать заранее (например при добавлении друзей в очередь)

[eigrad]

Еще сам запрос продумать… Можно сразу друзей второго круга например получать одной транзакцией… 5 секунд это если одним запросом? или несколькими?

[ainu]

5 секунд это максимум, при заторможенной системе. В среднем около 0.4 — 0.1 секунды идёт, иногда быстрее.
SELECT * from where id in (select ...) очень долго работает, такчто отпадает сразу.
Параллелить php не умею. Скрипт очень долгоо работал, выход нашёлся в модифицировании проверки искомого человека.
Проверяется не с искомыы человеком, а последовательно со списком его друзей.
Связи через 9-х человек ищет на ура, в этом Вам огромное спасибо. Более длинные цепочки не укладываются в 400 секунд.
Такое время выполнения и не позволяет селать скрипт публичным.
Так что скоро просто выложу сам скрипт поиска, у каждого своя персональная маленькая база будет.
Ну и соответственно, их объединять можно будет между пользователями в единую базу.

[eigrad]

Вернее просто при добавлении друзей в очередь получать список их друзей (для каждого друга) одним запросом…

[ainu]

Учтите, список его друзей закрыт. Но (!) он открыт у его друзей. Так что первоначальные 5 человек его первого круга пришлось искать «на шару». Их можно по пальцам пересчитать. Перечислите 20 друзей Павла Дурова — сниму шляпу)

[Jaco]

id39525

[ainu]

Виктор Новосельцев(39525) — Владимир Марченко(39643) — Андрей Дельфин Лысиков(3028766) — Эээ www.ED-WIN.com Altergott(99295) — Иван Говнов(4289) — Александр Викторович Беспалов(17) — Павел Дуров(1)

[Captcha]

Ну хоть на что-то вконтакт сгодится.

[GKelpi]

Ну вот, значит скоро спамеры соберут id и заспамят всех)))
Сомнительная затея, т.к. у id № 1 друзей многовато.

[ainu]

Перечислите 10-х? Они закрыты, смотрите сами vkontakte.ru/friend.php? id=1

[EvilFaeton]

По ссылке 310 человек друзей ПВД. По моему вписывается в понятие многовато.

[ainu]

Значит вы друг второго круга. Я ничего не вижу и ничего не могу с этим поделать.

[EvilFaeton]

А, черт, вы правы не принял это во внимание. =/

[EvilFaeton]

Кстати, сей сайт видели: vkontakte.net.ru/
На заре контакта его сделали, не знаю ли он функционирует в полной мере в данный момент.

[ainu]

Он и был вдохновителем=) Красивая задумка и реализация, хотя и с багами.

[GKelpi]

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

[leningradka]

давайте попробуем, интересно как именно:)
id881540

[ainu]

У Вас список друзей закрыт(

[madhat]

Dijkstra@Home? ;)

id10391770

[zemlanin]

А ну-ка, найди меня. 6821354

[ainu]

Нашёл=) Не до Дурова, но до меня. До Дурова можете провести дорожку сами, по графу.

[zemlanin]

Да мне до Дурова плевать:)
P.S. Мне кажется, что когда человек представляется ником, можно на «ты».

[Entropius]

А если по-пробовать со мной? 791406

[ainu]

Александр Entropius Комков(791406) — Денис Бирюков(3900553) — Полина Кузовкова(910092)—
Дмитрий Гребенщиков(13834) — Roman POMEO~xfl~ Zhirnov(28339) — Maria Ignatina(64184) — Митенька Миронов(70) — Александр Викторович Беспалов(17) — Павел Дуров(1)

Александр Entropius Комков(791406) — Женько Dark_Veter Ветров(5481757) — Анастасия Сулакова(182630)—
Лариса Пчельникова(2676506) — Юния [тихо] Куковякина(1111870) — Дамир ainu Фахрутдинов(2416637)[Я]

[ainu]

Да, спасибо eigrad за алгоритм.

[dnska]

И мне интересно :)) 107182

[Richard_Ferlow]

У Дурова там друзей — немеряно :) Так что как там и водится, не факт, что он хотя бы половину знает =)

[ainu]

Прошу прощения, если кого-то пропустил! Просьб было много, некоторые закрыли списки друзей, некоторых найти не удалось. Итак, смотрим граф.
Всем спасибо. Подготавливается публичный (вернее, персональный) скрипт.

[botnet]

классный скрипт! А когда ожидать релиз? Можно ли его сделать для firefox и оформить в виде скриптов на userscripts.org?

[ainu]

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

[zagir]

1022123 пожалуйста :)

[hemper]

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

[ainu]

уже нет, скрипт нерабочий, т.к. вконтакте смнили (и не раз) структуру внетренюю.
Логику работы могу сказать и так:
при просмотре страницы со списком друзей любого человека браузер с помощью UserJS (GreaseMonkey для ФФ) сохранял текущий список (отправляя через iframe на локальную страницу, обрабатываемую локлальным apache+php). Таким образом собиралась база.
Затем банальными sql запросами строились списки людей. Алгоритмы поиска в ширину по таким базам лучше искать самостоятельно, информация есть.

[hemper]

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