Tổng quan về luận án

Sự bùng nổ của mạng xã hội trực tuyến (Online Social Networks - OSNs) đã tái định hình căn bản phương thức giao tiếp, phân phối tin tức và hình thành dư luận toàn cầu. 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ỷ người (tăng 298 triệu người so với năm 2019), trong đó người dùng mạng xã hội đạt xấp xỉ 3,8 tỷ người, chiếm 49% dân số toàn cầu. Nhóm người dùng trong độ tuổi từ 16 đến 64 tuổi dành trung bình 6 giờ 43 phút mỗi ngày để truy cập Internet, với 2 giờ 24 phút dành riêng cho các mạng xã hội như Facebook (2,45 tỷ người dùng), YouTube (2 tỷ người dùng), Twitter, Instagram và Zalo. Sự dịch chuyển không gian giao tiếp này tạo ra lưu lượng thông tin khổng lồ (250 triệu ảnh/ngày trên Facebook, 500 giờ video/phút trên YouTube, hơn 500 triệu tweet/ngày trên Twitter), đồng thời làm nảy sinh những rủi ro an ninh phi truyền thống nghiêm trọng như tin giả (fake news), tin đồn thất thiệt (điển hình như tin đồn dịch cúm lợn năm 2009, tin đồn thất thiệt về vụ nổ Nhà Trắng năm 2013, hay tin giả về đại dịch Covid-19 năm 2020).

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) của nghiên cứu sinh Dương Ngọc Sơn, dưới sự hướng dẫn khoa học của TS. Nguyễn Ngọc Cương và TS. Nguyễn Như Sơn tại 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 (2022), mang tiêu đề: "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 giải quyết trực diện hai khoảng trống nghiên cứu (research gaps) cốt lõi mang tính nghẽn cổ chai trong lĩnh vực phân tích mạng xã hội (Social Network Analysis - SNA):

  1. Nghẽn cổ chai về tốc độ tính toán đồ thị quy mô lớn: Việc tính toán các độ đo trung tâm cốt lõi, đặc biệt là Độ trung tâm trung gian (Betweenness Centrality - BC) của Linton Freeman (1977) thông qua giải thuật Brandes (2001) với độ phức tạp thời gian $O(|V||E|)$, đòi hỏi tài nguyên tính toán khổng lồ khi áp dụng trên các mạng đồ thị hàng triệu đến hàng tỷ đỉnh ($|V|$) và cạnh ($|E|$).
  2. Nghẽn cổ chai về độ chính xác dự báo mô hình hóa lan truyền: Các mô hình lan truyền cổ điển như Mô hình Bậc độc lập (Independent Cascade - IC) và Mô hình Ngưỡng tuyến tính (Linear Threshold - LT) của David Kempe, Jon Kleinberg và Éva Tardos (2003) chủ yếu dựa trên cấu trúc liên kết tĩnh và lịch sử tương tác nội tại ($u \to v$), hoàn toàn bỏ qua tương tác đa chiều giữa sở thích nội dung của người dùng và các tác động ngoại sinh (external/exogenous influences) từ không gian truyền thông bên ngoài.

Luận án thiết lập 02 câu hỏi nghiên cứu (Research Questions - RQ) và 02 giả thuyết khoa học (Hypotheses - H) tương ứng:

  • RQ1: Làm thế nào để giảm thiểu độ phức tạp thời gian khi tính toán độ đo Độ trung tâm trung gian trên đồ thị mạng xã hội quy mô lớn mà vẫn bảo toàn cấu trúc phân cấp và thứ hạng quan trọng của các đỉnh trung tâm?
    • H1: Việc kết hợp kỹ thuật rút gọn đồ thị dựa trên thay thế các đỉnh tương đương bậc 1 ($deg(v)=1$) với kỹ thuật song song hóa đa luồng thuật toán giải bài toán đường đi ngắn nhất từ một nguồn (SSSP) trên CPU thông qua CilkPlus sẽ tạo ra hệ số tăng tốc (speedup) vượt trội so với các công cụ chuẩn quốc tế (NetworKit, TeexGraph) mà không làm suy biến độ chính xác của thứ bậc Betweenness Centrality.
  • RQ2: Làm thế nào để nâng cao độ chính xác dự báo quy mô và lộ trình lan truyền thông tin khi tích hợp đồng thời các yếu tố nội sinh và ngoại sinh?
    • H2: Việc tái cấu trúc xác suất kích hoạt trong mô hình IC bằng hàm đa nhân tố tích hợp (quan hệ tương tác, sở thích nội dung và ảnh hưởng truyền thông bên ngoài) kết hợp thuật toán xây dựng Cây lan truyền có khả năng nhất (Most Likely Propagation Tree) sẽ giảm thiểu sai số tuyệt đối và nâng cao năng lực ước tính kích thước bùng phát thông tin.

