Tổng quan luận án

Sự phát triển của các Mạng xã hội trực tuyến (MXHTT) đã đưa chúng trở thành nền tảng truyền thông đóng góp vào nền kinh tế toàn cầu, với hơn 3 tỷ người sử dụng [86] và 63% người dùng Facebook hoặc Twitter tại Mỹ xem đây là nguồn thông tin chính thức [110]. MXHTT mang các đặc tính như cập nhật thông tin nhanh, thời gian lan truyền ngắn và sự bùng nổ của nhiều nguồn tin tức. Tuy nhiên, sự phát triển này đi kèm với các thách thức: sự phát tán virus, mã độc, thư rác; hoạt động lừa đảo chiếm đoạt thông tin cá nhân (chiếm 84,5% các cuộc tấn công lừa đảo theo báo cáo an ninh của Microsoft); và sự lan truyền của thông tin sai lệch gây tổn hại về kinh tế, chính trị và xã hội (điển hình như thông tin sai lệch về vụ nổ tại Nhà Trắng khiến cựu Tổng thống Barack Obama bị thương đã gây thiệt hại 136,5 tỷ USD tới thị trường tài chính [31], hay các thông tin ảnh hưởng đến cuộc bầu cử tại Mỹ năm 2016 [3] và dịch bệnh Ebola [69]).

Xuất phát từ thực tiễn trên, việc quản lý thông tin trên MXHTT đặt ra hai nhóm bài toán lan truyền thông tin: Tối đa hóa ảnh hưởng (Influence Maximization - IM) và Ngăn chặn ảnh hưởng (Influence Blocking - IB). Theo quan điểm khoa học máy tính, các bài toán này được mô hình hóa dưới dạng bài toán tối ưu tổ hợp (TƯTH) trên các mô hình lan truyền thông tin như Ngưỡng tuyến tính (Linear Threshold - LT) và Bậc độc lập (Independent Cascade - IC) [43]. Khoảng trống nghiên cứu được tác giả chỉ ra bao gồm:

  • Lớp bài toán IM và IB thuộc lớp bài toán NP-Khó, việc tính toán chính xác hàm mục tiêu thuộc lớp #P-Khó [21, 22], đòi hỏi các thuật toán xấp xỉ và heuristic hiệu quả để xử lý trên mạng quy mô lớn hàng trăm nghìn đến hàng triệu đỉnh và cạnh.
  • Các nghiên cứu trước về tối đa hóa ảnh hưởng cạnh tranh thường giả định một bên chiếm ưu thế hoàn toàn, chưa phản ánh tính cạnh tranh công bằng trong tiếp thị sản phẩm; đồng thời bỏ qua hai yếu tố thực tế là chi phí lựa chọn từng người dùng và giới hạn bước thời gian lan truyền.
  • Các nghiên cứu ngăn chặn ảnh hưởng thường bỏ qua yếu tố ngân sách và thời gian can thiệp, hoặc chưa xác định chi phí tối thiểu để kiểm soát sự lan truyền thông tin sai lệch dưới một ngưỡng xác định.

Để giải quyết các hạn chế này, tác giả luận án xác định 03 mục tiêu nghiên cứu cụ thể:

  1. Nghiên cứu bài toán IM, IB trên các mô hình phát tán truyền thông tin. Qua đó đề xuất nghiên cứu các bài toán biến thể mới có tính ứng dụng trong thực tiễn.
  2. Đề xuất các mô hình giải quyết các bài toán trên, nghiên cứu độ phức tạp của chúng trên các mô hình lan truyền thông tin được sử dụng rộng rãi.
  3. Đề xuất các thuật toán hiệu quả để giải quyết các bài toán trên, trong đó đặc biệt chú trọng tới việc nâng cao chất lượng lời giải cũng như khả năng ứng dụng với các mạng cỡ lớn hàng trăm nghìn cho tới hàng triệu, tỷ cạnh hoặc đỉnh.

Luận án tập trung giải quyết các câu hỏi và bài toán nghiên cứu chính sau:

  1. Bài toán Tối đa hóa ảnh hưởng cạnh tranh tổng quát với ràng buộc thời gian và ngân sách (BCIM): Làm thế nào để tìm tập hạt giống $S_A$ của đối thủ $A$ (với chi phí của mỗi đỉnh $c(u) \ge 0$, tổng chi phí không vượt quá ngân sách $L$, thời gian lan truyền giới hạn trong $\tau$ bước) nhằm tối đa hóa số người dùng bị ảnh hưởng $I(S_A)$ khi đã biết trước tập hạt giống $S_B$ của đối thủ $B$?
  2. Bài toán Hạn chế tối đa thông tin sai lệch (MMR): Làm thế nào để lựa chọn tập đỉnh hoặc cạnh cần can thiệp nhằm giảm thiểu tối đa ảnh hưởng từ nguồn thông tin sai lệch cho trước trong điều kiện ngân sách và thời gian bị giới hạn?
  3. Bài toán Hạn chế thông tin sai lệch có chủ đích (TMB): Làm thế nào để tìm tập đỉnh nhỏ nhất cần loại bỏ khỏi mạng sao cho số người không bị ảnh hưởng bởi thông tin sai lệch giảm xuống và đảm bảo lớn hơn hoặc bằng một ngưỡng $\gamma$ cho trước?

