Giáo trình Tin học đại cương - Chương 2: Phân tích mạng xã hội

[IT4868] Khai phá Web Ch ng 2: Phân tích m ng xã h iươ ạ ộ 2 N i dungộ 2.1 M ng xã h iạ ộ 2.2 Thu t toán PageRankậ 2.3 Thu t toán HISTậ 2.4 Nh n d ng c ng đ ngậ ạ ộ ồ 3 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ạ ướ ườ ộ 4 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.1 M ng xã h iạ ộ Ví dụ 5 6 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ạ ộ “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 9Ch 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 vai trò c a các tác nhân trong m ng ủ ạ xã h iộ ● Nh n d ng các c ng đ ng trong m ng xã h iậ ạ ộ ồ ạ ộ ● D đoán các liên k t trong m ng xã h iự ế ạ ộ 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ộ ố ệ ơ ả ủ ồ ị ● Đ th = {đ nh, c nh}ồ ị ỉ ạ ● Đ th vô h ng/có h ngồ ị ướ ướ ● Ma tr n kậ ề ● B c c a đ nhậ ủ ỉ ● Đ ng đi ng n nh tườ ắ ấ 11 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ộ ố ệ ơ ả ủ ồ ị ` a) Đ th vô h ngồ ị ướ b) Đ th có h ngồ ị ướ 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ộ ố ệ ơ ả ủ ồ ị ` ● 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óế ồ ạ ạ ừ ộ ỉ ế 13 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ỏ ớ 15 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ộ ố ệ ơ ả ủ ồ ị ● 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ế ử ế ỉ 16 17 ` 18 19 20 21 22 23 24 25 26 27 28 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.1 M ng xã h iạ ộ Đ t p trung c a đ nhộ ậ ủ ỉ Phân tích vai trò c a các đ nh trong đ th d a ủ ỉ ồ ị ự trên: – Đ trung tâm: Nút ộ i có là thành ph n trung tâm c a ầ ủ đ th không?ồ ị – Đ quan tr ng: Nút ộ ọ i có đóng vai trò quan tr ng ọ trong đ thì không?ồ 29 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.1 M ng xã h iạ ộ Đ trung tâmộ Đ th vô h ng:ồ ị ướ Đ th có h ng:ồ ị ướ Đ trung tâm theo b c:ộ ậ [0,1] d(i): b c c a đ nh i ậ ủ ỉ n: S đ nh c a đ thố ỉ ủ ồ ị d 0 (i): b c ra c a đ nh iậ ủ ỉ ` 30 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.1 M ng xã h iạ ộ Đ trung tâmộ Đ trung tâm lân c n:ộ ậ d(i, j): Kho ng cách ng n nh t t nút i t i nút jả ắ ấ ừ ớ 31 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.1 M ng xã h iạ ộ Đ trung tâmộ Đ trung tâm trung gian:ộ p jk (i): S l ng đ ng đi ng n nh t t ố ượ ườ ắ ấ ừ j t i ớ k mà đi qua i C B (1) = 15, C B (2) = C B (3) = C B (4) = C B (5) = C B (6) = C B (7) = 0 32 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.1 M ng xã h iạ ộ Đ trung tâmộ 8 9 10 BTVN: Tính đ trung tâm c a các đ nh trong đ ộ ủ ỉ ồ th d i đây theo b c, trung gian, và lân c n ị ướ ậ ậ 33 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.1 M ng xã h iạ ộ Đ quan tr ngộ ọ Đ quan tr ng theo b c:ộ ọ ậ d i (i): S nút tr t i iố ỏ ớ 34 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.1 M ng xã h iạ ộ Đ quan tr ngộ ọ Đ quan tr ng lân c n:ộ ọ ậ I i : Các nút có th đi t i iể ớ 35 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.1 M ng xã h iạ ộ Đ quan tr ngộ ọ Đ quan tr ng th h ng:ộ ọ ứ ạ A ij = 1 n u i có th đi t i j, ng c l i Aế ể ớ ượ ạ ij = 0 ` 36 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.2 Thu t toán PageRankậ Lawrence (Larry) Page et al. 1999. “The PageRank Citation Ranking: Bringing Order to the Web” 1999: 150M pages, 1.7B links 37 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.2 Thu t toán PageRankậ Transition matrix ` 38 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.2 Thu t toán PageRankậ Transition matrix ` Chu n hóa:ẩ 39 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.2 Thu t toán PageRankậ Ranking PR(A) = (1 – d) / N + d * sum B:(B,A) in E PR(B) / d o (B) PR(A): Ranking c a đ nh Aủ ỉ d: damping factor N: s đ nh c a đ thố ỉ ủ ồ ị (B,A) c nh c a đ thạ ủ ồ ị d o (B) b c ra c a đ nh Bậ ủ ỉ 40 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.2 Thu t toán PageRankậ Ví d ụ (d = 1) 41 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.2 Thu t toán PageRankậ Ví d ụ (d = 1) 42 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.2 Thu t toán PageRankậ Ví d ụ (d = 0.85) 43 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.2 Thu t toán PageRankậ Luy n t p ệ ậ (d = 0.7) a) b) c) 44 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.2 Thu t toán PageRankậ Luy n t p ệ ậ (d = 0.7) a) 45 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.2 Thu t toán PageRankậ Luy n t p ệ ậ (d = 0.7) b) 46 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.2 Thu t toán PageRankậ Luy n t p ệ ậ (d = 0.7) c) 47 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.2 Thu t toán PageRankậ Cài đ tặ 48 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.2 Thu t toán PageRankậ T c đ h i tố ộ ộ ụ 49 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.2 Thu t toán PageRankậ T c đ h i tố ộ ộ ụ BTVN: ● T i Wikipedia ti ng Vi t t i ả ế ệ ạ https://dumps.wikimedia.org/viwiki/20180901/ ● L c ra các đ th g m các trang ch đ ọ ộ ị ồ ủ ề (category pages) và liên k t gi a chúngế ữ ● Th c hi n thu t toán PageRank trên đ th và ự ệ ậ ồ ị in ra k t qu là tiêu đ các trang có ranking cao ế ả ề nh t ấ 50 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.2 Thu t toán PageRankậ ng d ng 1: Tìm ki m WebỨ ụ ế 51 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.2 Thu t toán PageRankậ ng d ng 2: Phân tích trích d nỨ ụ ẫ Guan et al. 2008. “Bringing Page-Rank to the Citation Analysis” 52 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.2 Thu t toán PageRankậ ng d ng: Phân tích trích d nỨ ụ ẫ 53 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.2 Thu t toán PageRankậ ng d ng 2: Phân tích trích d nỨ ụ ẫ 54 Ch ng 2 Phân tích m ng xã h iươ ạ ộ 2.2 Thu t toán PageRankậ ng d ng 2: Phân tích trích d nỨ ụ ẫ 55 Q&A hieunk@soict.hust.edu.vn