Luận án Tiến sĩ Máy tính: 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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:107

Thêm vào BST

Báo xấu

31
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án Tiến sĩ Máy tính "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" trình bày các nội dung chính sau: Tổng quan về lan truyền thông tin trên mạng xã hội; Nâng cao tốc độ dự báo lan truyền thông tin; Nâng cao độ chính xác dự báo lan truyền thông tin.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Máy tính: 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

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, các số liệu, tài liệu được sử dụng trong Luận án này được thu thập từ nghiên cứu thực tế; trong đó, bao gồm một số kết quả nghiên cứu đã được đăng ở các tạp chí khoa học trong và ngoài nước cũng như thử nghiệm thực tế “Hệ thống phân tích dữ liệu mạng xã hội” mà tôi có cơ hội tham gia thực hiện. Các nội dung viết chung với các tác giả khác đều được sự đồng ý của các đồng tác giả trước khi đưa vào Luận án. Ngoài ra, những tài liệu tham khảo đều được trích dẫn nguồn đầy đủ. Trân trọng, Dương Ngọc Sơn
ii LỜI CẢM ƠN Để có kết quả hôm nay, tôi xin cảm ơn Học viện Khoa học và công nghệ, Viện Hàn lâm Khoa học và công nghệ Việt Nam đã tổ chức, đào tạo và hướng dẫn tôi hoàn thành các thủ tục hoàn thiện Luận án. Tôi xin bày tỏ lòng biết ơn sâu sắc đến TS. Nguyễn Ngọc Cương - Phó Cục trưởng Cục An ninh mạng và phòng chống tội phạm sử dụng công nghệ cao, Bộ Công an và TS.Nguyễn Như Sơn - Trưở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 học và công nghệ Việt Nam đã tận tình hướng dẫn, chỉ bảo và giúp đỡ tôi trong suốt quá trình thực hiện Luận án. Xin chân thành cảm ơ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 Ngọc Hóa - Trường Đại học Quốc gia Hà Nội đã truyền đạ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 cũng xin cảm ơn lãnh đạo đơn vị công tác Phòng Kỹ thuật và Viện Nghiên cứu KTNV, Cục Kỹ thuật nghiệp vụ, Bộ Công an đã tạo điều kiện cho tôi để tôi vừa làm việc, vừa học tập và thực hiện nghiên cứu. Trong quá trình làm việc đã cho tôi có điều kiện tiếp xúc với các hệ thống kỹ thuật, tham dự các hội thả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 cảm ơn sâu sắc và chân thành đến Gia đình, những người đã luôn ở bên ủng hộ, động viên để tôi có được ngày hôm nay. Trong quá trình thực hiện Luận án, tôi cũng nhận được sự giúp đỡ của rất nhiều người mà không tiện liệt kê ở đây, tôi xin cảm ơn và kính chúc tất cả mọi người sức khỏe, hạ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 chọn đề tài .....................................................................................................3 3. Mục tiêu của luận án ................................................................................................3 4. Các đóng góp của luận án ........................................................................................4 5. Bố cụ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. Mạng xã hội và lan truyền thông tin trên mạng xã hội .........................................6 1.1.1. Mạng xã hội....................................................................................................6 1.1.2. Lan truyền thông tin trên mạng xã hội ...........................................................8 1.2. Các lĩnh vực nghiên cứu trong phân tích mạng xã hội .........................................9 1.2.1. Khai phá dữ liệu mạ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ố phương pháp nâng cao hiệu quả dự báo lan truyền thông tin trên mạng xã hội ..............................................................................13 1.4. Các hướ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. Phương pháp đề xuất ..........................................................................................20 1.6. Một số định nghĩa cơ bả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 Chươ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. Các phép toá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 gọn đồ thị ...............................................................................................43 2.3.2. Song song hóa quá trình tính toán độ trung tâm trung gian .........................47 2.3.3. Phương pháp kết hợp hai kỹ thuật ...............................................................50 2.4. Thực nghiệm và kết quả......................................................................................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 quả thực nghiệm ....................................................................................54 2.5. Kết luận Chươ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 rạc ............................................................61 3.2.2. Mô hình Ngưỡ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 cạ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 hưởng của quan hệ người dùng ............................................................69 3.3.2. Ảnh hưởng sở thích của người dùng ............................................................71 3.3.3. Đo lường ảnh hưở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 quả......................................................................................76 3.4.1. Dữ liệu thực nghiệm.....................................................................................76 3.4.2. Phương pháp thực nghiệm ...........................................................................77 3.4.3. Kết quả thực nghiệm ....................................................................................78 3.5. Kết luận chươ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 Đườ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 cả 2 chiều 3 BC Betweenness Centrality Độ trung tâm trung gian 4 BFS Breadth-First Search Duyệt theo chiều rộng trướ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 trướ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ý đồ họa 12 IC Independent Cascade Bậc độc lập 13 LT Linear Threshold Ngưỡng tuyến tính 14 RM Regression Model Mô hình hồi quy Single-Destination Đường đi ngắn nhất đến 1 đỉnh 15 SDSP Shortest Path đích Single-Source Shortest Đường đi ngắn nhất từ 1 đỉnh 16 SSSP Path nguồn 17 UI User Interaction Tương tác ngườ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 đại công nghệ thông tin phát triển hiện nay, việc sử dụ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 lượng người dùng Internet trên toàn thế giới đạt 4,54 tỷ1. Số lượng người dùng Internet ngày càng tăng nhanh, cụ thể, so với tháng 1/2019, số người dùng mới đã tăng thêm 298 triệu người dùng. Ngày càng có nhiều người sử dụng Internet đồng nghĩa với việc gia tăng nhu cầu sử dụng mạng xã hội. Các con số thống kê cho thấy lượng người dùng mạng xã hội nói chung trên toàn thế giới đã chạm ngưỡ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 người dành nhiều thời gian trong ngày cho việc sử dụng Internet nói chung và mạng xã hội nói riêng. Cũng theo thống kê trên đối với những người trong độ tuổi từ 16 đến 64 tuổi, trung bình một ngày, mỗi người sử dụng 6h43p cho việc truy cập Internet và trong thời gian đó là 2h24p để sử dụng các tiện ích liên quan đến mạ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ử dụng mạng xã hội lớn như vậy, lượng thông tin trên mạng xã hội là rất lớn. Trong những năm vừa qua, có nhiều nhà khoa học cũng như nhiều công trình nghiên cứu về phân tích thông tin trên mạng xã hội để có thể khai thác nguồn dữ liệu lớn này. Một số hướng chính trong nghiên cứu phân tích trên thông tin trên mạng xã hội có thể kể đến khai phá dữ liệu mạng xã hội (phân tích hành vi, phát hiện điểm nóng, tư vấn xã hội...); phân tích mô hình dữ liệu đồ thị (nghiên cứu lý thuyết đồ thị, các phép đo, tính toán trên đồ thị,...); phát hiện cộng đồng (phân tích cấu trúc cộng đồng trong mạng xã hội, mối quan hệ tương tác trong cộng đồng); an toàn thông tin (bả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 mạng xã hội còn có những ý nghĩa thực tiễn. Hiện nay, rất nhiều cơ quan, doanh nghiệp có nhu cầu sử dụng các hệ thống phân tích thông tin trên mạng xã hội để phục vụ cho các mục đích khác nhau. Ví dụ các doanh nghiệp kinh doanh cần phân tích xu hướng lựa chọn hàng hóa của người tiêu dùng, sở thích của người dùng đối với những sản phẩm trên thị trường. Các cơ quan báo chí quan tâm đến những chủ đề nóng đang được quan tâm hiện nay để tập trung khai thác. Các doanh nghiệp cung cấp dịch vụ quan tâm đến thái độ, mức độ hài lòng của người dùng đối với những dịch vụ cụ thể. Bộ Thông tin và Truyền thông có nhu cầu đối với việc đảm bảo an ninh thông tin và quản lý các luồng thông tin lan truyền trên mạng xã hội. Bộ Công an cũ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 để có phương á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 đã có đ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 mạng xã hội của một số đơn vị, nhà cung cấp trong và ngoài nước. Hình 2 là một ví dụ một ứng dụng phân tích thông tin mà Nghiên cứu sinh đã được vận hành thử nghiệm. Qua đó, nổi bật lên hai vấn đề cần phải nghiên cứu, xử lý: (1) là phải giả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 được độ chính xác trong việc dự báo lan truyền thông tin trên mạ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, đã có một số công trình nghiên cứu được đề xuất để giải quyết hai vấn đề trên. Tuy nhiên, lan truyền thông tin trên mạ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̛u và mỗi nghiên cứu mới sẽ là một hướng bổ sung mới trong việc nâng cao hiệu quả 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” đượ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 đưa ra phương án xử lý hai vấn đề được nêu trên vừa để phục vụ công tác nghiên cứu khoa học, vừa có khả năng ứng dụng trong thực tế. 3. Mục tiêu của luận án Như đã trình bày, mục tiêu của Luận án này là nghiên cứu, phát triển, cải tiến một số phương pháp nâng cao hiệu quả trong việc dự báo lan truyền thông tin trên mạng xã hội, nằm trong chủ đề lớn là nâng cao hiệu quả phân tích mạng xã
4 hội phục vụ công tác nghiên cứu và khả năng ứng dụng vào thực tế. Kết quả của Luận án sẽ giải quyết được 02 vấn đề đó là nâng cao tốc độ (hay giảm thời gian) tính toán, phân tích thông tin phục vụ dự báo lan truyền thông tin và tăng độ chính xác (hay giảm thiểu sai số) trong dự báo lan truyền thông tin trên mạ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]. Cụ thể: - Đề xuất kỹ thuật rút gọn đồ thị dựa trên thay thế các đỉnh tương đương bậc 1. Kỹ thuật rút gọn này loại bỏ những đỉnh “không quan trọng”, giúp việc tính toán trên đồ thị đơn giản và hiệu quả hơn. Thực nghiệm cũng cho thấy đồ thị sau khi rút gọn có kết quả tính toán kích thước lan truyền nhanh hơn đồ thị chưa rút gọn. Ngoài ra, việc rút gọn sẽ giảm quy mô của đồ thị, do đó chắc chắn sẽ thay đổi kết quả tính toán các phép đo. Tuy nhiên, phương pháp chỉ loại bỏ những đỉnh bậc 1, không quan trọng, không làm ảnh hưởng quá lớn đến đồ thị và vẫn đảm bảo giữ nguyên tính chất “quan trọ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 trọng đã được chứng minh có ảnh hưởng lớn đến kết quả của việc lan truyền thông tin trên mạng xã hội. Bản chất của phương phá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ử dụng bộ thư viện CilkPlus. Có thể nói tính toán trên đồ thị với số lượng đỉnh và cạnh lớn, trong đó có việc tính Độ trung tâm trung gian BC là bài toán tương đối khó trong việc song song. Tuy nhiên, bằng một số kỹ thuật xử lý, Luận án đã giải quyết được việc song song hóa giúp giảm thời gian tính toán một cách hiệu quả. - Kết quả thực nghiệm và đánh giá trên một số bộ dữ liệu thực tế cho thấy phương pháp đề xuất giúp nâng cao đá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]. Cụ thể: - Đề xuất phương pháp tính xác suất chấp nhận thông tin của người dùng
5 (hay xác suất lan truyền) trên mạ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ệ người dùng, sở thích với nội dung và ảnh hưởng từ bên ngoài. Việc kết hợp các thông số giúp nâng cao đá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 “có khả năng nhất” cho một nội dung cụ thể để ước tính kích thước lan truyền thông tin. - Kết quả thực nghiệm và đánh giá trên một số bộ dữ liệu mô phỏng và thực tế cho thấy phương pháp đề xuất giúp nâng cao độ chính xác (hay giảm sai số) ước tính kích thước lan truyền trong dự báo lan truyền thông tin. 5. Bố cục Luận án Bố cục của Luận án được phân chia thành 03 chươ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 Chương này giới thiệu chung về mạng xã hội, phân tích thông tin trên mạng xã hội và bài toán lan truyền thông tin trên mạng xã hội, các nghiên cứu liên quan và phương pháp đề xuất của Luận án. Một số lý thuyết cơ bản phục vụ cho Luận án sẽ được trình bày ở cuối chương. Chương II. Nâng cao tốc độ dự báo lan truyền thông tin Trình bày phương pháp nâng cao tốc độ phân tích, tính toán phục vụ dự báo lan truyền thông tin bằng kỹ thuật rút gọn đồ thị và song song hóa quá trình tính toán Độ trung tâm trung gian. Nội dung trình bày trong chương được tổng hợp từ kết quả nghiên cứu đã đ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 phương phá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ố ảnh hưởng và xây dựng cây lan truyền. Nội dung trình bày trong chương được tổng hợp từ kết quả nghiên cứu đã đ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 Mục tiêu chính của chương này là trình bày những vấn đề tổng quan về mạng xã hội, các lĩnh vực phân tích thông tin trên mạng xã hội, bài toán lan truyền thông tin trên mạ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 hạn chế, tồn tại của mỗi phương pháp. Trên cơ sở đó, đưa ra hướng nghiên cứu cụ thể của Luận án. Những kết quả nghiên cứu của Luận án sẽ được trình bày ở các chươ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ề mạng xã hội: - Về cơ bả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 vụ, 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. Mạng xã hội xuất hiện lần đầu tiên năm 1995 với sự ra đời của trang Classmate [1], [2] nhằm mục đích kết nối bạn học tại Mỹ và Canada với 50 triệu người dùng, tiếp theo là sự xuất hiện của SixDegrees [1], [2] vào năm 1997 nhằm mục đích giao lưu kết bạn dựa theo sở thích với 3,5 triệu người dùng. Đến nay, trên thế giới có hàng trăm mạng mạng xã hội khác nhau, trong đó, phổ biến nhất có thể kể đến Facebook (2,45 tỷ người dùng), Youtube (2 tỷ người dùng), Whatsapp, Instagram, Twitter. Ngoài ra, tại mỗi nước hoặc mỗi khu vực cũng có
7 những mạng xã hội được sử dụng riêng như Weibo2 (Trung Quốc), CyWorld3 (Hàn Quốc), Mixi4 (Nhật Bản) hay Zalo5 (Việt Nam)... Mạng xã hội đóng vai trò quan trọng trong việc truyền bá thông tin ở quy mô lớn. Đến nay, nhiều nghiên cứu đã đ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ủ đề được quan tâm, phát hiện điểm nóng, nhận diện người dùng có ảnh hưởng trong mạng xã hội đến việc phân tích, nghiên cứu mô hình lan truyền thông tin. Mạng xã hội cho phép hàng tỷ người dùng Internet trên toàn thế giới kết nối, đăng và truyền tải nội dung. Người dùng được tiếp xúc và là một thành phần tạo ra nguồn thông tin rất lớn. Việc truyền bá thông tin tạo ra những tác động mạnh mẽ, ví dụ như trong việc tạo ra làn sóng cách mạng trên Facebook trong vụ việc mùa xuân Ả Rập năm 2010 [3] hay gây ra những tác động trên Twitter trong cuộc bầu cử tổng thống Hoa Kỳ năm 2008 [4],... Do tác động của các mạng xã hội đối với đời sống thực, trọ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ừ lượ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 mạng xã hội, do đó việc nắm bắt, tìm hiểu và dự đoán các sự kiện là vấn đề quan tâm của nhiều đối tượng khác nhau từ các tổ chức, doanh nghiệp đến các nhà nghiên cứu. Thực tế cũng cho thấy việc nắm bắt được mối quan hệ trong cộng đồng mạng xã hội và sự phát triển của các mạ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 hơn như việc phân tích tối ưu hóa hiệu quả kinh doanh bằng cách tạ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 người dùng thông qua những cá nhân có sức ảnh hưởng trong xã hội; hay việc phân tích các cuộc biểu tình từ đó giải quyết các vấn đề an ninh như ngăn chặn các cuộc tấn công khủng bố, dự báo các nguồn thông tin có tác động xấu đến xã hội... Do đó, phá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 mạng xã hội và lan truyền thông tin trong các mạng xã hội cũng là những chủ đề mà các nhà nghiên cứu quan tâm trong những nă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 được truyền đạt qua các kênh nhất định theo thời gian giữa các người dùng của một mạng xã hội. Có ba yếu tố quan trọng trong quá trình này là: thành viên trong mạng xã hội, sự tương tác lẫn nhau và các kênh truyền tải. Việc nghiên cứu các quá trình lan truyền trong mỗi hoàn cảnh cụ thể là nền tảng giúp con người có thể giải quyết các vấn đề liên quan đến sự lan truyền trong thực tế như: sự lan truyền của dịch bệnh (trong y học, dịch tễ học), sự lan truyền các ý kiến, tư tưở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 mạng máy tính, sự lan truyền thông tin trên mạng xã hội... Hình 1.1. Lan truyền thông tin Trong mạng xã hội, thông tin được lan truyền từ người dùng này đến người dùng khác thông qua nhiều hoạt động tương tác giữa các người dùng như: đăng bài, chia sẻ, bình luận... Quá trình này diễn ra tươ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 mạng xã hội giúp con người có thể quản trị, điều khiển các thông tin nhằm đảm bảo tính hữu ích của các mạng xã hội. Với mục đích đó, các nhà khoa học đã mô tả một cách ngắn gọn lạ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ự phát triển nhanh chóng của các mạng xã hội cung cấp một lượng lớn dữ liệu tạo ra bởi chính người dùng. Theo thống kê từ trang statista năm 2020, có khoảng 250 triệu bức ảnh được đăng tải lên Facebook mỗi ngày, 500 giờ video được đăng tải mỗi phút trên YouTube, hơn 500 triệu tweet mỗi ngày trên Twitter. Do vậy, cần phải có những kỹ thuật khai phá dữ liệu phù hợp để có thể trích xuất được những thông tin hữu ích từ lượng lớn dữ liệu phức tạp và thường xuyên thay đổi trong thời gian ngắn. Khai phá dữ liệu trên mạng xã hội có nhiều ứng dụng trong các lĩnh vực như: phân tích hành vi, phát hiện điểm nóng và tư vấn xã hội,... Trong bài toán phân tích hành vi người dùng trên mạng xã hội, khai phá dữ liệu mạng xã hội giúp các công ty hiểu hơn về khách hàng của họ, từ đó, cải thiện chiến dịch tiếp thị, bán hàng và đưa ra dịch vụ tốt hơn, nắm được dự định mua sản phẩm của khách hàng để tìm kiếm sản phẩm khách hàng có khả năng mua nhất. Trong bài toán phát hiện điểm nóng, khai phá dữ liệu mạng xã hội giúp giám sát các sự kiện nóng trên mạng xã hội phục vụ cho công tác theo dõi của cơ quan an ninh, báo chí, truyền thông,... Trong bài toán tư vấn xã hội, đây là hệ tư vấn nhằm gợi ý cho người dùng trên mạng xã hội, ví dụ tư vấn những người bạn mới, nhóm mới hữu ích cho người dùng. Ngoài ra, trong bài toán quản lý thương hiệu, khai phá dữ liệu mạng xã hội cũng giúp các doanh nghiệp, công ty theo dõi, giám sát mức độ thâm nhập, sức lan tỏa, ảnh hưởng của thương hiệu trên mạng xã hội... Một số nghiên cứu liên quan như nghiên cứu [6] về việc phân tích hành vi trên mạng xã hội và nghiên cứu [7] về vấn đề phát hiện điểm nóng dựa trên phân tích cảm xúc và khai thác văn bản.
10 1.2.2. Phân tích mô hình dữ liệu đồ thị Trong thời đại số hóa, dữ liệu ngày càng trở nên quan trọ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. Như đã thống kê ở trên, lượng dữ liệu rõ ràng ngày càng được sinh ra nhiều hơn, đồ sộ hơn về cả quy mô, tốc độ và sự đa dạ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 như mô hình quan hệ gặp khó khăn khi xử lý. Trong hoàn cảnh đó, một số mô hình quản lý dữ liệu mới đã được đề xuất, trong đó, mô hình dữ liệu hướ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 được xem là hiệu quả khi quản lý dữ liệu quy mô lớn như dữ liệu mạ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 được ứng dụng rộng rãi hiện nay, đặc biệt khi lượng dữ liệu chúng ta cần phải phân tích, xử lý có quy mô lớn và biến đổi liên tục. Việc áp dụng lý thuyết đồ thị vào các bài toán thực tiễn đã được tiến hành từ lâu, nhất là đối với nguồn dữ liệu lớn như từ các mạng xã hội Facebook, Youtube,... thì việc sử dụng mô hình hoá dữ liệu bằng lý thuyết đồ thị lại được quan tâm và đã minh chứng được hiệu năng nổi bật khi áp dụ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 thường các thực thể (như người dùng trên mạng xã hội) sẽ được biểu diễn thông qua các đỉnh còn các quan hệ giữa các thực thể (như quan hệ bạn bè giữa các người dùng) được quy về các cạnh liên kết các đỉnh trong đồ thị. Từ đó, thông qua các phép toán trên đồ thị như duyệt đồ thị, xác định khoảng cách ngắn nhất giữa các đỉnh, các độ đo trung tâm trên đồ thị,... ta sẽ khai thác được những thông tin như tìm kiếm người dùng có sức ảnh hưởng trong mạ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 học, bài toán quy hoạch mạng lướ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 trọng trong phân tích mạng xã hội đó là bài toán phát hiện cấu trúc cộng đồng. Mục tiêu của bài toán là từ các mạng xã hội cho trước, phát hiện được các cấu trúc cộng đồng trong đó 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 cũng như giữa các cộng đồng với nhau, từ đó giải quyết bài toán cá nhân/hay mối quan hệ nào đó ảnh hưởng thế nào đến cấu trúc của toàn mạ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 Phát hiện cộng đồng cũng giúp chúng ta hiểu được quan điểm của người dùng và sự tương tác của người dùng trong mạng xã hội. Việc phát hiện cấu trúc cộng đồng có nhiều ứng dụng cụ thể, ví dụ như việc xác định các cụm khách hàng có chung sở thích trong mạng lưới khách hàng và sản phẩm giúp xây dựng hệ thống tư vấn bán hàng hiệu quả; hay việc phân cụm các web client dựa trên các cụm khách hàng gần nhau về mặt địa lý và có cùng sở thích, thói quen sẽ được phục vụ bởi một máy chủ chuyên dụng đối với khu vực đó giúp cải thiện hiệu suất cung cấp dịch vụ trên Internet,... Các nghiên cứu về phát hiện cấu trúc cộng đồng có thể kể đến nghiên cứu [10], [11.] trình bày họ thuật toán phân tách Girvan-Newman theo độ trung gian, nghiên cứu [12] trình bày thuật toá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 được truyền đạ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 mạng xã hội. Có ba yếu tố quan trọng trong quá trình này là: thành viên trong mạng xã hội, sự