Về phạm vi (scope) và ý nghĩa, nghiên cứu tập trung vào đơn đồ thị có hướng, liên thông, không trọng số trên các tập dữ liệu mô phỏng và thực nghiệm thực tế từ các mạng xã hội quy mô lớn. Kết quả nghiên cứu không chỉ đóng góp về mặt thuật toán mà còn được kiểm chứng thực tế trong Đề tài cấp Viện Hàn lâm Khoa học và Công nghệ Việt Nam: "Xây dựng hệ thống giám sát và dự báo thông tin lan truyền trên mạng xã hội tại Việt Nam", cung cấp công cụ phục vụ trực tiếp công tác bảo vệ an ninh thông tin theo Nghị định 15/2020/NĐ-CP của Chính phủ.

Literature Review và Positioning

Phân tích lan truyền thông tin trên mạng xã hội là giao điểm liên ngành giữa Lý thuyết Đồ thị (Graph Theory), Khoa học Dữ liệu (Data Science), Vật lý Thống kê và Xã hội học Tính toán. Tổng quan y văn cho thấy hai luồng nghiên cứu chính đang tồn tại những tranh luận học thuật sâu sắc:

                                    CÁC NHÁNH NGHIÊN CỨU TIỀN NHIỆM VÀ VỊ TRÍ CỦA LUẬN ÁN
                                    
       [Tối ưu hóa Tốc độ Tính toán Đồ thị]                           [Nâng cao Độ chính xác Dự báo Lan truyền]

Tổng hợp các luồng nghiên cứu về tốc độ tính toán đồ thị

Trong bài toán tính toán Độ trung tâm trung gian (Betweenness Centrality - BC) giải bài toán All-Pairs Shortest Path (APSP), giải thuật nền tảng của Ulrik Brandes (2001) đạt độ phức tạp $O(|V||E|)$ cho đồ thị không trọng số, vượt trội hơn hẳn so với thuật toán Floyd-Warshall ($O(|V|^3)$) và Johnson ($O(|V|^2\log|V| + |V||E|)$). Tuy nhiên, trên mạng xã hội lớn, thời gian tính toán vẫn là rào cản nghiêm trọng. Để giải quyết, các tác giả quốc tế tiếp cận theo bốn hướng:

  • Nén đồ thị (Graph Compression): Tomás Feder và ctv (1995), Micah Adler và ctv (1998) đề xuất nén đồ thị lưỡng phân hoặc tối ưu cây bao trùm tối thiểu. Phương pháp này chỉ phù hợp để lưu trữ dữ liệu tĩnh, bất khả thi đối với các mạng xã hội có cấu trúc liên tục biến động do chi phí giải nén đồ thị quá lớn.
  • Rút gọn đồ thị (Graph Reduction): Seth Gilbert và ctv (2012) đề xuất các thuật toán KeepOne, KeepAll và Redundant Vertex Elimination (RVE). KeepOne bảo toàn nút quan trọng nhưng phá vỡ tính chất đường đi ngắn nhất; KeepAll bảo toàn đường đi ngắn nhất nhưng loại bỏ quá nhiều nút trung gian; RVE loại bỏ các nút có chung tập lân cận nhưng dễ triệt tiêu nhầm các nút trung tâm kề nhau. Luận án của Nguyễn Hải Dũng (2016) rút gọn dựa trên đỉnh treo và đỉnh sườn nhưng làm biến dạng đồ thị gốc quá lớn, chỉ áp dụng được trên đồ thị nhỏ từ 100 đến 1.000 đỉnh.
  • Tính toán xấp xỉ (Approximation): Ahmad Mahmoody và ctv (2016), Matteo Riondato và ctv (2016) sử dụng kỹ thuật lấy mẫu ngẫu nhiên đường đi ngắn nhất. Phương pháp này đánh đổi độ chính xác và không đảm bảo tính ổn định trong việc định danh các đỉnh trung tâm trên đồ thị bất đối xứng.
  • Tính toán song song (Parallel Computing): Massimo Bernaschi và ctv (2011), Fan và ctv (2016), Adam McLaughlin và David Bader (2014) tận dụng GPU. Mặc dù GPU tăng tốc đáng kể trên đồ thị tĩnh, kiến trúc bộ nhớ GPU hạn chế khả năng mở rộng trên mạng động. Trên kiến trúc CPU bộ nhớ chia sẻ, bộ công cụ NetworKit (Christian Staudt và ctv, 2016) và TeexGraph (Frank Takes và ctv) sử dụng OpenMP để song song hóa, trở thành chuẩn đối sánh hàng đầu hiện nay.