Đối tượng nghiên cứu của luận án là các mô hình phát tán thông tin rời rạc (IC, LT, CLT và các biến thể mở rộng) cùng các bài toán tối ưu tổ hợp (IM, IB, BCIM, MMR, TMB) trên mạng xã hội. Phạm vi không gian là cấu trúc đồ thị mạng xã hội có hướng $G = (V, E)$ với kích thước từ trung bình đến lớn (lên tới hàng triệu đỉnh và cạnh). Phạm vi thời gian trong các mô hình lan truyền được xét theo các bước thời gian rời rạc $t \in {0, 1, \dots, \tau}$.

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

Các nghiên cứu nền tảng về lan truyền thông tin trên mạng xã hội bắt đầu từ Domingo và Richardson [30] với bài toán tiếp thị lan truyền, sau đó được Kempe cùng các cộng sự [43] hình thức hóa thành bài toán tối ưu tổ hợp IM trên hai mô hình ngẫu nhiên cơ bản: Bậc độc lập (IC) và Ngưỡng tuyến tính (LT). Kempe et al. [43, 44] chứng minh bài toán IM là NP-Khó, hàm mục tiêu $\sigma(S)$ có tính chất đơn điệu tăng và submodular, từ đó thuật toán tham lam đạt tỷ lệ xấp xỉ $1 - 1/e$. Chen cùng các cộng sự [21, 22] tiếp tục chứng minh việc tính toán chính xác hàm ảnh hưởng $\sigma(S)$ trên cả hai mô hình IC và LT là bài toán #P-Khó.

Các hướng nghiên cứu chính đã được luận án tổng quan bao gồm:

1. Thuật toán cho bài toán Tối đa hóa ảnh hưởng (IM)

  • Thuật toán xấp xỉ: Kempe et al. [43] đề xuất thuật toán tham lam kết hợp mô phỏng Monte-Carlo với số lần mô phỏng $\Omega(\frac{n^2}{\epsilon^2} \ln \frac{1}{\delta})$ đạt độ phức tạp $O(k n R (m + n))$ hoặc $O(\epsilon^{-2} k^3 n^2 m \log n)$ [19]. Leskovec et al. [54] đề xuất thuật toán Lazy Greedy khai thác tính submodular để giảm số lần tính toán, cải thiện tốc độ tới 700 lần. Borg et al. [9] đưa ra phương pháp Mẫu ảnh hưởng ngược (Reverse Influence Sampling - RIS) đạt tỷ lệ xấp xỉ $1 - 1/e - \epsilon$ với xác suất ít nhất $3/5$ và độ phức tạp $O((m + n)\epsilon^{-3} k \log n)$. Tang et al. [95, 94] phát triển thuật toán TIM/TIM++ sử dụng bất đẳng thức Chernoff và thuật toán IMM kết hợp tính chất Martingale để giảm đáng kể số lượng mẫu cần sinh $\theta_2 < \theta_1$. Hung T. Nguyen et al. [75] đề xuất thuật toán SSA và D-SSA bổ sung bước kiểm tra điều kiện dừng. Tang et al. [93] đề xuất thuật toán OPIM tối ưu hóa cận trên và cận dưới để giảm số vòng lặp.
  • Thuật toán Heuristic: Dựa trên độ đo cấu trúc mạng như Degree, Closeness, Betweenness Centrality [40, 78, 21, 22, 37, 20]; thuật toán dựa trên đường đi như PMIA (trên mô hình IC) và LDAG (trên mô hình LT) của Chen et al. [21, 22], SIMPATH của Goyal et al. [37], IPA của Kim et al. [47]; thuật toán dựa trên phân vùng cộng đồng [114, 23, 6]; và thuật toán metaheuristic như PSO [34], SA [41], GA [49, 12].

2. Các biến thể của bài toán IM

  • Biến thể thời gian, chi phí, khoảng cách: Chen et al. [20] đề xuất mô hình IC-M với bước thời gian giới hạn $\tau$; Zhang et al. [112] xét độ trễ; Gomez-Rodriguez et al. [32, 33] đề xuất mô hình thời gian liên tục Continuous-Time IC. Về ràng buộc chi phí, Huy Nguyen et al. [72] gắn chi phí $c(v) \ge 0$ cho từng nút với tỷ lệ xấp xỉ $1 - 1/\sqrt{e}$; Nguyen et al. [76] mở rộng thành bài toán CVTM kết hợp giữa chi phí $c(v)$ và lợi nhuận $b(u)$. Li et al. [62] nghiên cứu IM theo chủ đề; Li et al. [59] và Wang et al. [101] nghiên cứu bài toán tối đa hóa ảnh hưởng theo vị trí và khoảng cách địa lý (LAIM, DAIM). Một số nghiên cứu gần đây khai thác mô hình tối ưu thích ứng [84, 109, 38, 15, 92].
  • Tối đa ảnh hưởng cạnh tranh (CIM): Bharathi et al. [8] khởi xướng bài toán CIM. Carnes et al. [14] và Chen et al. [18] mở rộng mô hình IC sang IC-N. Borodin et al. [10], He et al. [39], Lu [66, 67] phát triển các mô hình cạnh tranh dựa trên LT (như CLT, K-LT) và chứng minh tính submodular của hàm mục tiêu để áp dụng thuật toán xấp xỉ tỷ lệ $1 - 1/e$. Chen et al. [19] phân loại hai cơ chế giải quyết xung đột khi hai luồng tin cùng tới một đỉnh: Luật xác suất cố định (TB-FP) và Luật xác suất tỷ lệ (TB-PP). Một số tác giả tiếp cận CIM bằng cấu trúc cộng đồng [11], mở rộng thành bài toán thống trị DCIM [102], hoặc sử dụng học tăng cường Q-learning [1, 2].

