Tổng quan luận án

Luận án tiến sĩ chuyên ngành Hệ thống thông tin (mã số: 9 48 01 04) với đề 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í" được nghiên cứu sinh Vũ Chí Quang thực hiện dưới sự hướng dẫn của TS. Nguyễn Như Sơn và PGS. TS. Ngô Quốc Dũng 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 (bảo vệ năm 2024).

Tính cấp thiết và khoảng trống nghiên cứu

Mạng xã hội (Social Network - SN) hiện nay đã trở thành môi trường kết nối toàn cầu với quy mô hàng tỷ người dùng, làm thay đổi phương thức tiếp nhận và truyền tải thông tin so với các phương tiện truyền thống. Tuy nhiên, tính chất dữ liệu khổng lồ, cấu trúc mạng không đồng nhất, phân tán và quá trình lan truyền mang tính ngẫu nhiên đặt ra yêu cầu phải có các giải pháp tính toán hiệu quả về thời gian và bộ nhớ.

Trong nhóm các bài toán lan truyền thông tin (Spread Information - SI), bài toán Cực đại ảnh hưởng (Influence Maximization - IM) và các bài toán liên quan có bản chất thuộc lớp tối ưu tổ hợp NP-khó, trong khi việc tính toán giá trị hàm ảnh hưởng đạt độ phức tạp #P-khó. Dù đã có nhiều công trình nghiên cứu, các thuật toán hiện hữu vẫn bộc lộ hạn chế khi đối mặt với các kịch bản ứng dụng thực tế phức tạp:

  • Chưa xử lý hiệu quả bài toán khi có ràng buộc ưu tiên (cần đảm bảo ngưỡng tác động tối thiểu lên một nhóm đối tượng cụ thể trước khi tối đa hóa toàn mạng).
  • Chưa tối ưu hóa được bài toán lan truyền thông tin nhiều chủ đề khi có giới hạn về mặt chi phí và yêu cầu xử lý dữ liệu lớn theo mô hình luồng trực tuyến (streaming).

Mục tiêu nghiên cứu

Luận án xác định 03 mục tiêu nghiên cứu cụ thể:

  1. Nghiên cứu các bài toán cực đại ảnh hưởng trên các mô hình lan truyền thông tin; đề xuất hai biến thể bài toán mới có tính thực tiễn: bài toán Cực đại ảnh hưởng với ràng buộc ưu tiên (IMP) và 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).
  2. Xây dựng mô hình toán học giải quyết hai bài toán trên, phân tích và chứng minh độ phức tạp tính toán của chúng trên các mô hình lan truyền thông tin.
  3. Đề xuất các thuật toán xấp xỉ và thuật toán luồng hiệu quả, tập trung nâng cao chất lượng nghiệm và khả năng ứng dụng trên các đồ thị mạng xã hội quy mô lớn (hàng trăm nghìn đến hàng triệu nút và cạnh).

Hai bài toán trọng tâm

  • Bài toán 1 - Cực đại ảnh hưởng với ràng buộc ưu tiên (Influence Maximization with Priority - IMP): Tìm tập hạt giống nguồn $S$ có kích thước $|S| = k$ sao cho mức độ lan truyền ảnh hưởng đến tập ưu tiên $U$ ($U \subseteq V$) đạt ít nhất ngưỡng $T$ ($\sigma_U(S) \ge T$), đồng thời tổng mức độ ảnh hưởng $\sigma(S)$ trên toàn mạng đạt cực đại.
  • Bài toán 2 - Cực đại ảnh hưởng lan truyền thông tin nhiều chủ đề với chi phí giới hạn (Budgeted k-Influence Maximization - BkIM / $IM_B^k$): Tìm tập người dùng nguồn phân bổ theo $k$ chủ đề khác nhau (mỗi người dùng chỉ gán với tối đa một chủ đề) sao cho tổng ảnh hưởng đạt cực đại mà không vượt quá ngân sách chi phí tổng thể $B$.

