Tổng quan về luận án

Sự bùng nổ của mạng xã hội trực tuyến (MXHTT) với hơn 3 tỷ người dùng trên toàn cầu (chiếm gần một nửa dân số thế giới theo thống kê của Statista) cùng tỷ lệ 63% người dùng tại Mỹ xem Facebook và Twitter là kênh tiếp nhận thông tin chính thức đã tái định hình phương thức giao tiếp và tương tác xã hội. Tuy nhiên, đi kèm với lợi thế lan truyền thông tin theo quy luật mạng không tỉ lệ (scale-free network với phân bố bậc $P(k) = k^{-\gamma}$, $2 < \gamma < 3$) và hiệu ứng thế giới nhỏ (small-world phenomenon với khoảng cách liên kết trung bình nhỏ hơn 6), MXHTT cũng trở thành môi trường phát tán rủi ro với tin giả, tin đồn thất thiệt và mã độc. Điển hình, sự cố thông tin sai lệch về cựu Tổng thống Barack Obama bị thương tại Nhà Trắng năm 2013 đã gây thiệt hại 136,5 tỷ USD cho thị trường chứng khoán Mỹ chỉ trong vài phút.

Trước bối cảnh đó, luận án tiến sĩ chuyên ngành Khoa học máy tính (Mã số: 62480101) do nghiên cứu sinh Phạm Văn Cảnh thực hiện dưới sự hướng dẫn của GS. TS. Thái Trà My và PGS. TS. Hoàng Xuân Huấn đã tập trung giải quyết các bài toán nền tảng và đột phá thuộc nhóm lan truyền thông tin thông qua lăng kính tối ưu tổ hợp.

Khoảng trống nghiên cứu (research gap) cốt lõi được xác định là sự thiếu vắng các mô hình phản ánh chân thực bối cảnh thực tế: đa số các công trình kinh điển của Kempe et al. (2003), Chen et al. (2009, 2010) hay Borgs et al. (2014) chỉ xét sự lan truyền đơn lẻ, chi phí kích hoạt đồng nhất và không giới hạn thời gian thực thi. Luận án đã thiết lập 3 câu hỏi nghiên cứu chính:

  1. RQ1: Làm thế nào để tối đa hóa ảnh hưởng khi có sự cạnh tranh sòng phẳng giữa các thực thể dưới ràng buộc ngân sách không đồng nhất và ngưỡng thời gian hữu hạn $\tau$?
  2. RQ2: Cơ chế nào tối ưu hóa việc loại bỏ tập đỉnh để hạn chế tối đa sự lây lan của thông tin sai lệch từ nguồn xác định dưới trần ngân sách và thời gian can thiệp khắt khe?
  3. RQ3: Làm sao để tìm tập can thiệp có quy mô cực tiểu nhằm bảo vệ một tỷ lệ cá thể mục tiêu $\gamma$ không bị lây nhiễm thông tin xấu?

Hệ thống giả thuyết nghiên cứu bao gồm:

  • H1: Hàm mục tiêu của bài toán lan truyền cạnh tranh có ràng buộc thời gian không thỏa mãn tính chất submodular nhưng có thể bị chặn trên và chặn dưới bởi các hàm submodular.
  • H2: Việc hạn chế thông tin sai lệch có thể quy đổi và xấp xỉ hiệu quả thông qua cấu trúc đồ thị có hướng không chu trình (DAG) và lược đồ xấp xỉ thời gian đa thức đầy đủ (FPTAS).
  • H3: Bài toán ngăn chặn có chủ đích có thể giải quyết chính xác trên mô hình Ngưỡng tuyến tính (LT) và mô hình Bậc độc lập (IC) thông qua kỹ thuật quy hoạch tuyến tính và phân rã cây.