Tổng hợp các luồng nghiên cứu về độ chính xác mô hình hóa lan truyền

Các mô hình lan truyền rời rạc cổ điển của Kempe, Kleinberg và Tardos (2003) (LT và IC) xem xác suất kích hoạt giữa hai đỉnh là bất biến hoặc gán ngẫu nhiên. Nhằm tăng độ chính xác, Haewoon Kwak và ctv (2010), Taher Haveliwala (2002), Jianshu Weng và ctv (2010) phát triển TwitterRank dựa trên phân bố PageRank theo chủ đề. Tuy nhiên, các cách tiếp cận này chỉ mô hình hóa quan hệ theo dõi tĩnh (one-way follow) trên Twitter.

Seth Myers, Corey Zhu và Jure Leskovec (2012) cùng với Baojun Wu và ctv (2014) tiên phong xem xét ảnh hưởng bên ngoài tác động lên người dùng. Dẫu vậy, Myers chỉ đo lường sự tiếp nhận trực tiếp của người dùng từ phương tiện truyền thông ngoài, chưa định lượng được việc ngoại lực tác động làm biến đổi xác suất chuyển giao thông tin giữa các cặp người dùng nội bộ. Mặt khác, các nghiên cứu dự đoán kích thước lan truyền của Gabor Szabo và Bernardo Huberman (2010), Eytan Bakshy và ctv (2011), hay Maciej Kupavskii và ctv (2012) áp dụng mô hình hồi quy tuyến tính hoặc học có giám sát, đòi hỏi không gian đặc trưng phức tạp và không phản ánh bản chất ngẫu nhiên của chuỗi sự kiện lan truyền.

Vị trí của luận án được xác lập rõ ràng: Luận án không chọn phương pháp lấy mẫu xấp xỉ hay nén đồ thị phá vỡ topo, mà đề xuất giải pháp kép Red-Bet: Rút gọn bảo toàn cấu trúc thông qua thay thế các đỉnh tương đương bậc 1 ($deg(v)=1$) kết hợp song song hóa đa luồng thuật toán Brandes bằng thư viện CilkPlus trên CPU; đồng thời mở rộng mô hình IC tích hợp 3 tham số (tương tác quan hệ, độ tương đồng sở thích, và ảnh hưởng truyền thông bên ngoài) kết hợp giải thuật Cây lan truyền có khả năng nhất.

Đóng góp lý thuyết và khung phân tích

Đóng góp cho lý thuyết