Đối tượng và phạm vi nghiên cứu

  • Đối tượng nghiên cứu: Các mô hình phát tán thông tin rời rạc trên mạng xã hội (mô hình Bậc độc lập - IC, mô hình Ngưỡng tuyến tính - LT, mô hình Cạnh trực tuyến - LE); cấu trúc đồ thị mạng xã hội có hướng $G = (V, E)$; các thuật toán tối ưu tổ hợp xấp xỉ và thuật toán xử lý luồng.
  • Phạm vi không gian và dữ liệu: Đồ thị mạng xã hội thực tế được chuẩn hóa từ các bộ dữ liệu công khai: netHEPT, ENRON, netPHY, DBLP, RETWEET.
  • Phạm vi thời gian và mô hình: Quá trình lan truyền thông tin theo các bước thời gian rời rạc $t = 0, 1, 2, \dots$; các thuật toán luồng thực hiện theo cơ chế duyệt dữ liệu một lượt (one-pass streaming).

Tổng quan tài liệu và vị trí của luận án

Các hướng nghiên cứu nền tảng và liên quan

Luận án tổng thuật các công trình nghiên cứu theo các trục lý thuyết:

  1. Nền tảng mô hình hóa lan truyền thông tin: Domingo và Richardson (2001) [39, 48] đặt nền móng cho việc phân tích tiếp thị lan truyền dựa trên khai phá dữ liệu mạng xã hội. Kempe, Kleinberg và Tardos (2003) [3] chính thức hình thức hóa bài toán IM dưới dạng bài toán tối ưu rời rạc trên hai mô hình ngẫu nhiên cơ bản là IC (Independent Cascade) và LT (Linear Threshold), chứng minh bài toán thuộc lớp NP-khó và hàm ảnh hưởng có tính chất đơn điệu, submodular, cho phép thuật toán tham lam đạt tỷ lệ xấp xỉ $(1 - 1/e)$.
  2. Độ phức tạp tính toán và mô hình tương đương: Chen và cộng sự (2010, 2010) [5, 6, 40] chứng minh việc tính toán chính xác hàm ảnh hưởng $\sigma(S)$ trên mô hình IC và LT là #P-khó, đồng thời hoàn thiện cơ sở lý thuyết về sự tương đương giữa mô hình lan truyền rời rạc và mô hình Cạnh trực tuyến (Live Edge - LE), mở đường cho các phương pháp xấp xỉ qua tập mẫu ảnh hưởng ngược (Reverse Reachable - RR).
  3. Các biến thể mở rộng của bài toán IM: Các nghiên cứu mở rộng theo yếu tố thời gian (Gomez-Rodriguez và cs [9], Liu và cs [10]), theo chi phí và ngân sách (Nguyen và cs [11], Zhang và cs [14]), theo khoảng cách (Nguyen và cs [15]), theo chủ đề quan tâm (Tang và cs [16]), và bài toán cực đại ảnh hưởng cạnh tranh (CIM) (Bharathi và cs [4], Borodin và cs [18], Lu và cs [21]).
  4. Các bài toán lan truyền khác: Bài toán ngăn chặn ảnh hưởng (IB) và phát hiện thông tin (ID) với các công trình của Khalil và cs [75] (loại bỏ cạnh), Yang và cs [77] (tiêm vắc-xin DAVA trên mô hình IC), Zhang và cs [67, 68] (đặt điểm giám sát và phân phối vắc-xin trên mô hình LT), Song và cs [73].
  5. Nghiên cứu trong nước: Tác giả Phạm Văn Cảnh (2020) [95] nghiên cứu các bài toán ngăn chặn thông tin sai lệch có ràng buộc ngân sách và thời gian (MMR), ngăn chặn thông tin mục tiêu (TMB), cực đại ảnh hưởng cạnh tranh (BCIM) và phát hiện thông tin sai lệch tổng quát (GMD).

