Как программно доказать концепцию "шести степеней разделения"?
У меня есть база данных 20 миллионов пользователей и связей между этими людьми. Как я могу доказать концепцию "шести степеней разделения" наиболее эффективным способом в программировании?
4 ответа
Вы просто хотите измерить диаметр графика. Это именно та метрика, которая позволяет определить разделение между наиболее удаленными узлами в графе.
Множество алгоритмов в Google, граф Boost тоже.
Вы, вероятно, можете разместить граф в памяти (в представлении, что каждая вершина знает список своих соседей).
Затем из каждой вершины n вы можете выполнить поиск в ширину (используя очередь) до глубины 6 и подсчитать количество посещенных вершин. Если не все вершины посещены, вы опровергли теорему. В другом случае продолжите со следующей вершины n.
Это O(N*(N + #edges)) = N*(N + N*100) = 100N^2, если у пользователя в среднем 100 соединений, что не идеально для N=20 миллионов. Интересно, могут ли упомянутые библиотеки вычислить диаметр в лучшую временную сложность (общий алгоритм O(N^3)).
Вычисления для отдельных вершин являются независимыми, поэтому их можно выполнять параллельно.
Немного эвристики: начните с вершин, имеющих наименьшую степень (больше шансов опровергнуть теорему).
Что ж, лучший ответ уже был дан, но я бы предпочел использовать алгоритм кратчайшего пути Флойда-Варшалла для всех пар, который равен O(n^3). Я не уверен в сложности алгоритма диаметра графа, но он "звучит" так, как будто это тоже будет O(n^3). Я хотел бы уточнить это, если кто-нибудь знает.
Кстати, у вас действительно есть такая база данных? Страшно.
Я думаю, что самый эффективный способ (наихудший случай) - это почти N^3. Постройте матрицу смежности, а затем возьмите эту матрицу ^2, ^3, ^4, ^5 и ^6. Посмотрите на любые записи в графе, которые являются 0 для матрицы через матрицу ^6.
Эвристически вы можете попытаться выделить подграфы (большие скопления людей, которые связаны с другими скоплениями только относительно небольшим количеством "мостовых" узлов), но нет абсолютно никаких гарантий, что они у вас будут.