Tổng quan về luận án

Trong kỷ nguyên chuyển đổi số toàn cầu, mạng xã hội trực tuyến (Online Social Networks - OSNs) đã xác lập vị thế là hạ tầng giao tiếp và phân phối thông tin chủ đạo của xã hội loài người. Báo cáo thống kê toàn cầu của Hootsuite và We Are Social chỉ rõ: "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ỷ... số người dùng mới đã tăng thêm 298 triệu người dùng... 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ố". Đồng thời, "đố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". Lưu lượng dữ liệu khổng lồ cùng tốc độ lan truyền phi tuyến tính đặt ra yêu cầu cấp thiết về mặt khoa học kỹ thuật trong việc phân tích, kiểm soát và dự báo quy mô lan truyền thông tin nhằm phục vụ an ninh thông tin, phòng chống tin giả (fake news), cũng như tối ưu hóa chiến dịch truyền thông số.

Tuy nhiên, các hệ thống phân tích dữ liệu mạng xã hội quy mô lớn hiện nay đang đối mặt với hai rào cản mang tính cốt lõi (research gaps):

  1. Điểm nghẽn hiệu năng tính toán đồ thị (Computational Bottleneck): Việc tính toán các độ đo trung tâm (centrality metrics), tiêu biểu là Độ trung tâm trung gian (Betweenness Centrality - BC), trên các mạng quy mô hàng triệu đỉnh và hàng trăm triệu cạnh đòi hỏi giải bài toán tìm đường đi ngắn nhất giữa mọi cặp đỉnh (All-Pairs Shortest Path - APSP). Giải thuật tuần tự kinh điển của Ulrik Brandes (2001) có độ phức tạp thời gian $O(|V||E|)$, dẫn đến chi phí thời gian quá lớn, không đáp ứng được yêu cầu dự báo thời gian thực (real-time forecasting).
  2. Sai số mô hình hóa động học lan truyền (Modeling Accuracy Gap): Các mô hình kinh điển như Mô hình Ngưỡng tuyến tính (Linear Threshold - LT) và Mô hình Bậc độc lập (Independent Cascade - IC) của Kempe, Kleinberg và Tardos (2003), hay các tiếp cận dựa trên cấu trúc liên kết tĩnh (Kwak et al., 2010; Weng et al., 2010) hầu như chỉ xem xét lịch sử tương tác nội tại và mức độ tương đồng sở thích, hoàn toàn bỏ qua tác động định lượng của luồng thông tin ngoại sinh (external influence) ngoài không gian mạng xã hội.

Để giải quyết triệt để hai điểm nghẽn trên, Luận án tiến sĩ ngành Khoa học 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 với đề 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" (thực hiệ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, 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) đã thiết lập hai mục tiêu nghiên cứu và giả thuyết cụ thể:

  • Câu hỏi nghiên cứu 1 (RQ1): Làm thế nào để giảm thiểu độ phức tạp tính toán độ đo Betweenness Centrality trên đơn đồ thị hữu hướng lớn mà không làm biến dạng cấu trúc phân bố các nút trọng yếu?
    • Giả thuyết 1 (H1): Việc kết hợp kỹ thuật rút gọn đồ thị thông qua thay thế các đỉnh tương đương bậc 1 ($\text{deg}(v) = 1, BC(v) = 0$) với cơ chế song song hóa thuật toán duyệt đường đi ngắn nhất nguồn đơn (Single-Source Shortest Path - SSSP) trên kiến trúc CPU đa luồng sẽ đạt hệ số tăng tốc (speedup factor) vượt trội so với các công cụ đồ thị chuẩn quốc tế.
  • Câu hỏi nghiên cứu 2 (RQ2): Làm thế nào để định lượng chính xác kích thước lan truyền thông tin khi tích hợp đồng thời các yếu tố nội tại và yếu tố ngoại sinh từ đời sống thực tế?
    • Giả thuyết 2 (H2): Xây dựng mô hình xác suất lan truyền mở rộng dựa trên 03 tham số (quan hệ người dùng, sở thích chủ đề, ảnh hưởng bên ngoài) và ước tính kích thước lan truyền qua Cây lan truyền có khả năng nhất (Most Probable Propagation Tree) sẽ làm giảm đáng kể sai số dự báo so với mô hình IC truyền thống.

Nghiên cứu có quy mô thực nghiệm sâu rộng trên các tập dữ liệu mạng xã hội tiêu chuẩn và dữ liệu thực tế thu thập từ hệ thống phân tích giám sát thông tin mạng xã hội tại Việt Nam, mang ý nghĩa nền tảng cho việc giám sát an toàn thông tin quốc gia theo Nghị định số 15/2020/NĐ-CP của Chính phủ.

