8
저는 2,000 만 명의 사용자와 데이터베이스를 보유하고 있습니다. "6도 분리"개념의 개념을 증명하는 가장 좋은 방법은 프로그래밍에 있습니까?"Six Degrees of Separation"개념을 프로그래밍 방식으로 증명할 수있는 방법은 무엇입니까?
link to the article about Six degrees of separation
A
답변
10
당신은이 그래프에서 가장 먼 연결된 노드 사이의 단락 지을 알아낼 정확히 측정입니다 diameter of the graph. 을 측정하고자합니다.
Google의 알고리즘이 많습니다. Boost graph도 있습니다.
4
아마도 그래프를 메모리에 저장할 수 있습니다 (각 버텍스가 이웃들의 목록을 알고 있다는 표현으로).
각 정점 n에서 깊이 6까지 너비 우선 탐색 (대기열 사용) 및 방문한 정점 수를 계산할 수 있습니다. 모든 꼭지점을 방문한 것이 아니라면, 당신은 정리를 반증했습니다. 다른 경우에는 다음 버텍스 n으로 계속하십시오.
사용자가 평균 100 개의 연결을 갖는 경우 O (N * (N + #edges)) = N * (N + N * 100) = 100N^2이며 N은 2,000 만에 이상적입니다. 언급 한 라이브러리가 더 나은 시간 복잡도 (일반적인 알고리즘은 O (N^3))에서 지름을 계산할 수 있는지 궁금합니다.
개별 정점에 대한 계산은 독립적이므로 병렬로 수행 할 수 있습니다.
약간의 경험적 연구 : 가장 낮은 학위를 가진 꼭지점부터 시작하십시오 (정리를 반증 할 수있는 더 좋은 기회).
+0
이것은 O (n^2)보다 상당히 나쁘다고 생각합니다. 심지어 각 노드가 3 개의 다른 노드에만 연결되었다고 가정하면 깊이 6의 스택 추적은 3 * 2^0 + 3 * 2^1 + 3 * 2^2 + 3 * 2^3 + 3 * 2^4 + 3 * 2^5. 지수 성장 – patros
+1
각 꼭지점마다 최대 한 번씩 각 꼭지점을 방문하므로 하나의 꼭지점에 대한 실행에는 O (N)이 필요합니다. –
+1
아, 사실, 그게 한계입니다. 나는 이것이 아직도 O (N^3)라고 생각한다. 그렇지 않니? 정점 A에서 정점 B까지의 경로를 찾으면 O (N)이므로 O (N^2) 번 수행해야합니다. – patros
2
가장 효율적인 방법 (최악의 경우)이 거의 N^3이라고 생각합니다. 인접 행렬을 만들고^2,^3,^4,^5 및^6 행렬을 가져옵니다. 매트릭스에서 행렬^6을 통해 0 인 그래프의 항목을 찾습니다.
경험적으로 하위 그래프 (상대적으로 적은 수의 "브리지"노드로 다른 덩어리에만 연결되어있는 사람들의 큰 덩어리)를 추출 할 수는 있지만 절대적으로 보장 할 수는 없습니다.
2
더 나은 대답은 이미 주어졌지만 내 머리 꼭대기에서 O (n^3) 인 모든 쌍의 최단 경로 알고리즘 인 Floyd-Warshall으로 갔을 것입니다. 나는 그래프 직경 알고리즘의 복잡성을 확신 할 수 없지만, 이것 또한 O (n^3)와 같은 "소리"처럼 들린다. 나는 누군가가 알면 이것을 명확히하고 싶습니다.
사이드 노트에는 실제로 이러한 데이터베이스가 있습니까? 무서운.
6도가 최대입니까 평균입니까? 내가 읽은 실제 분석의 대부분은 평균이 아닌 평균을 사용합니다. –
"6 도의 분리"라는 일반적인 개념은 최대 값이라는 것입니다. 물론 현실에서는 그렇지 않습니다. 그런 식으로 말하면 반박하는 것이 더 인상적입니다. –