Khoảng trống nghiên cứu luận án lựa chọn giải quyết

  • Trong bài toán IM truyền thống và các biến thể, mục tiêu chủ yếu tập trung vào việc tối đa hóa độ phủ toàn mạng hoặc tối đa hóa trên một nhóm mục tiêu đơn lẻ. Chưa có nghiên cứu giải quyết thỏa đáng bài toán kết hợp: vừa phải thỏa mãn ngưỡng ảnh hưởng tối thiểu $T$ trên một tập ưu tiên $U$ xác định, vừa tối đa hóa tổng ảnh hưởng trên toàn mạng $V$, trong điều kiện các thuật toán IM hiện tại không thể áp dụng trực tiếp do vướng ràng buộc ưu tiên.
  • Trong bài toán cực đại ảnh hưởng đa chủ đề có ràng buộc chi phí, các phương pháp hiện hành đòi hỏi lưu trữ toàn bộ cấu trúc đồ thị vào bộ nhớ tĩnh, không khả thi khi dữ liệu mạng xã hội tăng trưởng liên tục. Luận án giải quyết khoảng trống này bằng cách xây dựng thuật toán luồng duyệt dữ liệu một lần (one-pass streaming) có đảm bảo cận lý thuyết và tối ưu không gian bộ nhớ.

Cơ sở lý thuyết và phương pháp nghiên cứu

Cơ sở lý thuyết và khung phân tích

  • Mô hình mạng: Đồ thị có hướng $G = (V, E)$ với tập đỉnh $V$ ($|V| = n$) biểu diễn người dùng, tập cạnh $E$ ($|E| = m$) biểu diễn mối liên kết.
  • Các mô hình lan truyền:
    • Mô hình Ngưỡng tuyến tính (LT): Trọng số cạnh $w(u, v)$ chuẩn hóa $\sum_{u \in N^{in}(v)} w(u, v) \le 1$. Nút $u$ có ngưỡng $\theta_u \in [0, 1]$ ngẫu nhiên. Nút chuyển sang kích hoạt khi tổng trọng số từ các nút lân cận kích hoạt đạt $\ge \theta_u$.
    • Mô hình Bậc độc lập (IC): Mỗi cạnh $(u, v)$ có xác suất kích hoạt $p(u, v) \in [0, 1]$. Mỗi nút đã kích hoạt có đúng một cơ hội kích hoạt nút lân cận chưa kích hoạt.
    • Mô hình Cạnh trực tuyến (LE): Đồ thị con ngẫu nhiên $g \sim G$ được sinh ra theo phân bố xác suất; hàm ảnh hưởng $\sigma(S) = \sum_{g \sim G} \Pr(g \sim G) |R(g, S)|$, với $R(g, S)$ là tập các nút đến được từ $S$ trong $g$.
  • Lý thuyết tối ưu tổ hợp và hàm Submodular:
    • Định nghĩa không gian bài toán $(S, f, \Omega)$, các lớp độ phức tạp P, NP, NP-đầy đủ, #P, #P-khó.
    • Hàm $f: 2^V \to \mathbb{R}$ có tính chất submodular: $\forall A \subseteq B \subseteq V, u \in V \setminus B \implies f(A \cup {u}) - f(A) \ge f(B \cup {u}) - f(B)$.

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

  1. Phương pháp phân tích lý thuyết:
    • Sử dụng kỹ thuật thiết kế thuật toán xấp xỉ và thuật toán luồng (streaming algorithms).
    • Xây dựng các hàm chặn cận trên (upper bound) và cận dưới (lower bound) cho giá trị nghiệm tối ưu $OPT$.
    • Chứng minh toán học chặt chẽ tính đúng đắn, tỷ lệ xấp xỉ, độ phức tạp thời gian truy vấn (query complexity) và độ phức tạp không gian (space complexity) thông qua hệ thống Bổ đề và Định lý.
  2. Phương pháp lấy mẫu và ước lượng ngẫu nhiên:
    • Kỹ thuật tạo tập mẫu ảnh hưởng ngược (Reverse Reachable - RR) và tập mẫu ảnh hưởng ngược có mục tiêu (Targeted Reverse Reachable - TRR) để khắc phục độ phức tạp #P-khó khi tính hàm ảnh hưởng $\sigma(S)$ và $\sigma_U(S)$.
    • Áp dụng các cận Martingale và biến ngẫu nhiên để xác định số lượng mẫu cần thiết, bảo đảm xác suất lỗi không vượt quá $\delta$.
  3. Phương pháp thực nghiệm kiểm chứng:
    • Cài đặt thuật toán bằng ngôn ngữ lập trình, so sánh thực nghiệm với các thuật toán cơ sở về: mức độ lan truyền ảnh hưởng ($\sigma(S)$, $\sigma_U(S)$), thời gian thực thi (giây), số lời gọi hàm mục tiêu và dung lượng bộ nhớ sử dụng (MB).

