Имам база данни от 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). дори да приемем, че всеки възел е свързан само с 3 други възела, следа на стека с дълбочина 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+#ръбове), където #ръбове е като 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 с алгоритъма на Strassen, тъй като те са квадратни матрици. също така не е необходимо да съхранявате целия matix в паметта, само частите, които активно умножавате. Извадете останалите на диска.
- person patros; 13.06.2009
Все пак изисква много диск... 400 TB за наивен подход. Въпреки това има много място за компресия.
- person patros; 13.06.2009
Е, вече беше даден по-добър отговор, но от главата ми щях да избера Floyd-Warshall всички двойки алгоритъм за най-кратък път, който е O(n^3). Не съм сигурен в сложността на алгоритъма за диаметър на графиката, но "звучи", сякаш това също ще бъде O(n^3). Бих искал разяснение по този въпрос, ако някой знае.
От друга страна, наистина ли имате такава база данни? Страшен.
person
Dan Olson
schedule
15.06.2009