Luận án mở rộng và làm sâu sắc thêm hai lý thuyết nền tảng trong khoa học mạng:

  1. Mở rộng Lý thuyết Độ trung tâm trung gian của Freeman (1977): Luận án chứng minh định lý toán học về việc bảo toàn nguyên vẹn giá trị Betweenness Centrality của các nút trung tâm khi triệt tiêu tập đỉnh treo bậc 1. Vì đỉnh có $deg(v)=1$ chỉ kết nối với một đỉnh duy nhất trong đồ thị, số lượng đường đi ngắn nhất đi qua $v$ nối giữa hai đỉnh bất kỳ khác $s$ và $t$ ($s \neq v \neq t$) luôn bằng 0, nghĩa là $BC(v) = 0$. Bằng cách gom cụm và thay thế các đỉnh treo có chung đỉnh lân cận bằng một đỉnh đại diện duy nhất, luận án thu hẹp không gian tính toán mà không làm thay đổi giá trị trung tâm tương đối của mạng.
  2. Mở rộng Mô hình Bậc độc lập (Independent Cascade Model) của Kempe et al. (2003): Luận án phát triển mô hình IC truyền thống thành Mô hình Lan truyền Đa nhân tố Ngoại sinh - Nội sinh (Exogenous-Endogenous Multi-factor Diffusion Model). Khung lý thuyết mới tái định nghĩa xác suất kích hoạt một bước $p_{u,v}$ không còn là hằng số tĩnh mà là một hàm phụ thuộc thời gian và ngữ cảnh: $$p_{u,v} = f(UI_{u,v}, Sim_{u,v}, Ext_v)$$ Trong đó:
    • $UI_{u,v}$: Cường độ tương tác lịch sử giữa người dùng $u$ và $v$.
    • $Sim_{u,v}$: Mức độ tương đồng về mặt sở thích nội dung giữa $u$ và $v$ đối với chủ đề lan truyền.
    • $Ext_v$: Hệ số thúc đẩy tiếp nhận thông tin từ các kênh truyền thông xã hội bên ngoài mạng lưới.
                                      KHUNG PHÂN TÍCH ĐA TẦNG CỦA LUẬN ÁN

Khung phân tích độc đáo

Khung phân tích của luận án tích hợp chặt chẽ 4 nhánh lý thuyết: Lý thuyết Đồ thị, Lý thuyết Lan truyền Rời rạc, Mô hình Hóa Tác động Ngoại sinh và Lý thuyết Tính toán Song song (Parallel Computing Architecture). Luận án xác lập rõ điều kiện biên (boundary conditions): Áp dụng cho các đơn đồ thị có hướng, liên thông, không trọng số, kích thước số đỉnh nhỏ hơn $2^{32}$, trong môi trường mạng xã hội mở nơi thông tin vừa truyền qua liên kết cá nhân vừa chịu tác động của truyền thông đại chúng.

Phương pháp nghiên cứu tiên tiến

Thiết kế nghiên cứu

Luận án tuân thủ nghiêm ngặt quan điểm thực chứng tính toán (computational positivism) kết hợp thiết kế thực nghiệm mô phỏng và kiểm chứng trên dữ liệu mạng thực tế. Thiết kế nghiên cứu gồm 2 nhánh song song giải quyết hai mục tiêu cốt lõi:

  • Nhánh 1 (Benchmark hiệu năng thuật toán): Đánh giá thời gian thực thi (execution time in seconds) và hệ số tăng tốc ($Speedup = T_{single} / T_{parallel}$) của thuật toán Red-Bet khi thay đổi số luồng CPU (từ 1 đến đa luồng), so sánh đối chuẩn trực tiếp với hai phần mềm hàng đầu thế giới: NetworKit (viết bằng C++ kết hợp OpenMP) và TeexGraph.
  • Nhánh 2 (Kiểm định độ chính xác mô hình dự báo): Đánh giá sai số dự báo quy mô tầng bậc và kích thước lan truyền giữa mô hình đề xuất với "sự thật cơ bản" (ground truth) trên tập dữ liệu mô phỏng và thực tế, phân tích hiệu suất trong hai trường hợp: chưa xét ảnh hưởng bên ngoài và có xuất hiện ảnh hưởng bên ngoài.

Quy trình nghiên cứu rigorous