Nguồn dữ liệu thực nghiệm

Luận án sử dụng 05 bộ dữ liệu mạng xã hội thực tế:

  • netHEPT: Mạng cộng tác học thuật trích xuất từ arXiv (lĩnh vực High Energy Physics Theory).
  • ENRON: Mạng lưới liên lạc thư điện tử của tập đoàn Enron.
  • netPHY: Mạng cộng tác học thuật trích xuất từ arXiv (lĩnh vực Vật lý tổng quát).
  • DBLP: Mạng cộng tác xuất bản khoa học máy tính từ cơ sở dữ liệu DBLP.
  • RETWEET: Mạng lưới chia sẻ lại bài viết (retweet) trên nền tảng mạng xã hội Twitter.

Nội dung chính theo từng chương

Chương 1: Cơ sở lý thuyết của luận án và các nghiên cứu liên quan

Chương 1 hệ thống hóa toàn diện các khái niệm, đặc trưng hình thái học và các cơ chế tương tác trên mạng xã hội, làm tiền đề lý thuyết cho các đề xuất thuật toán.

  • Đặc trưng mạng xã hội:
    • Đặc trưng thế giới nhỏ (Small-world): Khoảng cách kết nối trung bình giữa hai nút bất kỳ nhỏ hơn 6.
    • Đặc trưng tập nhân (Core/Hub nodes): Tồn tại các nút bậc cao chi phối cấu trúc liên kết và luồng thông tin.
    • Đặc trưng cấu trúc cộng đồng: Mạng phân rã thành các nhóm có mật độ liên kết nội bộ dày đặc (cộng đồng tách rời hoặc chồng chéo).
    • Đặc trưng phân bố lũy thừa (Power-law distribution): Xác suất một nút có bậc $k$ tuân theo $P(k) \propto k^{-\gamma}$ với $2 < \gamma < 3$.
  • Hệ thống hóa các bài toán lan truyền: Phân định rõ 03 nhóm bài toán: Cực đại ảnh hưởng (IM), Phát hiện thông tin (ID), và Ngăn chặn ảnh hưởng (IB) (bao gồm vô hiệu hóa liên kết/người dùng và cơ chế tẩy nhiễm thông tin).
  • Phương pháp tối ưu tổ hợp: Trình bày chi tiết lý thuyết thuật toán xấp xỉ, phương pháp mô phỏng Monte Carlo, thuật toán Heuristic/Metaheuristic và nguyên lý hoạt động của thuật toán luồng (xử lý dòng dữ liệu liên tục, bộ nhớ giới hạn, cập nhật một lượt).
  • Tổng kết các nghiên cứu liên quan: Đánh giá các công trình trong và ngoài nước về bài toán lan truyền thông tin, chỉ ra các giới hạn kỹ thuật mà luận án sẽ tập trung giải quyết.

Chương 2: Cực đại ảnh hưởng với ràng buộc ưu tiên trên mạng xã hội

Chương 2 giải quyết bài toán IMP, thiết lập mô hình toán học và đề xuất các thuật toán xấp xỉ cùng các phân tích lý thuyết và thực nghiệm.

