Dự đoán kết nối cạnh đồ thị
Tôi có một tập hợp các nút trong không gian vật lý 3d. Một số trong số các nút đó được kết nối với nhau bằng một cạnh đồ thị, trong khi những nút khác thì không. Chỉ vì hai nút gần nhau không có nghĩa là chúng được kết nối với nhau. (Ví dụ: Nút A và Nút B có thể nằm cạnh nhau về mặt vật lý, nhưng không có cạnh biểu đồ nào cho phép di chuyển giữa chúng.) Tôi biết trước về sự tồn tại của tất cả các nút, nhưng tôi không nhất thiết phải biết chính xác của chúng địa điểm thực tế. Tôi không biết trước bất kỳ cạnh nào.
Một người quan sát di chuyển xung quanh trong biểu đồ này bằng cách sử dụng một công cụ để xác định xem họ hiện đang ở nút nào. Công cụ này có độ chính xác hợp lý, nhưng đôi khi sẽ nhầm lẫn một nút với một nút khác gần đó. Ví dụ, thông thường khi người quan sát ở Nút A, thiết bị sẽ đọc "Nút A." Đôi khi, nó sẽ đọc "Node B." Công cụ có khả năng cho điểm tin cậy.
Nếu người quan sát di chuyển xung quanh biểu đồ này trong một khoảng thời gian dài và tôi có các kết quả đọc liên tục từ thiết bị, tôi có thể tìm hiểu biểu đồ không? (Giả sử các lần đọc đủ gần nhau để không có "khoảng trống" về thời gian khi người quan sát di chuyển nhiều hơn 1 nút.) Về cơ bản, tôi cần tách riêng các chuyển đổi (Nút A -> Nút B) xảy ra do các cạnh thực trong đồ thị từ các chuyển đổi từ chuyển đổi giả xảy ra do thiết bị đọc sai.
Tôi đã thực hiện khá nhiều Google, nhưng dường như tôi không thể tìm thấy nhiều về vấn đề cụ thể này. Hầu hết các tài liệu về "dự đoán cạnh" dường như là về dự đoán các cạnh đồ thị mới khi một loạt các cạnh đồ thị đã được biết trước (ví dụ: trong mạng xã hội). Nhưng, điều này không liên quan đến vấn đề của tôi.
Có cơ quan văn học nào tôi nên xem không? Một cụm từ tìm kiếm thậm chí có thể đủ như một câu trả lời cho câu hỏi của tôi.
Điều này cũng liên quan đáng kể đến mô hình Markov ẩn, nhưng tôi không biết trước bất kỳ xác suất chuyển đổi hoặc phát xạ nào và về cơ bản muốn tìm hiểu các xác suất chuyển đổi ...
Trả lời
Một giải pháp là sử dụng công cụ ước tính kích thước mẫu và điểm tin cậy phát hiện cạnh của bạn để lập bản đồ các cạnh “tự tin” nhất.
Ví dụ: nếu bạn thường xuyên quan sát đường truyền duy nhất giữa Nút A và Nút B và với độ tin cậy cao, đây có thể là một lợi thế. Tuy nhiên, nếu bạn quan sát thấy tương đối ít đường đi ngang giữa nút B đến nút C và với độ tin cậy thấp, thì đây không phải là một lợi thế. Như bạn đã chỉ ra, bạn có thể muốn sử dụng tiêu chí chấp nhận cao hơn cho các nút gần nhau về mặt vật lý để tránh tạo ra các cạnh sai do lỗi tín hiệu.
Các tọa độ GPS này hoặc dữ liệu tương tự có trong mạng động không? Nếu vậy, phương pháp trên có thể được áp dụng cho các mức độ phân giải không gian khác nhau, ví dụ: độ phân giải thô để phát hiện các tuyến đường chính và đường cao tốc, vừa phải cho đường khu vực, cao cho đường địa phương, v.v.