App: nhúng và vẽ đồ thị force-directed

Giới thiệu

Bài này học vẽ đồ thị bằng lực lò xo. Nút kề kéo nhau, nút xa đẩy nhau thành tranh thoáng.

Kiến thức cần nhớ

Layout force-directed là gì

• Đặt nút bừa rồi lặp lực đẩy và lực hút lò xo.
• Lực đẩy tách mọi cặp nút, lực hút kéo nút kề lại.
• Giới hạn bước dịch giảm dần như nhiệt độ nguội.
• Ví dụ đời thường: thả bi nam châm tự giãn thành hình đều.

SA tinh chỉnh giảm giao cắt

• Năng lượng = số cạnh cắt nhau + độ lệch dài cạnh.
• Đề xuất dịch bừa, đẹp lên thì giữ, xấu vẫn giữ theo nhiệt.
• Giảm ít nhất 30% giao cắt so với đặt bừa.
• Lưới 6x6 vẽ đúng phải về 0 giao cắt.

Embedding học vector nút

• Học 1 vector cho mỗi nút bằng gradient descent.
• Nút kề nhau phải gần nhau trong không gian vector.
• Chiếu xuống 2D để vẽ và so cụm với layout vật lý.
• Nút kề có khoảng cách nhỏ hơn cặp ngẫu nhiên.

Ví dụ

• Input: lưới 6x6 đặt bừa rối tung. Output: sau layout hiện rõ ô lưới, 0 giao cắt.
• Giải thích: lực lò xo duỗi thẳng từng ô lưới.
• Input: đồ thị ngẫu nhiên 100 nút. Output: SA giảm giao cắt ít nhất 30%.
• Giải thích: chấp nhận xấu tạm giúp thoát bố cục rối ban đầu.

💻 Bài tập

Ngôn ngữ: Python 3 với NumPy, networkx, matplotlib. Dùng code ngày 112, 121. Nộp vào day-137-graph-embed/.

Bài 1: Force-directed có nguội

1. Cài lại Fruchterman-Reingold: lực đẩy mọi cặp, lực hút theo cạnh, bước dịch tối đa t giảm dần mỗi vòng.
2. Dùng lưới ô để chỉ tính lực đẩy với đỉnh trong ô lân cận (giảm $O(n^2)$).
3. Chạy trên lưới 6x6: phải về 0 giao cắt. Chạy trên đồ thị 1000 đỉnh 3000 cạnh.

Lưới 6x6 xáo trộn -> 0 giao cắt sau khi chạy
Đồ thị ngẫu nhiên -> giao cắt giảm ít nhất 30% so với đặt ngẫu nhiên

Bài 2: SA tinh chỉnh

Dùng SA ngày 121 bắt đầu từ kết quả force-directed, nhiệt độ thấp. So số giao cắt trước và sau. In thời gian.

Bài 3: Graph embedding bằng gradient (nâng cao)

1. Học vector 16 chiều cho mỗi đỉnh bằng gradient descent: loss kéo cặp đỉnh kề gần nhau, đẩy cặp đỉnh lấy mẫu ngẫu nhiên (negative sampling) ra xa. $L = -\log\sigma(z_u \cdot z_v) - \sum \log\sigma(-z_u \cdot z_n)$.
2. Chạy trên đồ thị có 4 cộng đồng (stochastic block model). Chiếu xuống 2D bằng PCA (ngày 84). Tô màu theo cộng đồng thật.
3. Gom cụm embedding bằng K-means k = 4. Tính ARI so với cộng đồng thật.
4. So hình 2D của embedding với layout force-directed.

✅ Tiêu chí hoàn thành

• Lưới 6x6 về 0 giao cắt.
• Bảng giao cắt: ngẫu nhiên, force, force + SA.
• Embedding tách 4 cộng đồng, ARI trên 0.8.
• Có hình so sánh embedding và layout.

❓ Câu hỏi ôn tập

• Lực đẩy và lực hút mỗi cái giữ vai trò gì?
• Năng lượng vẽ đồ thị gồm 2 số hạng nào?
• Embedding khác layout vật lý ở mục tiêu nào?
• Đo tranh đẹp bằng 2 metric nào?

🌕 Bạn đã hoàn thành ngày 137. Làm hết bài tập phía trên rồi sang ngày tiếp theo.