Thành phần kỹ thuật Chi tiết nội dung / Đảm bảo lý thuyết
Phát biểu bài toán IMP Cho đồ thị $G=(V, E)$, tập ưu tiên $U \subseteq V$, ngưỡng $T > 0$, kích thước hạt giống $k$. Tìm $S \subseteq V, |S|=k$ sao cho: $\max \sigma(S)$ thỏa mãn điều kiện $\sigma_U(S) \ge T$.
Thuật toán đề xuất 1 IG (Integrated Greedy): Thuật toán tham lam tích hợp kết hợp đánh giá ảnh hưởng cục bộ trên $U$ và toàn cục trên $V$.
Đảm bảo lý thuyết IG Đạt nghiệm xấp xỉ với tỷ lệ $(1 - 1/e)(1 - 1/e)$.
Thuật toán đề xuất 2 IGS (Integrated Greedy-based Sampling): Thuật toán lấy mẫu dựa trên tham lam tích hợp, sử dụng kỹ thuật sinh tập mẫu RR và TRR để ước lượng $\sigma(S)$ và $\sigma_U(S)$.
Đảm bảo lý thuyết IGS Trả về nghiệm xấp xỉ $(1 - 1/e)(1 - 1/e - \epsilon)$ với xác suất ít nhất $1 - \delta$, với $\epsilon > 0$ và $\delta \in (0, 1)$ là các tham số đầu vào.
Thiết lập thực nghiệm Thực hiện trên 5 bộ dữ liệu (netHEPT, ENRON, netPHY, DBLP, RETWEET) với các tham số: $k = 100 \to 500$, kích thước tập ưu tiên $|U| = 200 \to 1000$, ngưỡng $T = 100 \to 500$.
Kết quả thực nghiệm - IGS đảm bảo vượt ngưỡng ưu tiên $T$ trong mọi kịch bản thử nghiệm.
- Thời gian chạy (s) của IGS thấp hơn đáng kể so với IG khi $k$ tăng từ 150 đến 200.
- Mức sử dụng bộ nhớ (MB) của IGS duy trì ở mức tối ưu trên các đồ thị có kích thước lớn.

Chương 3: Cực đại ảnh hưởng lan truyền thông tin nhiều chủ đề với chi phí giới hạn

Chương 3 xây dựng mô hình toán cho bài toán BkIM ($IM_B^k$) và đề xuất các thuật toán xử lý luồng duyệt một lần (one-pass streaming) cho cả trường hợp đặc biệt và trường hợp tổng quát.

Kịch bản bài toán Thuật toán đề xuất Độ phức tạp tính toán Tỷ lệ xấp xỉ đạt được
Trường hợp đặc biệt
($\beta = 1$: một phần tử chỉ có một mức chi phí khi thêm vào chủ đề thứ $i$)		 Thuật toán luồng tất định (Deterministic streaming) duyệt dữ liệu 1 lượt - Truy vấn: $O\left(\frac{k}{\epsilon} \log k\right)$
- Không gian: $O\left(\frac{k}{\epsilon} \log k\right)$		 - Hàm $f$ đơn điệu: $\frac{1}{4} - \epsilon$
- Hàm $f$ không đơn điệu: $\frac{1}{5} - \epsilon$
(với tham số $\epsilon \in (0, 1/5)$)
Trường hợp tổng quát
(Chi phí phụ thuộc phần tử và chủ đề, với $\alpha = \max \frac{c_i(u)}{c_j(u)}$)		 Thuật toán luồng ngẫu nhiên (Randomized streaming) duyệt dữ liệu 1 lượt - Truy vấn: $O\left(\frac{k}{\epsilon} \log k\right)$
- Không gian: $O\left(\frac{k}{\epsilon} \log k\right)$		 - Hàm $f$ đơn điệu: $\min\left{\frac{\alpha}{2}, \frac{1-\alpha}{1+\beta}\frac{1}{e-\epsilon}\right} - \epsilon$
- Hàm $f$ không đơn điệu: $\min\left{\frac{\alpha}{2}, \frac{1-\alpha}{1+2\beta}\frac{1}{e-2\epsilon}\right} - \epsilon$
(với $\epsilon \in (0, 1)$)
  • Thực nghiệm và đánh giá: Đánh giá thuật toán luồng trên ứng dụng cực đại ảnh hưởng với $k$ chủ đề trong điều kiện giới hạn chi phí. So sánh với thuật toán tham lam truyền thống dựa trên 03 chỉ số: giá trị hàm ảnh hưởng thu được, số lượng lời gọi hàm mục tiêu và thời gian chạy (giây). Kết quả chứng minh các thuật toán luồng giảm thiểu vượt trội số lời gọi hàm mục tiêu và thời gian thực thi trong khi vẫn duy trì giá trị hàm ảnh hưởng sát với cận tối ưu lý thuyết.