Đóng góp đột phá của luận án nằm ở việc mở rộng khung lý thuyết với các mô hình mới: Mô hình Ngưỡng tuyến tính cạnh tranh ràng buộc thời gian (TCLT), Mô hình Ngưỡng tuyến tính ràng buộc thời gian (TLT), cùng các thuật toán có đảm bảo tỷ lệ xấp xỉ lý thuyết như SPBA (Sandwich based PBA), FPTAS, SG (Accelerated Greedy), STMB-LT và STMB-IC có khả năng thực thi trên các mạng quy mô hàng triệu đỉnh và cạnh.

Literature Review và Positioning

Lý thuyết lan truyền thông tin khởi nguồn từ các mô hình toán dịch tễ học và tiếp thị lan truyền của Domingos & Richardson (2001), sau đó được Kempe et al. (2003) hình thức hóa thành hai mô hình rời rạc kinh điển: Ngưỡng tuyến tính (Linear Threshold - LT) và Bậc độc lập (Independent Cascade - IC). Trong mô hình LT, một đỉnh $u$ bị kích hoạt tại bước $t$ nếu tổng trọng số ảnh hưởng từ các láng giềng kích hoạt vượt qua ngưỡng ngẫu nhiên $\theta_u \in [0, 1]$:

$$\sum_{v \in N_{in}(u) \cap S_{t-1}} w(v, u) \ge \theta_u$$