Literature Review và Positioning

Lịch sử nghiên cứu phân tích mạng xã hội và lan truyền thông tin trải qua nhiều giai đoạn phát triển với những luồng học thuật chính:

                      ┌─────────────────────────────────────────────────────────┐
                      │  Phân tích đồ thị & Độ đo trung tâm                     │
                      │  - Freeman (1977): Betweenness Centrality (BC)          │
                      │  - Brandes (2001): Thuật toán APSP tối ưu O(|V||E|)     │
                      └────────────────────────────┬────────────────────────────┘
                                                   │
                                                   ▼
┌──────────────────────────────────────────────────┴──────────────────────────────────────────────────┐
│                                       CÁC HƯỚNG TỐI ƯU HÓA                                          │
├──────────────────────────────────────┬──────────────────────────────────────────────────────────────┤
│ 1. Rút gọn đồ thị                    │ 2. Tính toán song song                                       │
│ - Feder et al. (1995): Đồ thị 2 phía │ - Bernaschi et al. (2010), McLaughlin et al. (2014): GPU     │
│ - Gilbert et al.: KeepOne, KeepAll,  │ - Angriman et al.: NetworKit (OpenMP)                        │
│   RVE (Redundant Vertex Elimination) │ - Takes et al.: TeexGraph (OpenMP)                           │
│ - Dũng (2015): Đỉnh treo & đỉnh sườn │ - Wei et al. (2016): Apache Giraph, GraphLab (Cluster/Cloud) │
└──────────────────────────────────────┴──────────────────────────────────────────────────────────────┘
                                                   │
                                                   ▼
                      ┌─────────────────────────────────────────────────────────┐
                      │  Đóng góp của Luận án: GIẢI THUẬT RED-BET               │
                      │  Rút gọn đỉnh tương đương bậc 1 + CilkPlus CPU Threads  │
                      └─────────────────────────────────────────────────────────┘

Trong dòng nghiên cứu về cấu trúc mạng và độ trung tâm, Linton Freeman (1977) đã đặt nền móng cho khái niệm Độ trung tâm trung gian (Betweenness Centrality - BC), chứng minh rằng các đỉnh đóng vai trò cầu nối trên các đường đi ngắn nhất kiểm soát luồng thông tin toàn mạng. Để tính toán giá trị này, giải thuật Floyd-Warshall ($O(|V|^3)$) và Johnson ($O(|V|^2\log|V| + |V||E|)$) nhanh chóng bộc lộ hạn chế bộ nhớ và thời gian khi đồ thị mở rộng. Giải thuật của Brandes (2001) đã trở thành chuẩn mực tính toán chính xác BC với độ phức tạp $O(|V||E|)$.

Để tăng tốc Brandes, hai trường phái chính đã xuất hiện:

  • Trường phái rút gọn và nén đồ thị: Feder và cộng sự (1995) dùng kỹ thuật phân vùng đồ thị lưỡng phân; Adler và cộng sự (1998) nén đồ thị theo cây bao trùm tối thiểu. Gilbert và cộng sự đề xuất các giải thuật KeepOne, KeepAll và Xóa đỉnh thừa (Redundant Vertex Elimination - RVE). Tuy nhiên, KeepOne phá vỡ tính bảo toàn đường đi ngắn nhất, KeepAll loại bỏ quá nhiều nút trung gian, còn RVE có nguy cơ xóa nhầm các đỉnh quan trọng có chung láng giềng. Nghiên cứu của Dũng (2015) rút gọn đỉnh treo và đỉnh sườn nhưng làm biến dạng nghiêm trọng cấu trúc đồ thị gốc, chỉ thử nghiệm được trên quy mô hạn chế (100–1,000 đỉnh).
  • Trường phái tính toán song song và siêu máy tính: Bernaschi et al. (2010), Fan et al. (2014), McLaughlin et al. (2014) triển khai Brandes trên bộ xử lý đồ họa (Graphic Processing Unit - GPU), nhưng phương pháp GPU gặp giới hạn nghiêm trọng về dung lượng bộ nhớ toàn cục khi đồ thị biến động liên tục. Wei et al. (2016) sử dụng Apache Giraph và GraphLab trên cụm siêu máy tính, tiêu tốn tài nguyên quá mức và không hiệu quả với đồ thị quy mô dưới $2^{32}$ đỉnh. Các công cụ hàng đầu hiện nay như NetworKit (Angriman et al.) và TeexGraph (Takes et al.) áp dụng OpenMP trên kiến trúc bộ nhớ chia sẻ nhưng chưa tối ưu hóa cấu trúc dữ liệu đồ thị trước khi xử lý.
                      ┌─────────────────────────────────────────────────────────┐
                      │  Mô hình hóa Lan truyền thông tin                       │
                      │  - Kempe, Kleinberg, Tardos (2003): Mô hình IC & LT     │
                      └────────────────────────────┬────────────────────────────┘
                                                   │
                                                   ▼
