Два человека цепочка знакомых

Шесть рукопожатий | Журнал Популярная Механика

два человека цепочка знакомых

В среднем эта цепочка состоит из шести человек. Например, Кевина Бейкона отделяют от Чарли Чаплина всего три шага: сам Бейкон играл с Лоуренсом говорит Уоттс. - Вы думаете: "Кто же из моих знакомых русский ?". Впервые идею о том, что любые два человека в мире могут быть позволяющие проследить цепочку общих знакомых от одного. Цепочка друзей - теория шести рукопожатий .. видеть разные цепочки, связывающие вас с выбранным человеком, если их (цепочек) несколько. 4.

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

Как работает теория шести рукопожатий? / Моя Планета

Конечно, было бы прекрасно взять данные о друзьях из Facebook, ведь он охватывает весь мир, да и народа там. Такой объем трафика малость не вписывался в стремившийся к нулю бюджет исследования, и вариант с Facebook был откинут. Мой взгляд был устремлен на ВКонтакте. Да, он охватывает только Россию и СНГ причем неравномерно — в одноклассниках, к примеру, публика постарше. Да, там огромное количество ботов.

два человека цепочка знакомых

Но как эти данные хранить и обрабатывать? Можно пойти в лоб и писать сразу в MySQL: Цифра не запредельная, но с учетом того, что паук работал на слабом сервере старый одноядерный атлонне совсем радужная. Можно писать текстовый дамп на диск, а потом всасывать его в базу данных. Причем выборка с такой базы всех друзей пользователя не будет выглядеть как суперэффективный запрос. Можно забить на MySQL и использовать какое-нибудь hash-value хранилище.

В качестве хранилища изначально был выбран Kyoto Cabinet, но из-за каких-то странных аномалий в производительности на большой базе состоялся переезд на гугловый LevelDB.

Теория шести рукопожатий: еще одно подтверждение / Habr

Спустя трое суток и полтора терабайта трафика база друзей была получена между прочим, всего лишь 22Гб. И тут возникает самый интересный вопрос: Алгоритм Флойда-Уоршеллапозволил бы рассчитать дистанции от всех пользователей ко. Алгоритм Дейкстрыпозволил бы найти дистанции от одного пользователя до всех остальных.

два человека цепочка знакомых

Существует довольно много эффективных его реализаций, одна из которых и была ради эксперимента использована. Говоря человеческим языком, данные не помещались в кэш процессора, и тут начинались феерические тормоза. Да, не самый элегантный в мире алгоритм, зато простой как таблица умножения. Позволяет найти кратчайшую дистанцию между двумя пользователями. Повторите пункт 3, считая количество "рукопожатий".

В среднем бывает переходов. А поскольку девочка я литературно подкованная, но с вполне банальными ассоциациями, первыми на ум пришло имя сделайте паузу и проверьте себя Все верно, ищем Евгения Онегина. В контакте их аж 2 тыщи Не заморачиваясь, перехожу по верхней ссылке.

Теория шести рукопожатий

Хм, товарищ то необщительный, всего три гаврика в френдах. Большая редкость по нынешним временам.

два человека цепочка знакомых

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

два человека цепочка знакомых

С его перечня друзей первой в списке страничка некой Юлианны Жемчуговойпредстающей на своей страничке почему-то сразу в коленно-локтевой позе. Оказывается, с энтой очаровашкой у нас один общий знакомый! Итого - ровно 5 шагов. В легком остолбенении ставлю контрольный опыт.

Вспомнив менее банального и потрясшего меня в школьные годы персонажа классической литературы, задаю в поиске Екатерина Измайлова. Однофамилиц леди Макбет Мценского уезда нашлось штук, если "вконтакте" не врет.