Как устроен поиск пути между пользователями в LinkedIn.

[DorBer]

Завтра на Google Developer Day Фицпатрик, наверное, опять будет про социальные графы говорить. Как жаль, что не попаду. Разбередил душу ваш пост :)

[DorBer]

Нет, в этот раз Чуи. Или в прошлый тоже он был?

[nil]

Если это вопрос ко мне, то я не знаю :)

[DorBer]

Это я потихоньку сам с собой. В такое время народу не много :)
Большое спасибо за статью, на самом деле у них получился очень простой, но не совсем очевидный подход.

[nil]

Мне тоже подход понравился, поэтому и решил написать топик.

[BekoBou]

Был в прошлый раз и в этот раз тоже присутствовал :)

Собственно фото с семинара по OS на GDD'08, которое мне удалось сделать. :) Прошлогоднее фото наверное уже не найду.

[mcgregor]

А зачем, простите, «перебирать все возможные пути от пользователя до искомого человека»?
Они про алгоритмы нахождения кратчайшего пути слышали?
120 миллионов ребер — это примерно как все дороги Европы. Можно и не извращаться.

[nil]

Да, с перебором всех возможных путей я наверное погорячился. И тем не менее основная мысль от этого не меняется — алгоритм поиска кратчайшего пути будет работать значительно быстрее на персональном графе, чем на полном.

[mcgregor]

Логично.
Забавно, что выборка персонального подграфа и есть нахождение кратчайших путей ко всем вершинам, удаленным на, скажем, 3 ребра от выбранной вершины. По-английски это называется catchment area или coverage area и делается это с помощью того же алгоритма Дейкстры, который останавливается, не когда достиг искомой вершины, а когда путь из каждой анализируемой вершины превышает 3.

[mxc]

Банальные графы… Pathfinding