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

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