3. Ngăn chặn ảnh hưởng (IB) và tẩy nhiễm thông tin

  • Loại bỏ đỉnh và liên kết: Khalil et al. [45] nghiên cứu bài toán loại bỏ $k$ cạnh để cực tiểu hóa $\sigma(S \setminus X)$, chứng minh hàm mục tiêu là supermodular và đơn điệu giảm, từ đó đề xuất thuật toán tham lam đạt tỷ lệ $1 - 1/e - \epsilon$. Yang et al. [117] đề xuất bài toán tiêm chủng DAVA trên mô hình IC (chứng minh là NP-Khó và phi-submodular), đưa ra ba giải thuật DAVA, DAVA-prune và DAVA-Fast. Song et al. [87] mở rộng DAVA với yếu tố thời gian. Zhang et al. [115] nghiên cứu phân phối vắc xin theo cụm cạnh trên mô hình LT với tỷ lệ $1 - 1/e$. Zhang et al. [110] nghiên cứu bài toán $\tau$-MP đặt máy giám sát trong khoảng cách $\delta$ để khống chế ảnh hưởng tới nút đích $r$.
  • Tẩy nhiễm thông tin (Information Decontamination): Budak et al. [13] đề xuất mô hình MCIC tìm tập đỉnh bảo vệ tối đa với tỷ lệ tham lam $1 - 1/e$. He et al. [39] nghiên cứu bài toán IBM trên mô hình cạnh tranh CLT với ngưỡng kích hoạt tích cực $\theta_u^+$ và tiêu cực $\theta_u^-$. Song et al. [89] nghiên cứu bài toán TIB xét thời gian trễ. Nguyen et al. [77] xét bài toán $\beta$-TI chọn tập hạt giống nhỏ nhất để đạt tỷ số tẩy nhiễm $\beta$.

Vị trí và khoảng trống luận án giải quyết

Luận án định vị nghiên cứu vào các khoảng trống chưa được giải quyết thỏa đáng:

  1. Đối với CIM: Khắc phục nhược điểm của luật TB-FP (thiên vị một bên) bằng cách đề xuất luật tie-breaking dựa trên tỷ lệ trọng số (TB-WPP) phản ánh đúng tính cạnh tranh bình đẳng; tích hợp đồng thời ràng buộc chi phí riêng của từng nút $c(u)$ và giới hạn bước thời gian $\tau$ (bài toán BCIM).
  2. Đối với IB: Tích hợp đồng thời yếu tố ngân sách và thời gian lan truyền vào bài toán hạn chế thông tin sai lệch (bài toán MMR); đồng thời nghiên cứu bài toán tìm tập đỉnh can thiệp nhỏ nhất để đảm bảo ngưỡng an toàn $\gamma$ xác định (bài toán TMB).
  3. Đề xuất các thuật toán xấp xỉ có chứng minh lý thuyết chặt chẽ và có khả năng thực thi trên các đồ thị mạng xã hội quy mô hàng trăm nghìn đến hàng triệu phần tử.

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

Luận án dựa trên nền tảng lý thuyết tối ưu tổ hợp, lý thuyết độ phức tạp tính toán và các mô hình lan truyền thông tin ngẫu nhiên trên đồ thị. Mạng xã hội được biểu diễn bằng đồ thị có hướng $G = (V, E)$, với $V$ là tập đỉnh ($|V| = n$) và $E$ là tập cạnh ($|E| = m$).

1. Các khái niệm và mô hình nền tảng

  • Mô hình Ngưỡng tuyến tính (LT): Mỗi cạnh $(u, v) \in E$ có trọng số $w(u, v) \ge 0$ thỏa mãn $\sum_{u \in N_{in}(v)} w(u, v) \le 1$. Mỗi đỉnh $u$ có ngưỡng kích hoạt ngẫu nhiên $\theta_u \in [0, 1]$. Đỉnh $u$ chuyển sang kích hoạt tại bước $t$ nếu $\sum_{v \in N_{in}(u) \cap S_{t-1}} w(v, u) \ge \theta_u$.
  • Mô hình Bậc độc lập (IC): Mỗi cạnh $(u, v)$ có xác suất lan truyền $p(u, v) \in [0, 1]$. Mỗi đỉnh $u$ khi được kích hoạt tại bước $t-1$ có một cơ hội duy nhất để kích hoạt láng giềng $v \in N_{out}(u)$ với xác suất thành công $p(u, v)$.
  • Mô hình Cạnh trực tuyến (Live-edge model): Được Kempe et al. [43] và Chen et al. [19] xây dựng để chuyển đổi quá trình kích hoạt ngẫu nhiên trên đồ thị $G$ thành việc lấy mẫu đồ thị con $g \sim G$. Trên mô hình LT, mỗi đỉnh $v$ chọn nhiều nhất một cạnh đi vào $(u, v)$ với xác suất $w(u, v)$ và không chọn cạnh nào với xác suất $1 - \sum_{u \in N_{in}(v)} w(u, v)$. Trên mô hình IC, mỗi cạnh $e$ được chọn độc lập với xác suất $p(e)$. Phân bố tập đỉnh kích hoạt trên mô hình cạnh trực tuyến tương đương với phân bố kích hoạt của mô hình LT và IC gốc.
  • Lý thuyết hàm Submodular: Cho tập hữu hạn $U$, hàm tập $f: 2^U \to \mathbb{R}$ là submodular nếu với mọi $A \subseteq B \subseteq U$ và $x \in U \setminus B$, ta có: $$f(A \cup {x}) - f(A) \ge f(B \cup {x}) - f(B)$$ Nếu $f$ đơn điệu tăng và submodular với $f(\emptyset) = 0$, thuật toán tham lam giải bài toán Maximum Coverage (MC) đạt tỷ lệ tối ưu $1 - 1/e$ [46]. Đối với bài toán Set Cover (SC) và Weighted Set Cover (WSC), thuật toán tham lam đạt tỷ lệ xấp xỉ $1 + \ln n$ [100].
  • Kỹ thuật lấy mẫu và Luật dừng (Stopping Rule): Để ước lượng kỳ vọng $\mu$ của biến ngẫu nhiên $X \in [0, 1]$ đạt $(\delta, \epsilon)$-xấp xỉ (nghĩa là $\Pr[(1 - \epsilon)\hat{\mu} \le \mu \le (1 + \epsilon)\hat{\mu}] \ge 1 - \delta$), Dagum et al. [27] thiết lập thuật toán luật dừng sinh mẫu ngẫu nhiên cho tới khi tổng giá trị vượt ngưỡng: $$\Upsilon_1 = 1 + (1 + \epsilon) 4 (e - 2) \frac{\ln(2/\delta)}{\epsilon^2}$$

