[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
9
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 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:ậ ủ ỉ
d
i
(i) = s nút tr t i ố ỏ ớ i
d
o
(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