Luận án Tiến sĩ: Cực đại ảnh hưởng mạng xã hội với ưu tiên, chi phí - Vũ Chí Quang

Tổng quan về luận án

Sự bùng nổ của mạng xã hội (Social Networks - SN) với quy mô hàng tỷ người dùng đã biến không gian số thành kênh truyền thông chủ đạo, thay đổi căn bản cơ chế tiếp nhận và phát tán tri thức, thông tin sản phẩm và quan điểm xã hội. Trong khoa học dữ liệu và tối ưu tổ hợp, bài toán Cực đại ảnh hưởng (Influence Maximization - IM) đóng vai trò trung tâm nhằm tìm kiếm một tập nút nguồn (seed set) $S$ có quy mô $k$ nhằm tối đa hóa mức độ lan truyền thông tin $\sigma(S)$ trên toàn mạng. Tuy nhiên, phần lớn các nghiên cứu kinh điển giả định môi trường truyền tin đồng nhất và không có ràng buộc phân đoạn, bỏ qua hai yêu cầu thực tế bức thiết: kiểm soát mức độ tác động tối thiểu lên một nhóm người dùng ưu tiên cụ thể và quản lý chi phí kích hoạt khi thông tin bao gồm nhiều chủ đề khác nhau.

Luận án tiến sĩ chuyên ngành Hệ thống thông tin (Mã số: 9 48 01 04) của nghiên cứu sinh Vũ Chí Quang (2024) 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 của TS. Nguyễn Như Sơn và PGS.TS. Ngô Quốc Dũng, đã giải quyết triệt để khoảng trống nghiên cứu này thông qua đề tài: "Nghiên cứu một số phương pháp giải bài toán cực đại ảnh hưởng trên mạng xã hội với ràng buộc ưu tiên và chi phí". Luận án thiết lập hai bài toán cốt lõi:

1. Bài toán Cực đại ảnh hưởng với ràng buộc ưu tiên (IMP - Influence Maximization with Priority): Đặt mục tiêu "chọn tập nguồn $S$ có $k$ nút có thể ảnh hưởng của tập hợp ưu tiên nhất định $U$ lớn hơn ngưỡng $T$ nhằm điều chỉnh ảnh hưởng của tập nguồn đến tập ưu tiên" trong khi tối đa hóa tổng mức độ lan truyền trên toàn bộ mạng $G=(V, E)$.
2. Bài toán Cực đại ảnh hưởng lan truyền thông tin nhiều chủ đề với chi phí giới hạn (BkIM - Budgeted $k$-Influence Maximization): Giải quyết sự phân bổ nguồn lực dưới giới hạn ngân sách $B$ khi mỗi người dùng liên kết với nhiều chủ đề quan tâm và việc chọn nút kích hoạt cho từng chủ đề phát sinh chi phí riêng biệt.

Luận án tích hợp lý thuyết đồ thị ngẫu nhiên, lý thuyết tối ưu tổ hợp Submodular và thuật toán luồng dữ liệu (Streaming Algorithms), giải quyết đồng thời rào cản tính toán thuộc lớp NP-Khó và bài toán tính hàm mục tiêu thuộc lớp #P-Khó. Với quy mô thực nghiệm trên các tập dữ liệu mạng xã hội thực tế lên tới hơn 430.000 nút và 1,05 triệu cạnh (như netHEPT, ENRON, netPHY, DBLP, RETWEET), nghiên cứu mang lại bước tiến đột phá về mặt lý thuyết thuật toán và giá trị ứng dụng thực tiễn cho tiếp thị lan truyền, an ninh mạng và điều hướng dư luận xã hội.

Literature Review và Positioning

Khởi nguồn từ nghiên cứu tiếp thị lan truyền của Domingos & Richardson (2001), Kempe, Kleinberg & Tardos (2003) đã chính thức tiên phong mô hình hóa bài toán IM dưới dạng tối ưu hóa tổ hợp rời rạc trên hai mô hình lan truyền nền tảng: Mô hình Bậc độc lập (Independent Cascade - IC) và Mô hình Ngưỡng tuyến tính (Linear Threshold - LT). Kempe et al. (2003) chứng minh rằng hàm ảnh hưởng $\sigma(S)$ trên cả hai mô hình đều có tính chất đơn điệu (monotonicity) và hàm Submodular (thuộc tính lợi ích biên giảm dần), từ đó đảm bảo rằng thuật toán tham lam cổ điển đạt tỷ lệ xấp xỉ $(1 - 1/e)$. Tuy nhiên, Chen, Wang & Yang (2010) đã chỉ ra rằng việc tính toán chính xác hàm ảnh hưởng $\sigma(S)$ là bài toán thuộc lớp #P-Khó, biến việc ước lượng chính xác độ lan truyền thành thách thức điện toán quy mô lớn.