1. Quy trình rút gọn đồ thị và song song hóa (Thuật toán Red-Bet)

  • Bước 1 (Rút gọn đỉnh bậc 1 tương đương): Quét toàn bộ danh sách đỉnh của đồ thị $G=(V,E)$. Lọc ra các đỉnh treo có $deg(v)=1$. Nếu tồn tại một nhóm đỉnh treo $V_{sub} = {v_1, v_2, ..., v_k}$ cùng nối tới một đỉnh lân cận duy nhất $u \in V$, thuật toán thay thế toàn bộ nhóm $V_{sub}$ bằng một đỉnh đại diện duy nhất $v_{rep}$. Đồ thị sau rút gọn $G'=(V', E')$ có quy mô $|V'| < |V|$ và $|E'| < |E|$, giảm triệt để số lượng phép duyệt BFS không cần thiết.
  • Bước 2 (Song song hóa thuật toán Brandes bằng CilkPlus): Giải thuật Brandes truyền thống lặp qua từng đỉnh nguồn $s \in V$ để tính SSSP thông qua duyệt theo chiều rộng (BFS) và tính toán trọng số tích lũy $\delta[v]$ thông qua ngăn xếp $S$: $$\delta[v] = \sum_{w: v \in Pred[w]} \frac{\sigma[v]}{\sigma[w]} (1 + \delta[w])$$ Luận án thực hiện song song hóa vòng lặp ngoài cùng (foreach s = 0 to |V|) bằng cấu trúc cilk_for của Intel CilkPlus. Mỗi luồng CPU xử lý độc lập một đỉnh nguồn $s$, duy trì cấu trúc hàng đợi $Q$, ngăn xếp $S$, mảng khoảng cách $dist[]$, danh sách đỉnh tiền bối $Pred[]$, và mảng số đường đi ngắn nhất $\sigma[]$ cục bộ để loại bỏ hoàn toàn hiện tượng tương tranh (race conditions) mà không cần dùng khóa khóa (lock-free), tối ưu hóa hiệu năng bộ nhớ đệm cache L1/L2/L3.

2. Quy trình tính xác suất chấp nhận thông tin và xây dựng Cây lan truyền

  • Bước 1 (Đo lường ảnh hưởng quan hệ người dùng): Dựa trên nhật ký tương tác (Activity Log: đăng bài, chia sẻ, bình luận, tương tác qua lại), xác định tần suất và trọng số liên kết $UI(u,v)$ giữa hai nút người dùng.
  • Bước 2 (Đo lường ảnh hưởng sở thích nội dung): Sử dụng mô hình không gian vector biểu diễn hồ sơ sở thích của người dùng và chủ đề bài viết, tính toán độ tương đồng cosine giữa vector chủ đề của thông tin và vector hành vi quá khứ của người dùng nhận tin.
  • Bước 3 (Đo lường ảnh hưởng bên ngoài): Áp dụng hàm logistic chuẩn hóa để định lượng mức độ kích thích từ các nguồn tin bên ngoài mạng xã hội tác động lên tâm lý người dùng tại thời điểm $t$.
  • Bước 4 (Xây dựng Cây lan truyền có khả năng nhất): Khởi tạo từ nút nguồn (người phát tán thông tin đầu tiên). Tại mỗi bước thời gian $t$, xét tất cả các nút lân cận chưa được kích hoạt; tính xác suất kích hoạt tổng hợp. Chọn nhánh có xác suất vượt ngưỡng tối ưu để mở rộng cây lan truyền (Propagation Tree), từ đó xác định độ sâu tầng bậc và tổng số đỉnh bị kích hoạt trong toàn mạng.
                      SƠ ĐỒ KHỐI QUY TRÌNH THỰC THI THUẬT TOÁN RED-BET VÀ MÔ HÌNH DỰ BÁO
                      
   [Tính Xác suất Kích hoạt Tổng hợp p(u,v)]                 [Độ trung tâm Betweenness BC(v)]

Dữ liệu và phân tích

Thực nghiệm được triển khai trên hệ thống máy tính hiệu năng cao (HPC) đa lõi của Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội. Dữ liệu thử nghiệm bao gồm 5 bộ dữ liệu đồ thị mạng xã hội thực tế và mô phỏng chuẩn quốc tế (chứa từ hàng trăm nghìn đến hàng triệu đỉnh/cạnh) cùng các bộ dữ liệu ngẫu nhiên 400 đỉnh, 500 đỉnh để trực quan hóa cấu trúc topo. Toàn bộ mã nguồn thuật toán và tập dữ liệu thử nghiệm được tác giả công khai trên GitHub tại địa chỉ sondn89/bigGraphplus.

Phát hiện đột phá và implications

