У меня есть база данных из 20 миллионов пользователей и связей между этими людьми. Как я могу доказать концепцию «Шесть степеней разделения» наиболее эффективным способом в программировании?
Как я могу программно доказать концепцию шести степеней разделения?
Ответы (4)
Вы просто хотите измерить диаметр графика. между наиболее удаленными узлами графа.
Множество алгоритмов в Google, а также Boost graph .
person
SPWorley
schedule
12.06.2009
Шесть градусов это максимум или среднее значение? Большая часть фактического анализа, о котором я читал, использует среднее значение, а не максимум.
- person Kathy Van Stone; 13.06.2009
Общее представление о шести степенях разделения состоит в том, что это максимум. Конечно, на самом деле это совсем не так. Просто так звучит более впечатляюще, и трудно найти контрпримеры.
- person Tyler McHenry; 13.06.2009
Вероятно, вы можете уместить граф в памяти (в представлении, что каждая вершина знает список своих соседей).
Затем из каждой вершины n можно запустить поиск в ширину (используя очередь) до глубины 6 и подсчитать количество посещенных вершин. Если не все вершины посещены, вы опровергли теорему. В противном случае продолжите со следующей вершины n.
Это O(N*(N + #edges)) = N*(N + N*100) = 100N^2, если у пользователя в среднем 100 подключений, что не идеально для N=20 миллионов. Интересно, могут ли упомянутые библиотеки вычислить диаметр с большей временной сложностью (общий алгоритм - O (N ^ 3)).
Вычисления для отдельных вершин независимы, поэтому их можно выполнять параллельно.
Немного эвристики: начните с вершин с наименьшей степенью (больше шансов опровергнуть теорему).
person
Martin Konicek
schedule
12.06.2009
Я думаю, что это значительно хуже, чем O (n ^ 2). даже если предположить, что каждый узел подключен только к трем другим узлам, трассировка стека глубины 6 будет иметь вид 3 * 2 ^ 0 + 3 * 2 ^ 1 + 3 * 2 ^ 2 + 3 * 2 ^ 3 + 3 * 2 ^ 4 + 3*2^5. Экспоненциальный рост
- person patros; 13.06.2009
Для каждой вершины вы посещаете каждую вершину не более одного раза, поэтому прогон для одной вершины занимает O (N).
- person Martin Konicek; 13.06.2009
Ах, правда, это предел. Я думаю, что это все еще O (N ^ 3), не так ли? Поиск пути из вершины A в вершину B — это O(N), и вы должны сделать это O(N^2) раз.
- person patros; 14.06.2009
Привет, представьте, что вы хотите вычислить кратчайшее расстояние от одной вершины до каждой другой вершины в графе. Поскольку ребра не имеют веса (длина пути = # ребер), это можно сделать за O(N+#ребер): запустить поиск в ширину - en.wikipedia.org/wiki/Breadth-first_search. Вы правы, это не O(N), а O(N+#edges), где #edges равно 100*N (если у пользователя в среднем 100 подключений). Спасибо
- person Martin Konicek; 15.06.2009
Я думаю, что самый эффективный способ (худший случай) - это почти N ^ 3. Постройте матрицу смежности, а затем возьмите эту матрицу ^2, ^3, ^4, ^5 и ^6. Ищите любые записи в графе, которые равны 0 для матрицы через матрицу ^ 6.
Эвристически вы можете попытаться выделить подграфы (большие группы людей, которые соединены с другими группами только относительно небольшим количеством «мостовых» узлов), но нет абсолютно никакой гарантии, что они у вас будут.
person
patros
schedule
12.06.2009
Вы не можете построить в памяти матрицу смежности размером 20x20 миллионов. Кроме того, умножение будет O (N ^ 3), где N равно 20 миллионам.
- person Martin Konicek; 13.06.2009
Это примерно n ^ 2,8 с алгоритмом Штрассена, так как это квадратные матрицы. вам также не нужно хранить в памяти всю матрицу, только те части, которые вы активно умножаете. Страница остальные на диск.
- person patros; 13.06.2009
Однако требуется много места на диске... 400 ТБ для наивного подхода. Зато много места для компрессии.
- person patros; 13.06.2009
Что ж, лучший ответ уже был дан, но мне не пришло в голову, что я бы выбрал Алгоритм Флойда-Уоршалла для всех пар кратчайшего пути, который равен O(n^3). Я не уверен в сложности алгоритма диаметра графа, но это «звучит» так, как будто это также будет O (n ^ 3). Хотелось бы разъяснений по этому поводу, если кто знает.
Кстати, у вас действительно есть такая база данных? Страшный.
person
Dan Olson
schedule
15.06.2009