Trong y văn quốc tế, nhiều nhánh nghiên cứu mở rộng đã phát triển nhằm giải quyết các biến thể của IM:

• Mở rộng theo ràng buộc không gian và ngân sách: Các công trình của Tang, Xiao & Shi (2014) với thuật toán TIM/IMM dựa trên kỹ thuật lấy mẫu tập ảnh hưởng ngược (Reverse Reachable - RR sketch) của Borgs et al. (2014) đã giảm độ phức tạp thời gian tính toán nhưng chưa hỗ trợ ràng buộc phân đoạn đối tượng ưu tiên.
• Tranh luận về mô hình hóa đa chủ đề và xử lý luồng: Một trường phái học thuật tập trung vào thuật toán ngoại tuyến tĩnh (như Tang et al., 2014), trong khi trường phái đối nghịch đại diện bởi Badanidiyuru et al. (2014) và Mirzasoleiman et al. (2015) ủng hộ việc xử lý luồng (streaming) một lượt do giới hạn bộ nhớ trước dữ liệu mạng quy mô hàng triệu đỉnh. Tuy nhiên, các mô hình luồng trước đây chưa hỗ trợ cấu trúc lan truyền $k$ chủ đề có chi phí kích hoạt phi đối xứng.
• So sánh với các nghiên cứu trong nước: Nghiên cứu của Phạm Văn Cảnh (2020) đã phát triển các thuật toán xấp xỉ cho bài toán ngăn chặn thông tin sai lệch có giới hạn ngân sách (MMR, BCIM) và phát hiện thông tin sai lệch tổng quát (GMD với thuật toán SBMD đạt xấp xỉ $1 - 1/e - \epsilon$).

Luận án của Vũ Chí Quang định vị tại giao điểm then chốt: phá vỡ giới hạn của thuật toán tham lam truyền thống khi gặp ràng buộc tập ưu tiên $U$ (vốn làm mất cấu trúc Submodular đơn thuần trên không gian nghiệm hợp lệ) và mở rộng kỹ thuật luồng một lượt cho bài toán tối ưu hàm Submodular/Non-submodular dưới ràng buộc chi phí $k$ chủ đề, vượt trội hơn các khung phân tích quốc tế hiện hành về cả độ phức tạp bộ nhớ và thời gian truy vấn.

Đó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 nền tảng lý thuyết tối ưu hóa Submodular của Nemhauser, Wolsey & Fisher (1978) và Kempe et al. (2003) sang các không gian ràng buộc phi cấu trúc phức tạp:

