Comments 185
Добровольцев нет? Или в контакте никто не сидит?
клёва, заходите, тестьте: id3710341
ещё бы, если можно, выложите свой JS-ник, хотелось бы его к ФФ прикрутить-погонять. :)
ещё бы, если можно, выложите свой JS-ник, хотелось бы его к ФФ прикрутить-погонять. :)
id288968 — интересно :)
вообще пару месяцев назад у меня с Дуровым был общий друг, потом он удалился из контакта…
вообще пару месяцев назад у меня с Дуровым был общий друг, потом он удалился из контакта…
А почему без автоматического скрипта? Ведь вроде несложно его написать.
Мой: id3624179
Мой: id3624179
и меня, пожайлуста:) id6798242
Анка 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)
а меня можно еще id48437
«Шесть рукопожатий» действуют не всегда. Но мир и правда тесен: не раз убеждался и сам, что среди знакомых моих знакомых находится люди множества умений и профессий.
Только «контакт» не лучший выбор для опытов, нередко «в друзья» добавляют людей, вообще их не зная. Вот для теста очередного скрипта, повышения программерского скилла или составления списка пользователей (а вот с последним будьте аккуратнее, можно попасть) — это можно ;)
з.ы. если не трудно, id674210 :)
Только «контакт» не лучший выбор для опытов, нередко «в друзья» добавляют людей, вообще их не зная. Вот для теста очередного скрипта, повышения программерского скилла или составления списка пользователей (а вот с последним будьте аккуратнее, можно попасть) — это можно ;)
з.ы. если не трудно, id674210 :)
и ооочень хотелось бы потестить скриптик. Думаю самому написать, но зачем делать одно и тоже, предлагаю вам посильную помощь…
id7379963
id5958359
id7490373 :)
id633454
Начинание интересное и полезное.
Полезное в том, что поднимает людям настроение и сообщает им полезную информацию.
Но нет необходимости пытаться доказать аксиому)
Полезное в том, что поднимает людям настроение и сообщает им полезную информацию.
Но нет необходимости пытаться доказать аксиому)
Отличный эксперемент! Тоже недавно ломал голову над таким, но к действиям так и не перешел :)
id399912
зы надеюсь опровергну вашу гипотезу)
зы надеюсь опровергну вашу гипотезу)
Хороший топик- и главное все остались довольны- и автор и комментаторы, судя по плюсам.
Вот все бы темы так гармонично шли!
Вот все бы темы так гармонично шли!
id1516701
буду благодарен)
буду благодарен)
id2856612
Очень сомневаюсь, но вдруг…
P.S. Заранее спасибо :)
Очень сомневаюсь, но вдруг…
P.S. Заранее спасибо :)
id5355398
id5491025
id888570 Если до меня дело дойдёт :)
И до Вас дело дошло :)
Нашлась связь между Вами и Rchee (id241410).
Хоть что-то.
Нашлась связь между Вами и Rchee (id241410).
Хоть что-то.
Эльвира *Рыжая_Вельха* Хабибулина (можно найти на графе) — Павел Тутубалин — Игорь Hellsing666 Рыбаков — Елизавета Likogra Кондакова — Аня — Леди Лиса — Хурхулу — Даша *without_me* Шевлякова — Сергей t1nkk… Пономаренко
Извините за отсутствие id номеров, времени в обрез, да и бета сырая=)
Смоделировано алгоритмом номер 2, спасибо хабрачеловеку eigrad. Думало 300 секунд.
ОДнако сам факт нахождения цепочки длиной в 9 рукопожатий предполагает возможность создания универсально публичного (вернее, персонального для каждого) скрипта поиска.
Извините за отсутствие id номеров, времени в обрез, да и бета сырая=)
Смоделировано алгоритмом номер 2, спасибо хабрачеловеку eigrad. Думало 300 секунд.
ОДнако сам факт нахождения цепочки длиной в 9 рукопожатий предполагает возможность создания универсально публичного (вернее, персонального для каждого) скрипта поиска.
id738345
Попробуйте — у меня достаточно узкий круг друзей(правда, есть среди них и рекордсмены в 500+ френдов)
Попробуйте — у меня достаточно узкий круг друзей(правда, есть среди них и рекордсмены в 500+ френдов)
И меня, и меня тоже :)
id253875
id253875
Если не сложно..) id6181
спасибо)).
спасибо)).
А как насчёт такого же, но только уже на Хабре и его друзьях ?:) я думаю было б интересно.А так експеремент меня очень удивил, класно вышло :) спасибо за то, что изменили некоторые мои взгляды.
Ну чтож, попробуйте.
id829436
id829436
инетресно, сколько у кого новых друзей появилось теперь в контакте?
id175 — одно рукопожатие до Павла Дурова
Интересная тема)
id427647
id427647
id842053?25858
интересно стало… только вот народу уже много. надеюсь не обойдете меня стороной)
id5776045
id5776045
354639
спасибо, интересно :)
спасибо, интересно :)
вот статейка пробегала
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
Хм, странно.
У нас пусть около 7*109
если мы извлечем корень третьей степени, то получим число знакомых, которых минимально необходимо иметь для покрытия всего земного шара.
У меня получилось 1913 людей. Имхо это несколько больше, чем в среднем количество людей, с которыми нормально общается человек.
У нас пусть около 7*109
если мы извлечем корень третьей степени, то получим число знакомых, которых минимально необходимо иметь для покрытия всего земного шара.
У меня получилось 1913 людей. Имхо это несколько больше, чем в среднем количество людей, с которыми нормально общается человек.
id1405401
id6721642
id277926
интересно :)
интересно :)
id6949
Если будет время :)
Если будет время :)
vkontakte.ru/id9477
Умираю от любопытства
Умираю от любопытства
Мда… Хоть для что-то Вконтакте полезен…
moikrug.ru/ — социальная сеть, основанная на теории о 3 рукопожатиях.
А во вконтакте, да, порой нехватает видения «кругов».
А во вконтакте, да, порой нехватает видения «кругов».
id404582
id575175
id241410
Ооо… имя «Дамир» знакомо. Это не тот, про которого на башорге писали?
цитата:
:) ща на форуме нашем человек зарегился, Дамир зовут. e-mail: yesworld@…
цитата:
:) ща на форуме нашем человек зарегился, Дамир зовут. e-mail: yesworld@…
Можно не считать — два рукопожатия до ПВД.
Но, господи, смотрю на хабратопик, вижу знакомые имена/фамилии и втупляю не могу понять чего они на хабре делают. :))
Но, господи, смотрю на хабратопик, вижу знакомые имена/фамилии и втупляю не могу понять чего они на хабре делают. :))
Классная тема :)
id4625479
id4625479
id2551971.
На самом деле такую штуку бы — да вконтакт встроить. Жалкое подобие есть на одноклассниках — там максимум 3(?) «рукопожатия». С другой стороны, это приватность как-то нарушает…
На самом деле такую штуку бы — да вконтакт встроить. Жалкое подобие есть на одноклассниках — там максимум 3(?) «рукопожатия». С другой стороны, это приватность как-то нарушает…
Жаль, вас уже так завалили заявками, вручную такой объём вряд ли возьмётесь обрабатывать, а палить вконтакт впустую не хочется. Всё же (надеяться не вредно): id23959.
Интересно, на фейсбуке подобного функционала нет?
Интересно, на фейсбуке подобного функционала нет?
id1562664
Я звезда! Я там два раза!
Смотрите, у меня никнейм в xml-комментарии!
Смотрите, у меня никнейм в xml-комментарии!
Если дадите структуру БД завтра-послезавтра могу набросать скриптик для поиска кратчайшего пути в графе.
Слил slil.ru/26134283 кусок таблицы (но она должна называться не friends_copy, как в дампе, а friends)
На сколько я разбираюсь в БД то вам крайне желательно удалить ключевое поле(зачем оно?) и создать индекс по myid. так же name можно вынести в отдельную таблицу чтоб не было дублирующихся данных и таблица связей работала быстрей.
мой скриптик:
протестировал на 4000000 базе с рандомными значениями. цепочку глубиной в 10 и общим количеством участников ~350 прошло за 0.07 секунды на моем сервере.
Количество запросов к БД = количеству просматриваемых уровней.
Если не заработает буду рад разобраться и помочь. критика, вопросы, советы — велком!
мой скриптик:
протестировал на 4000000 базе с рандомными значениями. цепочку глубиной в 10 и общим количеством участников ~350 прошло за 0.07 секунды на моем сервере.
Количество запросов к БД = количеству просматриваемых уровней.
Если не заработает буду рад разобраться и помочь. критика, вопросы, советы — велком!
myid и frid повторяются, нельзя их делать ключевыми.
А насчёт name — это правильно, спасибо. Небольшой минус в том, что просто при просмотре страницы контакта проводится запись в базу, и на страницах размером в 500 контактов чувствуются ощутимые тормоза. При таком подходе они удвоятся.
А скриптик сейчас посмотрим, спасибо.
А насчёт name — это правильно, спасибо. Небольшой минус в том, что просто при просмотре страницы контакта проводится запись в базу, и на страницах размером в 500 контактов чувствуются ощутимые тормоза. При таком подходе они удвоятся.
А скриптик сейчас посмотрим, спасибо.
Честно говоря, удивлён скоростью работы, спасибо!
Чудеса просто.
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. Надо уметь закрывать пути через определённых людей, запрещая их.
1-й пункт сделал сам.
второй пункт не понял что вы имеете в виду. привидите пример.
2-3 секунды это очень много на такой базе(или цепочка была очень длинная?). сделайте индекс на frid и myid и вынесете имя в отдельную таблицу — уверен скорость увеличиться в разы. добавление новых записей будет немного медленне, но если у вас не граббер который делает это в режиме постоянного сканирования, то вы этого не ощутите.
2-3 секунды это очень много на такой базе(или цепочка была очень длинная?). сделайте индекс на frid и myid и вынесете имя в отдельную таблицу — уверен скорость увеличиться в разы. добавление новых записей будет немного медленне, но если у вас не граббер который делает это в режиме постоянного сканирования, то вы этого не ощутите.
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]]);
}
а я через одного друга знаком
id1019587
id1019587
id2415323
Готов стать добровольцем :)
id222737
id222737
Готов вступить в ряды. id5415769
Надо скрипт в общее использование, с веб-интерфейсом, вводишь id от кого, и id до кого, скрипт считает и выводит граф) красота была б)
Будет алгоритм — будет и скрипт.
Вот текущий алгоритм (только 4 рукопожатия): ramainen.ru/i/download/graf.php.txt
очень круто!
id1795320
id1795320
а кто такой Павел Дуров? о_О
добровольцы++ :)
id3981543
id3981543
Поставьте апдейты под хабракат, чтоли…
id2245179
:)
:)
Поиск пути на невзвешанном графе в 20млн вершин эт простой поиск волной:
N вершин (N < 20 млн. — допустим у нас стока народу вконтакте)
Есть очередь вершин в которые мы собираемся идти и массив из N элементов где отмечаем в каких вершинах были. Изначально массив забит нулями, единицей отмечена только начальная вершина, а в очереди только начальная вершина.
На каждом шаге берем одну вершину из очереди, добавляем ее детей в которых еще небыли и пишем единички в элементах массива им соответствующих. Заодно сравниваем с номером конечной вершины. Можем в массив вместо единичек писать расстояние до начальной (что обычно и делается). Можно в дополнительный массив писать данные для трассировки — номер вершины из которой мы пришли.
Массив из 20млн. байт — 20 МБ. Очередь (каждая вершина побывает в очереди <= 1 раза) <= 20Мб…
Помоему работает за t(N)…
Собственно всё…
N вершин (N < 20 млн. — допустим у нас стока народу вконтакте)
Есть очередь вершин в которые мы собираемся идти и массив из N элементов где отмечаем в каких вершинах были. Изначально массив забит нулями, единицей отмечена только начальная вершина, а в очереди только начальная вершина.
На каждом шаге берем одну вершину из очереди, добавляем ее детей в которых еще небыли и пишем единички в элементах массива им соответствующих. Заодно сравниваем с номером конечной вершины. Можем в массив вместо единичек писать расстояние до начальной (что обычно и делается). Можно в дополнительный массив писать данные для трассировки — номер вершины из которой мы пришли.
Массив из 20млн. байт — 20 МБ. Очередь (каждая вершина побывает в очереди <= 1 раза) <= 20Мб…
Помоему работает за t(N)…
Собственно всё…
Кстати предположив что у каждого примерно по 100-200 друзей и с каждым из них от 10 до 50 общих друзей можно оценить диаметр нашего графа… Только, извините, мне лень)))
Идея, безусловно, красивая, да вот на практик уж очень туго работает. Долго.
Каждое t (которых N) делает запрос к базе данных. К приличной базе данных.
Каждое t (которых N) делает запрос к базе данных. К приличной базе данных.
Можно распараллелить и запросы к базе данных слать заранее (например при добавлении друзей в очередь)
Еще сам запрос продумать… Можно сразу друзей второго круга например получать одной транзакцией… 5 секунд это если одним запросом? или несколькими?
5 секунд это максимум, при заторможенной системе. В среднем около 0.4 — 0.1 секунды идёт, иногда быстрее.
SELECT * from where id in (select ...) очень долго работает, такчто отпадает сразу.
Параллелить php не умею. Скрипт очень долгоо работал, выход нашёлся в модифицировании проверки искомого человека.
Проверяется не с искомыы человеком, а последовательно со списком его друзей.
Связи через 9-х человек ищет на ура, в этом Вам огромное спасибо. Более длинные цепочки не укладываются в 400 секунд.
Такое время выполнения и не позволяет селать скрипт публичным.
Так что скоро просто выложу сам скрипт поиска, у каждого своя персональная маленькая база будет.
Ну и соответственно, их объединять можно будет между пользователями в единую базу.
SELECT * from where id in (select ...) очень долго работает, такчто отпадает сразу.
Параллелить php не умею. Скрипт очень долгоо работал, выход нашёлся в модифицировании проверки искомого человека.
Проверяется не с искомыы человеком, а последовательно со списком его друзей.
Связи через 9-х человек ищет на ура, в этом Вам огромное спасибо. Более длинные цепочки не укладываются в 400 секунд.
Такое время выполнения и не позволяет селать скрипт публичным.
Так что скоро просто выложу сам скрипт поиска, у каждого своя персональная маленькая база будет.
Ну и соответственно, их объединять можно будет между пользователями в единую базу.
Вернее просто при добавлении друзей в очередь получать список их друзей (для каждого друга) одним запросом…
id39525
Виктор Новосельцев(39525) — Владимир Марченко(39643) — Андрей Дельфин Лысиков(3028766) — Эээ www.ED-WIN.com Altergott(99295) — Иван Говнов(4289) — Александр Викторович Беспалов(17) — Павел Дуров(1)
Ну хоть на что-то вконтакт сгодится.
Ну вот, значит скоро спамеры соберут id и заспамят всех)))
Сомнительная затея, т.к. у id № 1 друзей многовато.
Сомнительная затея, т.к. у id № 1 друзей многовато.
Перечислите 10-х? Они закрыты, смотрите сами vkontakte.ru/friend.php? id=1
По ссылке 310 человек друзей ПВД. По моему вписывается в понятие многовато.
Значит вы друг второго круга. Я ничего не вижу и ничего не могу с этим поделать.
А, черт, вы правы не принял это во внимание. =/
Кстати, сей сайт видели: vkontakte.net.ru/
На заре контакта его сделали, не знаю ли он функционирует в полной мере в данный момент.
На заре контакта его сделали, не знаю ли он функционирует в полной мере в данный момент.
Они были закрыты не всегда, а потом Павел, это по сути техподдержка, а друзей у техподдержки всегда много.
Я говорю о фиктивности социальной связи типа «Друг», это сбивает теорию о рукопожатиях, при желании будет вам и два и одно рукопожатие.
Я говорю о фиктивности социальной связи типа «Друг», это сбивает теорию о рукопожатиях, при желании будет вам и два и одно рукопожатие.
давайте попробуем, интересно как именно:)
id881540
id881540
Dijkstra@Home? ;)
id10391770
id10391770
А ну-ка, найди меня. 6821354
А если по-пробовать со мной? 791406
Александр 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)[Я]
Да, спасибо eigrad за алгоритм.
И мне интересно :)) 107182
У Дурова там друзей — немеряно :) Так что как там и водится, не факт, что он хотя бы половину знает =)
Прошу прощения, если кого-то пропустил! Просьб было много, некоторые закрыли списки друзей, некоторых найти не удалось. Итак, смотрим граф.
Всем спасибо. Подготавливается публичный (вернее, персональный) скрипт.
Всем спасибо. Подготавливается публичный (вернее, персональный) скрипт.
классный скрипт! А когда ожидать релиз? Можно ли его сделать для firefox и оформить в виде скриптов на userscripts.org?
1022123 пожалуйста :)
Дамир, вы бы не могли выложить куда-то алгоритм, а то топик уже старый и ссылки не работают, а мне очень интересно посмотреть реализацию.
Буду очень признателен, спасибо!
Буду очень признателен, спасибо!
уже нет, скрипт нерабочий, т.к. вконтакте смнили (и не раз) структуру внетренюю.
Логику работы могу сказать и так:
при просмотре страницы со списком друзей любого человека браузер с помощью UserJS (GreaseMonkey для ФФ) сохранял текущий список (отправляя через iframe на локальную страницу, обрабатываемую локлальным apache+php). Таким образом собиралась база.
Затем банальными sql запросами строились списки людей. Алгоритмы поиска в ширину по таким базам лучше искать самостоятельно, информация есть.
Логику работы могу сказать и так:
при просмотре страницы со списком друзей любого человека браузер с помощью UserJS (GreaseMonkey для ФФ) сохранял текущий список (отправляя через iframe на локальную страницу, обрабатываемую локлальным apache+php). Таким образом собиралась база.
Затем банальными sql запросами строились списки людей. Алгоритмы поиска в ширину по таким базам лучше искать самостоятельно, информация есть.
Sign up to leave a comment.
Очередная попытка доказать что мир тесен