Kết quả và những đóng góp mới

Đóng góp về mặt lý luận và khoa học

  1. Định nghĩa hai bài toán mới: Hình thức hóa bài toán Cực đại ảnh hưởng với ràng buộc ưu tiên (IMP) và 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), mở rộng phạm vi ứng dụng của lý thuyết lan truyền thông tin sang các bài toán tối ưu có điều kiện biên phức tạp.
  2. Đề xuất và chứng minh thuật toán cho bài toán IMP:
    • Xây dựng thuật toán tham lam tích hợp IG đạt tỷ lệ xấp xỉ $(1 - 1/e)(1 - 1/e)$.
    • Xây dựng thuật toán lấy mẫu ngẫu nhiên IGS sử dụng cấu trúc mẫu TRR và RR, chứng minh thuật toán đạt tỷ lệ xấp xỉ $(1 - 1/e)(1 - 1/e - \epsilon)$ với xác suất thành công ít nhất $1 - \delta$.
  3. Đề xuất và chứng minh thuật toán luồng cho bài toán BkIM:
    • Thiết kế thuật toán luồng tất định một lượt cho trường hợp $\beta = 1$ với độ phức tạp truy vấn và không gian đều là $O(\frac{k}{\epsilon} \log k)$, đạt tỷ lệ xấp xỉ $1/4 - \epsilon$ (hàm đơn điệu) và $1/5 - \epsilon$ (hàm không đơn điệu).
    • Thiết kế thuật toán luồng ngẫu nhiên một lượt cho trường hợp tổng quát với độ phức tạp truy vấn và không gian $O(\frac{k}{\epsilon} \log k)$, chứng minh các tỷ lệ xấp xỉ lý thuyết tương ứng cho cả hàm mục tiêu đơn điệu và không đơn điệu.

Đóng góp về mặt thực tiễn và ứng dụng

  • Tối ưu hóa hiệu năng tính toán: Giảm thiểu độ phức tạp tính toán và tiêu thụ tài nguyên bộ nhớ khi xử lý các mạng xã hội quy mô lớn, cho phép tính toán trên các dòng dữ liệu cập nhật liên tục mà không cần nạp toàn bộ đồ thị vào bộ nhớ.
  • Ứng dụng tiếp thị và định hướng truyền thông: Cung cấp công cụ toán học và thuật toán hỗ trợ doanh nghiệp tối ưu hóa chiến dịch quảng bá đa sản phẩm/chủ đề trong điều kiện ngân sách hạn chế; hỗ trợ các tổ chức xã hội phát tán thông tin định hướng ưu tiên đến các nhóm đối tượng trọng điểm.
  • Công bố khoa học: Các kết quả của luận án đã được công bố trong 02 bài báo trên tạp chí quốc tế thuộc danh mục SCIE/SCOPUS (Algorithms, Journal of Combinatorial Optimization), 01 bài báo tại hội thảo quốc tế thuộc danh mục SCOPUS (LNCS), và 02 bài báo tại các hội thảo khoa học chuyên ngành trong nước.