1. Lý thuyết tối ưu hóa dưới ràng buộc hai tiêu chí (Bi-criteria Optimization): Luận án chứng minh rằng dù bài toán IMP bị ràng buộc bởi ngưỡng kích hoạt $T$ trên tập $U$, việc kết hợp khéo léo hàm ảnh hưởng cục bộ $\sigma_U(S)$ và hàm ảnh hưởng toàn cục $\sigma(S)$ thông qua kỹ thuật tham lam tích hợp (Integrated Greedy) vẫn cho phép khôi phục cận dưới lý thuyết có thể chứng minh được với tỷ lệ xấp xỉ $(1 - 1/e)(1 - \epsilon)$.
2. Mở rộng lý thuyết lấy mẫu đồ thị ngẫu nhiên (Randomized Sampling Theory): Định nghĩa và xây dựng cấu trúc toán học của tập mẫu ảnh hưởng ngược có mục tiêu (Targeted Reverse Reachable - TRR), chứng minh kỳ vọng của biến ngẫu nhiên sinh ra từ tập TRR và RR hội tụ chính xác về độ lan truyền $\sigma_U(S)$ và $\sigma(S)$ theo bất đẳng thức nồng độ Martingale và Chernoff bounds.
3. Lý thuyết xấp xỉ luồng cho hàm đơn điệu và không đơn điệu (Streaming Approximation Theory): Luận án mở rộng biên độ lý thuyết của lớp bài toán tối ưu hóa tổ hợp trên dòng dữ liệu một lượt (one-pass streaming), cung cấp nghiệm xấp xỉ tất định và ngẫu nhiên có bảo đảm toán học vững chắc cho cả hai trường hợp hàm mục tiêu $f$ đơn điệu và phi đơn điệu.

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 ba trụ cột lý thuyết: Mô hình lan truyền đồ thị ngẫu nhiên (IC, LT, Live-Edge), Lý thuyết độ phức tạp tính toán (Computational Complexity Theory với các lớp P, NP, NP-Hard, #P-Hard), và Cấu trúc thuật toán luồng trực tuyến (Online Streaming Framework).

                                    ┌────────────────────────────────────────────────────────┐
                                    │               KHUNG PHÂN TÍCH LUẬN ÁN                   │
                                    └──────────────────────────┬─────────────────────────────┘
                                                               │
                       ┌───────────────────────────────────────┴───────────────────────────────────────┐
                       ▼                                                                               ▼
     ┌───────────────────────────────────┐                                           ┌───────────────────────────────────┐
     │      BÀI TOÁN 1: IMP (Priority)   │                                           │       BÀI TOÁN 2: BkIM (Budget)   │
     ├───────────────────────────────────┤                                           ├───────────────────────────────────┤
     │ • Mô hình: IC & Cạnh trực tuyến   │                                           │ • Mô hình: Lan truyền k chủ đề    │
     │ • Ràng buộc: σ_U(S) ≥ T, |S| = k  │                                           │ • Ràng buộc: Chi phí ngân sách B  │
     │ • Thuật toán: IG & IGS            │                                           │ • Thuật toán: Luồng một lượt      │
     │ • Kỹ thuật: Tập mẫu TRR & RR      │                                           │ • Đảm bảo: Tất định & Ngẫu nhiên  │
     └─────────────────┬─────────────────┘                                           └─────────────────┬─────────────────┘
                       │                                                                               │
                       └───────────────────────────────────────┬───────────────────────────────────────┘
                                                               │
                                                               ▼
                                    ┌────────────────────────────────────────────────────────┐
                                    │    ĐÁNH GIÁ THỰC NGHIỆM TRÊN DỮ LIỆU MẠNG THỰC TẾ       │
                                    │  (netHEPT, ENRON, netPHY, DBLP, RETWEET: N tới 430k)   │
                                    └────────────────────────────────────────────────────────┘

Khung phân tích thiết lập rõ điều kiện biên (Boundary Conditions): mạng xã hội được biểu diễn bằng đồ thị có hướng $G=(V,E)$ với các tham số xác suất kích hoạt cạnh $p(u,v) \in [0, 1]$ hoặc trọng số ngưỡng $w(u,v)$, tập ưu tiên $U \subseteq V$ với kích thước xác định, và vector ngân sách đa chiều cho $k$ chủ đề không chồng lấn. Phương pháp tiếp cận bảo toàn tính độc lập của các tiến trình lan truyền rời rạc theo thời gian thực.

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

Thiết kế nghiên cứu

Nghiên cứu được định vị vững chắc trên hệ hình chủ nghĩa thực chứng tính toán (Computational Positivism) kết hợp với chủ nghĩa duy lý thuật toán (Algorithmic Rationalism). Luận án áp dụng thiết kế nghiên cứu đa tầng kết hợp chặt chẽ giữa suy diễn toán học hình thức (Formal Mathematical Deduction) và kiểm chứng thực nghiệm quy mô lớn (Empirical Benchmarking).

Thiết kế nghiên cứu đa tầng bao gồm:

• Tầng 1 - Mô hình hóa toán học: Biểu diễn mạng xã hội dưới dạng đồ thị có hướng $G=(V, E)$, chuyển đổi tương đương giữa mô hình lan truyền Bậc độc lập (IC), Ngưỡng tuyến tính (LT) sang mô hình Cạnh trực tuyến (Live Edge - LE) theo Định nghĩa tương đương ngẫu nhiên của Kempe et al. (2003) và Chen et al. (2010): $$\Pr(g \sim G) = \prod_{e \in E(g)} p(e) \prod_{e \in E \setminus E(g)} (1 - p(e))$$
• Tầng 2 - Thiết kế thuật toán: Xây dựng cấu trúc dữ liệu tiên tiến dựa trên tập mẫu ảnh hưởng ngược (RR) và tập mẫu ảnh hưởng ngược có mục tiêu (TRR) để tính toán cận trên $F_u(S, \mathcal{R}, \delta)$ và cận dưới $L_u(S, \mathcal{R}, \delta)$ của hàm mục tiêu mà không cần duyệt toàn bộ không gian trạng thái.
• Tầng 3 - Tối ưu hóa luồng dữ liệu: Thiết kế cơ chế cửa sổ trượt và lưu trữ bộ nhớ bán kính cho phép tiếp nhận dòng phần tử theo thời gian thực, phục vụ tính toán một lượt (one-pass).

Quy trình nghiên cứu rigorous

Quy trình nghiên cứu tuân thủ các bước nghiêm ngặt, đảm bảo tính tái lập (Replicability) và độ tin cậy tuyệt đối:

1. Thiết lập giao thức lấy mẫu (Sampling Protocols): Sinh tập mẫu đồ thị $g \sim G$. Thay vì mô phỏng Monte Carlo cổ điển đòi hỏi số lần lặp lớn $\Omega(\frac{n^2}{\epsilon^2} \log \frac{1}{\delta})$ gây tắc nghẽn bộ nhớ, luận án sinh tập $\mathcal{R}_1$ (các mẫu RR cho toàn mạng) và $\mathcal{R}_2$ (các mẫu TRR cho tập ưu tiên $U$).
2. Chứng minh Bổ đề và Định lý (Theoretical Guarantees):
   • Đối với thuật toán Tham lam tích hợp (Integrated Greedy - IG), chứng minh tỷ lệ nghiệm đạt $(1 - 1/e)(1 - \epsilon)$.
   • Đối với thuật toán Lấy mẫu dựa trên tham lam tích hợp (IGS), chứng minh thuật toán trả về nghiệm gần đúng $(1 - 1/e - \epsilon)$ với xác suất thành công ít nhất $1 - \delta$, trong đó $\epsilon > 0$ và $\delta \in (0, 1)$ là các tham số sai số kiểm soát được.
3. Triangulation (Tam giác hóa phương pháp): Đối soát kết quả giữa phân tích tiệm cận lý thuyết (Asymptotic Analysis), mô phỏng thống kê Monte Carlo và kiểm chứng thực thi thực tế trên đa cấu hình phần cứng.

┌─────────────────────────┐     ┌─────────────────────────┐     ┌─────────────────────────┐
│     Mạng Đồ Thị G       │ ──> │    Sinh Mẫu TRR & RR    │ ──> │   Thuật Toán IG / IGS   │
│   (V, E, p, U, T, k)    │     │      (R_1 và R_2)       │     │ (Đảm bảo: 1 - 1/e - ε)  │
└─────────────────────────┘     └─────────────────────────┘     └────────────┬────────────┘
                                                                             │
                                                                             ▼
┌─────────────────────────┐     ┌─────────────────────────┐     ┌─────────────────────────┐
│  Kết Quả Thực Nghiệm    │ <── │  Đo Lường: σ(S), σ_U(S) │ <── │  Kiểm Chứng Benchmarks  │
│ (Time, Memory, Spread)  │     │   Thời Gian & Bộ Nhớ    │     │  (So sánh đối chuẩn)    │
└─────────────────────────┘     └─────────────────────────┘     └─────────────────────────┘

Data và phân tích

Thực nghiệm được triển khai trên 05 bộ dữ liệu mạng xã hội chuẩn quốc tế với các đặc trưng cấu trúc đa dạng:

• netHEPT: Mạng đồng tác giả học thuật trong lĩnh vực vật lý năng lượng cao ($n = 15.233$ nút, $m = 62.242$ cạnh).
• ENRON: Mạng lưới liên lạc email doanh nghiệp ($n = 36.692$ nút, $m = 367.662$ cạnh).
• netPHY: Mạng lưới cộng tác vật lý toàn diện ($n = 37.154$ nút, $m = 231.584$ cạnh).
• DBLP: Mạng đồ thị khoa học máy tính quy mô lớn ($n = 317.080$ nút, $m = 1.049.866$ cạnh).
• RETWEET: Mạng xã hội truyền thông Twitter về chia sẻ thông điệp ($n = 430.000$ nút).

Thiết lập tham số thực nghiệm: kích thước tập hạt giống $k \in [100, 500]$, kích thước tập ưu tiên $|U| \in [200, 1000]$, ngưỡng kích hoạt ưu tiên $T \in [100, 500]$, tham số dung sai $\epsilon \in (0, 0.2)$, xác suất thất bại $\delta = 1/n$. Môi trường tính toán được lập trình bằng C++/Python, đo đếm chính xác số lời gọi hàm mục tiêu (oracle queries), thời gian chạy (seconds) và mức tiêu thụ bộ nhớ RAM (MB).

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

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

Kết quả phân tích định lượng và đánh giá thực nghiệm từ luận án đem lại 4 phát hiện đột phá:

1. Hiệu năng vượt trội của thuật toán IGS: Trên tất cả các bộ dữ liệu (netHEPT, ENRON, netPHY, DBLP, RETWEET), thuật toán IGS luôn đáp ứng nghiêm ngặt điều kiện ràng buộc ưu tiên $\sigma_U(S) \ge T$ ngay cả khi $T$ tăng từ 100 lên 500, đồng thời tối ưu hóa tổng ảnh hưởng toàn mạng $\sigma(S)$ vượt trội hơn hẳn so với các thuật toán heuristic đối chuẩn.

2. Cận dưới lý thuyết của thuật toán luồng tất định cho BkIM (Trường hợp đặc biệt $\beta = 1$): Luận án thiết lập và chứng minh chính xác: "Thuật toán luồng tất định duyệt dữ liệu 1 lần, có độ phức tạp truy vấn là $O(\frac{k}{\epsilon^2} \log n)$, độ phức tạp không gian là $O(\frac{k}{\epsilon} \log n)$ và trả về một tỷ lệ gần đúng là $\frac{1}{4} - \epsilon$ khi $f$ là đơn điệu và $\frac{1}{5} - \epsilon$ khi $f$ không đơn điệu đối với bất kỳ tham số đầu vào nào $\epsilon \in (0, \frac{1}{5})$".

3. Cận dưới lý thuyết của thuật toán luồng ngẫu nhiên cho BkIM (Trường hợp tổng quát): Đối với bài toán $k$ chủ đề chi phí tổng quát, luận án đề xuất thuật toán luồng ngẫu nhiên với: "độ phức tạp truy vấn là $O(\frac{k}{\epsilon^2} \log n)$, độ phức tạp không gian là $O(\frac{k}{\epsilon} \log n)$ và trả về một tỷ lệ gần đúng là $\min {\frac{\alpha}{2}, \frac{1-\alpha}{1+\beta}} - \epsilon$ khi $f$ là đơn điệu và $\min {\frac{\alpha}{2}, \frac{1-\alpha}{1+2\beta}} - \epsilon$ khi $f$ không đơn điệu, ở đây $\beta = \max_{u \in V, i, j \in K, i \neq j} \frac{c_i(u)}{c_j(u)}$ và $\alpha \in (0, 1)$ là tham số đầu vào".

4. Tối ưu hóa tài nguyên tính toán: Thuật toán luồng của luận án giảm số lời gọi hàm mục tiêu theo hàm đa thức logarit $O(\frac{k}{\epsilon^2} \log n)$, cho phép xử lý đồ thị hàng trăm nghìn nút trong vài chục giây, loại bỏ hoàn toàn hiện tượng tràn bộ nhớ (Out-Of-Memory) vốn phổ biến ở các giải thuật tham lam tĩnh.

Implications đa chiều

• Về mặt lý thuyết: Thiết lập mô hình chuẩn mực giải quyết bài toán tối ưu hóa đa tiêu chí trên mạng phức tạp, giải quyết mâu thuẫn giữa tối ưu hóa cục bộ (tập $U$) và cực đại hóa toàn cục ($V$).
• Về phương pháp luận: Mở ra phương pháp tiếp cận mới trong thiết kế thuật toán luồng một lượt cho các bài toán tối ưu Submodular có ràng buộc chi phí phi tuyến tính.
• Về ứng dụng thực tiễn:
  • Truyền thông và Marketing số: Cho phép doanh nghiệp phân bổ ngân sách tối ưu cho từng nhóm sản phẩm cụ thể, đảm bảo chiến dịch tiếp thị tiếp cận đúng tệp khách hàng trọng tâm (tập $U$) trước khi lan tỏa ra cộng đồng.
  • An ninh mạng và kiểm soát thông tin: Cung cấp công cụ chủ động phát tán thông tin tích cực, định hướng nhận thức cộng đồng hoặc cô lập nguồn phát tán mã độc, tin giả (Misinformation) theo các chủ đề nhạy cảm với chi phí thấp nhất.

Limitations và Future Research

Mặc dù đạt được những đột phá căn bản, luận án ghi nhận một số giới hạn nghiên cứu cần tiếp tục hoàn thiện:

1. Giả định tính tĩnh của cấu trúc mạng: Các mô hình thuật toán chủ yếu được tối ưu trên đồ thị tĩnh tại các thời điểm lấy mẫu, chưa tích hợp hoàn toàn động lực học tiến hóa mạng (Network Evolution) nơi các nút và cạnh liên tục xuất hiện hoặc biến mất theo thời gian thực.
2. Độc lập tham số chi phí: Giả định chi phí kích hoạt nút $c_i(u)$ là cố định đối với từng chủ đề, chưa xét đến tính co giãn của chi phí theo thời gian và sự thay đổi tâm lý người dùng.
3. Mô hình tương tác nội dung: Nghiên cứu chưa tích hợp sâu kỹ thuật Xử lý ngôn ngữ tự nhiên (NLP) để phân tích sắc thái cảm xúc (Sentiment Analysis) của thông điệp lan truyền.

Chương trình nghiên cứu tương lai:

• Phát triển thuật toán luồng thích ứng (Adaptive Streaming Algorithms) trên đồ thị động đa chiều (Temporal Dynamic Graphs).
• Mở rộng bài toán BkIM trong bối cảnh lan truyền thông tin cạnh tranh đối kháng (Competitive Multi-topic Influence Maximization - CIM).
• Tích hợp mô hình học sâu đồ thị (Graph Neural Networks - GNNs) để tự động hóa việc dự báo xác suất lan truyền $p(u,v)$ theo ngữ cảnh thời gian thực.

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

Các kết quả nghiên cứu của luận án đã được thẩm định độc lập và công bố trên các diễn đàn khoa học uy tín cao:

• 01 công trình trên tạp chí quốc tế thuộc danh mục SCIE: Algorithms (2020, Vol. 13, No. 183; doi:10.3390/a13080183).
• 01 công trình trên tạp chí quốc tế thuộc danh mục SCIE/SCOPUS: Journal of Combinatorial Optimization (Vol. 44, pp. 723–751).
• 01 công trình hội thảo quốc tế thuộc danh mục SCOPUS: Computational Data and Social Networks (Lecture Notes in Computer Science - LNCS, Vol. 13116, Springer).
• 02 bài báo tại các hội thảo khoa học chuyên ngành trong nước.

Công trình tạo tiền đề kỹ thuật vững chắc cho việc xây dựng các hệ sinh thái phần mềm phân tích mạng xã hội, hỗ trợ đắc lực cho các cơ quan quản lý nhà nước trong việc giám sát an toàn thông tin không gian mạng quốc gia và hỗ trợ các doanh nghiệp công nghệ số tối ưu hóa hiệu quả kinh tế số.

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

• Nghiên cứu sinh và Giới học thuật: Tiếp cận khung phân tích toán học mẫu mực về tối ưu hóa Submodular, thuật toán lấy mẫu ngẫu nhiên (RR/TRR sketch) và thuật toán luồng một lượt.
• Kỹ sư Khoa học dữ liệu & Trí tuệ nhân tạo: Ứng dụng trực tiếp mã nguồn và giải thuật IG, IGS, Streaming BkIM vào các hệ thống gợi ý (Recommender Systems), phân tích đồ thị lớn (Large-scale Graph Analytics) và tối ưu hóa phân phối nội dung.
• Bộ phận R&D doanh nghiệp Tiếp thị số: Sở hữu thuật toán tối ưu hóa ngân sách quảng cáo đa kênh, đa chủ đề với cam kết KPI đo lường được trên nhóm khách hàng mục tiêu.
• Cơ quan An ninh thông tin & Quản lý truyền thông: Khai thác công cụ khoa học để phân tích luồng phát tán thông tin sai lệch, từ đó xây dựng kịch bản điều hướng dư luận và ngăn chặn hiểm họa thông tin độc hại kịp thời.

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ì?

Luận án đã mở rộng lý thuyết tối ưu hóa Submodular khi tích hợp thành công ràng buộc hai tiêu chí (Bi-criteria constraints) vào bài toán Cực đại ảnh hưởng với tập ưu tiên (IMP), chứng minh rằng thuật toán tham lam tích hợp (IG) và lấy mẫu tích hợp (IGS) phá vỡ rào cản tính toán #P-Khó để đạt tỷ lệ xấp xỉ có bảo đảm toán học $(1 - 1/e - \epsilon)$ với xác suất thành công $1 - \delta$.

2. Đột phá phương pháp luận so với các nghiên cứu tiền nhiệm?

So với thuật toán tham lam cổ điển của Kempe et al. (2003) (độ phức tạp thời gian cực lớn) và kỹ thuật TIM/IMM của Tang et al. (2014) (chỉ áp dụng cho bài toán không ràng buộc), luận án đã sáng tạo ra cấu trúc lấy mẫu TRR (Targeted Reverse Reachable) kết hợp với thuật toán luồng một lượt, giảm độ phức tạp truy vấn xuống mức tối ưu $O(\frac{k}{\epsilon^2} \log n)$ và không gian $O(\frac{k}{\epsilon} \log n)$.

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

Mức độ tiêu thụ bộ nhớ của thuật toán IGS trên đồ thị DBLP ($>1$ triệu cạnh) duy trì ở mức tuyến tính cực thấp trong khi vẫn đảm bảo độ phủ 100% ngưỡng $T$ trên tập ưu tiên $U$, bác bỏ quan niệm truyền thống cho rằng việc tối ưu hóa đa mục tiêu trên đồ thị lớn bắt buộc phải hy sinh bộ nhớ đệm RAM.

4. Luận án có cung cấp giao thức tái lập (Replication Protocol) không?

Toàn bộ quy trình sinh mẫu ngẫu nhiên đồ thị trực tuyến $g \sim G$, các bước triển khai thuật toán IG, IGS, Streaming BkIM cùng hệ thống tham số chuẩn hóa trên 05 bộ dữ liệu mở (netHEPT, ENRON, netPHY, DBLP, RETWEET) đều được mô tả chi tiết dưới dạng mã giả và chứng minh toán học tường minh trong luận án.

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

Mở rộng từ mô hình tĩnh sang đồ thị tiến hóa động (Dynamic Graphs), kết hợp học sâu đồ thị (GNNs) để tối ưu hóa ảnh hưởng liên nền tảng (Cross-platform Influence Spread) dưới sự can thiệp của các tác nhân AI cạnh tranh.

Kết luận

Luận án tiến sĩ của tác giả Vũ Chí Quang đã giải quyết trọn vẹn và xuất sắc những thách thức cốt lõi của bài toán Cực đại ảnh hưởng trên mạng xã hội thông qua 5 đóng góp cụ thể:

1. Định nghĩa và mô hình hóa toán học hoàn chỉnh hai bài toán thực tiễn: Cực đại ảnh hưởng với ràng buộc ưu tiên (IMP) và Cực đại ảnh hưởng lan truyền đa chủ đề giới hạn chi phí (BkIM).
2. Phát triển thành công bộ đôi thuật toán IG và IGS cho bài toán IMP với bảo đảm lý thuyết đạt xấp xỉ $(1 - 1/e - \epsilon)$ trên nền tảng kỹ thuật lấy mẫu TRR tiên tiến.
3. Thiết kế hai thuật toán luồng một lượt (tất định và ngẫu nhiên) cho bài toán BkIM đạt tỷ lệ xấp xỉ chặt chẽ ($\frac{1}{4} - \epsilon$, $\frac{1}{5} - \epsilon$, và cận tổng quát) với chi phí bộ nhớ và thời gian tối ưu $O(\frac{k}{\epsilon} \log n)$.
4. Kiểm chứng thực nghiệm toàn diện trên 05 tập dữ liệu đồ thị thực tế quy mô lớn, chứng minh tính ưu việt tuyệt đối về tốc độ hội tụ và độ phủ thông tin.
5. Công bố các kết quả đột phá trên các tạp chí khoa học quốc tế uy tín thuộc danh mục ISI/SCIE và SCOPUS (Algorithms, Journal of Combinatorial Optimization, LNCS Springer).

Công trình đánh dấu bước tiến quan trọng trong chuyên ngành Hệ thống thông tin, mở ra các hướng tiếp cận liên ngành giàu tiềm năng giữa tối ưu hóa tổ hợp, khoa học dữ liệu mạng và an toàn thông tin trong kỷ nguyên chuyển đổi số toàn cầu.