Как я могу доказать концепцию «шести степеней разделения» программно?

Question

У меня есть база данных из 20 миллионов пользователей и связей между этими людьми. Как я могу доказать концепцию «Шесть степеней разделения» концепции наиболее эффективным способом в программировании?

ссылка на статью о Шести степенях разделения

Answer 1

Вы просто хотите измерить диаметр графика. Это именно та метрика, которая позволяет определить разделение между наиболее удаленными узлами в графе.

Множество алгоритмов в Google, График усиления .

Answer 2

Вы, вероятно, можете разместить граф в памяти (в представлении, что каждая вершина знает список своих соседей).

Затем из каждой вершины n вы можете выполнить поиск в ширину (используя очередь) до глубины 6 и подсчитать количество посещенных вершин. Если не все вершины посещены, вы опровергли теорему. В другом случае продолжите со следующей вершины n .

Это O (N * (N + #edges)) = N * (N + N * 100) = 100N ^ 2, если у пользователя в среднем 100 соединений, что не идеально для N = 20 миллионов. Интересно, могут ли упомянутые библиотеки вычислить диаметр в лучшую временную сложность (общий алгоритм O (N ^ 3)).

Вычисления для отдельных вершин независимы, поэтому их можно выполнять параллельно.

Немного эвристики: начните с вершин, имеющих наименьшую степень (больше шансов опровергнуть теорему).

Answer 3

Что ж, лучший ответ уже был дан, но я бы предпочел использовать алгоритм Floyd-Warshall по кратчайшему пути всех пар, который равен O (n ^ 3). Я не уверен в сложности алгоритма диаметра графа, но он «звучит» так, как будто это тоже будет O (n ^ 3). Я хотел бы получить разъяснения по этому вопросу, если кто-нибудь знает.

Кстати, у вас действительно есть такая база данных? Страшно.

Answer 4

Я думаю, что наиболее эффективный способ (наихудший случай) - это почти N ^ 3. Постройте матрицу смежности, а затем возьмите эту матрицу ^ 2, ^ 3, ^ 4, ^ 5 и ^ 6. Ищите все записи на графике, которые являются 0 для матрицы через матрицу ^ 6.

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