Hạn chế và hướng nghiên cứu tiếp

Căn cứ vào phạm vi và nội dung trình bày trong luận án, một số hạn chế và hướng phát triển được xác định như sau:

  • Hạn chế:
    • Các thuật toán đề xuất cho bài toán IMP chủ yếu tập trung thiết kế và đánh giá trên mô hình Bậc độc lập (IC) theo thời gian rời rạc; chưa mở rộng đánh giá chi tiết trên các mô hình lan truyền thời gian liên tục hoặc mô hình cạnh tranh phức hợp.
    • Trong bài toán BkIM, giả định mỗi người dùng chỉ được phân bổ tối đa cho một chủ đề duy nhất trong lời giải; chưa mở rộng cho kịch bản một người dùng có thể đồng thời là hạt giống lan truyền cho nhiều chủ đề với các mức chi phí phân mảnh.
    • Dữ liệu thực nghiệm dù đa dạng nhưng vẫn dựa trên các đồ thị tĩnh hoặc các chuỗi sự kiện được mô phỏng hóa theo luồng, chưa tích hợp trực tiếp với API luồng dữ liệu thời gian thực của các nền tảng mạng xã hội đang vận hành.
  • Hướng nghiên cứu tiếp:
    • Nghiên cứu mở rộng bài toán IMP và BkIM trên mô hình mạng xã hội động (Dynamic Social Networks), nơi các nút và cạnh liên tục xuất hiện hoặc mất đi theo thời gian.
    • Phát triển các thuật toán giải quyết bài toán cực đại ảnh hưởng đa chủ đề kết hợp đồng thời cả ràng buộc ưu tiên và yếu tố cạnh tranh giữa các luồng thông tin đối kháng.
    • Ứng dụng các kỹ thuật học máy và học sâu trên đồ thị (Graph Neural Networks) để nâng cao độ chính xác khi ước lượng xác suất lan truyền trên từng cạnh của đồ thị.

Giá trị tham khảo

