Nghiên cứu độ đo trung gian và thuật toán phát hiện cộng đồng trên mạng xã hội

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN

THÔNG

DƯƠNG THỊ TÌNH

NGHIÊN CỨU ĐỘ ĐO TRUNG GIAN VÀ THUẬT TOÁN

PHÁT HIỆN CỘNG ĐỒNG TRÊN MẠNG XÃ HỘI

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên - 2020

LỜI CAM ĐOAN

Tôi xin cam đoan các kết quả nghiên cứu trong luận văn này là do tự

bản thân tôi tìm hiểu dưới sự hướng dẫn của PGS. TS. Đoàn Văn Ban. Các

chương trình thực nghiệm do chính bản thân tôi lập trình, các kết quả là hoàn

toàn trung thực. Các thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn

gốc.

TÁC GIẢ LUẬN VĂN

Dương Thị Tình

LỜI CẢM ƠN

Để hoàn thành được luận văn này, tôi đã nhận được rất nhiều sự quan

tâm, giúp đỡ và góp ý quý báu của các cá nhân và tập thể.

Trước hết tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo PGS.TS. Đoàn

Văn Ban đã quan tâm, định hướng và đưa ra những góp ý chỉnh sửa quý báu

cho tôi trong quá trình làm luận văn tốt nghiệp.

Đồng thời tôi cũng xin chân thành cảm ơn sự góp ý chân thành của các

thầy, cô giáo Viện Công nghệ thông tin, các thầy, cô giáo Trường Đại học Công

nghệ thông tin và Truyền thông Thái Nguyên đã tạo mọi điều kiện thuận lợi

cho tôi hoàn thành đề tài này.

Dù đã rất cố gắng nhưng chắc chắn sẽ không tránh khỏi những thiếu sót

vì vậy rất mong nhận được sự góp ý của các thầy, cô và các bạn để luận văn

này được hoàn thiện hơn.

Tôi xin chân thành cảm ơn!

Thái Nguyên, tháng 08 năm 2020

Dương Thị Tình

MỤC LỤC

Trang

MỞ ĐẦU .......................................................................................................... 1

CHƯƠNG 1 MẠNG XÃ HỘI VÀ CÁC ĐỘ ĐO TRÊN ĐỒ THỊ MẠNG

XÃ HỘI ............................................................................................................ 4

1.1. MẠNG XÃ HỘI ......................................................................................... 4

1.2. CẤU TRÚC CỘNG ĐỒNG MẠNG XÃ HỘI...................................................... 8

1.3. CÁC ĐỘ ĐO TRÊN ĐỒ THỊ MẠNG XÃ HỘI.................................................. 11

1.3.1. Hệ số cố kết của mạng .................................................................. 12

1.3.2. Hệ số trung tâm vector đặc trưng.................................................. 13

1.3.3. Độ đo trung tâm của đỉnh.............................................................. 14

1.3.4. Hệ số trung gian của đỉnh ............................................................. 18

1.3.5. Độ đo trung gian của cạnh ............................................................ 20

1.4. THUẬT TOÁN TÍNH ĐỘ TRUNG GIAN ....................................................... 22

1.5. KẾT LUẬN CHƯƠNG ............................................................................... 26

CHƯƠNG 2 THUẬT TOÁN PHÁT HIỆN CỘNG ĐỒNG MẠNG XÃ HỘI

......................................................................................................................... 27

2.1. BÀI TOÁN PHÁT HIỆN CỘNG ĐỒNG TRÊN ĐỒ THỊ MẠNG XÃ HỘI............... 27

2.2. THUẬT TOÁN PHÂN CỤM PHÂN CẤP........................................................ 28

2.3. THUẬT TOÁN PHÁT HIỆN CỘNG ĐỒNG DỰA TRÊN TỐI ƯU HOÁ ĐỘ ĐO ĐƠN

THỂ............................................................................................................... 30

2.4. THUẬT TOÁN PHÁT HIỆN CỘNG ĐỒNG DỰA VÀO ĐỘ ĐO TRUNG GIAN...... 30

2.5. PHÁT HIỆN CÁC CỘNG ĐỒNG GỐI NHAU.................................................. 33

2.5.1. Phát hiện các k-cliques trong mạng xã hội ................................... 34

2.5.2. Thuật toán phát hiện k-clique........................................................ 36

2.5.3. Thuật toán EAGLE ....................................................................... 38

2.5.4. Đánh giá thuật toán ....................................................................... 43

2.6. KẾT LUẬN CHƯƠNG 2............................................................................. 44

CHƯƠNG 3 ỨNG DỤNG THUẬT TOÁN GIRVAN-NEWMAN TRONG

PHÁT HIỆN CỘNG ĐỒNG MẠNG XÃ HỘI.......................................... 45

3.1. MÔ TẢ BÀI TOÁN PHÁT HIỆN CỘNG ĐỒNG MẠNG XÃ HỘI ........................ 45

3.2. CHƯƠNG TRÌNH PHÁT HIỆN CỘNG ĐỒNG MẠNG XÃ HỘI .......................... 45

3.2.1. Bộ cơ sở dữ liệu ............................................................................ 45

3.2.2. Môi trường thử nghiệm................................................................. 47

3.2.3. Thử nghiệm và đánh giá................................................................ 49

3.3. KẾT LUẬN CHƯƠNG 3............................................................................. 54

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN................................................... 55

TÀI LIỆU THAM KHẢO ............................................................................ 56

DANH MỤC CÁC HÌNH VẼ

Hình 1.1. Mạng xã hội Facebook...................................................................... 7

Hình 1.2. Mạng xã hội Zing me ........................................................................ 7

Hình 1.3. Mô hình mạng lưới cộng tác của các nhà khoa học làm việc tại SFI9

Hình 1.4. Đồ thị có 4 đỉnh và 5 cạnh .............................................................. 15

Hình 1.5. Những đồ thị hình sao, bánh xe có số đỉnh 3, 4, 5, 6, 7.................. 17

Hình 1.6. Đồ thị mạng xã hội đơn giản gồm 7 nút ......................................... 21

Hình 2.1. Phát hiện cộng đồng mạng sử dụng Girven-Newman .................... 32

Hình 2.2. Ví dụ 1-clique, 2-clique và 3-clique................................................ 35

Hình 2.3. 2-cliques, 2-clan và 2-club.............................................................. 36

Hình 2.4. (a), (b). Mạng ban đầu..................................................................... 40

Hình 2.5. (c). Các cộng đồng được phát hiện bởi thuận toán của Newman ... 41

Hình 2.6.(d). Các cộng đồng được phát hiện bởi thuật toán k-clique............. 41

Hình 2.7.(e). Các cộng đồng thể hiện sự chồng chéo và phân cấp rõ ràng được

phát hiện bởi thuật toán EAGLE..................................................................... 42

Hình 3.1. Mô phỏng số cộng đồng tìm được trong đồ thị simple_network.... 49

Hình 3.2. Mô phỏng số cộng đồng tìm được trong bộ dữ liệu dolphin. ......... 50

Hình 3.3. Mô phỏng số cộng đồng tìm được trong bộ dữ liệu karate............. 50

Hình 3.4. Mô phỏng số cộng đồng tìm được trong bộ dữ liệu football.......... 51

Hình 3.5. Mô phỏng kết quả tìm kiếm cộng đồng trên bộ dữ liệu amazon_small

......................................................................................................................... 51