Thuật toán để xác định các biểu đồ con "được kết nối mờ"

Question

Tôi có vấn đề giống như vấn đề đồ thị con nối từ một dặm cao, nhưng hoàn toàn khác biệt ở chỗ nó không nằm dưới định nghĩa nghiêm ngặt.

Tôi phải đối mặt với biểu đồ có vài triệu nút và liên kết (không thể phân tích thủ công), trong số hàng triệu nút đó, có 2 hoặc 3 tập hợp.

Mỗi "bộ" bao gồm hàng trăm nghìn nút và hàng chục nghìn biểu đồ phụ, không được kết nối chặt chẽ. Mỗi bộ trong những bộ đó về mặt lý thuyết không được liên kết với các bộ khác ... nhưng có (guesstimation) một tá các liên kết sai lầm kết thúc việc kết nối các bộ đó.

Vấn đề là tìm các bộ đó và các liên kết sai, hoặc ít nhất có được danh sách các ứng viên liên kết sai có thể quản lý bằng tay có thể được xác minh thủ công.

"Ý tưởng tốt nhất" hiện tại của tôi là chọn ngẫu nhiên hai nút, tìm đường đi ngắn nhất giữa chúng, sau đó đánh dấu các liên kết trên đường đi ngắn nhất đó. Rửa sạch & lặp lại hàng triệu lần, và các liên kết sai lầm cuối cùng kết thúc như là những cái được đánh dấu nhất, vì chúng là "chokepoints" giữa các bộ.

Tuy nhiên, điều này khá chậm, và khi một bộ lớn hơn nhiều so với những người khác và có các điểm ngắt nội bộ, nó kết thúc thống trị danh sách "được đánh dấu nhiều nhất", làm cho nó vô nghĩa.

Are thuật toán có tốt hơn/cách tiếp cận cho rằng?

chỉnh sửa: tinh chỉnh đánh dấu đường dẫn là đánh dấu tỷ lệ tương ứng với chiều dài của đường dẫn, giúp với vấn đề "chokepoints nội bộ lớn", nhưng không loại bỏ hoàn toàn các "ngoại lệ" xa xôi, trong khi các bộ khác có nhiều nút được kết nối chặt chẽ (khoảng cách ngắn bên trong)

Answer 1

Ý tưởng của tôi là ant colony algorithm. Tôi lấy cảm hứng với cách tiếp cận của bạn trong việc chọn hai nút ngẫu nhiên, nhưng nghĩ rằng nó sẽ hữu ích để làm điều gì đó thay vì chỉ tính toán con đường ngắn nhất.

Bắt đầu n kiến ​​ở nút n ngẫu nhiên. Bạn sẽ cần phải điều chỉnh n với phương pháp thử và lỗi. Kiến để lại một pheromone trên các cạnh đi. Pheromone bay hơi trong thời gian. Kiến chọn một trong các cạnh riêng biệt để di chuyển theo xác suất. Pheromone càng có nhiều cạnh thì càng có nhiều kiến ​​sẽ chọn cạnh đó.

Trong kiến ​​bắt đầu di chuyển hoàn toàn ngẫu nhiên, vì không có pheromone và các cạnh có khả năng tương tự. Tuy nhiên, theo thời gian, các cạnh phổ biến nhất, các cầu nối giữa hai thành phần "kết nối mờ" sẽ có ngày càng nhiều pheromone trên chúng.

Vì vậy, bạn ném n kiến, mô phỏng cho m lần lượt và trả về các cạnh có số lượng pheromone cao nhất trên chúng. Bạn có thể hình dung quá trình này để xem rõ những gì đang diễn ra.

Cập nhật: tôi nhận ra rằng câu "Tuy nhiên, theo thời gian, các cạnh phổ biến nhất, cầu giữa hai 'hơi quăn kết nối' các thành phần sẽ có ngày càng nhiều pheromone trên chúng" là sai. Tôi implemented nó và nó trông giống như hầu hết các cầu thời gian không nhất thiết phải thu hút kiến:

Có n = 1.000 kiến ​​và m = 1.000 bước.Ban đầu, mỗi cạnh có 1 đơn vị pheromone và nó tăng lên 1 nếu kiến ​​đi qua nó. Không bốc hơi, tuy nhiên tôi nghĩ rằng nó sẽ không cải thiện tình hình. Cầu có 49845 đơn vị pheromone, nhưng có ba cạnh khác có hơn 100k.

---

Theo đề nghị của Peter de Rivaz trong các bình luận, tôi đã cố gắng (source code) lặp đi lặp lại min-cut giữa 2 nút ngẫu nhiên và nó là tốt hơn nhiều:

_{đồ thị được tạo ra với python-igraph thư viện.}