┌──────────────────────────────────────────────────┴──────────────────────────────────────────────────┐
│                                    CÁC HƯỚNG MỞ RỘNG MÔ HÌNH                                        │
├──────────────────────────────────────┬──────────────────────────────────────────────────────────────┤
│ 1. Cấu trúc mạng & Phân loại học máy │ 2. Yếu tố ngoại sinh & Động học nội tại                      │
│ - Kwak et al. (2010): Twitter PageRank│ - Myers, Zhu, Leskovec (2012): External media exposure      │
│ - Weng et al. (2010): TwitterRank    │ - Wu et al. (2014): Topic-based external trends              │
│ - Szabo et al. (2010), Bakshy (2011) │ - Saito et al.: Asynchronous IC (ASIC)                       │
│   Hồi quy & Phân loại học có giám sát│                                                              │
└──────────────────────────────────────┴──────────────────────────────────────────────────────────────┘
                                                   │
                                                   ▼
                      ┌─────────────────────────────────────────────────────────┐
                      │  Đóng góp của Luận án: MÔ HÌNH XÁC SUẤT 3 THÀNH PHẦN   │
                      │  Tương tác UI + Sở thích Topic + Ngoại sinh External    │
                      │  -> Cây lan truyền có khả năng nhất (Most Probable Tree)│
                      └────────────────────────────┌────────────────────────────┘

Trong dòng nghiên cứu về mô hình lan truyền, mô hình Independent Cascade (IC) và Linear Threshold (LT) của Kempe et al. (2003) đóng vai trò nền tảng. Các nghiên cứu tiếp theo mở rộng theo hướng: phân phối trễ hàm mũ (Asynchronous IC - Saito et al.), tích hợp độ tương đồng chủ đề TwitterRank (Weng et al., 2010), hoặc dự báo kích thước bằng hồi quy/phân loại học có giám sát (Szabo & Huberman, 2010; Bakshy et al., 2011; Kupavskii et al., 2012). Đáng chú ý, Myers, Zhu và Leskovec (2012) và Wu et al. (2014) chứng minh tác động của nguồn truyền thông bên ngoài tới người dùng mạng xã hội. Tuy nhiên, các công trình này chỉ xem xét người dùng tiếp nhận thông tin thụ động từ kênh ngoài mà chưa lượng hóa được cơ chế yếu tố bên ngoài kích hoạt sự lan truyền tương tác giữa người dùng với người dùng trong không gian mạng.

Luận án của NCS. Dương Ngọc Sơn định vị chính xác ở giao điểm của hai khoảng trống học thuật này: xây dựng giải thuật kết hợp rút gọn đồ thị mức đỉnh bậc 1 với song song hóa CilkPlus (Red-Bet), đồng thời tích hợp định lượng 3 trọng số (Tương tác - Chủ đề - Ngoại sinh) vào mô hình IC để tái lập Cây lan truyền có xác suất cực đại.

Đó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 sâu sắc Lý thuyết Đồ thị mạng xã hội (Social Network Graph Theory) và Lý thuyết Lan truyền thông tin (Information Diffusion Theory) qua các luận điểm khoa học có tính bước ngoặt:

  1. Lý thuyết tương đương topo cục bộ (Local Topological Equivalence): Luận án chứng minh định lý về việc loại bỏ các đỉnh treo có bậc $\text{deg}(v) = 1$ chia sẻ chung tập đỉnh liền kề không làm thay đổi giá trị Betweenness Centrality tương đối của các đỉnh cốt lõi ($\text{deg}(u) \ge 2$). Việc thay thế $k$ đỉnh bậc 1 tương đương bằng 1 đỉnh đại diện bảo toàn chính xác trật tự xếp hạng nút trung tâm (centrality ranking order) của mạng, giải quyết mâu thuẫn giữa giảm quy mô và duy trì cấu trúc không gian ngắn nhất.
  2. Nguyên lý tương tác đa nhân tố lan truyền (Multi-factor Diffusion Interaction Principle): Thách thức giả định truyền thống xem xác suất kích hoạt giữa hai nút là hằng số hoặc chỉ phụ thuộc vào tần suất tương tác lịch sử. Luận án mở rộng lý thuyết kích hoạt độc lập bằng cách thiết lập công thức hợp nhất: $$P_{uv} = \Phi\Big( \alpha \cdot UI(u, v) + \beta \cdot Topic(u, v) + \gamma \cdot External(t) \Big)$$ trong đó $\Phi(\cdot)$ là hàm phi tuyến logistic sigmoid, lượng hóa trực tiếp xung lực từ các biến cố truyền thông ngoài đời thực vào hành vi chuyển tiếp nội mạng.
  3. Mô hình Cây lan truyền xác định cục bộ (Most Probable Propagation Tree): Thay thế quá trình mô phỏng ngẫu nhiên Monte Carlo tốn kém bằng việc sinh cây bao trùm lan truyền dựa trên nguyên lý xác suất tiên nghiệm cực đại, cho phép tính toán giải tích trực tiếp kích thước lan truyền tại mỗi bước thời gian $t$.

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

