Comments 185
Добровольцев нет? Или в контакте никто не сидит?
+2
клёва, заходите, тестьте: id3710341
ещё бы, если можно, выложите свой JS-ник, хотелось бы его к ФФ прикрутить-погонять. :)
ещё бы, если можно, выложите свой JS-ник, хотелось бы его к ФФ прикрутить-погонять. :)
+4
id288968 — интересно :)
вообще пару месяцев назад у меня с Дуровым был общий друг, потом он удалился из контакта…
вообще пару месяцев назад у меня с Дуровым был общий друг, потом он удалился из контакта…
+1
А почему без автоматического скрипта? Ведь вроде несложно его написать.
Мой: id3624179
Мой: id3624179
+2
Я в курсе. Но это не есть хорошо, такие вещи писать. За это и забанить могут.
+2
Готово) 4 «рукопожатия» до Дурова.
+2
и меня, пожайлуста:) id6798242
+2
Анка Partyzanka Заика(6798242) — Ксения Кондрашова(7855546) — Леся ॐ Pyromancy(1635334) — Сергей Алхимик Невзоров(5046973) — Александр Conqueror Ярошенко(6931374) — Андрей Лопатин(11191) — Павел Дуров(1)
Анка Partyzanka Заика(6798242) — Коля Наумов(11182297) — Persona Grata(4822233) — Максим Чеботаев(11146947) — Александр «SAleX» Сидоров(62691) — Андрей Лопатин(11191) — Павел Дуров(1)
Анка Partyzanka Заика(6798242) — Коля Наумов(11182297) — Persona Grata(4822233) — Максим Чеботаев(11146947) — Александр «SAleX» Сидоров(62691) — Андрей Лопатин(11191) — Павел Дуров(1)
0
а меня можно еще id48437
+2
«Шесть рукопожатий» действуют не всегда. Но мир и правда тесен: не раз убеждался и сам, что среди знакомых моих знакомых находится люди множества умений и профессий.
Только «контакт» не лучший выбор для опытов, нередко «в друзья» добавляют людей, вообще их не зная. Вот для теста очередного скрипта, повышения программерского скилла или составления списка пользователей (а вот с последним будьте аккуратнее, можно попасть) — это можно ;)
з.ы. если не трудно, id674210 :)
Только «контакт» не лучший выбор для опытов, нередко «в друзья» добавляют людей, вообще их не зная. Вот для теста очередного скрипта, повышения программерского скилла или составления списка пользователей (а вот с последним будьте аккуратнее, можно попасть) — это можно ;)
з.ы. если не трудно, id674210 :)
+3
и ооочень хотелось бы потестить скриптик. Думаю самому написать, но зачем делать одно и тоже, предлагаю вам посильную помощь…
+2
Помощь нужна от людей, понимающих, что такое графы и оптимизация, нахождение кратчайших путей.
+2
id7379963
+1
id5958359
+1
id7490373 :)
0
id633454
0
Начинание интересное и полезное.
Полезное в том, что поднимает людям настроение и сообщает им полезную информацию.
Но нет необходимости пытаться доказать аксиому)
Полезное в том, что поднимает людям настроение и сообщает им полезную информацию.
Но нет необходимости пытаться доказать аксиому)
+2
Отличный эксперемент! Тоже недавно ломал голову над таким, но к действиям так и не перешел :)
+1
id399912
зы надеюсь опровергну вашу гипотезу)
зы надеюсь опровергну вашу гипотезу)
0
Хороший топик- и главное все остались довольны- и автор и комментаторы, судя по плюсам.
Вот все бы темы так гармонично шли!
Вот все бы темы так гармонично шли!
+2
id1516701
буду благодарен)
буду благодарен)
0
id2856612
Очень сомневаюсь, но вдруг…
P.S. Заранее спасибо :)
Очень сомневаюсь, но вдруг…
P.S. Заранее спасибо :)
0
id5355398
0
id5491025
0
id888570 Если до меня дело дойдёт :)
0
И до Вас дело дошло :)
Нашлась связь между Вами и Rchee (id241410).
Хоть что-то.
Нашлась связь между Вами и Rchee (id241410).
Хоть что-то.
0
Эльвира *Рыжая_Вельха* Хабибулина (можно найти на графе) — Павел Тутубалин — Игорь Hellsing666 Рыбаков — Елизавета Likogra Кондакова — Аня — Леди Лиса — Хурхулу — Даша *without_me* Шевлякова — Сергей t1nkk… Пономаренко
Извините за отсутствие id номеров, времени в обрез, да и бета сырая=)
Смоделировано алгоритмом номер 2, спасибо хабрачеловеку eigrad. Думало 300 секунд.
ОДнако сам факт нахождения цепочки длиной в 9 рукопожатий предполагает возможность создания универсально публичного (вернее, персонального для каждого) скрипта поиска.
Извините за отсутствие id номеров, времени в обрез, да и бета сырая=)
Смоделировано алгоритмом номер 2, спасибо хабрачеловеку eigrad. Думало 300 секунд.
ОДнако сам факт нахождения цепочки длиной в 9 рукопожатий предполагает возможность создания универсально публичного (вернее, персонального для каждого) скрипта поиска.
0
id738345
Попробуйте — у меня достаточно узкий круг друзей(правда, есть среди них и рекордсмены в 500+ френдов)
Попробуйте — у меня достаточно узкий круг друзей(правда, есть среди них и рекордсмены в 500+ френдов)
0
UFO just landed and posted this here
UFO just landed and posted this here
И меня, и меня тоже :)
id253875
id253875
0
Если не сложно..) id6181
спасибо)).
спасибо)).
0
А как насчёт такого же, но только уже на Хабре и его друзьях ?:) я думаю было б интересно.А так експеремент меня очень удивил, класно вышло :) спасибо за то, что изменили некоторые мои взгляды.
0
инетресно, сколько у кого новых друзей появилось теперь в контакте?
+1
id175 — одно рукопожатие до Павла Дурова
+2
Интересная тема)
id427647
id427647
0
id842053?25858
-1
интересно стало… только вот народу уже много. надеюсь не обойдете меня стороной)
id5776045
id5776045
0
354639
спасибо, интересно :)
спасибо, интересно :)
0
вот статейка пробегала
www.techcrunch.com/2008/09/03/six-degrees-of-separation-is-now-three/
если вкратце — мир теснее, чем 6 рукопожатий. всего 3
www.techcrunch.com/2008/09/03/six-degrees-of-separation-is-now-three/
если вкратце — мир теснее, чем 6 рукопожатий. всего 3
+4
Хм, странно.
У нас пусть около 7*109
если мы извлечем корень третьей степени, то получим число знакомых, которых минимально необходимо иметь для покрытия всего земного шара.
У меня получилось 1913 людей. Имхо это несколько больше, чем в среднем количество людей, с которыми нормально общается человек.
У нас пусть около 7*109
если мы извлечем корень третьей степени, то получим число знакомых, которых минимально необходимо иметь для покрытия всего земного шара.
У меня получилось 1913 людей. Имхо это несколько больше, чем в среднем количество людей, с которыми нормально общается человек.
0
id1405401
0
id6721642
0
id277926
интересно :)
интересно :)
0
id6949
Если будет время :)
Если будет время :)
0
UFO just landed and posted this here
vkontakte.ru/id9477
Умираю от любопытства
Умираю от любопытства
0
Мда… Хоть для что-то Вконтакте полезен…
0
UFO just landed and posted this here
moikrug.ru/ — социальная сеть, основанная на теории о 3 рукопожатиях.
А во вконтакте, да, порой нехватает видения «кругов».
А во вконтакте, да, порой нехватает видения «кругов».
0
id404582
0
id575175
0
id241410
0
Ооо… имя «Дамир» знакомо. Это не тот, про которого на башорге писали?
цитата:
:) ща на форуме нашем человек зарегился, Дамир зовут. e-mail: yesworld@…
цитата:
:) ща на форуме нашем человек зарегился, Дамир зовут. e-mail: yesworld@…
+1
Можно не считать — два рукопожатия до ПВД.
Но, господи, смотрю на хабратопик, вижу знакомые имена/фамилии и втупляю не могу понять чего они на хабре делают. :))
Но, господи, смотрю на хабратопик, вижу знакомые имена/фамилии и втупляю не могу понять чего они на хабре делают. :))
+1
Классная тема :)
id4625479
id4625479
0
id2551971.
На самом деле такую штуку бы — да вконтакт встроить. Жалкое подобие есть на одноклассниках — там максимум 3(?) «рукопожатия». С другой стороны, это приватность как-то нарушает…
На самом деле такую штуку бы — да вконтакт встроить. Жалкое подобие есть на одноклассниках — там максимум 3(?) «рукопожатия». С другой стороны, это приватность как-то нарушает…
+1
Жаль, вас уже так завалили заявками, вручную такой объём вряд ли возьмётесь обрабатывать, а палить вконтакт впустую не хочется. Всё же (надеяться не вредно): id23959.
Интересно, на фейсбуке подобного функционала нет?
Интересно, на фейсбуке подобного функционала нет?
0
id1562664
0
Я звезда! Я там два раза!
Смотрите, у меня никнейм в xml-комментарии!
Смотрите, у меня никнейм в xml-комментарии!
+2
UFO just landed and posted this here
Если дадите структуру БД завтра-послезавтра могу набросать скриптик для поиска кратчайшего пути в графе.
0
Слил slil.ru/26134283 кусок таблицы (но она должна называться не friends_copy, как в дампе, а friends)
0
На сколько я разбираюсь в БД то вам крайне желательно удалить ключевое поле(зачем оно?) и создать индекс по myid. так же name можно вынести в отдельную таблицу чтоб не было дублирующихся данных и таблица связей работала быстрей.
мой скриптик:
протестировал на 4000000 базе с рандомными значениями. цепочку глубиной в 10 и общим количеством участников ~350 прошло за 0.07 секунды на моем сервере.
Количество запросов к БД = количеству просматриваемых уровней.
Если не заработает буду рад разобраться и помочь. критика, вопросы, советы — велком!
мой скриптик:
протестировал на 4000000 базе с рандомными значениями. цепочку глубиной в 10 и общим количеством участников ~350 прошло за 0.07 секунды на моем сервере.
Количество запросов к БД = количеству просматриваемых уровней.
Если не заработает буду рад разобраться и помочь. критика, вопросы, советы — велком!
+1
myid и frid повторяются, нельзя их делать ключевыми.
А насчёт name — это правильно, спасибо. Небольшой минус в том, что просто при просмотре страницы контакта проводится запись в базу, и на страницах размером в 500 контактов чувствуются ощутимые тормоза. При таком подходе они удвоятся.
А скриптик сейчас посмотрим, спасибо.
А насчёт name — это правильно, спасибо. Небольшой минус в том, что просто при просмотре страницы контакта проводится запись в базу, и на страницах размером в 500 контактов чувствуются ощутимые тормоза. При таком подходе они удвоятся.
А скриптик сейчас посмотрим, спасибо.
0
Честно говоря, удивлён скоростью работы, спасибо!
Чудеса просто.
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. Надо уметь закрывать пути через определённых людей, запрещая их.
Чудеса просто.
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. Надо уметь закрывать пути через определённых людей, запрещая их.
0
1-й пункт сделал сам.
0
второй пункт не понял что вы имеете в виду. привидите пример.
2-3 секунды это очень много на такой базе(или цепочка была очень длинная?). сделайте индекс на frid и myid и вынесете имя в отдельную таблицу — уверен скорость увеличиться в разы. добавление новых записей будет немного медленне, но если у вас не граббер который делает это в режиме постоянного сканирования, то вы этого не ощутите.
2-3 секунды это очень много на такой базе(или цепочка была очень длинная?). сделайте индекс на frid и myid и вынесете имя в отдельную таблицу — уверен скорость увеличиться в разы. добавление новых записей будет немного медленне, но если у вас не граббер который делает это в режиме постоянного сканирования, то вы этого не ощутите.
0
2-й тоже. Вероятно, кривовато, но на скорости сказывается слабо:
После загрузки списка друзей,
for($i=0;$i<=count($zapret)-1;$i++)
{
unset ($friends[$zapret[$i]]);
}
После загрузки списка друзей,
for($i=0;$i<=count($zapret)-1;$i++)
{
unset ($friends[$zapret[$i]]);
}
0
а я через одного друга знаком
id1019587
id1019587
0
id2415323
0
Готов стать добровольцем :)
id222737
id222737
0
Готов вступить в ряды. id5415769
0
Надо скрипт в общее использование, с веб-интерфейсом, вводишь id от кого, и id до кого, скрипт считает и выводит граф) красота была б)
+1
Будет алгоритм — будет и скрипт.
0
Вот текущий алгоритм (только 4 рукопожатия): ramainen.ru/i/download/graf.php.txt
0
очень круто!
id1795320
id1795320
0
UFO just landed and posted this here
а кто такой Павел Дуров? о_О
+3
добровольцы++ :)
id3981543
id3981543
0
Поставьте апдейты под хабракат, чтоли…
0
id2245179
:)
:)
0
Поиск пути на невзвешанном графе в 20млн вершин эт простой поиск волной:
N вершин (N < 20 млн. — допустим у нас стока народу вконтакте)
Есть очередь вершин в которые мы собираемся идти и массив из N элементов где отмечаем в каких вершинах были. Изначально массив забит нулями, единицей отмечена только начальная вершина, а в очереди только начальная вершина.
На каждом шаге берем одну вершину из очереди, добавляем ее детей в которых еще небыли и пишем единички в элементах массива им соответствующих. Заодно сравниваем с номером конечной вершины. Можем в массив вместо единичек писать расстояние до начальной (что обычно и делается). Можно в дополнительный массив писать данные для трассировки — номер вершины из которой мы пришли.
Массив из 20млн. байт — 20 МБ. Очередь (каждая вершина побывает в очереди <= 1 раза) <= 20Мб…
Помоему работает за t(N)…
Собственно всё…
N вершин (N < 20 млн. — допустим у нас стока народу вконтакте)
Есть очередь вершин в которые мы собираемся идти и массив из N элементов где отмечаем в каких вершинах были. Изначально массив забит нулями, единицей отмечена только начальная вершина, а в очереди только начальная вершина.
На каждом шаге берем одну вершину из очереди, добавляем ее детей в которых еще небыли и пишем единички в элементах массива им соответствующих. Заодно сравниваем с номером конечной вершины. Можем в массив вместо единичек писать расстояние до начальной (что обычно и делается). Можно в дополнительный массив писать данные для трассировки — номер вершины из которой мы пришли.
Массив из 20млн. байт — 20 МБ. Очередь (каждая вершина побывает в очереди <= 1 раза) <= 20Мб…
Помоему работает за t(N)…
Собственно всё…
+1
Кстати предположив что у каждого примерно по 100-200 друзей и с каждым из них от 10 до 50 общих друзей можно оценить диаметр нашего графа… Только, извините, мне лень)))
0
Идея, безусловно, красивая, да вот на практик уж очень туго работает. Долго.
Каждое t (которых N) делает запрос к базе данных. К приличной базе данных.
Каждое t (которых N) делает запрос к базе данных. К приличной базе данных.
0
Можно распараллелить и запросы к базе данных слать заранее (например при добавлении друзей в очередь)
+1
Еще сам запрос продумать… Можно сразу друзей второго круга например получать одной транзакцией… 5 секунд это если одним запросом? или несколькими?
0
5 секунд это максимум, при заторможенной системе. В среднем около 0.4 — 0.1 секунды идёт, иногда быстрее.
SELECT * from where id in (select ...) очень долго работает, такчто отпадает сразу.
Параллелить php не умею. Скрипт очень долгоо работал, выход нашёлся в модифицировании проверки искомого человека.
Проверяется не с искомыы человеком, а последовательно со списком его друзей.
Связи через 9-х человек ищет на ура, в этом Вам огромное спасибо. Более длинные цепочки не укладываются в 400 секунд.
Такое время выполнения и не позволяет селать скрипт публичным.
Так что скоро просто выложу сам скрипт поиска, у каждого своя персональная маленькая база будет.
Ну и соответственно, их объединять можно будет между пользователями в единую базу.
SELECT * from where id in (select ...) очень долго работает, такчто отпадает сразу.
Параллелить php не умею. Скрипт очень долгоо работал, выход нашёлся в модифицировании проверки искомого человека.
Проверяется не с искомыы человеком, а последовательно со списком его друзей.
Связи через 9-х человек ищет на ура, в этом Вам огромное спасибо. Более длинные цепочки не укладываются в 400 секунд.
Такое время выполнения и не позволяет селать скрипт публичным.
Так что скоро просто выложу сам скрипт поиска, у каждого своя персональная маленькая база будет.
Ну и соответственно, их объединять можно будет между пользователями в единую базу.
0
Вернее просто при добавлении друзей в очередь получать список их друзей (для каждого друга) одним запросом…
0
UFO just landed and posted this here
id39525
-1
Виктор Новосельцев(39525) — Владимир Марченко(39643) — Андрей Дельфин Лысиков(3028766) — Эээ www.ED-WIN.com Altergott(99295) — Иван Говнов(4289) — Александр Викторович Беспалов(17) — Павел Дуров(1)
0
Ну хоть на что-то вконтакт сгодится.
-1
Ну вот, значит скоро спамеры соберут id и заспамят всех)))
Сомнительная затея, т.к. у id № 1 друзей многовато.
Сомнительная затея, т.к. у id № 1 друзей многовато.
0
Перечислите 10-х? Они закрыты, смотрите сами vkontakte.ru/friend.php? id=1
0
По ссылке 310 человек друзей ПВД. По моему вписывается в понятие многовато.
-1
Значит вы друг второго круга. Я ничего не вижу и ничего не могу с этим поделать.
+1
А, черт, вы правы не принял это во внимание. =/
0
Кстати, сей сайт видели: vkontakte.net.ru/
На заре контакта его сделали, не знаю ли он функционирует в полной мере в данный момент.
На заре контакта его сделали, не знаю ли он функционирует в полной мере в данный момент.
0
Они были закрыты не всегда, а потом Павел, это по сути техподдержка, а друзей у техподдержки всегда много.
Я говорю о фиктивности социальной связи типа «Друг», это сбивает теорию о рукопожатиях, при желании будет вам и два и одно рукопожатие.
Я говорю о фиктивности социальной связи типа «Друг», это сбивает теорию о рукопожатиях, при желании будет вам и два и одно рукопожатие.
0
давайте попробуем, интересно как именно:)
id881540
id881540
0
Dijkstra@Home? ;)
id10391770
id10391770
0
А ну-ка, найди меня. 6821354
-2
А если по-пробовать со мной? 791406
0
Александр 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)[Я]
Дмитрий Гребенщиков(13834) — Roman POMEO~xfl~ Zhirnov(28339) — Maria Ignatina(64184) — Митенька Миронов(70) — Александр Викторович Беспалов(17) — Павел Дуров(1)
Александр Entropius Комков(791406) — Женько Dark_Veter Ветров(5481757) — Анастасия Сулакова(182630)—
Лариса Пчельникова(2676506) — Юния [тихо] Куковякина(1111870) — Дамир ainu Фахрутдинов(2416637)[Я]
+1
И мне интересно :)) 107182
0
У Дурова там друзей — немеряно :) Так что как там и водится, не факт, что он хотя бы половину знает =)
0
классный скрипт! А когда ожидать релиз? Можно ли его сделать для firefox и оформить в виде скриптов на userscripts.org?
0
1022123 пожалуйста :)
0
Дамир, вы бы не могли выложить куда-то алгоритм, а то топик уже старый и ссылки не работают, а мне очень интересно посмотреть реализацию.
Буду очень признателен, спасибо!
Буду очень признателен, спасибо!
0
уже нет, скрипт нерабочий, т.к. вконтакте смнили (и не раз) структуру внетренюю.
Логику работы могу сказать и так:
при просмотре страницы со списком друзей любого человека браузер с помощью UserJS (GreaseMonkey для ФФ) сохранял текущий список (отправляя через iframe на локальную страницу, обрабатываемую локлальным apache+php). Таким образом собиралась база.
Затем банальными sql запросами строились списки людей. Алгоритмы поиска в ширину по таким базам лучше искать самостоятельно, информация есть.
Логику работы могу сказать и так:
при просмотре страницы со списком друзей любого человека браузер с помощью UserJS (GreaseMonkey для ФФ) сохранял текущий список (отправляя через iframe на локальную страницу, обрабатываемую локлальным apache+php). Таким образом собиралась база.
Затем банальными sql запросами строились списки людей. Алгоритмы поиска в ширину по таким базам лучше искать самостоятельно, информация есть.
0
Sign up to leave a comment.
Очередная попытка доказать что мир тесен