Những phát hiện then chốt

  1. Hiệu quả vượt bậc của kỹ thuật rút gọn đồ thị bậc 1: Việc thay thế các đỉnh treo tương đương bậc 1 giúp giảm từ 15% đến 35% số đỉnh cần duyệt trong bài toán SSSP mà hoàn toàn không làm sai lệch thứ hạng (ranking order) của các đỉnh có Độ trung tâm trung gian cao nhất ($BC_{max}$). Đồ thị sau rút gọn giữ nguyên 100% tính chất liên thông của các thành phần lõi.
  2. Hệ số tăng tốc (Speedup) vượt trội của giải thuật Red-Bet: Thực nghiệm đối chuẩn trên 5 bộ dữ liệu đồ thị mạng thực tế cho thấy giải thuật Red-Bet đạt hiệu năng xử lý cao hơn đáng kể so với TeexGraph và NetworKit. Khi tăng số luồng CPU, thời gian tính toán BC giảm theo hàm hyperbol rõ rệt, chứng minh tính ưu việt của mô hình lập trình luồng CilkPlus trong việc cân bằng tải phân tán so với chỉ thị OpenMP truyền thống.
  3. Sự vượt trội của mô hình IC tích hợp 3 tham số: Bảng đối sánh thực nghiệm trên tập dữ liệu hoạt động người dùng cho thấy:
    • Khi chưa xét ảnh hưởng bên ngoài, việc kết hợp giữa quan hệ người dùng và sở thích nội dung đã cải thiện độ chính xác dự báo quy mô lan truyền lên 18,4% so với mô hình IC truyền thống của Kempe et al.
    • Khi xuất hiện các sự kiện nóng có ảnh hưởng bên ngoài (ngoại lực truyền thông), mô hình 3 tham số của luận án giúp giảm sai số dự báo kích thước lan truyền lên tới 32,6% so với các phương pháp chỉ xét dữ liệu nội mạng.
  4. Khả năng dự báo chính xác hình thái Cây lan truyền: Thuật toán xây dựng Cây lan truyền có khả năng nhất tái lập chính xác cấu trúc phân tầng (cascade depth) và nhận diện sớm các "nút phát tán siêu cấp" (super-spreaders) chỉ sau 1 đến 2 bước nhảy (hops) đầu tiên của luồng tin.

Implications đa chiều

  • Về mặt học thuật (Theoretical Advances): Công trình đặt nền móng cho việc kết hợp giữa Lý thuyết Đồ thị rút gọn và Lý thuyết Xử lý Tác động Ngoại sinh trong khoa học mạng xã hội; chứng minh rằng mô hình hóa mạng xã hội không thể tiếp cận thuần túy từ cấu trúc liên kết đóng mà bắt buộc phải gắn liền với môi trường thông tin mở.
  • Về mặt phương pháp luận (Methodological Innovations): Thuật toán Red-Bet mở ra hướng tiếp cận mới cho các bài toán phân tích đồ thị quy mô lớn ($N < 2^{32}$) trên phần cứng CPU đa lõi thông thường mà không nhất thiết phải đầu tư hạ tầng siêu máy tính hoặc cụm GPU đắt đỏ.
  • Về mặt thực tiễn và an ninh quốc gia (Policy & Practical Applications): Kết quả nghiên cứu cung cấp thuật toán lõi cho các hệ thống giám sát không gian mạng của Cục An ninh mạng và phòng chống tội phạm sử dụng công nghệ cao (A05 - Bộ Công an) và Viện Công nghệ thông tin (Viện Hàn lâm Khoa học và Công nghệ Việt Nam). Mô hình cho phép phát hiện sớm các chiến dịch tin giả, khoanh vùng nguồn phát tán độc hại và chủ động dự báo quy mô khủng hoảng truyền thông theo tinh thần các Nghị định 174/2013/NĐ-CP, Nghị định 49/2017/NĐ-CP và Nghị định 15/2020/NĐ-CP.

Limitations và Future Research

Luận án thừa nhận một cách khách quan các giới hạn nghiên cứu:

  1. Giới hạn về mô hình đồ thị: Luận án mới chỉ tập trung nghiên cứu trên đơn đồ thị, có hướng, liên thông và không trọng số. Trong thực tế, mạng xã hội có thể là đa đồ thị (multi-graph) với các cạnh có trọng số biến thiên liên tục phản ánh mức độ thân thiết hoặc thời lượng tương tác.
  2. Giới hạn về giả định rút gọn: Kỹ thuật rút gọn hiện tại chỉ áp dụng cho các đỉnh tương đương bậc 1 ($deg(v)=1$). Các cấu trúc cụm dày đặc (cliques) hoặc các đỉnh bậc cao có vai trò ngoại vi chưa được tối ưu hóa rút gọn.
  3. Giới hạn về tính động của dữ liệu: Thuật toán song song hóa hiện tại tối ưu xuất sắc trên các ảnh chụp đồ thị tĩnh (static graph snapshots) tại từng cửa sổ thời gian, chưa hỗ trợ cập nhật động liên tục theo thời gian thực (streaming graphs) khi có luồng cạnh/đỉnh thêm mới với tần suất mili-giây.

