Для затравки оставлю здесь картинку:
От безделья передо мной стояла задача: есть два пользователя vk.com, необходимо найти цепочку других пользователей, через которых они знакомы. Ну и, конечно, предоставить результат в удобном виде.
Должно было получиться что-то вроде:
1. Первое, что приходит в голову — это рекурсивно построить деревья друзей для каждого пользователя. Но для моей задачи достаточно одного дерева. Второе будет только кушать память.
Вытянем через VK API для первого пользователя его друзей, друзей друзей и т. д. до глубины поиска (first depth), которую примем за 3. Три — удобная величина, потому что два — мало, а четыре заставят браузер ощутимо залипать. Строя такие структуры, надо помнить, что с увеличением глубины на единицу число пользователей увеличивается на два порядка (число Данбара).
2. Затем можно сделать то же самое со вторым, но не сохраняя результат в памяти. Всё, что нужно — это проверять, находится ли каждый найденный пользователь в дереве из п.1.
*second depth — это, как можно догадаться, глубина поиска для второго. Её величина во многом определяет скорость работы, об этом ниже
3. В случае совпадения вся цепочка сохраняется:
4. На выходе имеем последовательности идентификаторов пользователей между двумя заданными, включая их:
*обведён общий из п.2.
5. С полученным массивом последовательностей остаётся сделать всего лишь две вещи: оставить последовательности минимальной длины и удалить дубликаты.
6. PROFIT! В работе попробовать можно здесь: artfultom.github.io/whom-i-know
Задача решена IMHO «в лоб», реализацию можно пощупать, работает с приемлемой скоростью. Небольшие замечания:
- Слабым местом является функция для поиска идентификатора из дерева второго пользователя в дереве первого (п.2). Поэтому чем меньше она используется, тем быстрее можно увидеть результат. А она используется тем меньше, чем меньше глубина поиска для второго (second depth). В этом легко убедиться, если в приложении по приведённой мной ссылке поменять максимальную длину цепочки. Для длины 4: first depth равна 3, а second depth — 2. Для длины 5 обе равны 3;
- На практике самым интересным вариантом является самый простой с длиной цепочки 4. Для больших значений результаты «слишком многословны» и включают множество пользователей-тысячников;
- Сложно найти пользователей, не знакомых через троих.
Комментарии (28)
Evengard
25.05.2015 15:41+3Не лучшая библиотека для отрисовки графа. Всё дёргается, только вроде вытянул как реально удобно видно — а оно опять куда-то поскакало как только кнопку мыши отпустил.
dmkuznetsov
25.05.2015 16:28+1Классно было бы отображать не все возможные связи, а по выбору. Например, справа от графа вывести список друзей, через которых есть связь и по клику на каждого эта связь бы отображалась.
А так штука интересная! Спасибо!
babayota_kun
25.05.2015 19:18+1В закладках у себя обнаружил ещё один забавный визуализатор. Но он строит графы друзей, а не ищет цепочки. Вот он, если кому интересно.
inwardik
25.05.2015 20:20+2Круто! А вообще было б здорово, если б сама социальная сеть умела делать такие вещи. С глубиной до 7)
SLashRU
25.05.2015 23:21+2Что интересно, сама сеть делает что-то подобное! Только в неявном виде (или это самовнушение, но экспериментальным путём работает всегда :) ). А именно: в полноценной веб версии выбираете любого человека, заходите ему в список друзей, нажимаете на первого в списке, заходите ему в список друзей, нажимаете на первого в списке (повторяете так несколько раз — 3-6)… и вуаля, человек с общими друзьями.
Т.е. есть некое ранжирование списка друзей по вашей близости в графе (или это самовнушение, но повторюсь — работает). В мобильном приложении как-то раз пробовал проделать такое — не сработало, а вот в веб-версии работает.inwardik
26.05.2015 12:43Действительно работает и тоже укладывается в 4-5 шагов. Забавно, что к публичным личностям у меня все цепочки выстраиваются через страницу /id1. Интересно, это случайность или так и задумано?
aalebedev
25.05.2015 20:592 года назад делал подобное.
С трудом работает. Но я им не занимался полтора года.
vk.com/app1886758#chain=ОДИН_ИД=ВТОРОЙ_ИД
Пример:
vk.com/app1886758#chain=5057680=1
В свое время находил цепочки и в 6 длиной. Да долго, но прикольно.
AYShestakov
25.05.2015 23:33+1C большинством наобум введенных словосочетаний (пользователей) я знаком через 2-3 контакта.
С трудом подобрал такого с кем связь достаточно неочевидна
xenohunter
26.05.2015 01:29+5Вы знаете, что делать: https://vk.com/sashagrey.
artyums
26.05.2015 11:23+2Забавно, что от Дмитрия Медведева, как и от Sasha Grey меня отделяет одна и та же цепочка из трех людей))
robux
26.05.2015 12:46Сложно найти пользователей, не знакомых через троих.
Отлично! Получается, практика подтверждает моё теоретическое предположение об избыточности «теории 6 рукопожатий» в статье "Сеть доверия", которую я писал пол года назад.
Для постсоветского пространства с числом пользователей в районе 200 млн., получается действительно 3 посредника:
Mendel
26.05.2015 13:06+4тут скорее играет фактор, что у публичных людей колво связей сильно выше Данбара. Даже если они и не помнят, но другие то помнят…
так же и в сети — половину френдов мы помним плохо, а тысячники и вовсе 80% не помнят, но вспомнить можно, и связь есть…
Если строить связь, пусть и не кратчайшую до любого человека, не имея полной базы, то как это делать?
Я бы шел по пути наибольшей публичности.
Например у нас есть человек из глухой деревни. Его нужно соединить с человеком из другой глухой деревни, в другой стране.
Человек с вождем/председателем сельсовета знаком? Если и не напрямую, то всё равно знаком. Аналогично и его визави.
Далее их вожди знакомы с председателями райсоветов / губернаторами… Которые знакомы с главами государств.
Те знакомы между собой. Если нет, то через послов, или через бывших глав, или через еще какие связи…
Всё, цепочка есть, теперь мы ее оптимизируем. Может есть какие-то связи в цепочке что короче, или еще как… может не по политике пойдем, а по общим увлечениям. Например кто-то в цепочке занимается теннисом. И еще кто-то…
Кто-то блогер…
Деятели искусства…
Примерно так я составлял цепочки когда только узнал про теорию 6.
Например моя цепь до Буша младшего была такая:
Бабушкина бывшая начальница была любовницей одного зам.министра в СССР. Тот был знаком с Горбачевым, тот знал старшего, а тот уже своего сына.
Если бы я не имел знаний о начальнице, то мог бы строить цепь скажем через мэра. На мэра цепь всегда есть, кто из знакомых самый богатый/известный? бывший шеф, брат первой жены любовника сестры… не важно, всегда есть кто-то, кто крупнее всех. Как правило до мэра от него связи будут доступны. Ну если нет, то можно мельче идти. Скажем того кто с налоговой контактировал взять, инспектор с начальником имел дело, тот с нач.областной, тот с губернатором и т.п… Всегда есть контакт…
dkuzevanov
Я нашел, я нашел!
c2n.me/3iezijJ.jpg
Keyten
И я, и я :)
Что интересно, нашлось более 200 вариантов.
NikMelnikov
Следующий должен быть через одного;)
stasmus
Видимо все проверяют сначала на этом Аккаунте (dm), у меня тоже 2 промежуточных друга.
Все через Елена Бочерова попадают? Кто эта женщина?
Mendel
Я первым делом решил задать сложную задачу. Указал двух друзей которые живут в разных странах, между собой не знакомы, но имеют общие интересы… только когда увидел ответ понял насколько лоханулся :)
Вторым у меня был ид1, забавно что 90% цепочек ведут через малознакомого разработчика которому я чуть помог с кодом…
про ДМ я даже сначала не понял, кто это, но раз все меряют, то и сам померял… далеко. Только после переключения на 5 нашло. При этом половина путей шли через ид1.
Пару наблюдений.
1 — когда я мысленно строю цепочки по публичным людям, то они оказываются очень простыми. Сильно помогает то, что я примерно знаю куда идти. Сокращается колво переборов.
2 — живые рукопожатия мало значат, потому что никак не отражают «качество» рукопожатий.
Скажем на Тимошенко кратчайшие пути у меня это через тёщу (напрямую) и через отца моего друга (через друга).
Вроде как через тёщу цепочка короче, но тёща бывший сотрудник налоговой который проверял Тимошенко более десяти лет назад. Контакт устарел и бесполезен. В то время как у друга отец связан по партийной линии, и при достаточной мотивации вполне может по своим контактам связаться…
Аналогично например живая цепочка до ДМ у меня идет через его хозяина, с которым совершенно случайно в одной ситуации пересекался мой знакомый. Со знакомым сейчас контакта нет, да и если бы я мог связаться, то он бы тоже ничего не смог — его встреча была случайной, и воспроизвести он ее не способен. Гораздо проще мне кажется идти по длинной цепочке из пяти рук через ид1, ибо там везде более-менее понятные люди, и понятно как создавать с ними контакт и т.п., тут хоть есть шанс, а по короткой дорожке пройти в принципе невозможно…
3 — цифровые френды тоже нерепрезентативны и именно по той же причине — нет контроля качества френдов. Очень искажают картину «тысячники». При этом проблема качества связей выше, но зато полнота доступных связей намного лучше. Да, контакт тоже не знает многих связей, к примеру хозяин ДМ в нем отсутствует, но, в реальном мире связи дальше собственного носа мы знаем еще хуже…