Bài giảng Khai phá Web: Chương 2 - TS. Nguyễn Kiêm Hiếu

Bài giảng "Khai phá Web - Chương 2: Phân tích mạng xã hội" cung cấp cho người học các kiến thức: Mạng xã hội, thuật toán PageRank, thuật toán HIST, nhận dạng cộng đồng. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Khai phá Web: Chương 2 - TS. Nguyễn Kiêm Hiếu Nội dung 2.1 Mạng xã hội 2.2 Thuật toán PageRank 2.3 Thuật toán HIST [IT4868] Khai phá Web 2.4 Nhận dạng cộng đồng Chương 2: Phân tích mạng xã hội 2 Chương 2 Phân tích mạng xã hội 2.1 Mạng xã hội Ví dụ Chương 2 Phân tích mạng xã hội 2.1 Mạng xã hội Ví dụ ● www ● FB, Twitter, weibo, zalo ● Wikipedia ● Mạng lưới bài báo khoa học, mạng l ưới h ợp tác ● Mạng lưới người dùng di động 3 4 5 6 Chương 2 Phân tích mạng xã hội 2.1 Mạng xã hội Phân tích mạng xã hội “Phân tích mạng xã hội là nghiên c ứu các th ực thể xã hội (tác nhân) và s ự tương tác, liên k ết giữa chúng.” - Bing Liu 7 Source: https://kieranhealy.org/blog/archives/2013/06/18/a-co-citation-network-for-philosophy/ 8 Chương 2 Phân tích mạng xã hội 2.1 Mạng xã hội Phân tích mạng xã hội ● Chương 2 Phân tích mạng xã hội 2.1 Mạng xã hội Một số khái niệm cơ bản của đồ thị Phân tích vai trò của các tác nhân trong m ạng xã hội ● Đồ thị = {đỉnh, cạnh} ● Đồ thị vô hướng/có hướng ● Nhận dạng các cộng đồng trong mạng xã h ội ● Ma trận kề ● Dự đoán các liên kết trong m ạng xã h ội ● Bậc của đỉnh ● Đường đi ngắn nhất 9 Chương 2 Phân tích mạng xã hội 2.1 Mạng xã hội Một số khái niệm cơ bản của đồ thị 10 Chương 2 Phân tích mạng xã hội 2.1 Mạng xã hội Một số khái niệm cơ bản của đồ thị ● Ma trận kề: – a[i, j] = 1 nếu tồn tại cạnh (i,j) = 0 nếu ngược lại = 2 nếu tồn tại cạnh từ một đ ỉnh đ ến chính nó ` ` a) Đồ thị vô hướng b) Đồ thị có hướng 11 12 Chương 2 Phân tích mạng xã hội 2.1 Mạng xã hội Một số khái niệm cơ bản của đồ thị ● Chương 2 Phân tích mạng xã hội 2.1 Mạng xã hội Một số khái niệm cơ bản của đồ thị Bậc của đỉnh: ● di(i) = số nút trỏ tới i ● do(i) = số nút i trỏ tới Thuật toán Dijkstra tìm đ ường đi ng ắn nh ất t ừ một đỉnh s tới các đỉnh còn lại của đ ồ th ị d(v): Khoảng cách từ đỉnh v tới đỉnh s B1: Khởi tạo d(s) = 0; d(v) = oo B2: Sắp xếp các đỉnh v theo một trật tự xác định trên hàng đợi Q B3: Lấy một đỉnh u thuộc hàng đợi Q và cập nhật khoảng cách d(v) (nếu cần) với mỗi đỉnh v liền kề với u Quay lại B2 cho đến khi xử lý hết các đỉnh 13 15 ` 16 17 18 19 20 21