Bài giảng Khai phá web - Bài 5: Phân tích liên kết (Phần 2)

Chia sẻ: Dương Hoàng Lạc Nhi | Ngày: | Loại File: PDF | Số trang:38

Thêm vào BST

Báo xấu

27
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Khai phá web - Bài 5: Phân tích liên kết (Phần 2). Bài này cung cấp cho học viên những nội dung về: nhận diện cộng đồng; thuật toán Kernighan–Lin; thuật toán Girvan-Newman; học biểu diễn đồ thị;... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Khai phá web - Bài 5: Phân tích liên kết (Phần 2)

BÀI 5: PHÂN TÍCH LIÊN KẾT (TIẾP)
2. Nhận diện cộng đồng 2.1 Nhận diện cộng đồng ◼ Phát hiện các cộng đồng trong mạng lưới ◼ Các thành viên trong cộng đồng có tính chất tương tự nhau ◼ Các cộng đồng có thể có mối liên hệ với nhau ◼ Số lượng cộng đồng phụ thuộc vào thuật toán from Fortunato (2015) 2
a) Zachary’s karate club b) Collaboration network between scientists working at the Santa Fe Institute c) Lusseau’s network of bottlenose dolphins 3 from Fortunato (2015)
Community structure in protein–protein interaction networks 4 from Fortunato (2015)
Overlapping communities in a network of word association 5 from Fortunato (2015)
Community structure of a social network of mobile phone communication in Belgium 6 from Fortunato (2015)
Network of friendships between students at Caltech from Fortunato (2015) 7
Map of science derived from a clustering analysis of a citation network 8 from Fortunato (2015)
2.2 Thuật toán Kernighan–Lin Bài toán lắt cắt nhỏ nhất: Phân miền đồ thị vô hướng thành hai miền có số đỉnh tương đương sao cho tổng trọng số của các cạnh nối hai cụm là nhỏ nhất 9
Thuật toán ◼ G = (V, E) ◼ Chia các đỉnh vào hai cụm A và B không trùng lặp ◼ a ∈ A: Chi phí bên trong Ia = Σ u ∈ A ca,u Chi phí bên ngoài Ea = Σ ∈ B ca,v Da = Ea – Ia ◼ b ∈ B, chi phí giảm nếu đổi chỗ a và b Told - Tnew = Da + Db – 2ca,b ◼ Lặp lại việc tìm các cặp tối ưu (a,b) để giảm chi phí trong khi tổng chi phí (của lát cắt) tiếp tục giảm 10
Cập nhật chi phí 11
VD 12
Thuật toán 13
Độ phức tạp tính toán ◼ Khởi tạo tính toán D: O(n2) (line 4) ◼ Vòng lặp: O(n) (line 5) ◼ Thân vòng lặp: O(n2) ◼ Bước i cần (n – i + 1)2 thời gian ◼ Mỗi vòng lặp: O(n3) (line 4-11) ◼ Giả sử thuật toán kết thúc sau r vòng lặp ◼ Tổng thời gian: O(rn3) 14
VD 15
VD (tiếp) 16
VD (tiếp) 17
VD (tiếp) a d 18
VD (tiếp) 19
2.3 Thuật toán Girvan-Newman ◼ Tìm các cầu nối giữa các cộng đồng dựa trên khả năng thông qua ◼ Lặp lại với các cộng đồng để tìm các cộng đồng con ◼ Kết quả là các cây phân cấp với gốc là toàn bộ đồ thị, lá là các đỉnh của đồ thị 20