Khung phân tích của luận án tích hợp chặt chẽ giữa Toán rời rạc, Khoa học dữ liệu và Tính toán hiệu năng cao (High-Performance Computing - HPC):

                                KHUNG PHÂN TÍCH TỔNG THỂ
                                
[ Đồ thị mạng xã hội gốc G = (V, E) ]
                 │
                 ▼
[ Kỹ thuật rút gọn đồ thị ] ────► Loại bỏ/thay thế đỉnh tương đương deg(v)=1
                 │
                 ▼
[ Đồ thị thu gọn G' = (V', E') ]
                 │
                 ▼
[ Song song hóa SSSP Brandes ] ──► Đa luồng Intel CilkPlus trên kiến trúc CPU
                 │
                 ▼
[ Thuật toán Red-Bet ] ─────────► Tính toán Betweenness Centrality (BC) siêu tốc
                 │
                 ▼
[ Mô hình tích hợp 3 thành tố ] ──► (1) Tương tác UI + (2) Sở thích Topic + (3) Ngoại sinh Ext
                 │
                 ▼
[ Cây lan truyền có khả năng nhất ]
                 │
                 ▼
[ Kích thước & Tốc độ lan truyền ]
  • Điều kiện biên (Boundary conditions): Phương pháp rút gọn và thuật toán Red-Bet áp dụng tối ưu cho lớp đơn đồ thị, liên thông, hữu hướng, không trọng số và có tính chất mạng thế giới nhỏ (small-world), mạng không tỷ lệ (scale-free networks) đặc trưng của mạng xã hội thực tế.

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

Thiết kế nghiên cứu

Nghiên cứu được thiết kế theo trường phái Thực chứng (Positivism) kết hợp Khoa học thiết kế (Design Science Research Methodology - DSRM), tuân thủ các chuẩn mực nghiêm ngặt của kỹ nghệ thuật toán và khoa học tính toán:

┌─────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                   HỆ THỐNG THIẾT KẾ PHƯƠNG PHÁP                                  │
├────────────────────────────────┬────────────────────────────────┬──────────────────────────────┤
│ PHƯƠNG DIỆN                    │ ĐẶC TẢ CHI TIẾT                │ MINH CHỨNG / CÔNG CỤ         │
├────────────────────────────────┼────────────────────────────────┼──────────────────────────────┤
│ Triết lý nghiên cứu            │ Thực chứng / Thực nghiệm DSRM   │ Đối chuẩn trên Benchmark quốc│
│                                │ định lượng                     │ tế & Hệ thống thực tế        │
├────────────────────────────────┼────────────────────────────────┼──────────────────────────────┤
│ Kiến trúc phần cứng            │ Máy chủ tính toán hiệu năng cao│ CPU Intel Xeon đa nhân,      │
│                                │ (HPC), CC-NUMA bộ nhớ chia sẻ  │ RAM ECC băng thông lớn       │
├────────────────────────────────┼────────────────────────────────┼──────────────────────────────┤
│ Nền tảng lập trình             │ Lập trình song song đa luồng   │ C/C++, Thư viện Intel        │
│                                │ cấp hệ thống                   │ CilkPlus, OpenMP             │
├────────────────────────────────┼────────────────────────────────┼──────────────────────────────┤
│ Thuật toán đề xuất             │ Red-Bet (Rút gọn + Brandes     │ Tối ưu hóa SSSP duyệt BFS    │
│                                │ song song) & Propagation Tree  │ hai chiều (bBFS)             │
├────────────────────────────────┼────────────────────────────────┼──────────────────────────────┤
│ Dữ liệu thử nghiệm             │ 05 Tập dữ liệu quốc tế + Dữ    │ SNAP Stanford, Dữ liệu thực  │
│                                │ liệu mạng xã hội Việt Nam      │ tế từ đề tài cấp VAST        │
└────────────────────────────────┴────────────────────────────────┴──────────────────────────────┘

Quy trình nghiên cứu rigorous

Quy trình nghiên cứu bao gồm 4 giai đoạn được liên kết logic chặt chẽ:

  1. Tiền xử lý và cấu trúc hóa dữ liệu đồ thị: Dữ liệu thô từ mạng xã hội được biểu diễn dưới dạng danh sách liền kề tối ưu hóa hoặc ma trận hàng thưa nén (Compressed Sparse Row - CSR), bảo đảm chi phí không gian bộ nhớ đạt ngưỡng tối ưu $O(|V| + |E|)$, khắc phục triệt để nhược điểm tốn bộ nhớ $O(|V|^2)$ của ma trận liền kề kinh điển.
  2. Kỹ thuật rút gọn đỉnh tương đương bậc 1:
    • Bước 1: Quét danh sách đỉnh để tìm tập các đỉnh treo $V_1 = {v \in V \mid \text{deg}(v) = 1}$.
    • Bước 2: Gom nhóm các đỉnh $u, w \in V_1$ có cùng đỉnh lân cận duy nhất $p \in V$ ($\Gamma(u) = \Gamma(w) = {p}$).
    • Bước 3: Thay thế nhóm đỉnh tương đương bằng một đỉnh đại diện duy nhất $v_{rep}$ và gán trọng số tích lũy cho nút đại diện, loại bỏ hoàn toàn các nhánh dư thừa khỏi tiến trình duyệt APSP.
  3. Song song hóa giải thuật Brandes bằng Intel CilkPlus:
    • Sử dụng từ khóa cilk_for tại vòng lặp ngoài cùng của giải thuật Brandes để phân tán độc lập các tác vụ duyệt SSSP từ mỗi đỉnh nguồn $s \in V'$ tới các luồng CPU (worker threads).
    • Áp dụng cấu trúc dữ liệu cục bộ (thread-local storage) cho mảng ngăn xếp $S$, hàng đợi $Q$, mảng khoảng cách $\text{dist}[]$, số đường đi ngắn nhất $\sigma[]$, và mảng phụ thuộc $\delta[]$ nhằm loại bỏ hoàn toàn hiện tượng tranh chấp bộ nhớ (race conditions) và khóa chết (deadlock) mà không cần lạm dụng biến khóa luồng (mutex locks).
  4. Xây dựng Cây lan truyền và dự báo kích thước:
    • Trích xuất nhật ký hoạt động người dùng (Activity Logs) để tính tần suất tương tác: $$UI(u, v) = \frac{\text{Interactions}(u \to v)}{\sum_{w \in \Gamma(u)} \text{Interactions}(u \to w)}$$
    • Tính toán độ tương đồng cosine giữa vector chủ đề của nội dung $C$ và hồ sơ sở thích của người dùng $v$: $$Topic(C, v) = \cos(\vec{\theta}_C, \vec{\phi}_v)$$
    • Lượng hóa hệ số lan truyền ngoại sinh $External(t)$ thông qua tần suất xuất hiện của từ khóa sự kiện trên báo chí điện tử và công cụ tìm kiếm tại thời điểm $t$.
    • Xác định cạnh kích hoạt theo điều kiện cực đại và kết nạp nút vào cây lan truyền qua các tầng thời gian rời rạc $t_0, t_1, \dots, t_k$.
┌─────────────────────────────────────────────────────────────────────────────────────────────────┐
│                           BẢNG DỮ LIỆU ĐỐI CHUẨN THỬ NGHIỆM THUẬT TOÁN                          │
├───────────────────┬───────────────────┬───────────────────┬─────────────────────────────────────┤
│ Tập dữ liệu (DS)  │ Số đỉnh (|V|)     │ Số cạnh (|E|)     │ Nguồn / Đặc trưng                   │
├───────────────────┼───────────────────┼───────────────────┼─────────────────────────────────────┤
│ DS1 (Wiki-Vote)   │ 7,115             │ 103,689           │ Mạng bầu chọn Wikipedia (SNAP)      │
│ DS2 (Email-Enron) │ 36,692            │ 367,662           │ Mạng truyền thông email Enron       │
│ DS3 (Slashdot)    │ 82,168            │ 948,464           │ Mạng xã hội công nghệ Slashdot      │
│ DS4 (Twitter)     │ 81,306            │ 1,768,149         │ Mạng tương tác Twitter microblog    │
│ DS5 (Facebook-VN) │ 128,450           │ 2,410,230         │ Dữ liệu thử nghiệm từ Đề tài VAST   │
└───────────────────┴───────────────────┴───────────────────┴─────────────────────────────────────┘

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

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

Các kết quả thực nghiệm của luận án mang lại những phát hiện đột phá có ý nghĩa khoa học và thực tiễn sâu sắc:

HIỆU NĂNG TĂNG TỐC TÍNH TOÁN BC CỦA RED-BET SO VỚI CÁC CÔNG CỤ QUỐC TẾ
(Thời gian tính toán tính bằng Giây trên tập dữ liệu DS4 - Twitter)

  NetworKit (OpenMP)  │ ████████████████████████████████ 1,245s
  TeexGraph (OpenMP)  │ █████████████████████████ 982s
  Red-Bet (Đề xuất)   │ ███████ 286s  [Nhanh hơn 3.43x - 4.35x]
                      └────────────────────────────────────────────────────────► Thời gian (s)
  1. Hiệu năng gia tốc vượt trội của giải thuật Red-Bet: Khi chạy trên hệ thống đa luồng CPU (từ 2 đến 32 luồng), giải thuật Red-Bet đạt hệ số tăng tốc tuyến tính cao (near-linear speedup). Tại tập dữ liệu lớn DS4 và DS5, Red-Bet giảm thời gian tính toán BC từ hàng giờ xuống vài phút. So với bộ công cụ chuẩn quốc tế NetworKit, Red-Bet nhanh hơn từ 3.2 đến 4.35 lần; so với TeexGraph, Red-Bet nhanh hơn từ 2.8 đến 3.43 lần.
  2. Tính bảo toàn cấu trúc sau rút gọn: Thực nghiệm chứng minh việc rút gọn đỉnh bậc 1 giúp giảm từ 12% đến 28% tổng số đỉnh cần duyệt trong đồ thị thực tế mà sai số xếp hạng các nút có BC cao nhất (Top-k Central Nodes) bằng 0% ($p < 0.001$), đảm bảo độ tin cậy tuyệt đối trong việc phát hiện người có tầm ảnh hưởng (influencers) hoặc tâm dịch/điểm nóng tin đồn.
  3. Hiện tượng bùng nổ do tác động ngoại sinh (Exogenous Shock Cascade): Dữ liệu thực nghiệm chứng minh khi xuất hiện các sự kiện xã hội nóng, nếu mô hình chỉ xét quan hệ nội tại và sở thích thì kích thước lan truyền bị đánh giá thấp (underestimated) từ 35% đến 58%. Khi tích hợp tham số $External(t)$, độ chính xác dự báo (đo bằng chỉ số sai số tương đối tuyệt đối trung bình - MAPE và RMSE) của mô hình đề xuất cải thiện vượt trội, giảm sai số dự báo xuống dưới 8.5%.
┌─────────────────────────────────────────────────────────────────────────────────────────────────┐
│                      SO SÁNH ĐỘ CHÍNH XÁC DỰ BÁO KÍCH THƯỚC LAN TRUYỀN                          │
├────────────────────────────────────┬───────────────────────┬────────────────────────────────────┤
│ Phương pháp / Mô hình              │ Sai số MAPE (%)       │ Nhận xét động học                  │
├────────────────────────────────────┼───────────────────────┼────────────────────────────────────┤
│ Mô hình IC chuẩn (Kempe et al.)    │ 42.6%                 │ Đánh giá thấp quy mô bùng phát     │
│ Mô hình TwitterRank (Weng et al.)  │ 31.2%                 │ Chỉ phản ánh tốt chủ đề hẹp        │
│ Mô hình ASIC trễ (Saito et al.)    │ 27.8%                 │ Bỏ qua xung lực truyền thông ngoài │
│ Mô hình Đề xuất (Luận án - 3 Yếu tố)│ 8.3%                 │ Dự báo chính xác đỉnh lan truyền   │
└────────────────────────────────────┴───────────────────────┴────────────────────────────────────┘

Implications đa chiều

  • Về mặt lý thuyết: Chứng minh rằng động học lan truyền trên không gian số là một hệ thống mở (open socio-technical system), chịu sự chi phối liên tục của thế giới thực. Luận án đặt nền tảng cho lý thuyết lan truyền thông tin đa kênh lai ghép (Hybrid Multi-Channel Diffusion Theory).
  • Về mặt phương pháp luận: Mở ra hướng tiếp cận mới trong tính toán đồ thị lớn bằng việc kết hợp xử lý song song mức luồng hệ thống với tiền xử lý cấu trúc topo thông minh, có thể áp dụng cho các độ đo phức tạp khác như Closeness Centrality, PageRank, Coreness (K-core decomposition).
  • Về mặt ứng dụng thực tiễn: Cung cấp lõi thuật toán trực tiếp cho hệ thống giám sát không gian mạng quốc gia, cho phép cơ quan chức năng nhận diện sớm nguồn phát tán tin giả, khoanh vùng đối tượng phát tán độc hại và dự báo tốc độ lây lan của luồng thông tin xấu độc chỉ trong vài giây sau khi xuất hiện.

Limitations và Future Research

Mặc dù đạt được những kết quả đột phá, luận án thẳng thắn thừa nhận các giới hạn học thuật cần tiếp tục hoàn thiện:

  1. Phạm vi lớp đồ thị: Các thuật toán đề xuất mới chỉ tập trung xử lý tối ưu trên lớp đơn đồ thị, hữu hướng, không trọng số. Việc mở rộng sang đồ thị đa quan hệ (multi-relational graphs) hoặc đồ thị có trọng số âm/biến động liên tục theo mili-giây (dynamic streaming graphs) vẫn chưa được tích hợp trọn vẹn.
  2. Giới hạn kiến trúc phần cứng: Giải thuật song song hiện tại được tối ưu hóa trên nền tảng CPU đa lõi (bộ nhớ chia sẻ - CilkPlus). Việc kết hợp kiến trúc lai ghép Heterogeneous CPU-GPU hoặc phân tán trên các cụm máy chủ lớn (Cluster/Cloud MPI) là định hướng mở đầy triển vọng.
  3. Độ trễ của dữ liệu ngoại sinh: Việc thu thập và phân tích sắc thái dữ liệu truyền thông bên ngoài ($External(t)$) còn phụ thuộc vào API của bên thứ ba, có thể gây ra độ trễ nhất định trong việc cập nhật trọng số theo thời gian thực.

Chương trình nghiên cứu tương lai (Agenda 5–10 năm):

  • Phát triển biến thể thuật toán Red-Bet thích ứng trên kiến trúc phần cứng chuyên dụng GPU/TPU với thư viện CUDA/OpenCL.
  • Mở rộng mô hình lan truyền sang mạng xã hội đa lớp (Multilayer/Heterogeneous Information Networks), nơi người dùng đồng thời tương tác trên Facebook, TikTok, YouTube và Telegram.
  • Ứng dụng mô hình hóa học sâu trên đồ thị (Graph Neural Networks - GNNs) kết hợp cơ chế chú ý (Graph Attention Networks - GAT) để tự động học biểu diễn đặc trưng ảnh hưởng ngoại sinh.

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

Công trình luận án của NCS. Dương Ngọc Sơn tạo ra chuỗi giá trị và tác động sâu rộng:

  • Tác động học thuật (Academic Impact): Các kết quả cốt lõi của luận án đã được công bố trên các tạp chí và kỷ yếu hội nghị khoa học uy tín chuyên ngành trong và ngoài nước (gồm 05 công trình [C1]–[C5]), minh chứng cho giá trị học thuật xuất sắc và tính liêm chính khoa học. Mã nguồn của giải thuật được công khai minh bạch trên nền tảng GitHub (bigGraphplus), đóng góp trực tiếp vào kho tài nguyên nghiên cứu mở toàn cầu.
  • Tác động chuyển giao công nghệ và chính sách (Policy & Industrial Influence): Kết quả nghiên cứu đã được thử nghiệm và tích hợp thành công vào đề 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". Đồng thời, sản phẩm nghiên cứu phục vụ trực tiếp cho công tác chuyên môn tại Cục Kỹ thuật nghiệp vụ và 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), cung cấp cơ sở khoa học xác thực để thực thi Luật An ninh mạng và các Nghị định quản lý thông tin trực tuyến của Chính phủ.

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

  • Nghiên cứu sinh & Nhà khoa học máy tính: Tiếp cận giải thuật tối ưu hóa đồ thị song song tiên tiến (Red-Bet) và mã nguồn mở để mở rộng nghiên cứu về khai phá đồ thị lớn.
  • Chuyên gia phân tích dữ liệu & R&D doanh nghiệp số: Sở hữu công cụ dự báo xu hướng thị hiếu khách hàng, lan tỏa thương hiệu (viral marketing) và tối ưu hóa chi phí chiến dịch quảng cáo với độ chính xác cao.
  • Cơ quan quản lý nhà nước & Lực lượng an ninh mạng: Được trang bị hệ thống giám sát, phát hiện sớm điểm nóng dư luận, nhận diện phần tử cốt lõi phát tán thông tin sai sự thật để chủ động triển khai phương án đấu tranh, xử lý, bảo vệ an ninh thông tin quốc gia.

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 độc đáo nhất là việc mở rộng Mô hình Bậc độc lập (IC) của Kempe et al. (2003) sang Mô hình xác suất lan truyền 3 thành tố tích hợp yếu tố ngoại sinh. Luận án đã bác bỏ giả định cô lập của mạng xã hội số, chứng minh toán học và thực nghiệm rằng luồng thông tin ngoài đời thực kích hoạt đột biến xác suất lan truyền nội mạng, tái định hình khung lý thuyết lan truyền thông tin trong ngành Khoa học mạng.

2. Sự đổi mới về mặt phương pháp luận của giải thuật Red-Bet so với các công trình quốc tế?

So với thuật toán Brandes gốc ($O(|V||E|)$) và các công cụ hàng đầu hiện nay như NetworKit hay TeexGraph (vốn chỉ áp dụng OpenMP thuần túy trên đồ thị gốc), Red-Bet tạo đột phá bằng cơ chế 2 giai đoạn (Two-stage Hybrid): Rút gọn topo nút bậc 1 trước khi phân rã đa luồng CilkPlus. Phương pháp này cắt giảm hàng trăm nghìn nhánh tính toán vô ích nhưng bảo toàn 100% kết quả xếp hạng trung tâm của các nút quan trọng.

3. Phát hiện thực nghiệm nào gây bất ngờ nhất trong quá trình nghiên cứu?

Phát hiện bất ngờ nhất là việc rút gọn tới 28% số đỉnh bậc 1 trên các mạng xã hội lớn không hề làm thay đổi giá trị Betweenness Centrality tương đối của các nút chủ chốt. Điều này khẳng định cấu trúc mạng xã hội có tính dư thừa topo rất lớn tại vùng biên và các giải thuật phân tích truyền thống đã lãng phí tài nguyên tính toán khổng lồ vào các nút lá không có vai trò điều phối thông tin.

4. Luận án có cung cấp quy trình tái lập nghiên cứu (Replication Protocol) không?

Có. Luận án cung cấp đầy đủ mã nguồn thuật toán, cấu trúc dữ liệu CSR, các kịch bản thực nghiệm và công khai repository trên GitHub (github.com/sondn89/bigGraphplus), cho phép cộng đồng học thuật toàn cầu tải về, đối chuẩn (benchmark) và tái lập chính xác mọi kết quả thực nghiệm trên các tập dữ liệu SNAP.

5. Lộ trình nghiên cứu 10 năm được phác thảo như thế nào?

Luận án định hình lộ trình nghiên cứu mở rộng trong thập kỷ tới xoay quanh 3 trụ cột: (1) Tính toán đồ thị động quy mô hàng tỷ đỉnh trên kiến trúc lai CPU-GPU/TPU; (2) Tích hợp Mạng nơ-ron đồ thị (GNN) để tự động hóa trích xuất đặc trưng ngoại sinh; (3) Phát triển hệ thống tự hành can thiệp và triệt tiêu luồng tin giả thời gian thực trên mạng xã hội đa nền tảng.

Kết luận

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

  1. Đề xuất kỹ thuật rút gọn đồ thị thông minh dựa trên việc thay thế các đỉnh tương đương bậc 1, giúp thu nhỏ quy mô đồ thị từ 12% đến 28% mà vẫn bảo toàn chính xác cấu trúc nút trung tâm.
  2. Xây dựng giải thuật Red-Bet song song hóa tính toán Betweenness Centrality bằng Intel CilkPlus trên CPU đa lõi, đạt tốc độ vượt trội hơn 3.2 đến 4.35 lần so với NetworKit và 2.8 đến 3.43 lần so với TeexGraph.
  3. Phát triển mô hình xác suất lan truyền 3 tham số toàn diện (Tương tác người dùng - Mức độ quan tâm chủ đề - Ảnh hưởng ngoại sinh), phản ánh chân thực bản chất mở của không gian mạng.
  4. Đề xuất phương pháp xây dựng Cây lan truyền có khả năng nhất, giảm sai số dự báo kích thước lan truyền xuống dưới 8.5% so với dữ liệu thực tế.
  5. Cung cấp giải pháp công nghệ có tính ứng dụng cao, chuyển giao trực tiếp vào hệ thống giám sát an ninh mạng quốc gia và công bố mã nguồn mở cho cộng đồng khoa học quốc tế.

Công trình tạo ra bước tiến quan trọng trong chuyên ngành Hệ thống thông tin, khẳng định năng lực nghiên cứu đỉnh cao của các nhà khoa học Việt Nam trong việc giải quyết các bài toán công nghệ mũi nhọn của thời đại số.