2. Mô hình và khung phân tích do luận án đề xuất

  • Mô hình TCLT (Time-Constrained Competitive Linear Threshold): Mở rộng mô hình CLT với bước thời gian giới hạn $\tau \ge 1$ và bổ sung luật hòa theo tỷ lệ trọng số (TB-WPP). Nếu tại bước $t$, đỉnh $v$ đồng thời thỏa mãn điều kiện kích hoạt từ đối thủ $A$ và đối thủ $B$, đỉnh $v$ sẽ chuyển sang trạng thái $A$-active với xác suất: $$p_A(v \mid A_{t-1}, B_{t-1}) = \frac{\sum_{u \in N_{in}(v) \cap A_{t-1}} w_A(u, v)}{\sum_{u \in N_{in}(v) \cap A_{t-1}} w_A(u, v) + \sum_{u \in N_{in}(v) \cap B_{t-1}} w_B(u, v)}$$
  • Mô hình CLE (Competitive Live-Edge): Luận án sinh hai đồ thị con ngẫu nhiên $g_A$ và $g_B$ độc lập từ $G$ chứa các cạnh $A$-live và $B$-live. Tác giả chứng minh Định lý 3.1: phân bố trạng thái kích hoạt của các đỉnh tại mỗi bước $t = 1, \dots, \tau$ trên mô hình TCLT và mô hình CLE là hoàn toàn trùng khớp.

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