Chương trình nghiên cứu tiếp theo (Future Research Agenda) bao gồm 4 định hướng:

  • Mở rộng thuật toán Red-Bet sang đồ thị có trọng số và mạng không thuần nhất (Heterogeneous Information Networks).
  • Kết hợp kiến trúc lai CPU-GPU (sử dụng CUDA/OpenCL) để xử lý song song phân tán trên các đồ thị có quy mô hàng chục tỷ cạnh.
  • Ứng dụng các mô hình Học sâu trên Đồ thị (Graph Neural Networks - GNNs) và Graph Convolutional Networks (GCN) để tự động hóa việc học biểu diễn người dùng và tham số hóa ma trận lan truyền.
  • Xây dựng cơ chế mô hình hóa lan truyền tin tức xuyên nền tảng (Cross-platform Diffusion) đồng thời giữa Facebook, YouTube, Twitter và TikTok.

Tác động và ảnh hưởng

  • Tác động học thuật: Các công trình trích xuất từ luận án đã được công bố trên các tạp chí và kỷ yếu hội thảo khoa học chuyên ngành uy tín trong nước và quốc tế ([C1] đến [C5]), khẳng định năng lực nghiên cứu độc lập và tiên phong của tác giả trong lĩnh vực Hệ thống thông tin.
  • Chuyển đổi công nghệ và ứng dụng thực tiễn: Thuật toán được đóng gói thành thư viện mã nguồn mở C++ hiệu năng cao (sondn89/bigGraphplus), sẵn sàng chuyển giao cho các doanh nghiệp công nghệ thông tin trong nước để xây dựng các nền tảng lắng nghe mạng xã hội (Social Listening Tools) phục vụ quản trị thương hiệu, tối ưu hóa chiến dịch tiếp thị số và chăm sóc khách hàng.
  • Tác động xã hội và an ninh trật tự: Công trình đóng góp trực tiếp vào việc bảo vệ chủ quyền không gian mạng quốc gia, hỗ trợ đắc lực cho các cơ quan chức năng trong việc định hướng dư luận xã hội, dập tắt các tin đồn thất thiệt liên quan đến thiên tai, dịch bệnh và an ninh chính trị.

Đối tượng hưởng lợi

                                    CÁC NHÓM ĐỐI TƯỢNG HƯỞNG LỢI TRỰC TIẾP

Câu hỏi chuyên sâu

1. Đóng góp lý thuyết độc đáo nhất của luận án là gì và đã mở rộng lý thuyết nào?

Đóng góp lý thuyết độc đáo nhất là việc mở rộng Mô hình Bậc độc lập (Independent Cascade Model) của Kempe et al. (2003) từ mô hình nội sinh cục bộ sang Mô hình Đa nhân tố Ngoại sinh - Nội sinh. Luận án đã tích hợp thành công tham số ảnh hưởng ngoại lực truyền thông bên ngoài kết hợp với độ tương đồng sở thích và lịch sử tương tác vào một công thức tính xác suất kích hoạt thống nhất, giải quyết triệt để khiếm khuyết xem nhẹ tác động truyền thông đại chúng của các mô hình truyền thống.

2. Điểm đột phá về phương pháp luận tính toán của luận án khi so sánh với các nghiên cứu quốc tế là gì?

Điểm đột phá là giải thuật Red-Bet, kết hợp hai kỹ thuật: (1) Rút gọn đồ thị thông qua thay thế các đỉnh tương đương bậc 1 ($deg(v)=1$) giúp triệt tiêu các phép duyệt BFS dư thừa mà vẫn bảo toàn 100% thứ hạng của các đỉnh Betweenness Centrality cốt lõi; (2) Song song hóa giải thuật Brandes bằng mô hình luồng CilkPlus với cơ chế phân chia công việc (work-stealing) tối ưu trên bộ nhớ chia sẻ CPU. Phương pháp này vượt trội hơn NetworKit (sử dụng OpenMP) và TeexGraph về hệ số tăng tốc, đồng thời khắc phục triệt để nhược điểm làm biến dạng đồ thị của phương pháp RVE (Gilbert et al.) và phương pháp rút gọn của Nguyễn Hải Dũng.

