Egonet và centrality - degree, betweenness, closeness, eigenvector

Mạng lưới lấy ego làm trung tâm, vùng lân cận một và hai bước, tam giác, mật độ, và bốn độ đo centrality kèm quy trình phân tích chung.

Trung bìnhThuật toán ~60 phút

Ôn lại trước khi học

Thuật toán và môi trường phát triển

Giới thiệu

Bài này học egonet nhìn mạng từ một người trung tâm. Bài cũng học 4 cách đo ai quan trọng nhất.

Kiến thức cần nhớ

Egonet là gì

Ego là đỉnh trung tâm, alter là bạn trực tiếp.
Egonet 1 bước chỉ lấy bạn trực tiếp.
Egonet 2 bước lấy thêm bạn của bạn.
Ví dụ đời thường: soi 2 vòng bạn quanh tài khoản đáng ngờ.

Tam giác và mật độ

Tam giác là 3 đỉnh đôi một kề nhau.
Tam giác nhiều nghĩa là cộng đồng gắn kết.
Mật độ là số cạnh thật chia số cặp có thể.
Ví dụ đời thường: nhóm lừa đảo hay giao dịch vòng tròn khép kín.

Bốn độ đo quan trọng

Degree: số bạn trực tiếp, tìm người nổi tiếng.
Betweenness: số đường đi ngắn nhất giữa các cặp đỉnh khác phải đi qua mình, tìm gác cổng.
Closeness: nghịch đảo tổng khoảng cách, tìm nơi lan tin nhanh.
Eigenvector: chơi với người lớn thì mình cũng lớn.
Ví dụ đời thường: cầu duy nhất nối hai làng thì degree thấp nhưng betweenness cao.

Độ đo	Hỏi gì	Dùng khi
Degree	Nhiều bạn không	Tìm nổi tiếng
Betweenness	Gác cổng không	Tìm nút thắt
Closeness	Gần mọi người không	Chọn nơi phát tin
Eigenvector	Bạn có lớn không	Xếp hạng uy tín

Ví dụ

Input: sao 1 trung tâm nối 5 lá -> Output: trung tâm degree 5, lá betweenness 0.
Câu này cho thấy trung tâm nắm hết luồng đi.
Input: đường thẳng 4 đỉnh -> Output: 2 đỉnh giữa betweenness cao hơn 2 đầu.
Câu này cho thấy gác cổng nằm ở giữa đường.

💻 Bài tập

Ngôn ngữ: Python 3 (được dùng collections, không dùng networkx trừ khi đối chiếu kết quả). Nộp vào day-044/. Đồ thị vô hướng, lưu dict[int, set[int]].

Bài 1: Egonet và tam giác

Hàm	Yêu cầu
`egonet(G, ego, radius=1)`	Trả đồ thị con gồm ego và các đỉnh cách ego tối đa `radius` bước
`count_triangles(G)`	Đếm tam giác, mỗi tam giác đếm 1 lần
`density(G)`	$\frac{2m}{n(n-1)}$
`clustering(G, v)`	Tỉ lệ cặp bạn của `v` cũng là bạn nhau

Sao 1 tâm nối 5 lá      -> triangles 0, density 0.333, clustering(tâm) 0
Đồ thị đầy đủ K4        -> triangles 4, density 1.0

Bài 2: Bốn độ đo trung tâm

Hàm	Công thức
`degree_centrality(G)`	$\deg(v) / (n-1)$
`closeness(G)`	$(n-1) / \sum_u d(v,u)$ , dùng BFS
`betweenness(G)`	Thuật toán Brandes, $O(nm)$
`eigenvector(G, iters=100)`	Lặp lũy thừa, chuẩn hóa vector mỗi vòng

Đường thẳng 0-1-2-3: betweenness (không chuẩn hóa) -> [0, 2, 2, 0]
Sao 1 tâm 5 lá:      betweenness tâm = 10, lá = 0

Bài 3: Phân tích mạng thật (nâng cao)

Tải mạng Zachary's Karate Club (34 đỉnh, 78 cạnh, có trong nhiều nguồn công khai).

In top 5 đỉnh theo từng độ đo. Chỉ ra đỉnh nào là "gác cổng" và vì sao.
So kết quả với networkx để kiểm tra, sai số dưới 1e-6.
Vẽ đồ thị (matplotlib) với kích thước đỉnh tỉ lệ betweenness.

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

Test mẫu pass.
Betweenness khớp networkx trên Karate Club.
Bảng top 5 kèm nhận xét cho từng độ đo.
Giải thích được khác biệt giữa degree và betweenness bằng một ví dụ.

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

Egonet 1 bước và 2 bước khác nhau sao?
Tam giác và mật độ nói lên gì?
Betweenness khác degree ở chỗ nào?
Muốn lan tin nhanh thì dùng độ đo nào?

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

Ngày 43

A* heuristic và Prim cây khung nhỏ nhất

Ngày 45

K-d tree - luân phiên chiều, bất biến và cân bằng