Luận án là tài liệu tham khảo chuyên sâu cho các nhóm đối tượng:

  • Nghiên cứu sinh và học viên cao học ngành Khoa học máy tính, Hệ thống thông tin, Toán tin ứng dụng: Có thể tham khảo phương pháp luận chứng minh độ phức tạp tính toán (#P-khó, NP-khó), kỹ thuật lấy mẫu TRR/RR để ước lượng hàm submodular, và kỹ thuật thiết kế thuật toán luồng một lượt với các cận đảm bảo lý thuyết.
  • Giảng viên và nhà nghiên cứu trong lĩnh vực Phân tích mạng xã hội và Tối ưu tổ hợp: Sử dụng làm tài liệu tham khảo cho các chuyên đề về khai phá dữ liệu đồ thị, thuật toán xấp xỉ và các mô hình lan truyền thông tin (IC, LT, LE).
  • Kỹ sư hệ thống và chuyên gia phân tích dữ liệu tại các doanh nghiệp/tổ chức: Tham khảo mã giả và khung thuật toán (IGS, Streaming BkIM) để triển khai các hệ thống tiếp thị lan truyền đa chiến dịch, tối ưu hóa chi phí quảng cáo số hoặc xây dựng các hệ thống giám sát và định hướng thông tin cộng đồng.

Câu hỏi thường gặp

1. Điểm khác biệt căn bản giữa bài toán Cực đại ảnh hưởng truyền thống (IM) và bài toán Cực đại ảnh hưởng với ràng buộc ưu tiên (IMP) là gì?
Trả lời: Bài toán IM truyền thống chỉ tìm tập hạt giống $S$ kích thước $k$ để tối đa hóa tổng số người bị ảnh hưởng $\sigma(S)$ trên toàn bộ đồ thị mạng. Bài toán IMP bổ sung thêm điều kiện biên: tập hạt giống $S$ bắt buộc phải tạo ra mức độ ảnh hưởng đến một tập ưu tiên $U$ cho trước đạt ít nhất ngưỡng $T$ ($\sigma_U(S) \ge T$), sau đó mới tối đa hóa tổng ảnh hưởng $\sigma(S)$ trên toàn mạng.

2. Vì sao các thuật toán IM hiện có không thể áp dụng trực tiếp để giải bài toán IMP?
Trả lời: Mặc dù hàm mục tiêu vẫn giữ tính chất đơn điệu và submodular, sự xuất hiện của ràng buộc ưu tiên ($\sigma_U(S) \ge T$) làm thay đổi không gian nghiệm chấp nhận được. Việc lựa chọn hạt giống thuần túy theo mức tăng ích biên trên toàn mạng có thể không thỏa mãn ngưỡng tác động trên tập $U$, dẫn đến vi phạm ràng buộc bài toán. Do đó, cần có các thuật toán tích hợp như IG và IGS để cân bằng đồng thời giữa mức độ lan truyền cục bộ trên $U$ và toàn cục trên $V$.

3. Kỹ thuật lấy mẫu TRR trong thuật toán IGS có vai trò gì?
Trả lời: TRR (Targeted Reverse Reachable) là tập mẫu ảnh hưởng ngược có mục tiêu, được sinh ra từ các nút gốc thuộc tập ưu tiên $U$. Kỹ thuật này cho phép ước lượng chính xác và không chệch giá trị hàm ảnh hưởng $\sigma_U(S)$ mà không cần duyệt toàn bộ mạng, giúp giảm độ phức tạp tính toán từ #P-khó xuống mức đa thức với xác suất lỗi được kiểm soát bởi tham số $\delta$.

4. Thuật toán luồng cho bài toán BkIM mang lại ưu thế gì so với thuật toán tham lam truyền thống?
Trả lời: Thuật toán luồng chỉ duyệt dữ liệu đồ thị một lần duy nhất (one-pass), duy trì độ phức tạp không gian bộ nhớ và số lượt truy vấn ở mức nhỏ $O(\frac{k}{\epsilon} \log k)$, không đòi hỏi lưu toàn bộ đồ thị vào bộ nhớ tĩnh. Điều này giúp hệ thống xử lý được các mạng dữ liệu lớn với thời gian chạy và số lời gọi hàm mục tiêu giảm đáng kể so với thuật toán tham lam thông thường, trong khi vẫn bảo đảm được tỷ lệ xấp xỉ lý thuyết đã chứng minh.

5. Luận án đã kiểm chứng thực nghiệm các thuật toán đề xuất trên những bộ dữ liệu nào?
Trả lời: Luận án đã tiến hành thử nghiệm trên 05 bộ dữ liệu mạng thực tế gồm: netHEPT, ENRON, netPHY, DBLP và RETWEET, đại diện cho các mạng cộng tác khoa học, mạng thư điện tử và mạng xã hội chia sẻ trực tuyến.

Kết luận

Luận án tiến sĩ của tác giả Vũ Chí Quang đã giải quyết hai biến thể quan trọng của bài toán lan truyền thông tin trên mạng xã hội gồm: Cực đại ảnh hưởng với ràng buộc ưu tiên (IMP) và Cực đại ảnh hưởng đa chủ đề với chi phí giới hạn (BkIM). Bằng việc đề xuất các thuật toán xấp xỉ IG, IGS và các thuật toán luồng duyệt một lượt (tất định và ngẫu nhiên), luận án đã chứng minh chặt chẽ các tỷ lệ xấp xỉ lý thuyết cùng giới hạn độ phức tạp tính toán tối ưu. Các kết quả thực nghiệm trên các bộ dữ liệu thực tế lớn xác chứng tính hiệu quả về thời gian thực thi, khả năng tiết kiệm bộ nhớ và độ chính xác của các giải pháp đề xuất, đóng góp cả về mặt học thuật tối ưu tổ hợp lẫn ứng dụng thực tiễn trong hệ thống thông tin mạng xã hội.