3. Phát hiện bất ngờ nhất từ dữ liệu thực nghiệm là gì?

Phát hiện bất ngờ nhất là: Các đỉnh treo bậc 1 tuy hoàn toàn không đóng góp vào giá trị Độ trung tâm trung gian ($BC=0$) nhưng lại chiếm tới 20-35% tổng thời gian tính toán duyệt đồ thị trong giải thuật Brandes truyền thống. Việc loại bỏ nhóm đỉnh này không chỉ tăng tốc tính toán từ 1,5 đến 3 lần mà còn hoàn toàn không làm thay đổi cấu trúc cây đường đi ngắn nhất giữa các nút trung tâm còn lại.

4. Luận án có cung cấp quy trình tái lập thực nghiệm (Replication Protocol) không?

Có. Luận án cung cấp quy trình tái lập hoàn chỉnh: Toàn bộ mã nguồn thuật toán C++, các chỉ thị song song CilkPlus, tập dữ liệu thực nghiệm và hướng dẫn cài đặt chi tiết đã được tác giả công khai trên kho lưu trữ GitHub tại địa chỉ: https://github.com/sondn89/bigGraphplus.

5. Định hướng nghiên cứu 10 năm tới được phác thảo như thế nào?

Chương trình nghiên cứu dài hạn tập trung vào 3 trụ cột: (1) Phát triển khung tính toán phân tán lai GPU-CPU quy mô đồ thị hàng chục tỷ cạnh; (2) Tích hợp Graph Neural Networks (GNN) để dự báo lan truyền trên mạng xã hội động theo thời gian thực (Streaming Temporal Graphs); (3) Xây dựng hệ thống tự động phát hiện và ngăn chặn chiến dịch tấn công tin giả xuyên nền tảng (Cross-platform Disinformation Campaigns) dựa trên trí tuệ nhân tạo.

Kết luận

Công trình Luận án Tiến sĩ của tác giả Dương Ngọc Sơn đã hoàn thành xuất sắc các mục tiêu nghiên cứu đề ra với 05 đóng góp cốt lõi:

  1. Đề xuất kỹ thuật rút gọn đồ thị bảo toàn độ trung tâm: Loại bỏ và thay thế các đỉnh tương đương bậc 1 ($deg(v)=1$), giảm mạnh không gian tính toán đồ thị mà không làm suy biến độ chính xác của các phép đo trung tâm cốt lõi.
  2. Phát triển giải thuật song song hóa Red-Bet: Ứng dụng thành công Intel CilkPlus đa luồng để song song hóa giải thuật Brandes trên CPU, đạt tốc độ vượt trội so với các công cụ chuẩn quốc tế NetworKit và TeexGraph.
  3. Mở rộng mô hình lan truyền IC đa nhân tố: Thiết lập công thức xác định xác suất lan truyền dựa trên 03 tham số then chốt (quan hệ tương tác, sở thích nội dung và tác động truyền thông ngoại sinh), nâng cao độ chính xác dự báo lên tới 32,6%.
  4. Đề xuất thuật toán xây dựng Cây lan truyền có khả năng nhất: Mô phỏng chính xác cấu trúc phân tầng và quy mô bùng phát của luồng tin theo thời gian thực.
  5. Chuyển giao và ứng dụng thực tiễn thành công: Đóng gói công cụ mã nguồn mở và ứng dụng trực tiếp vào Hệ thống giám sát, dự báo thông tin mạng xã hội cấp Viện Hàn lâm Khoa học và Công nghệ Việt Nam, phục vụ đắc lực công tác bảo đảm an ninh mạng quốc gia.

Luận án khẳng định bước tiến vững chắc về mặt học thuật trong ngành Hệ thống thông tin, mở ra các hướng nghiên cứu liên ngành giá trị cao và để lại dấu ấn thực tiễn sâu sắc trong kỷ nguyên quản trị dữ liệu lớn và không gian số toàn cầu.