Tôi có cơ sở dữ liệu gồm 20 triệu người dùng và kết nối giữa những người đó. Làm thế nào tôi có thể chứng minh khái niệm "Sáu độ tách" khái niệm theo cách hiệu quả nhất trong lập trình?Làm thế nào tôi có thể chứng minh khái niệm "Sáu độ tách" theo lập trình?
link to the article about Six degrees of separation
Bạn chỉ muốn đo diameter of the graph. Đây chính là số liệu để tìm ra sự chia tách giữa các nút nhất-xa-kết nối trong một đồ thị.
Rất nhiều thuật toán trên Google, Boost graph cũng vậy.
Bạn có thể phù hợp với biểu đồ trong bộ nhớ (trong biểu diễn rằng mỗi đỉnh đều biết danh sách những người hàng xóm của nó).
Sau đó, từ mỗi đỉnh n, bạn có thể chạy tìm kiếm rộng đầu tiên (sử dụng hàng đợi) đến độ sâu 6 và đếm số đỉnh truy cập. Nếu không phải tất cả các đỉnh được truy cập, bạn đã bác bỏ định lý. Trong trường hợp khác, tiếp tục với đỉnh tiếp theo n.
Đây là O (N * (N + #edges)) = N * (N + N * 100) = 100N^2, nếu người dùng có 100 kết nối trung bình, Đó không phải là lý tưởng cho N = 20 triệu. Tôi tự hỏi nếu các thư viện được đề cập có thể tính toán đường kính trong thời gian phức tạp tốt hơn (thuật toán chung là O (N^3)).
Tính toán cho từng đỉnh độc lập, do đó chúng có thể được thực hiện song song.
Một chút heuristic: bắt đầu với đỉnh có mức độ thấp nhất (cơ hội tốt hơn để bác bỏ định lý).
Tôi nghĩ rằng điều này là tồi tệ hơn đáng kể so với O (n^2). thậm chí giả sử mỗi nút được kết nối với chỉ 3 nút khác, một dấu vết ngăn xếp của độ sâu 6 sẽ là 3 * 2^0 + 3 * 2^1 + 3 * 2^2 + 3 * 2^3 + 3 * 2^4 + 3 * 2^5. Tăng trưởng theo cấp số nhân – patros
Đối với mỗi đỉnh bạn truy cập mỗi đỉnh tối đa một lần, do đó, chạy cho một đỉnh có O (N). –
Ah, đúng, đó là một giới hạn trên đó. Tôi nghĩ đây vẫn là O (N^3), phải không? Tìm một đường đi từ đỉnh A đến đỉnh B là O (N), và bạn phải làm điều này O (N^2) lần. – patros
Tôi nghĩ cách hiệu quả nhất (trường hợp xấu nhất) gần như là N^3. Xây dựng một ma trận kề, và sau đó lấy ma trận đó^2,^3,^4,^5 và^6. Tìm kiếm bất kỳ mục nào trong biểu đồ là 0 cho ma trận thông qua ma trận^6. Về mặt lý thuyết bạn có thể cố gắng tách ra các hình con (một nhóm lớn những người chỉ được kết nối với các cụm khác bằng một số nút "cầu" tương đối nhỏ) nhưng hoàn toàn không đảm bảo bạn sẽ có bất kỳ.
Bạn không thể xây dựng ma trận kề có kích thước 20x20 triệu bộ nhớ. Ngoài ra, phép nhân sẽ là O (N^3), trong đó N là 20 triệu. –
Đó là khoảng n^2.8 với thuật toán của strassen, vì chúng là các ma trận vuông. bạn cũng không cần phải giữ toàn bộ matix trong bộ nhớ, chỉ những phần bạn đang tích cực nhân lên. Trang phần còn lại ra đĩa. – patros
Có yêu cầu nhiều đĩa mặc dù ... 400 TB cho một cách tiếp cận ngây thơ. Rất nhiều phòng cho nén mặc dù. – patros
Một câu trả lời hay hơn đã được đưa ra, nhưng ngoài đỉnh đầu tôi đã đi với Floyd-Warshall tất cả các cặp thuật toán đường ngắn nhất, là O (n^3). Tôi không chắc chắn về độ phức tạp của thuật toán đường kính đồ thị, nhưng "âm thanh" như thế này cũng sẽ là O (n^3). Tôi muốn làm rõ điều này nếu có ai biết.
Một lưu ý phụ, bạn có thực sự có một cơ sở dữ liệu như vậy không? Đáng sợ.
Có sáu degress tối đa hoặc trung bình? Hầu hết các phân tích thực tế tôi đã đọc về sử dụng trung bình không phải là tối đa. –
Quan niệm chung về "sáu độ phân tách" là nó là tối đa. Tất nhiên, điều đó không đúng trong thực tế. Nó chỉ là ấn tượng hơn để nói nó theo cách đó và khó để tìm counterexamples. –