Network Link Prediction (dự đoán liên kết trong mạng) là một nhánh của khoa học mạng (network science) và machine learning, với mục tiêu dự đoán xem liệu hai nút trong mạng có khả năng hình thành một liên kết mới trong tương lai hay không, hoặc khôi phục các liên kết bị thiếu.
Điều này rất có ý nghĩa vì trong nhiều hệ thống thực tế (mạng xã hội, sinh học, kinh tế), mạng luôn thay đổi theo thời gian. Dữ liệu thu thập thường không đầy đủ, có thể bị thiếu liên kết. Khi đó, link prediction sẽ giúp hiểu rõ cấu trúc mạng, phát hiện mối quan hệ tiềm ẩn và dự đoán sự phát triển của mạng trong tương lai.
Phương pháp chính
- Dựa trên độ tương đồng (similarity-based methods)
- Local similarity: tính dựa trên hàng xóm chung
- Global similarity: dùng đường đi ngắn nhất, Katz index, random walk.
- Các chỉ số khác: Jaccard, Adamic–Adar, Resource Allocation.
- Dựa trên mô hình xác suất
- Giả định một mô hình sinh mạng (graph generative model). Ví dụ như Stochastic Block Model (SBM), mô hình đồ thị ngẫu nhiên, mô hình xác suất Bayes.
- Dựa trên machine learning / deep learning
- Trích xuất đặc trưng (features) từ cặp nút và huấn luyện mô hình phân loại (SVM, logistic regression).
- Graph embedding (node2vec, DeepWalk, Graph Neural Networks – GNNs) → học vector đặc trưng cho nút, dự đoán xác suất liên kết bằng khoảng cách vector.
Một số ứng dụng
- Mạng xã hội, ví dụ: gợi ý bạn bè, gợi ý kết nối trên Facebook, LinkedIn.
- Thương mại điện tử, ví dụ: gợi ý sản phẩm (user–item link).
- Sinh học, ví dụ: dự đoán tương tác protein–protein, gen–bệnh, thuốc–mục tiêu.
- Hệ thống tri thức, ví dụ: hoàn thiện mạng tri thức (knowledge graphs) bằng cách thêm quan hệ còn thiếu.
- An ninh mạng, ví dụ: phát hiện kết nối bất thường.
- Và nhiều các ứng dụng tiềm năng khác
Tài liệu tham khảo
- https://www.sciencedirect.com/science/article/pii/S221509862400168X
- https://www.sciencedirect.com/topics/computer-science/link-prediction
- https://arxiv.org/pdf/2305.10257
- https://www.tandfonline.com/doi/full/10.1080/17460441.2023.2267020