Trường phái tiếp theo tập trung vào việc vượt qua rào cản độ phức tạp tính toán khi Chen et al. (2009, 2010) chứng minh việc tính toán hàm ảnh hưởng $\sigma(S)$ trên cả LT và IC là bài toán thuộc lớp #P-Khó (được định nghĩa theo lý thuyết của Valiant, 1979). Leskovec et al. (2007) đề xuất kỹ thuật CELF/Lazy Greedy giúp tăng tốc độ thực thi lên tới 700 lần dựa trên tính chất biên giảm dần (diminishing returns). Đột phá tiếp tục diễn ra khi Borgs et al. (2014) giới thiệu kỹ thuật Lấy mẫu ảnh hưởng ngược (Reverse Influence Sampling - RIS) đạt tỷ lệ xấp xỉ $(1 - 1/e - \epsilon)$ trong thời gian $O((m+n)\epsilon^{-3}k\log n)$, được cải tiến vượt bậc bởi Tang et al. qua các thuật toán TIM/TIM++ (2014), IMM (2015) và OPIM (2018), cũng như công trình SSA/D-SSA của Hung T. Nguyen et al. (2016).

                      [LƯỢC ĐỒ TIẾN HÓA LÝ THUYẾT LAN TRUYỀN VÀ TỐI ƯU HÓA]
                      
   Domingos & Richardson (2001)                     Valiant (1979)
   [Tiếp thị lan truyền định lượng]                  [Lý thuyết độ phức tạp #P-Khó]
     [Mô hình LT, IC; Tính chất Submodular;           [Chứng minh hàm σ(S) là #P-Khó;
      Xấp xỉ Greedy (1 - 1/e)]                        Thuật toán LDAG, PMIA]
     Borgs et al. (2014)                              Bharathi et al. (2007) / He et al. (2012)
     [Kỹ thuật RIS đột phá]                           [Lan truyền cạnh tranh: CLT, MCIC]
     Tang et al. (IMM 2015), Nguyen et al. (2016)     Khalil et al. (2014), Yang et al. (2013)
     [Tối ưu hóa chặn mẫu Martingale & Stopping Rule] [Xóa cạnh, tiêm vaccine DAVA không có ràng buộc]
                             LUẬN ÁN PHẠM VĂN CẢNH (2024)
   [Tối đa ảnh hưởng cạnh tranh:  [Hạn chế thông tin sai lệch:  [Ngăn chặn mục tiêu có chủ đích:
    BCIM trên TCLT/DCLT,           MMR trên TLT, thuật toán       TMB trên LT/IC, STMB-LT,
    Thuật toán SPBA]               FPTAS, SG, Heuristic PR-DAG]   STMB-IC qua Quy hoạch tuyến tính]

Về mặt học thuật, tồn tại hai luồng tranh luận đối lập rõ nét:

  1. Luồng giả định cạnh tranh phi đối xứng vs. Cạnh tranh công bằng: Các nghiên cứu cạnh tranh trước đây như He et al. (2012) với mô hình CLT hay Budak et al. (2011) với MCIC luôn giả định thông tin tích cực hoặc một bên ưu thế tuyệt đối sẽ giành chiến thắng khi hai luồng thông tin chạm trán cùng lúc. Ngược lại, luận án định vị rằng trong tiếp thị thương mại (ví dụ: Apple vs. Samsung), người dùng tiếp nhận thông tin theo tỷ lệ phân chia ảnh hưởng công bằng.
  2. Luồng can thiệp toàn cục vs. Can thiệp thực tế: Các phương pháp ngăn chặn của Khalil et al. (2014) hay Yang et al. (2013 với mô hình DAVA) giả định chi phí loại bỏ đỉnh là đồng nhất và không có hạn định thời gian. Luận án tái định vị bằng cách tích hợp cả chi phí tổng quát $c(v)$ và ngưỡng thời gian can thiệp $\tau$.

So sánh với các nghiên cứu quốc tế: Trong khi công trình Cost-aware TVM của Huy Nguyen et al. (2013) và CVTM của Nguyen et al. (2016) chỉ xét bối cảnh đơn nguồn, luận án đã mở rộng thành công sang bài toán cạnh tranh đa nguồn BCIM. Đồng thời, so với bài toán $\tau$-MP của Zhang et al. (2014) vốn chỉ dừng lại ở thuật toán heuristic không có chặn lý thuyết, luận án cung cấp thuật toán FPTAS và xấp xỉ tăng tốc SG với đảm bảo toán học vững chắc.

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

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

Luận án đã tạo ra bước tiến quan trọng khi thách thức và mở rộng các lý thuyết tối ưu hóa tổ hợp kinh điển của Nemhauser et al. (1978) và Kempe et al. (2003):

  • Chứng minh sự phá vỡ tính chất Submodular trong môi trường cạnh tranh có ràng buộc: Luận án chỉ ra rằng khi tích hợp đồng thời ràng buộc thời gian $\tau$ và đối thủ cạnh tranh trên mô hình TCLT, hàm mục tiêu $\sigma(S)$ không còn giữ tính chất đơn điệu tăng và submodular. Đây là phát hiện quan trọng giải thích vì sao thuật toán tham lam truyền thống hoàn toàn thất bại trong bài toán BCIM.
  • Khung xấp xỉ Sandwich kép (Sandwich Approximation Framework): Để vượt qua rào cản phi submodular, luận án kiến tạo hai hàm chặn: hàm xấp xỉ trên $C_U(g, v)$ và hàm xấp xỉ dưới $C_L(g, v)$ thỏa mãn tính chất submodular trên mô hình đồ thị mẫu cạnh trực tuyến (live-edge graph).
  • Hệ thống hóa độ khó tính toán: Thiết lập chứng minh toán học chặt chẽ khẳng định các bài toán BCIM, MMR và TMB đều thuộc lớp NP-Khó thông qua các phép quy dẫn đa thức (polynomial reduction) từ bài toán Ba lô (Knapsack Problem) và bài toán Tập đường đi $s-t$ rời nhau (s-t paths problem).
                      [CƠ CHẾ XẤP XỈ SANDWICH TRONG BÀI TOÁN BCIM]

               [Thuật toán PBA tối ưu hóa đồng thời trên hai chặn]
               [Tỷ lệ xấp xỉ tổng thể thuật toán SPBA: ρ = (1 - 1/e) · α]

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

Khung phân tích của luận án tích hợp liên ngành giữa Lý thuyết Đồ thị ngẫu nhiên, Tối ưu hóa Tổ hợp và Lý thuyết Dịch tễ học tính toán:

  1. Mô hình hóa TCLT (Time-constrained Competitive Linear Threshold): Mở rộng mô hình LT bằng cách gán vector trọng số cạnh $w(u,v)$, ngưỡng kích hoạt động theo thời gian rời rạc $t \in [0, \tau]$, và cơ chế kích hoạt cạnh tranh sòng phẳng khi các tập nguồn xuất phát tại các mốc thời gian khác nhau.
  2. Kỹ thuật rút gọn cấu trúc DAG (Directed Acyclic Graph): Thay vì ước lượng Monte Carlo tốn kém trên toàn bộ không gian ngẫu nhiên, khung phân tích rút gọn đồ thị ban đầu $G$ về cấu trúc DAG cục bộ theo khoảng cách lan truyền $\tau$. Cơ chế này cho phép tính toán chính xác hàm hạn chế thông tin sai lệch trong thời gian tuyến tính với số lượng cạnh của DAG.
  3. Mô hình hóa TMB qua Quy hoạch tuyến tính (Linear Programming Formulation): Chuyển đổi bài toán chặn thông tin có chủ đích dưới mô hình IC thành hệ thống bất phương trình ràng buộc khả năng kết nối $s-t$, cho phép trích xuất tập đỉnh cắt nhỏ nhất thông qua giải pháp đối ngẫu.

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ủ thế giới quan thực chứng (Positivism) và chủ nghĩa hiện thực tính toán (Computational Realism). Phương pháp tiếp cận kết hợp chặt chẽ giữa phân tích suy diễn toán học hình thức (Formal Mathematical Deduction) và phân tích thực nghiệm quy mô lớn (Large-scale Empirical Analysis).

Mẫu dữ liệu thực nghiệm được lựa chọn từ thư viện Stanford Network Analysis Platform (SNAP) bao gồm các đồ thị MXHTT thực tế có quy mô từ hàng chục nghìn đến hàng triệu phần tử:

  • Mạng Oregon (AS-Oregon): 10.670 đỉnh, 22.002 cạnh (đặc trưng cho cấu trúc kết nối mạng).
  • Mạng chia sẻ tệp Gnutella (p2p-Gnutella08/09): từ 6.301 đến 8.114 đỉnh, 20.777 đến 26.013 cạnh.
  • Mạng học thuật DBLP: 317.080 đỉnh, 1.049.866 cạnh.
  • Mạng Youtube: 1.134.890 đỉnh, 2.987.624 cạnh.

Quy trình nghiên cứu rigorous

Quy trình nghiên cứu được chuẩn hóa qua 4 giai đoạn logic khép kín:

[BƯỚC 1: HÌNH THỨC HÓA BÀI TOÁN]
- Thiết lập định nghĩa toán học (G, S, k, B, τ)
- Xây dựng mô hình lan truyền mới (TCLT, TLT)
[BƯỚC 2: PHÂN TÍCH ĐỘ PHỨC TẠP VÀ TÍNH CHẤT]
- Chứng minh NP-Khó / #P-Khó qua Phép dẫn đa thức (Knapsack, s-t paths)
- Đánh giá tính chất Submodular / Supermodular / Phi-submodular
[BƯỚC 3: THIẾT KẾ THUẬT TOÁN VÀ CHỨNG MINH LÝ THUYẾT]
- Xây dựng thuật toán: SPBA, FPTAS, SG, PR-DAG, STMB
- Chứng minh tỷ lệ xấp xỉ ρ, chặn sai số ε, độ phức tạp thời gian/bộ nhớ
[BƯỚC 4: THỰC NGHIỆM ĐỐI CHUẨN VÀ ĐÁNH GIÁ ĐA CHIỀU]
- Kiểm thử trên bộ dữ liệu thực SNAP (Oregon, Gnutella, DBLP, Youtube)
- Đo lường: Chất lượng lời giải (Influence/Blocked nodes), Thời gian thực thi (Runtime),
  Độ nhạy tham số (τ, B, k, θ)

Quy trình đảm bảo tính chân xác (validity) và độ tin cậy (reliability) thông qua:

  • Tam giác đạc lý thuyết (Theoretical Triangulation): Kiểm chứng tính đúng đắn của thuật toán thông qua Bổ đề, Định lý toán học độc lập kết hợp mô phỏng Monte Carlo với số lần lặp $R = 10.000$ để đảm bảo chặn sai số xác suất $\Omega\left(\frac{n^2}{\epsilon^2} \ln \frac{1}{\delta}\right)$ theo tiêu chuẩn Dagum et al. (2000).
  • Phép kiểm định vững (Robustness Checks): Kiểm tra hiệu năng thuật toán dưới hai kịch bản chi phí: (1) Chi phí đồng nhất $c(v) = 1$ và (2) Chi phí tổng quát tỉ lệ với bậc vào/ra của đỉnh $c(v) = \frac{d_{in}(v)}{\sum d_{in}} \times B$.

Data và phân tích

Các công cụ phần mềm và môi trường tính toán: Toàn bộ thuật toán được cài đặt bằng ngôn ngữ C++ (chuẩn C++11/14), biên dịch bằng GCC 7.5.0 tối ưu hóa cờ -O3, thực thi trên hệ thống máy chủ tính toán hiệu năng cao chạy hệ điều hành Linux (Ubuntu Server), CPU Intel Xeon đa nhân xung nhịp 3.2 GHz, 64 GB RAM.

Các kỹ thuật phân tích cốt lõi:

  1. Lược đồ xấp xỉ FPTAS (Fully Polynomial Time Approximation Scheme): Luận án chứng minh rằng trên cấu trúc cây có gốc (rooted tree), bài toán MMR có thể giải quyết đạt nghiệm tối ưu $(1 - \epsilon)\text{OPT}$ trong thời gian đa thức $O\left(\frac{n^3}{\epsilon}\right)$ thông qua kỹ thuật quy hoạch động kết hợp làm tròn không gian trạng thái.
  2. Thuật toán tham lam tăng tốc SG (Accelerated Greedy): Cải tiến việc tính toán độ tăng biên $\Delta_u = f(S \cup {u}) - f(S)$ bằng cách duy trì cây lan truyền ngược, giảm số lần duyệt từ $O(k \cdot n)$ xuống còn một phân số nhỏ của $n$.

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

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

  1. Hiệu năng vượt trội của thuật toán SPBA trong môi trường cạnh tranh: Trên bộ dữ liệu DBLP và Youtube, thuật toán SPBA đạt chất lượng lan truyền ảnh hưởng cao hơn từ 18% đến 35% so với các thuật toán heuristic dựa trên bậc (Degree Discount, High Degree) và thuật toán đường đi cục bộ (LDAG), trong khi bảo đảm tỷ lệ xấp xỉ lý thuyết được chứng minh qua khung Sandwich.
  2. Sự đánh đổi phi tuyến giữa bước thời gian can thiệp $\tau$ và chi phí ngăn chặn: Thực nghiệm trên mô hình TLT chỉ ra rằng khi bước thời gian can thiệp $\tau$ tăng từ 2 lên 5, hiệu quả ngăn chặn của cùng một mức ngân sách $B$ bị suy giảm tới 62%. Điều này cung cấp bằng chứng định lượng khẳng định "thời điểm vàng" để dập tắt tin giả là ngay tại các bước lan truyền đầu tiên ($t \le 2$).
  3. Tính ưu việt về thời gian của Heuristic PR-DAG: Thuật toán PR-DAG giảm thời gian tính toán từ hàng giờ của thuật toán tham lam truyền thống xuống còn vài giây trên mạng Oregon và Gnutella, với độ suy giảm chất lượng lời giải không đáng kể (chênh lệch $< 4.5%$ so với cận tối ưu).
  4. Phát hiện nghịch lý về vai trò của đỉnh bậc cao (Hub nodes): Trong bài toán TMB, việc loại bỏ các đỉnh có bậc cao nhất (Degree Centrality) không mang lại hiệu quả chặn tối ưu bằng việc loại bỏ các đỉnh nằm trên các "nút thắt cổ chai" (cut-nodes) được phát hiện bởi thuật toán STMB-IC qua giải pháp đối ngẫu quy hoạch tuyến tính.
+---------------------------------------------------------------------------------------+
|              BẢNG TỔNG HỢP SO SÁNH HIỆU NĂNG CÁC NHÓM THUẬT TOÁN ĐỀ XUẤT             |
+-------------------+-----------------+-----------------------+-------------------------+
| Thuật toán        | Không gian bài  | Đảm bảo lý thuyết     | Thời gian thực thi      |
|                   | toán            | (Approximation Ratio) | (Quy mô mạng lớn)       |
+-------------------+-----------------+-----------------------+-------------------------+
| SPBA              | BCIM            | Có bảo đảm            | Nhanh (vài phút trên    |
|                   | (Cạnh tranh)    | (Sandwich bounds)     | DBLP/Youtube)           |
+-------------------+-----------------+-----------------------+-------------------------+
| FPTAS             | MMR             | (1 - ε)·OPT           | Đa thức trên cây        |
|                   | (Cây có gốc)    |                       |                         |
+-------------------+-----------------+-----------------------+-------------------------+
| SG                | MMR             | (1 - 1/e)             | Trung bình              |
|                   | (Tổng quát)     |                       | (Có tăng tốc biên)      |
+-------------------+-----------------+-----------------------+-------------------------+
| PR-DAG            | MMR             | Heuristic             | Cực nhanh               |
|                   | (Mạng lớn)      | (Không bảo đảm)       | (Vài giây)              |
+-------------------+-----------------+-----------------------+-------------------------+
| STMB-LT / STMB-IC | TMB             | Tối ưu hóa            | Tuyến tính theo         |
|                   | (Mục tiêu γ)    | Quy hoạch tuyến tính  | kích thước DAG/Cây      |
+-------------------+-----------------+-----------------------+-------------------------+

Implications đa chiều

  • Về mặt học thuật và lý thuyết: Mở rộng lý thuyết tối ưu hóa tổ hợp sang lớp các hàm phi-submodular có ràng buộc thời gian; đặt nền móng phương pháp luận cho việc phân tích các tiến trình động học cạnh tranh trên mạng phức hợp.
  • Về mặt kỹ thuật và thuật toán: Cung cấp bộ công cụ thuật toán hoàn chỉnh với mã nguồn mở có khả năng mở rộng (scalability), áp dụng trực tiếp cho các hệ thống giám sát đồ thị tri thức quy mô cực lớn.
  • Về mặt ứng dụng thực tiễn doanh nghiệp: Cung cấp chiến lược tối ưu hóa ngân sách tiếp thị số (digital marketing) trong bối cảnh thị trường có đối thủ cạnh tranh gay gắt, giúp doanh nghiệp phân bổ ngân sách hạt giống đạt hiệu quả ROI cao nhất.
  • Về mặt chính sách an ninh thông tin: Cung cấp cơ chế khoa học cho các cơ quan quản lý nhà nước và ban quản trị nền tảng MXHTT trong việc chủ động thiết lập kịch bản cách ly các nguồn phát tán tin giả, tin đồn nguy hại trước khi lan truyền qua ngưỡng kiểm soát.

Limitations và Future Research

Luận án thẳng thắn thừa nhận các giới hạn nghiên cứu:

  1. Giới hạn về cấu trúc mạng tĩnh: Các mô hình đề xuất chủ yếu giả định đồ thị mạng $G=(V, E)$ là cố định trong suốt quá trình lan truyền, chưa phản ánh đầy đủ tính chất biến đổi động liên tục (time-varying/temporal networks) của các kết nối xã hội.
  2. Giả định thông tin hoàn hảo về đối thủ và nguồn tin: Các bài toán BCIM và MMR yêu cầu phải biết trước tập hạt giống đối thủ hoặc tập nguồn phát tán $S$, điều này không phải lúc nào cũng khả thi trong các tình huống an ninh thực tế.
  3. Mô hình hóa trọng số đồng nhất theo ngữ cảnh: Trọng số ảnh hưởng $w(u, v)$ và xác suất $p(u, v)$ hiện được gán tĩnh dựa trên cấu trúc đồ thị, chưa tích hợp được nội dung ngữ nghĩa (semantic content) và phân tích cảm xúc (sentiment analysis) của bài đăng.

Chương trình nghiên cứu 10 năm tiếp theo tập trung vào:

  • Mở rộng các bài toán BCIM và MMR trên mô hình mạng xã hội động đa lớp (Multi-layer Dynamic Social Networks).
  • Tích hợp học máy tăng cường (Reinforcement Learning) và Đồ thị mạng nơ-ron (Graph Neural Networks - GNN) để dự đoán cấu trúc liên kết và tối ưu hóa tập can thiệp trong điều kiện thông tin không đầy đủ (incomplete information).
  • Nghiên cứu bài toán lan truyền thông tin kết hợp giữa không gian mạng và không gian địa lý thực (Location-aware Temporal Diffusion).

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

Các kết quả nghiên cứu của luận án đã được công bố trên các diễn đàn khoa học quốc tế uy tín, bao gồm 03 bài báo trên các tạp chí quốc tế thuộc danh mục SCIE (Journal of Combinatorial Optimization, Applied Sciences) và 04 bài báo trên kỷ yếu các hội nghị quốc tế chuyên ngành thuộc danh mục Scopus (CSoNet, RIVF, SoICT, ACIIDS).

Ước tính tiềm năng trích dẫn của các công trình này là rất lớn do đánh đúng vào trọng tâm của hai vấn đề nóng hổi trong khoa học máy tính: Tối ưu hóa lan truyền cạnh tranh và Kiểm soát tin giả. Về mặt kinh tế - xã hội, ứng dụng thuật toán của luận án có tiềm năng giúp các doanh nghiệp tiết kiệm từ 20% đến 40% chi phí tiếp thị số, đồng thời cung cấp giải pháp kỹ thuật giảm thiểu thiệt hại hàng tỷ USD do các chiến dịch thông tin sai lệch gây ra cho nền kinh tế số.

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

  • Nghiên cứu sinh và Giới nghiên cứu học thuật: Tiếp cận khung lý thuyết xấp xỉ Sandwich kép, các phép dẫn chứng minh NP-Khó và kỹ thuật phân tích hàm phi-submodular trên đồ thị ngẫu nhiên.
  • Kỹ sư R&D và Kiến trúc sư hệ thống tại các tập đoàn công nghệ: Trực tiếp sử dụng các thuật toán hiệu năng cao (SPBA, PR-DAG, STMB) để tích hợp vào các hệ thống khuyến nghị, phân tích xu hướng và quản trị rủi ro mạng xã hội.
  • Các nhà hoạch định chính sách và Quản trị an ninh mạng: Nhận được cơ sở khoa học định lượng vững chắc để xây dựng các quy trình phản ứng nhanh dập tắt thông tin xấu độc và tin đồn thất thiệt trên không gian mạng 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? Đó là việc giải quyết thành công bài toán Tối đa ảnh hưởng cạnh tranh có ràng buộc thời gian (BCIM) - một bài toán có hàm mục tiêu phi-submodular. Luận án đã mở rộng lý thuyết tối ưu hóa Submodular của Nemhauser (1978) và Kempe (2003) thông qua việc phát triển kỹ thuật Xấp xỉ Sandwich kép (SPBA), chặn hàm mục tiêu phức tạp bằng hai hàm submodular để khôi phục đảm bảo xấp xỉ toán học vững chắc.

2. Điểm đổi mới phương pháp luận khi so sánh với các nghiên cứu tiền nhiệm? So với nghiên cứu IBM của He et al. (2012) (giả định tin tích cực luôn thắng) và DAVA của Yang et al. (2013) (chỉ dùng heuristic không có ràng buộc thời gian/chi phí), luận án đã: (1) Mô hình hóa sự cạnh tranh sòng phẳng không thiên vị; (2) Tích hợp đồng thời hai biến số thực tế là chi phí tổng quát $c(v)$ và ngưỡng thời gian $\tau$; (3) Cung cấp thuật toán FPTAS với bảo đảm sai số $\epsilon$ trên cây và heuristic PR-DAG đạt tốc độ thực thi trong vài giây trên mạng triệu đỉnh.

3. Phát hiện thực nghiệm nào gây bất ngờ nhất và bằng chứng dữ liệu đi kèm? Phát hiện về "ngưỡng sụp đổ hiệu quả" theo thời gian can thiệp: Hiệu quả ngăn chặn thông tin sai lệch giảm phi tuyến tính tới 62% khi độ trễ can thiệp tăng từ $\tau = 2$ lên $\tau = 5$. Điều này chứng minh rằng việc tăng ngân sách $B$ ở các giai đoạn sau hoàn toàn không thể bù đắp được sự chậm trễ trong thời gian can thiệp ban đầu.

4. Luận án có cung cấp quy trình tái lập thực nghiệm (Replication Protocol) không? Có. Toàn bộ tham số thực nghiệm (phân bố ngưỡng $\theta_u \sim U[0,1]$, trọng số chuẩn hóa $\sum w(u,v) \le 1$, số lần mô phỏng Monte Carlo $R = 10.000$, phân bố chi phí $c(v)$), cùng các bộ dữ liệu chuẩn công khai từ SNAP (Oregon, Gnutella, DBLP, Youtube) đều được mô tả chi tiết, rõ ràng, cho phép cộng đồng học thuật tái lập chính xác kết quả.

5. Lộ trình nghiên cứu 10 năm tiếp theo được định hình ra sao? Lộ trình hướng tới việc hợp nhất mô hình tối ưu hóa tổ hợp với Học sâu trên đồ thị (Graph Deep Learning) và Lý thuyết Trò chơi động (Dynamic Game Theory) nhằm giải quyết bài toán kiểm soát thông tin trên các mạng xã hội động đa lớp biến đổi theo thời gian thực dưới điều kiện đối thủ có khả năng thích ứng (adaptive adversaries).

Kết luận

Luận án tiến sĩ của NCS. Phạm Văn Cảnh đã hoàn thành xuất sắc các mục tiêu nghiên cứu với những đóng góp cốt lõi:

  1. Thiết lập và hình thức hóa toán học 3 bài toán tối ưu mới: BCIM (Tối đa ảnh hưởng cạnh tranh có ngân sách và thời gian), MMR (Hạn chế tối đa thông tin sai lệch có ngân sách và thời gian) và TMB (Ngăn chặn thông tin sai lệch có chủ đích).
  2. Chứng minh tường minh tính chất tính toán: Khẳng định độ phức tạp NP-Khó của các bài toán và chỉ ra sự phá vỡ tính chất submodular trong điều kiện cạnh tranh ràng buộc thời gian.
  3. Đề xuất hệ thống thuật toán tiên tiến với bảo đảm toán học: Bao gồm thuật toán xấp xỉ SPBA, lược đồ FPTAS, thuật toán tham lam tăng tốc SG, heuristic PR-DAG và thuật toán quy hoạch tuyến tính STMB-IC/STMB-LT.
  4. Kiểm chứng thực nghiệm quy mô lớn: Chứng minh tính khả thi, độ chính xác và khả năng mở rộng vượt trội của các thuật toán trên các mạng xã hội thực tế quy mô hàng triệu đỉnh và cạnh.
  5. Mở ra 3 hướng nghiên cứu mới: Tối ưu hóa lan truyền trên mạng động đa tầng, tích hợp AI dẫn dắt dữ liệu trong tối ưu hóa tổ hợp, và kiểm soát an ninh thông tin mạng dựa trên lý thuyết trò chơi.