Xem mẫu
- BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC
VÀ CÔNG NGHỆ VIỆT NAM
HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ
……..….***…………
DƯƠNG NGỌC SƠN
MỘT SỐ PHƯƠNG PHÁP NÂNG CAO HIỆU QUẢ
DỰ BÁO LAN TRUYỀN THÔNG TIN TRÊN MẠNG XÃ HỘI
LUẬN ÁN TIẾN SĨ NGÀNH MÁY TÍNH
Hà Nội - 2022
- VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM
HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ
……..….***…………
DƯƠNG NGỌC SƠN
MỘT SỐ PHƯƠNG PHÁP NÂNG CAO HIỆU QUẢ
DỰ BÁO LAN TRUYỀN THÔNG TIN TRÊN MẠNG XÃ HỘI
LUẬN ÁN TIẾN SĨ NGÀNH MÁY TÍNH
Chuyên ngành : Hệ thống thông tin
Mã số: 9 48 01 04
Người hướng dẫn khoa học:
1. TS. Nguyễn Như Sơn
2. TS. Nguyễn Ngọc Cương
Hà Nội - 2022
- i
LỜI CAM ĐOAN
Tôi cam đoan đây là công trình nghiên cứu của riêng tôi, các số liệu, tài
liệu được sử dụng trong Luận án này được thu thập từ nghiên cứu thực tế; trong
đó, bao gồm một số kết quả nghiên cứu đã được đăng ở các tạp chí khoa học trong
và ngoài nước cũng như thử nghiệm thực tế “Hệ thống phân tích dữ liệu mạng xã
hội” mà tôi có cơ hội tham gia thực hiện. Các nội dung viết chung với các tác giả
khác đều được sự đồng ý của các đồng tác giả trước khi đưa vào Luận án. Ngoài
ra, những tài liệu tham khảo đều được trích dẫn nguồn đầy đủ.
Trân trọng,
Dương Ngọc Sơn
- ii
LỜI CẢM ƠN
Để có kết quả hôm nay, tôi xin cảm ơn Học viện Khoa học và công nghệ,
Viện Hàn lâm Khoa học và công nghệ Việt Nam đã tổ chức, đào tạo và hướng
dẫn tôi hoàn thành các thủ tục hoàn thiện Luận án. Tôi xin bày tỏ lòng biết ơn sâu
sắc đến TS. Nguyễn Ngọc Cương - Phó Cục trưởng Cục An ninh mạng và phòng
chống tội phạm sử dụng công nghệ cao, Bộ Công an và TS.Nguyễn Như Sơn -
Trưởng Phòng Các hệ thống phần mềm tích hợp, Viện Công nghệ thông tin, Viện
Hàn lâm Khoa học và công nghệ Việt Nam đã tận tình hướng dẫn, chỉ bảo và giúp
đỡ tôi trong suốt quá trình thực hiện Luận án.
Xin chân thành cảm ơn sự giúp đỡ của PGS.TS.Nguyễn Long Giang,
TS.Nguyễn Việt Anh - Viện Công nghệ thông tin, PGS.TS.Nguyễn Ngọc Hóa -
Trường Đại học Quốc gia Hà Nội đã truyền đạt cho tôi những kiến thức quý báu
làm tiền đề cho tôi từ quá trình bắt đầu nghiên cứu đến khi xây dựng và hoàn thiện
Luận án này.
Tôi cũng xin cảm ơn lãnh đạo đơn vị công tác Phòng Kỹ thuật và Viện
Nghiên cứu KTNV, Cục Kỹ thuật nghiệp vụ, Bộ Công an đã tạo điều kiện cho tôi
để tôi vừa làm việc, vừa học tập và thực hiện nghiên cứu. Trong quá trình làm
việc đã cho tôi có điều kiện tiếp xúc với các hệ thống kỹ thuật, tham dự các hội
thảo liên quan đến nội dung trình bày trong Luận án.
Cuối cùng, tôi xin gửi lời cảm ơn sâu sắc và chân thành đến Gia đình, những
người đã luôn ở bên ủng hộ, động viên để tôi có được ngày hôm nay. Trong quá
trình thực hiện Luận án, tôi cũng nhận được sự giúp đỡ của rất nhiều người mà
không tiện liệt kê ở đây, tôi xin cảm ơn và kính chúc tất cả mọi người sức khỏe,
hạnh phúc và thành công.
Dương Ngọc Sơn
- iii
MỤC LỤC
LỜI CAM ĐOAN .......................................................................................................................... i
LỜI CẢM ƠN ............................................................................................................................... ii
MỤC LỤC..................................................................................................................................... iii
DANH MỤC CÁC TỪ VIẾT TẮT ........................................................................................... v
DANH MỤC CÁC BẢNG ......................................................................................................... vi
DANH MỤC CÁC HÌNH ......................................................................................................... vii
MỞ ĐẦU ........................................................................................................................................ 1
1. Phát biểu vấn đề .......................................................................................................1
2. Lý do chọn đề tài .....................................................................................................3
3. Mục tiêu của luận án ................................................................................................3
4. Các đóng góp của luận án ........................................................................................4
5. Bố cục Luận án ........................................................................................................5
Chương I. TỔNG QUAN VỀ LAN TRUYỀN THÔNG TIN TRÊN MẠNG XÃ HỘI.. 6
1.1. Mạng xã hội và lan truyền thông tin trên mạng xã hội .........................................6
1.1.1. Mạng xã hội....................................................................................................6
1.1.2. Lan truyền thông tin trên mạng xã hội ...........................................................8
1.2. Các lĩnh vực nghiên cứu trong phân tích mạng xã hội .........................................9
1.2.1. Khai phá dữ liệu mạng xã hội ........................................................................9
1.2.2. Phân tích mô hình dữ liệu đồ thị ..................................................................10
1.2.3. Phát hiện cộng đồng .....................................................................................10
1.2.4. Dự báo lan truyền thông tin .........................................................................11
1.2.5. An toàn thông tin ..........................................................................................12
1.3. Phát biểu bài toán phát triển một số phương pháp nâng cao hiệu quả dự báo lan
truyền thông tin trên mạng xã hội ..............................................................................13
1.4. Các hướng nghiên cứu liên quan ........................................................................16
1.4.1. Nâng cao tốc độ dự báo lan truyền thông tin ...............................................16
1.4.2. Nâng cao độ chính xác dự báo lan truyền thông tin.....................................18
1.5. Phương pháp đề xuất ..........................................................................................20
1.6. Một số định nghĩa cơ bản....................................................................................21
1.6.1. Đồ thị ............................................................................................................21
1.6.2. Tính toán song song .....................................................................................26
1.6.3. Mô hình lan truyền thông tin........................................................................27
1.7. Kết luận Chương I ..............................................................................................28
- iv
Chương II. NÂNG CAO TỐC ĐỘ DỰ BÁO LAN TRUYỀN THÔNG TIN................. 30
2.1. Đặt vấn đề ...........................................................................................................30
2.2. Một số khái niệm liên quan.................................................................................33
2.2.1. Các phép toán trên đồ thị .............................................................................33
2.2.2. Độ trung tâm ................................................................................................37
2.2.3. Tính toán song song .....................................................................................39
2.3. Nâng cao tốc độ dự báo lan truyền thông tin ......................................................43
2.3.1. Rút gọn đồ thị ...............................................................................................43
2.3.2. Song song hóa quá trình tính toán độ trung tâm trung gian .........................47
2.3.3. Phương pháp kết hợp hai kỹ thuật ...............................................................50
2.4. Thực nghiệm và kết quả......................................................................................53
2.4.1. Dữ liệu thực nghiệm.....................................................................................53
2.4.2. Cài đặt thực nghiệm .....................................................................................53
2.4.3. Kết quả thực nghiệm ....................................................................................54
2.5. Kết luận Chương II .............................................................................................58
Chương III. NÂNG CAO ĐỘ CHÍNH XÁC DỰ BÁO LAN TRUYỀN THÔNG TIN 59
3.1. Đặt vấn đề ...........................................................................................................59
3.2. Một số khái niệm liên quan.................................................................................61
3.2.1. Mô hình lan truyền thông tin rời rạc ............................................................61
3.2.2. Mô hình Ngưỡng tuyến tính (LT) ................................................................62
3.2.3. Mô hình bậc độc lập (IC) .............................................................................64
3.2.4. Mô hình cạnh trực tuyến (live-edge)............................................................65
3.3. Nâng cao độ chính xác dự báo lan truyền thông tin ...........................................68
3.3.1. Ảnh hưởng của quan hệ người dùng ............................................................69
3.3.2. Ảnh hưởng sở thích của người dùng ............................................................71
3.3.3. Đo lường ảnh hưởng bên ngoài ....................................................................73
3.3.4. Xây dựng cây lan truyền ..............................................................................74
3.4. Thực nghiệm và kết quả......................................................................................76
3.4.1. Dữ liệu thực nghiệm.....................................................................................76
3.4.2. Phương pháp thực nghiệm ...........................................................................77
3.4.3. Kết quả thực nghiệm ....................................................................................78
3.5. Kết luận chương III .............................................................................................81
KẾT LUẬN CHUNG................................................................................................................. 83
DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ ............................................................ 86
TÀI LIỆU THAM KHẢO ........................................................................................................ 87
- v
DANH MỤC CÁC TỪ VIẾT TẮT
Từ viết
STT Viết đầy đủ Dịch nghĩa
tắt
Đường đi ngắn nhất giữa cặp đỉnh
1 APSP All-Pairs Shortest Path
bất kỳ
2 bBFS bi-directional BFS Duyệt theo chiều rộng cả 2 chiều
3 BC Betweenness Centrality Độ trung tâm trung gian
4 BFS Breadth-First Search Duyệt theo chiều rộng trước
5 CC Closeness Centrality Độ trung tâm gần
6 CPU Central Processing Unit Bộ xử lý trung tâm
7 DC Degree Centrality Độ trung tâm bậc
8 DFS Depth-First Search Duyệt theo chiều sâu trước
9 DS Dataset Bộ dữ liệu
10 EC Eigenvector Centrality Độ trung tâm vector riêng
11 GPU Graphic Processing Unit Bộ xử lý đồ họa
12 IC Independent Cascade Bậc độc lập
13 LT Linear Threshold Ngưỡng tuyến tính
14 RM Regression Model Mô hình hồi quy
Single-Destination Đường đi ngắn nhất đến 1 đỉnh
15 SDSP
Shortest Path đích
Single-Source Shortest Đường đi ngắn nhất từ 1 đỉnh
16 SSSP
Path nguồn
17 UI User Interaction Tương tác người dùng
- vi
DANH MỤC CÁC BẢNG
Bảng 2.1. So sánh thời gian lan truyền (s) ....................................................................47
Bảng 2.2. Kết quả tính BC và CC trước khi rút gọn .....................................................51
Bảng 2.3. Kết quả tính BC và CC sau khi rút gọn ........................................................52
Bảng 2.4. Thông tin các bộ dữ liệu thử nghiệm ............................................................53
Bảng 2.5. So sánh thời gian tính toán BC trước và sau khi rút gọn .............................55
Bảng 2.6. Thời gian tính toán BC của giải thuật Red-Bet khi số luồng thay đổi (giây) ..55
Bảng 2.7. Hệ số tăng tốc của giải thuật Red-Bet khi số luồng thay đổi........................56
Bảng 2.8. Thời gian tính toán BC với 5 bộ dữ liệu của ba giải pháp (giây) .................57
Bảng 2.9. Hệ số tăng tốc của Red-Bet so với TeexGraph và NetworKit khi tính toán BC 58
Bảng 3.1. Ví dụ về nhật ký hoạt động ............................................................................69
Bảng 3.2. So sánh hiệu suất của các phương pháp chưa xét ảnh hưởng bên ngoài .....79
Bảng 3.3. So sánh hiệu suất của các phương pháp khi xuất hiện ảnh hưởng bên ngoài 80
- vii
DANH MỤC CÁC HÌNH
Hình 1. Thống kê số liệu người dùng năm 2020 .............................................................1
Hình 2. Ứng dụng phân tích thông tin trên mạng xã hội ................................................3
Hình 1.1. Lan truyền thông tin ........................................................................................8
Hình 1.2. Bài toán phát hiện cấu trúc cộng đồng học viên của trường đại học ...........11
Hình 1.3. Cấu trúc đồ thị ...............................................................................................21
Hình 1.4. Một số kiểu đồ thị cơ bản ..............................................................................22
Hình 2.1. Ví dụ về duyệt theo chiều rộng trước ............................................................34
Hình 2.2. Ví dụ về duyệt theo chiều sâu trước ..............................................................35
Hình 2.3. Mô hình xử lý song song trong CilkPlus .......................................................43
Hình 2.4. Đồ thị ngẫu nhiên 500 đỉnh ...........................................................................46
Hình 2.5. Đồ thị ngẫu nhiên 400 đỉnh ...........................................................................46
Hình 2.6. Sơ đồ khối quá trình tính toán Độ trung tâm trung gian theo giải thuật kết hợp . 49
Hình 2.7. Đồ thị trước rút gọn.......................................................................................51
Hình 2.8. Đồ thị sau rút gọn ..........................................................................................52
Hình 2.9. Đồ thị hóa thời gian tính toán BC của giải thuật Red-Bet khi số luồng thay đổi . 56
Hình 2.10. Biểu diễn thời gian tính toán BC với 5 bộ dữ liệu của ba giải pháp...........57
Hình 3.1. Ví dụ cho mô hình LT ....................................................................................63
Hình 3.2. Ví dụ cho mô hình IC .....................................................................................64
Hình 3.3. Hình dạng của hàm logistic ...........................................................................74
Hình 3.4. Sơ đồ khối quá trình xây dựng cây lan truyền...............................................75
Hình 3.5. Hình dạng cây lan truyền ..............................................................................76
Hình 3.6. Biểu diễn chi tiết hiệu suất của các phương pháp chưa xét ảnh hưởng bên
ngoài ..............................................................................................................................80
Hình 3.7. Biểu diễn chi tiết hiệu suất của các phương pháp khi xuất hiện ảnh hưởng
bên ngoài .......................................................................................................................81
- 1
MỞ ĐẦU
1. Phát biểu vấn đề
Trong thời đại công nghệ thông tin phát triển hiện nay, việc sử dụng Internet
trở nên phổ cập. Thống kê của Hootsuite và We Are Social cho thấy, tính đến
tháng 1/2020, tổng lượng người dùng Internet trên toàn thế giới đạt 4,54 tỷ1. Số
lượng người dùng Internet ngày càng tăng nhanh, cụ thể, so với tháng 1/2019, số
người dùng mới đã tăng thêm 298 triệu người dùng. Ngày càng có nhiều người sử
dụng Internet đồng nghĩa với việc gia tăng nhu cầu sử dụng mạng xã hội. Các con
số thống kê cho thấy lượng người dùng mạng xã hội nói chung trên toàn thế giới
đã chạm ngưỡng xấp xỉ 3,8 tỷ chiếm 49% dân số.
Hình 1. Thống kê số liệu người dùng năm 2020
Con người dành nhiều thời gian trong ngày cho việc sử dụng Internet nói
chung và mạng xã hội nói riêng. Cũng theo thống kê trên đối với những người
trong độ tuổi từ 16 đến 64 tuổi, trung bình một ngày, mỗi người sử dụng 6h43p
cho việc truy cập Internet và trong thời gian đó là 2h24p để sử dụng các tiện ích
liên quan đến mạng xã hội.
1
https://wearesocial.com/blog/2020/01/digital-2020-3-8-billion-people-use-social-media
- 2
Với sự quan tâm và nhu cầu sử dụng mạng xã hội lớn như vậy, lượng thông
tin trên mạng xã hội là rất lớn. Trong những năm vừa qua, có nhiều nhà khoa học
cũng như nhiều công trình nghiên cứu về phân tích thông tin trên mạng xã hội để
có thể khai thác nguồn dữ liệu lớn này. Một số hướng chính trong nghiên cứu
phân tích trên thông tin trên mạng xã hội có thể kể đến khai phá dữ liệu mạng xã
hội (phân tích hành vi, phát hiện điểm nóng, tư vấn xã hội...); phân tích mô hình
dữ liệu đồ thị (nghiên cứu lý thuyết đồ thị, các phép đo, tính toán trên đồ thị,...);
phát hiện cộng đồng (phân tích cấu trúc cộng đồng trong mạng xã hội, mối quan
hệ tương tác trong cộng đồng); an toàn thông tin (bảo mật thông tin, phát hiện
thông tin sai lệch...) và phân tích, dự báo lan truyền thông tin.
Ngoài việc nghiên cứu, phân tích thông tin trên mạng xã hội còn có những
ý nghĩa thực tiễn. Hiện nay, rất nhiều cơ quan, doanh nghiệp có nhu cầu sử dụng
các hệ thống phân tích thông tin trên mạng xã hội để phục vụ cho các mục đích
khác nhau. Ví dụ các doanh nghiệp kinh doanh cần phân tích xu hướng lựa chọn
hàng hóa của người tiêu dùng, sở thích của người dùng đối với những sản phẩm
trên thị trường. Các cơ quan báo chí quan tâm đến những chủ đề nóng đang được
quan tâm hiện nay để tập trung khai thác. Các doanh nghiệp cung cấp dịch vụ
quan tâm đến thái độ, mức độ hài lòng của người dùng đối với những dịch vụ cụ
thể. Bộ Thông tin và Truyền thông có nhu cầu đối với việc đảm bảo an ninh thông
tin và quản lý các luồng thông tin lan truyền trên mạng xã hội. Bộ Công an cũng
có nhu cầu đối với việc phân tích thông tin, phát hiện những thông tin sai sự thật,
tìm kiếm nguồn phát tán thông tin, dự báo thông tin lan truyền để có phương án
đấu tranh, xử lý.
Xuất phát từ nhu cầu thực tế công tác, Nghiên cứu sinh đã có điều kiện tiếp
xúc với một số hệ thống phân tích thông tin trên mạng xã hội của một số đơn vị,
nhà cung cấp trong và ngoài nước. Hình 2 là một ví dụ một ứng dụng phân tích
thông tin mà Nghiên cứu sinh đã được vận hành thử nghiệm. Qua đó, nổi bật lên
hai vấn đề cần phải nghiên cứu, xử lý: (1) là phải giảm thời gian tính toán, phân
tích dự báo lan truyền thông tin và (2) là nâng cao được độ chính xác trong việc
dự báo lan truyền thông tin trên mạng xã hội.
- 3
Hình 2. Ứng dụng phân tích thông tin trên mạng xã hội
2. Lý do chọn đề tài
Trong quá trình nghiên cứu, tìm hiểu, đã có một số công trình nghiên cứu
được đề xuất để giải quyết hai vấn đề trên. Tuy nhiên, lan truyền thông tin trên
mạng xã hội là một lĩnh vực rộng lớn, không có nghiên cứu nào là hoàn toàn tối
ưu và mỗi nghiên cứu mới sẽ là một hướng bổ sung mới trong việc nâng cao hiệu
quả phân tích lan truyền thông tin.
Đề tài “Một số phương pháp nâng cao hiệu quả dự báo lan truyền thông
tin trên mạng xã hội” được thực hiện trong khuôn khổ Luận án tiến sỹ chuyên
ngành Hệ thống thông tin góp phần đưa ra phương án xử lý hai vấn đề được nêu
trên vừa để phục vụ công tác nghiên cứu khoa học, vừa có khả năng ứng dụng
trong thực tế.
3. Mục tiêu của luận án
Như đã trình bày, mục tiêu của Luận án này là nghiên cứu, phát triển, cải
tiến một số phương pháp nâng cao hiệu quả trong việc dự báo lan truyền thông tin
trên mạng xã hội, nằm trong chủ đề lớn là nâng cao hiệu quả phân tích mạng xã
- 4
hội phục vụ công tác nghiên cứu và khả năng ứng dụng vào thực tế. Kết quả của
Luận án sẽ giải quyết được 02 vấn đề đó là nâng cao tốc độ (hay giảm thời gian)
tính toán, phân tích thông tin phục vụ dự báo lan truyền thông tin và tăng độ chính
xác (hay giảm thiểu sai số) trong dự báo lan truyền thông tin trên mạng xã hội.
4. Các đóng góp của luận án
Đóng góp thứ nhất của luận án là đề xuất phương pháp nâng cao tốc độ
tính toán, phân tích phục vụ dự báo lan truyền thông tin trên mạng xã hội [C1],
[C2], [C3], [C4]. Cụ thể:
- Đề xuất kỹ thuật rút gọn đồ thị dựa trên thay thế các đỉnh tương đương
bậc 1. Kỹ thuật rút gọn này loại bỏ những đỉnh “không quan trọng”, giúp việc tính
toán trên đồ thị đơn giản và hiệu quả hơn. Thực nghiệm cũng cho thấy đồ thị sau
khi rút gọn có kết quả tính toán kích thước lan truyền nhanh hơn đồ thị chưa rút
gọn. Ngoài ra, việc rút gọn sẽ giảm quy mô của đồ thị, do đó chắc chắn sẽ thay
đổi kết quả tính toán các phép đo. Tuy nhiên, phương pháp chỉ loại bỏ những đỉnh
bậc 1, không quan trọng, không làm ảnh hưởng quá lớn đến đồ thị và vẫn đảm
bảo giữ nguyên tính chất “quan trọng” của những đỉnh trung tâm.
- Đề xuất kỹ thuật song song hóa quá trình tính toán Độ trung tâm trung
gian (Betweenness Centrality), là một giá trị quan trọng đã được chứng minh có
ảnh hưởng lớn đến kết quả của việc lan truyền thông tin trên mạng xã hội. Bản
chất của phương pháp là việc song song hóa các phép tính SSSP trong thuật toán
của Brandes với mô hình lập trình luồng song song trên CPU và sử dụng bộ thư
viện CilkPlus. Có thể nói tính toán trên đồ thị với số lượng đỉnh và cạnh lớn, trong
đó có việc tính Độ trung tâm trung gian BC là bài toán tương đối khó trong việc
song song. Tuy nhiên, bằng một số kỹ thuật xử lý, Luận án đã giải quyết được
việc song song hóa giúp giảm thời gian tính toán một cách hiệu quả.
- Kết quả thực nghiệm và đánh giá trên một số bộ dữ liệu thực tế cho thấy
phương pháp đề xuất giúp nâng cao đáng kể tốc độ tính toán.
Đóng góp thứ hai của luận án là đề xuất phương pháp nâng cao độ chính
xác dự báo lan truyền thông tin [C5]. Cụ thể:
- Đề xuất phương pháp tính xác suất chấp nhận thông tin của người dùng
- 5
(hay xác suất lan truyền) trên mạng xã hội theo mô hình Bậc độc lập IC
(Independent Cascade) dựa trên 03 thông số: quan hệ người dùng, sở thích với
nội dung và ảnh hưởng từ bên ngoài. Việc kết hợp các thông số giúp nâng cao
đáng kể độ chính xác dự báo.
- Đồng thời, dựa trên các xác suất đã tính, xây dựng Cây lan truyền “có khả
năng nhất” cho một nội dung cụ thể để ước tính kích thước lan truyền thông tin.
- Kết quả thực nghiệm và đánh giá trên một số bộ dữ liệu mô phỏng và thực
tế cho thấy phương pháp đề xuất giúp nâng cao độ chính xác (hay giảm sai số)
ước tính kích thước lan truyền trong dự báo lan truyền thông tin.
5. Bố cục Luận án
Bố cục của Luận án được phân chia thành 03 chương bao gồm:
Chương I. Tổng quan về lan truyền thông tin trên mạng xã hội
Nội dung chính của Chương này giới thiệu chung về mạng xã hội, phân tích
thông tin trên mạng xã hội và bài toán lan truyền thông tin trên mạng xã hội, các
nghiên cứu liên quan và phương pháp đề xuất của Luận án. Một số lý thuyết cơ
bản phục vụ cho Luận án sẽ được trình bày ở cuối chương.
Chương II. Nâng cao tốc độ dự báo lan truyền thông tin
Trình bày phương pháp nâng cao tốc độ phân tích, tính toán phục vụ dự báo
lan truyền thông tin bằng kỹ thuật rút gọn đồ thị và song song hóa quá trình tính
toán Độ trung tâm trung gian. Nội dung trình bày trong chương được tổng hợp từ
kết quả nghiên cứu đã được công bố trong [C1], [C2], [C3], [C4].
Chương III. Nâng cao độ chính xác dự báo lan truyền thông tin
Trình bày phương pháp nâng cao độ chính xác trong dự báo lan truyền bằng
cách tính xác suất lan truyền thông tin dựa trên một số yếu tố ảnh hưởng và xây
dựng cây lan truyền. Nội dung trình bày trong chương được tổng hợp từ kết quả
nghiên cứu đã được công bố trong [C5].
- 6
1. Chương I. TỔNG QUAN VỀ LAN TRUYỀN THÔNG TIN
TRÊN MẠNG XÃ HỘI
Mục tiêu chính của chương này là trình bày những vấn đề tổng quan về
mạng xã hội, các lĩnh vực phân tích thông tin trên mạng xã hội, bài toán lan truyền
thông tin trên mạng xã hội, một số nghiên cứu, cách tiếp cận liên quan, phân tích
rõ những hạn chế, tồn tại của mỗi phương pháp. Trên cơ sở đó, đưa ra hướng
nghiên cứu cụ thể của Luận án. Những kết quả nghiên cứu của Luận án sẽ được
trình bày ở các chương tiếp theo.
1.1. Mạng xã hội và lan truyền thông tin trên mạng xã hội
1.1.1. Mạng xã hội
Có nhiều khái niệm khác nhau về mạng xã hội:
- Về cơ bản, mạng xã hội là một tập hợp các tác nhân có yếu tố xã hội được
kết nối với nhau bởi một hoặc nhiều các quan hệ xã hội.
- Về mặt dịch vụ, mạng xã hội trực tuyến (online social network) là dịch
vụ kết nối các thành viên trên Internet với nhiều mục đích khác nhau không phân
biệt không gian và thời gian.
- Trong phân tích (lý thuyết đồ thị), mạng xã hội là một cấu trúc xã hội bao
gồm các cá nhân hay tổ chức, thường được biểu diễn bằng các nút, cùng với các
quan hệ xã hội, tương ứng với các cạnh/liên kết giữa các nút.
Mạng xã hội xuất hiện lần đầu tiên năm 1995 với sự ra đời của trang
Classmate [1], [2] nhằm mục đích kết nối bạn học tại Mỹ và Canada với 50 triệu
người dùng, tiếp theo là sự xuất hiện của SixDegrees [1], [2] vào năm 1997 nhằm
mục đích giao lưu kết bạn dựa theo sở thích với 3,5 triệu người dùng. Đến nay,
trên thế giới có hàng trăm mạng mạng xã hội khác nhau, trong đó, phổ biến nhất
có thể kể đến Facebook (2,45 tỷ người dùng), Youtube (2 tỷ người dùng),
Whatsapp, Instagram, Twitter. Ngoài ra, tại mỗi nước hoặc mỗi khu vực cũng có
- 7
những mạng xã hội được sử dụng riêng như Weibo2 (Trung Quốc),
CyWorld3 (Hàn Quốc), Mixi4 (Nhật Bản) hay Zalo5 (Việt Nam)...
Mạng xã hội đóng vai trò quan trọng trong việc truyền bá thông tin ở quy
mô lớn. Đến nay, nhiều nghiên cứu đã được thực hiện để tìm hiểu quá trình này,
từ bài toán khai phá dữ liệu để phát hiện chủ đề được quan tâm, phát hiện điểm
nóng, nhận diện người dùng có ảnh hưởng trong mạng xã hội đến việc phân tích,
nghiên cứu mô hình lan truyền thông tin.
Mạng xã hội cho phép hàng tỷ người dùng Internet trên toàn thế giới kết
nối, đăng và truyền tải nội dung. Người dùng được tiếp xúc và là một thành phần
tạo ra nguồn thông tin rất lớn. Việc truyền bá thông tin tạo ra những tác động
mạnh mẽ, ví dụ như trong việc tạo ra làn sóng cách mạng trên Facebook trong vụ
việc mùa xuân Ả Rập năm 2010 [3] hay gây ra những tác động trên Twitter trong
cuộc bầu cử tổng thống Hoa Kỳ năm 2008 [4],... Do tác động của các mạng xã
hội đối với đời sống thực, trọng tâm nghiên cứu gần đây tập trung vào việc phát
hiện cộng đồng và khai thác thông tin có giá trị từ lượng dữ liệu khổng lồ này.
Các sự kiện diễn ra và phát triển rất nhanh trong các mạng xã hội, do đó việc nắm
bắt, tìm hiểu và dự đoán các sự kiện là vấn đề quan tâm của nhiều đối tượng khác
nhau từ các tổ chức, doanh nghiệp đến các nhà nghiên cứu.
Thực tế cũng cho thấy việc nắm bắt được mối quan hệ trong cộng đồng
mạng xã hội và sự phát triển của các mạng xã hội có thể giúp điều chỉnh hành vi
và dự báo các sự kiện tiếp theo tốt hơn như việc phân tích tối ưu hóa hiệu quả
kinh doanh bằng cách tạo ra các chiến dịch tiếp thị xã hội; điều chỉnh hành vi của
cộng đồng người dùng thông qua những cá nhân có sức ảnh hưởng trong xã hội;
hay việc phân tích các cuộc biểu tình từ đó giải quyết các vấn đề an ninh như ngăn
chặn các cuộc tấn công khủng bố, dự báo các nguồn thông tin có tác động xấu đến
xã hội... Do đó, phát triển các kỹ thuật và mô hình để phát hiện cộng đồng, nắm
2
https://weibo.com/overseas
3
http://www.cyworld.com/42book/
4
https://mixi.jp/
5
https://zalo.me/
- 8
bắt sự phát triển của mạng xã hội và lan truyền thông tin trong các mạng xã hội
cũng là những chủ đề mà các nhà nghiên cứu quan tâm trong những năm gần đây.
1.1.2. Lan truyền thông tin trên mạng xã hội
Theo [5], lan truyền là một quá trình mà một sự cập nhật thông tin được
truyền đạt qua các kênh nhất định theo thời gian giữa các người dùng của một
mạng xã hội. Có ba yếu tố quan trọng trong quá trình này là: thành viên trong
mạng xã hội, sự tương tác lẫn nhau và các kênh truyền tải. Việc nghiên cứu các
quá trình lan truyền trong mỗi hoàn cảnh cụ thể là nền tảng giúp con người có thể
giải quyết các vấn đề liên quan đến sự lan truyền trong thực tế như: sự lan truyền
của dịch bệnh (trong y học, dịch tễ học), sự lan truyền các ý kiến, tư tưởng giữa
các cá nhân trong một xã hội, sự phát tán của virus trên một mạng máy tính, sự
lan truyền thông tin trên mạng xã hội...
Hình 1.1. Lan truyền thông tin
Trong mạng xã hội, thông tin được lan truyền từ người dùng này đến người
dùng khác thông qua nhiều hoạt động tương tác giữa các người dùng như: đăng
bài, chia sẻ, bình luận... Quá trình này diễn ra tương đối nhanh và có những đặc
điểm khác với sự lan truyền thông tin truyền thống. Việc hiểu rõ quá trình này
- 9
trên các mạng xã hội giúp con người có thể quản trị, điều khiển các thông tin nhằm
đảm bảo tính hữu ích của các mạng xã hội. Với mục đích đó, các nhà khoa học đã
mô tả một cách ngắn gọn lại quá trình lan truyền thông tin bằng các mô hình lan
truyền thông tin.
1.2. Các lĩnh vực nghiên cứu trong phân tích mạng xã hội
1.2.1. Khai phá dữ liệu mạng xã hội
Sự phát triển nhanh chóng của các mạng xã hội cung cấp một lượng lớn dữ
liệu tạo ra bởi chính người dùng. Theo thống kê từ trang statista năm 2020, có
khoảng 250 triệu bức ảnh được đăng tải lên Facebook mỗi ngày, 500 giờ video
được đăng tải mỗi phút trên YouTube, hơn 500 triệu tweet mỗi ngày trên Twitter.
Do vậy, cần phải có những kỹ thuật khai phá dữ liệu phù hợp để có thể trích xuất
được những thông tin hữu ích từ lượng lớn dữ liệu phức tạp và thường xuyên thay
đổi trong thời gian ngắn.
Khai phá dữ liệu trên mạng xã hội có nhiều ứng dụng trong các lĩnh vực
như: phân tích hành vi, phát hiện điểm nóng và tư vấn xã hội,... Trong bài toán
phân tích hành vi người dùng trên mạng xã hội, khai phá dữ liệu mạng xã hội giúp
các công ty hiểu hơn về khách hàng của họ, từ đó, cải thiện chiến dịch tiếp thị,
bán hàng và đưa ra dịch vụ tốt hơn, nắm được dự định mua sản phẩm của khách
hàng để tìm kiếm sản phẩm khách hàng có khả năng mua nhất. Trong bài toán
phát hiện điểm nóng, khai phá dữ liệu mạng xã hội giúp giám sát các sự kiện nóng
trên mạng xã hội phục vụ cho công tác theo dõi của cơ quan an ninh, báo chí,
truyền thông,... Trong bài toán tư vấn xã hội, đây là hệ tư vấn nhằm gợi ý cho
người dùng trên mạng xã hội, ví dụ tư vấn những người bạn mới, nhóm mới hữu
ích cho người dùng. Ngoài ra, trong bài toán quản lý thương hiệu, khai phá dữ
liệu mạng xã hội cũng giúp các doanh nghiệp, công ty theo dõi, giám sát mức độ
thâm nhập, sức lan tỏa, ảnh hưởng của thương hiệu trên mạng xã hội...
Một số nghiên cứu liên quan như nghiên cứu [6] về việc phân tích hành vi
trên mạng xã hội và nghiên cứu [7] về vấn đề phát hiện điểm nóng dựa trên phân
tích cảm xúc và khai thác văn bản.
- 10
1.2.2. Phân tích mô hình dữ liệu đồ thị
Trong thời đại số hóa, dữ liệu ngày càng trở nên quan trọng, cung cấp
những giá trị to lớn cho các tổ chức, doanh nghiệp và cá nhân có thể khai thác.
Như đã thống kê ở trên, lượng dữ liệu rõ ràng ngày càng được sinh ra nhiều hơn,
đồ sộ hơn về cả quy mô, tốc độ và sự đa dạng của dữ liệu. Điều này dẫn đến
những mô hình dữ liệu truyền thống như mô hình quan hệ gặp khó khăn khi xử
lý. Trong hoàn cảnh đó, một số mô hình quản lý dữ liệu mới đã được đề xuất,
trong đó, mô hình dữ liệu hướng tài liệu (document-based model) và mô hình dữ
liệu đồ thị (graph data model) [8] là hai mô hình được xem là hiệu quả khi quản
lý dữ liệu quy mô lớn như dữ liệu mạng xã hội.
Để phân tích mô hình dữ liệu đồ thị, lý thyết đồ thị là một khái niệm kinh
điển và vẫn đang được ứng dụng rộng rãi hiện nay, đặc biệt khi lượng dữ liệu
chúng ta cần phải phân tích, xử lý có quy mô lớn và biến đổi liên tục. Việc áp
dụng lý thuyết đồ thị vào các bài toán thực tiễn đã được tiến hành từ lâu, nhất là
đối với nguồn dữ liệu lớn như từ các mạng xã hội Facebook, Youtube,... thì việc
sử dụng mô hình hoá dữ liệu bằng lý thuyết đồ thị lại được quan tâm và đã minh
chứng được hiệu năng nổi bật khi áp dụng vào thực tế [9].
Trong lý thuyết đồ thị, khi mô hình hoá dữ liệu bằng đồ thị, thông thường
các thực thể (như người dùng trên mạng xã hội) sẽ được biểu diễn thông qua các
đỉnh còn các quan hệ giữa các thực thể (như quan hệ bạn bè giữa các người dùng)
được quy về các cạnh liên kết các đỉnh trong đồ thị. Từ đó, thông qua các phép
toán trên đồ thị như duyệt đồ thị, xác định khoảng cách ngắn nhất giữa các đỉnh,
các độ đo trung tâm trên đồ thị,... ta sẽ khai thác được những thông tin như tìm
kiếm người dùng có sức ảnh hưởng trong mạng xã hội, phát hiện điểm nóng, hay
trong bài toán tìm kiếm tâm dịch bệnh trong sinh học, bài toán quy hoạch mạng
lưới giao thông, lan truyền thông tin,...
1.2.3. Phát hiện cộng đồng
Một vấn đề quan trọng trong phân tích mạng xã hội đó là bài toán phát hiện
cấu trúc cộng đồng. Mục tiêu của bài toán là từ các mạng xã hội cho trước, phát
hiện được các cấu trúc cộng đồng trong đó và tìm hiểu mối quan hệ giữa các cá
- 11
nhân bên trong các cộng đồng cũng như giữa các cộng đồng với nhau, từ đó giải
quyết bài toán cá nhân/hay mối quan hệ nào đó ảnh hưởng thế nào đến cấu trúc
của toàn mạng xã hội.
Hình 1.2. Bài toán phát hiện cấu trúc cộng đồng học viên của trường đại học
Phát hiện cộng đồng cũng giúp chúng ta hiểu được quan điểm của người
dùng và sự tương tác của người dùng trong mạng xã hội. Việc phát hiện cấu trúc
cộng đồng có nhiều ứng dụng cụ thể, ví dụ như việc xác định các cụm khách hàng
có chung sở thích trong mạng lưới khách hàng và sản phẩm giúp xây dựng hệ
thống tư vấn bán hàng hiệu quả; hay việc phân cụm các web client dựa trên các
cụm khách hàng gần nhau về mặt địa lý và có cùng sở thích, thói quen sẽ được
phục vụ bởi một máy chủ chuyên dụng đối với khu vực đó giúp cải thiện hiệu
suất cung cấp dịch vụ trên Internet,...
Các nghiên cứu về phát hiện cấu trúc cộng đồng có thể kể đến nghiên cứu
[10], [11.] trình bày họ thuật toán phân tách Girvan-Newman theo độ trung gian,
nghiên cứu [12] trình bày thuật toán chia đỉnh CONGA, CONGO và gán nhãn
COPRA.
1.2.4. Dự báo lan truyền thông tin
Lan truyền là một quá trình mà một sự đổi mới thông tin được truyền đạt
qua các kênh nhất định theo thời gian giữa các thành viên của một mạng xã hội.
Có ba yếu tố quan trọng trong quá trình này là: thành viên trong mạng xã hội, sự
nguon tai.lieu . vn