Luận án kết hợp phương pháp phân tích lý thuyết toán học (phát biểu và chứng minh các Bổ đề, Định lý, Hệ quả về độ phức tạp NP-Khó, #P-Khó, tính submodular, các hàm chặn trên $U(\cdot)$ và chặn dưới $L(\cdot)$) với phương pháp thiết kế thuật toán xấp xỉ, heuristic và phương pháp thực nghiệm mô phỏng trên máy tính sử dụng các bộ dữ liệu mạng xã hội thực tế.

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

Chương 1: Tổng quan về các bài toán lan truyền thông tin

Chương 1 hệ thống hóa các đặc trưng cấu trúc cơ bản của MXHTT:

  • Đặc trưng thế giới nhỏ (khoảng cách kết nối trung bình giữa hai người dùng bất kỳ nhỏ hơn 6 [90, 29]).
  • Đặc trưng tập nhân (mạng chịu ảnh hưởng chi phối bởi một số nút bậc cao có sự phân cấp).
  • Phân bố bậc dạng lũy thừa của mạng không tỷ lệ (scale-free network) với hàm xác suất $P(k) = k^{-\gamma}$ ($2 < \gamma < 3$) [26].
  • Cấu trúc cộng đồng (cộng đồng tách rời và cộng đồng chồng chéo).

Chương này trình bày chi tiết cơ chế hoạt động theo thời gian rời rạc của hai mô hình gốc LT và IC, mô hình cạnh trực tuyến tương đương của Kempe [43] và Chen [19], cùng việc chứng minh độ phức tạp tính toán hàm ảnh hưởng $\sigma(S)$ là #P-Khó. Tiếp đó, tác giả phân loại và đánh giá ưu nhược điểm của các thuật toán giải bài toán IM (thuật toán xấp xỉ Greedy, Lazy Greedy, RIS, TIM/TIM++, IMM, SSA, D-SSA, OPIM; thuật toán heuristic dựa trên độ đo, đường đi PMIA/LDAG/SIMPATH/IPA, cấu trúc cộng đồng và metaheuristic) và bài toán IB (loại bỏ liên kết/đỉnh, tiêm chủng vắc xin DAVA, đặt máy giám sát $\tau$-MP và tẩy nhiễm thông tin MCIC, CLT, IBM, $\beta$-TI).

Chương 2: Bài toán tối ưu tổ hợp và một số phương pháp giải các bài toán tối ưu tổ hợp

Chương 2 trình bày cơ sở lý thuyết về bài toán tối ưu tổ hợp định nghĩa bởi bộ ba $(S, f, \Omega)$, hệ thống hóa phân lớp bài toán quyết định và bài toán tối ưu (P, NP, NP-đầy đủ, NP-Khó, #P-Khó) cùng khái niệm phép toán đơn định và không đơn định.

Chương này đi sâu vào phân tích vai trò của hàm mục tiêu submodular thông qua 03 bài toán chuẩn:

  1. Bài toán Phủ tập hợp (Set Cover - SC): Thuật toán tham lam đạt tỷ lệ xấp xỉ $1 + \ln n$ (Thuật toán 1).
  2. Bài toán Phủ tập hợp có trọng số (Weighted Set Cover - WSC): Thuật toán tham lam lựa chọn tập con tối đa hóa tỷ số $\Delta_S f(C') / w(S)$ đạt tỷ lệ xấp xỉ $1 + \ln n$ (Thuật toán 2).
  3. Bài toán Phủ cực đại (Maximum Coverage - MC): Khuller et al. [46] chứng minh thuật toán tham lam đạt tỷ lệ tối ưu $1 - 1/e$ (Thuật toán 3).

Bên cạnh đó, chương phân tích phương pháp Monte-Carlo trong bài toán tìm cực đại hàm mục tiêu trên miền giới nội và bài toán ước lượng kỳ vọng biến ngẫu nhiên theo tiêu chuẩn $(\delta, \epsilon)$-xấp xỉ sử dụng bất đẳng thức Chernoff: $$\Pr[X - c\mu \ge \delta \cdot c\mu] \le \exp\left(-\frac{\delta^2}{2}\right)$$ Từ đó trình bày Thuật toán Luật dừng (Stopping Rule - Thuật toán 4) của Dagum et al. [27], làm tiền đề cho các kỹ thuật dừng trong thuật toán xấp xỉ ảnh hưởng. Cuối cùng, chương tổng quan về thuật toán heuristic cấu trúc (Thuật toán 5) và metaheuristic như giải thuật Memetic (Thuật toán 6), tối ưu bầy đàn (PSO) và thuật toán di truyền (GA).

Chương 3: Tối đa ảnh hưởng cạnh tranh với ràng buộc về thời gian và ngân sách

Chương 3 giải quyết bài toán Tối đa ảnh hưởng cạnh tranh tổng quát (BCIM). Sau khi chỉ ra các khiếm khuyết của các mô hình CLT trước đây (sử dụng luật TB-FP thiên vị một bên, không xét chi phí $c(u)$ và thời gian $\tau$), tác giả đề xuất:

  • Mô hình ngưỡng tuyến tính cạnh tranh ràng buộc thời gian (TCLT) với luật hòa theo trọng số tỷ lệ TB-WPP.
  • Mô hình Cạnh tranh cạnh trực tuyến (CLE) và chứng minh toán học sự tương đương giữa TCLT và CLE (Định lý 3.1).
  • Chứng minh tính chất bài toán: Hàm mục tiêu $I(S_A)$ trong bài toán BCIM không còn thỏa mãn tính chất submodular do sự cạnh tranh giữa hai đối thủ và việc tính toán $I(S_A)$ vẫn là #P-Khó.

Để giải quyết bài toán, luận án thiết lập các hàm chặn dưới $L(\cdot)$ và hàm chặn trên $U(\cdot)$ cho hàm mục tiêu $I(\cdot)$, phân tích các tham số lý thuyết phục vụ việc lấy mẫu ngẫu nhiên được tổng hợp tại Bảng 3.1 của luận án:

Ký hiệu Ý nghĩa tham số
$S_A, S_B$ Tập hạt giống của đối thủ $A$ và đối thủ $B$
$n_0$ Số đỉnh không thuộc tập hạt giống của $B$: $n_0 = n - |S_B|$
$I(\cdot), L(\cdot), U(\cdot)$ Số đỉnh bị ảnh hưởng bởi $A$, hàm chặn dưới và hàm chặn trên của $I(\cdot)$
$S^, S_L^, S_U^*$ Lời giải tối ưu của BCIM, lời giải tối ưu cực đại $L(\cdot)$ và cực đại $U(\cdot)$
$OPT, OPT_L, OPT_U$ Giá trị tối ưu: $OPT = I(S^)$, $OPT_L = L(S_L^)$, $OPT_U = U(S_U^*)$
$\Upsilon(\epsilon, \delta)$ Ngưỡng dừng: $1 + (1 + \epsilon)(2 + \frac{2}{3}\epsilon) \frac{\ln(2/\delta)}{\epsilon^2}$
$Cov_{\mathcal{R}}(S)$ Số tập mẫu LRR (hoặc URR) $R_j$ bị phủ bởi tập đỉnh $S$ trong họ mẫu $\mathcal{R}$
$k_{max}$ Số lượng đỉnh tối đa có thể chọn: $\max {k \mid \exists S_A \subseteq V, |S_A| = k, c(S_A) \le L}$
$\alpha, \beta$ Các hệ số xác suất: $\alpha = (1 - 1/\sqrt{e})\sqrt{\ln(2/\delta)}$, $\beta = (1 - 1/\sqrt{e})\sqrt{\ln(2/\delta) + \ln \binom{n}{k_{max}}}$
$N(\epsilon, \delta)$ Số lượng mẫu giới hạn: $\frac{2n(\alpha + \beta)^2}{\epsilon^2 OPT_U}$

Dựa trên các phân tích trên, tác giả đề xuất thuật toán xấp xỉ ngẫu nhiên SPBA cho bài toán BCIM. Luận án cũng mở rộng phân tích bài toán BCIM trên mô hình Ngưỡng tuyến tính cạnh tranh xác định (DCLT). Thực nghiệm chứng minh SPBA hoạt động hiệu quả và có thể mở rộng trên các đồ thị mạng xã hội thực tế có quy mô hàng triệu đỉnh và cạnh.

Chương 4: Hạn chế tối đa ảnh hưởng của một tập nguồn phát tán thông tin sai lệch cho trước với ràng buộc về thời gian và ngân sách

Chương 4 nghiên cứu bài toán Hạn chế tối đa thông tin sai lệch (MMR) - một biến thể của bài toán IB. Bài toán đặt ra yêu cầu tìm tập nút cần loại bỏ hoặc cách ly với ngân sách chi phí giới hạn và bước thời gian lan truyền cho trước để giảm thiểu tối đa sự lây lan của thông tin sai lệch từ một tập nguồn $S$ đã biết.

Nội dung chính của chương bao gồm:

  • Xây dựng mô hình bài toán MMR trên mô hình ngưỡng tuyến tính mở rộng và mô hình ngưỡng tuyến tính xác định.
  • Phân tích tính chất toán học và độ phức tạp tính toán của bài toán MMR.
  • Đề xuất các thuật toán xấp xỉ lý thuyết gồm: Thuật toán xấp xỉ thời gian đa thức đầy đủ FPTAS (Fully Polynomial-Time Approximation Scheme), thuật toán IGA và thuật toán SG.
  • Đề xuất thuật toán heuristic PR-DAG dựa trên đồ thị có hướng không chu trình để xử lý mạng quy mô lớn.
  • Đánh giá thực nghiệm so sánh chất lượng lời giải và thời gian chạy của các thuật toán đề xuất trên các bộ dữ liệu mạng xã hội thực tế.

Chương 5: Hạn chế thông tin sai lệch có chủ đích

Chương 5 nghiên cứu bài toán Hạn chế thông tin sai lệch có chủ đích (Targeted Misinformation Blocking - TMB). Khác với bài toán MMR ở Chương 4 (cố định ngân sách chi phí để cực đại hóa mức độ ngăn chặn), bài toán TMB đặt ra mục tiêu ngược lại: tìm tập đỉnh có quy mô nhỏ nhất (hoặc chi phí thấp nhất) để loại bỏ ra khỏi mạng sao cho số người dùng không bị ảnh hưởng bởi thông tin sai lệch đạt tối thiểu một ngưỡng $\gamma$ cho trước.

Nội dung chính của chương bao gồm:

  • Mô hình hóa toán học bài toán TMB và chứng minh độ khó của bài toán trên hai mô hình lan truyền cơ bản là Bậc độc lập (IC) và Ngưỡng tuyến tính (LT).
  • Đề xuất hai thuật toán giải quyết bài toán: Thuật toán STMB-IC (trên mô hình IC) và thuật toán STMB-LT (trên mô hình LT).
  • Tiến hành thực nghiệm trên các tập dữ liệu mạng xã hội thực tế có quy mô hàng trăm nghìn đỉnh, chỉ ra tính khả thi và hiệu quả của các giải thuật STMB-IC và STMB-LT.

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

1. Đóng góp về mặt lý luận và mô hình hóa

  • Luận án đã đề xuất và định nghĩa 03 bài toán tối ưu tổ hợp mới mang tính ứng dụng thực tiễn cao trên MXHTT: bài toán Tối đa ảnh hưởng cạnh tranh tổng quát (BCIM), bài toán Hạn chế tối đa thông tin sai lệch (MMR) và bài toán Hạn chế thông tin sai lệch có chủ đích (TMB).
  • Đề xuất mô hình Ngưỡng tuyến tính cạnh tranh ràng buộc thời gian (TCLT) với quy tắc hòa theo trọng số tỷ lệ TB-WPP, phản ánh chính xác hơn sự cạnh tranh giữa các luồng thông tin dựa trên mức độ thân thiết của các mối quan hệ; đồng thời xây dựng mô hình Cạnh trực tuyến cạnh tranh (CLE) và chứng minh toán học sự tương đương giữa hai mô hình (Định lý 3.1).
  • Mở rộng phân tích các bài toán trên các mô hình xác định và mô hình ngưỡng tuyến tính mở rộng (DCLT, Extended LT); phân tích và chứng minh độ phức tạp tính toán (NP-Khó, #P-Khó) cũng như cấu trúc hàm mục tiêu (submodular, supermodular, phi-submodular, cận trên $U(\cdot)$, cận dưới $L(\cdot)$).

2. Đóng góp về mặt thuật toán và giải pháp thực tiễn

  • Thiết kế thuật toán xấp xỉ ngẫu nhiên SPBA cho bài toán BCIM, có khả năng mở rộng xử lý đồ thị mạng xã hội quy mô hàng triệu đỉnh và cạnh.
  • Thiết kế các thuật toán xấp xỉ FPTAS, IGA, SG và thuật toán heuristic PR-DAG cho bài toán MMR; thiết kế các thuật toán STMB-IC và STMB-LT cho bài toán TMB với khả năng thực thi trên đồ thị hàng trăm nghìn đỉnh.
  • Các giải pháp đề xuất cung cấp cơ sở kỹ thuật cho các doanh nghiệp xây dựng chiến lược tiếp thị sản phẩm cạnh tranh tối ưu hóa theo ngân sách và thời gian; đồng thời cung cấp công cụ cho các nhà quản trị mạng xã hội và cơ quan quản lý để kiểm soát, ngăn chặn sự phát tán của tin giả, virus và các thông tin sai lệch với chi phí tối thiểu.

3. Công bố khoa học

Các kết quả nghiên cứu của luận án đã được công bố qua 07 công trình khoa học, bao gồm 03 bài báo trên các tạp chí quốc tế chuyên ngành thuộc danh mục SCIE và 04 bài báo trên kỷ yếu hội nghị quốc tế có bình duyệt thuộc danh mục SCOPUS:

  • Tạp chí SCIE (03 bài):
    1. Applied Sciences (Section Computing and Artificial Intelligence), năm 2019 (kết quả bài toán BCIM).
    2. Journal of Combinatorial Optimization, năm 2018 (kết quả bài toán MMR).
    3. Journal of Combinatorial Optimization, năm 2019 (kết quả bài toán TMB).
  • Hội nghị quốc tế SCOPUS (04 bài):
    1. Symposium on Information and Communication Technology (SoICT), năm 2017.
    2. Asian Conference on Intelligent Information and Database Systems (ACIIDS), năm 2018.
    3. Computational Data & Social Networks (CSoNet), năm 2018.
    4. IEEE-RIVF International Conference on Computing and Communication Technologies (RIVF), năm 2019.

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

Dựa trên nội dung văn bản luận án, các hạn chế và hướng mở rộng nghiên cứu được xác định như sau:

  • Mô hình hóa thời gian: Quá trình lan truyền trong luận án chủ yếu được xây dựng trên mô hình thời gian rời rạc theo từng bước bước $t = 0, 1, \dots, \tau$. Trong thực tế, quá trình truyền tin trên mạng xã hội diễn ra liên tục theo thời gian thực (Continuous-time). Hướng nghiên cứu tiếp theo là mở rộng bài toán BCIM, MMR và TMB sang các mô hình Continuous-Time IC/LT.
  • Tính chất động của mạng: Đồ thị mạng xã hội $G = (V, E)$ trong các bài toán được giả định là đồ thị tĩnh với cấu trúc đỉnh và cạnh không đổi trong suốt quá trình lan truyền. Hướng nghiên cứu mở rộng cần xem xét bài toán trên mạng xã hội động (Dynamic/Evolving social networks), nơi các liên kết và người dùng liên tục xuất hiện hoặc mất đi.
  • Mô hình tối ưu hóa thích ứng: Luận án tập trung vào việc chọn toàn bộ tập hạt giống hoặc tập đỉnh cần loại bỏ một lần từ thời điểm ban đầu. Hướng tiếp cận tiếp theo có thể áp dụng mô hình tối ưu thích ứng (Adaptive Optimization), cho phép lựa chọn các đỉnh tuần tự dựa trên quan sát trạng thái lan truyền thực tế ở các bước trước đó.
  • Tối ưu hóa số lượng mẫu ngẫu nhiên: Việc tính toán hàm mục tiêu là #P-Khó đòi hỏi sinh số lượng mẫu đồ thị trực tuyến lớn. Việc tiếp tục cải tiến các kỹ thuật lấy mẫu nhằm giảm chặn trên của số mẫu cần thiết mà vẫn bảo đảm tỷ lệ xấp xỉ lý thuyết sẽ giúp tăng tốc độ thực thi của thuật toán trên các mạng có quy mô lớn hơn nữa.

Giá trị tham khảo

Luận án là tài liệu tham khảo hữu ích cho các nhóm đối tượng:

  • Nghiên cứu sinh, học viên cao học và giảng viên chuyên ngành Khoa học máy tính, Toán tin ứng dụng và Tối ưu tổ hợp: Chương 1 và Chương 2 cung cấp hệ thống kiến thức toàn diện về lý thuyết độ phức tạp tính toán, các mô hình lan truyền thông tin ngẫu nhiên (LT, IC, CLT), mô hình cạnh trực tuyến, lý thuyết hàm submodular và phương pháp chứng minh tỷ lệ xấp xỉ thông qua kỹ thuật lấy mẫu Monte-Carlo và luật dừng.
  • Các nhà nghiên cứu trong lĩnh vực Phân tích mạng xã hội (Social Network Analysis - SNA): Khung mô hình TCLT cùng luật hòa TB-WPP và phương pháp tương đương CLE tại Chương 3 cung cấp một công cụ lý thuyết để mô phỏng và phân tích các tương tác cạnh tranh đa đối thủ trên cấu trúc mạng phức tạp.
  • Chuyên gia phân tích dữ liệu và người làm chính sách, an ninh thông tin: Chương 4 và Chương 5 cung cấp các mô hình toán học và thuật toán cụ thể (MMR, TMB, STMB-IC, STMB-LT) phục vụ trực tiếp cho việc hoạch định chính sách kiểm soát tin sai lệch, khoanh vùng dịch bệnh hoặc mã độc trên các mạng lưới truyền thông với chi phí tối thiểu.

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

1. Luật hòa theo trọng số tỷ lệ (TB-WPP) đề xuất trong Chương 3 khác biệt như thế nào so với luật TB-PP trước đó?

Luật TB-PP truyền thống [19] xác định xác suất kích hoạt của đỉnh $v$ dựa thuần túy trên số lượng đỉnh hàng xóm đi vào đang kích hoạt bởi mỗi đối thủ: $$\frac{|A_t(v)|}{|A_t(v)| + |B_t(v)|}$$ Ngược lại, luật TB-WPP do luận án đề xuất tính toán xác suất kích hoạt dựa trên tổng trọng số tương tác của các liên kết từ các đỉnh hàng xóm đi vào: $$\frac{\sum_{u \in N_{in}(v) \cap A_{t-1}} w_A(u, v)}{\sum_{u \in N_{in}(v) \cap A_{t-1}} w_A(u, v) + \sum_{u \in N_{in}(v) \cap B_{t-1}} w_B(u, v)}$$ Quy tắc này phản ánh đúng thực tế rằng ảnh hưởng giữa các cá nhân phụ thuộc vào mức độ thân thiết (thể hiện qua trọng số liên kết) chứ không chỉ đơn thuần là số lượng người tác động.

2. Vì sao việc tính toán hàm mục tiêu trong các bài toán lan truyền thông tin lại là rào cản tính toán lớn?

Theo các chứng minh của Chen et al. [21, 22], việc tính toán chính xác hàm ảnh hưởng $\sigma(S)$ trên cả hai mô hình ngẫu nhiên cơ bản LT và IC là bài toán thuộc lớp #P-Khó. Do không gian trạng thái bùng nổ theo cấp số mũ, việc tính toán trực tiếp giá trị kỳ vọng không thể thực hiện được trong thời gian đa thức trên các mạng quy mô lớn, buộc các nhà nghiên cứu phải sử dụng mô phỏng Monte-Carlo hoặc các kỹ thuật xấp xỉ qua mô hình cạnh trực tuyến (Live-edge).

3. Bài toán BCIM khác biệt như thế nào so với bài toán Tối đa hóa ảnh hưởng cạnh tranh (CIM) truyền thống?

Bài toán CIM truyền thống [8] chỉ tìm tập hạt giống $S_A$ với số lượng cố định $|S_A| \le k$ để cực đại hóa ảnh hưởng và thường giả định một bên chiếm ưu thế trong luật cạnh tranh. Bài toán BCIM tổng quát hóa bài toán CIM bằng cách tích hợp đồng thời 03 yếu tố thực tế: gắn chi phí riêng $c(u) \ge 0$ cho từng nút với tổng ngân sách không vượt quá $L$; giới hạn thời gian lan truyền trong $\tau$ bước; và áp dụng luật cạnh tranh công bằng TB-WPP dựa trên trọng số liên kết.

4. Điểm khác biệt căn bản giữa hai bài toán ngăn chặn thông tin sai lệch MMR (Chương 4) và TMB (Chương 5) là gì?

Hai bài toán có định hướng mục tiêu tối ưu ngược nhau:

  • Bài toán MMR (Maximizing Misinformation Restriction) tối ưu hóa hàm mục tiêu theo ngân sách cho trước: với một mức chi phí giới hạn và thời gian xác định, tìm phương án can thiệp để giảm tối đa số người bị ảnh hưởng bởi tin sai lệch.
  • Bài toán TMB (Targeted Misinformation Blocking) tối ưu hóa chi phí theo mục tiêu định lượng cho trước: tìm tập nút can thiệp có số lượng hoặc chi phí nhỏ nhất để bảo đảm số người không bị ảnh hưởng bởi tin sai lệch đạt tối thiểu một ngưỡng an toàn $\gamma$ xác định.

5. 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 nào?

Toàn bộ các đóng góp chính của luận án đã được bình duyệt và công bố tại 03 bài báo trên các tạp chí quốc tế chuyên ngành thuộc danh mục SCIE (tạp chí Applied Sciences năm 2019, tạp chí Journal of Combinatorial Optimization năm 2018 và năm 2019) cùng 04 bài báo trên các kỷ yếu hội nghị quốc tế thuộc danh mục SCOPUS (hội nghị SoICT 2017, ACIIDS 2018, CSoNet 2018 và IEEE-RIVF 2019).

Kết luận

Luận án "Một số bài toán tối ưu trên mạng xã hội" là một công trình nghiên cứu hoàn chỉnh thuộc chuyên ngành Khoa học máy tính, tập trung giải quyết các thách thức tối ưu tổ hợp NP-Khó và #P-Khó trong lĩnh vực lan truyền và kiểm soát thông tin trên mạng xã hội trực tuyến. Bằng việc tích hợp các ràng buộc thực tế về chi phí, ngân sách và thời gian, tác giả đã xây dựng các bài toán và mô hình mở rộng có giá trị lý thuyết như BCIM, MMR, TMB cùng mô hình TCLT với luật hòa TB-WPP. Các thuật toán xấp xỉ và heuristic được đề xuất (SPBA, FPTAS, IGA, SG, PR-DAG, STMB-IC, STMB-LT) đều có chứng minh toán học chặt chẽ và được kiểm chứng hiệu quả thực nghiệm trên các tập dữ liệu mạng quy mô lớn lên tới hàng triệu đỉnh và cạnh. Các kết quả công bố trên 03 tạp chí SCIE và 04 kỷ yếu hội nghị SCOPUS khẳng định tính học thuật và giá trị ứng dụng của luận án trong phân tích mạng xã hội, tiếp thị số và an toàn thông tin.