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. . | Nội dung Mạng xã hội Thuật toán PageRank Thuật toán HIST [IT4868] Khai phá Web 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 Mạng xã hội Ví dụ Chương 2 Phân tích mạng xã hội 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 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: 8 Chương 2 Phân tích mạng xã hội 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 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 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 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 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 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 .
