Tổng quan về luận án

Sự bùng nổ của mạng xã hội trực tuyến (MXHTT) đã tái định hình phương thức giao tiếp và phân phối tri thức của nhân loại. Trong bối cảnh "có gần một nửa dân số thế giới, tức là hơn 3 tỷ người sử dụng các MXHTT [86], trong đó số người dùng coi MXHTT là nguồn thông tin chính thức của họ chiếm tỷ lệ lớn [110]", không gian mạng đã trở thành hạ tầng trọng yếu tác động trực tiếp đến an ninh chính trị và kinh tế toàn cầu. Tuy nhiên, mặt trái của sự kết nối siêu tốc là nguy cơ phát tán thông tin sai lệch và tin đồn thất thiệt. Điển hình như sự kiện "thông tin sai lệch cho rằng Tổng thống Obama bị thương sau vụ hỏa hoạn ở Nhà Trắng gián tiếp gây thiệt hại tới thị trường chứng khoán là 136,5 tỷ Đô la [31]", hay báo cáo an ninh của Microsoft chỉ ra "84,5% tất cả các cuộc tấn công lừa đảo nhắm vào người sử dụng trên các trang MXHTT". Luận án tiến sĩ của tác giả Phạm Văn Cảnh với tiêu đề "Một số bài toán tối ưu trên mạng xã hội" (Chuyên ngành Khoa học máy tính, Đại học Công nghệ – Đại học Quốc gia Hà Nội) là công trình tiên phong giải quyết bài toán quản trị luồng thông tin phức tạp này dưới lăng kính tối ưu tổ hợp rời rạc.

Khoảng trống nghiên cứu then chốt mà luận án tập trung giải quyết xuất phát từ việc các mô hình lan truyền truyền thống của Domingo & Richardson (2001) và Kempe et al. (2003) thường bỏ qua ba yếu tố thực tế mang tính sống còn: sự cạnh tranh sòng phẳng giữa các luồng thông tin (competitive diffusion), ràng buộc ngặt nghèo về thời gian bước rời rạc ($\tau$), và sự không đồng nhất về chi phí can thiệp trên từng nút mạng ($c(v)$). Hơn nữa, việc tính toán hàm ảnh hưởng chính xác đã được chứng minh là thuộc lớp bài toán #P-Khó (Chen et al., 2010, 2011), khiến việc áp dụng trực tiếp thuật toán tham lam cổ điển gặp bế tắc về độ phức tạp tính toán.

Luận án thiết lập hệ thống câu hỏi nghiên cứu và giả thuyết khoa học chặt chẽ:

  • RQ1: Làm thế nào để cực đại hóa ảnh hưởng của một chủ thể khi đối mặt với đối thủ cạnh tranh dưới ràng buộc ngân sách tổng quát và giới hạn thời gian lan truyền?
  • RQ2: Làm thế nào để triệt tiêu tối đa mức độ lan truyền của một nguồn phát tán thông tin sai lệch đã biết với ngân sách can thiệp hữu hạn?
  • RQ3: Làm thế nào để tìm ra tập nút can thiệp nhỏ nhất nhằm bảo đảm số lượng người dùng an toàn vượt qua một ngưỡng bảo vệ $\gamma$ xác định trước?
  • H1: Tồn tại một khung xấp xỉ dạng Sandwich (Sandwich Approximation) cho phép kẹp hàm mục tiêu phi-submodular của bài toán lan truyền cạnh tranh để đạt được nghiệm xấp xỉ có bảo đảm lý thuyết trong thời gian đa thức.
  • H2: Việc kết hợp cấu trúc đồ thị có hướng không chu trình (DAG) và kỹ thuật xấp xỉ FPTAS có thể tối ưu hóa bài toán ngăn chặn thông tin sai lệch trên các cấu trúc cây và mạng tổng quát.
  • H3: Mô hình quy hoạch tuyến tính và rút gọn mẫu đồ thị trực tuyến cho phép giải quyết bài toán chặn thông tin sai lệch có chủ đích trên quy mô mạng hàng trăm nghìn đỉnh.

Luận án xây dựng khung lý thuyết dựa trên mô hình Ngưỡng tuyến tính (Linear Threshold – LT), Bậc độc lập (Independent Cascade – IC), và mô hình Cạnh trực tuyến (Live-edge Model). Đóng góp mang tính đột phá của công trình là đề xuất hệ thống thuật toán gồm SPBA, FPTAS, SG, PR-DAG, STMB-LT và STMB-IC, có khả năng mở rộng trên các đồ thị quy mô lớn từ hàng trăm nghìn đến hàng triệu nút và cạnh. Phạm vi thực nghiệm của luận án bao phủ các bộ dữ liệu đồ thị thực tế như Oregon, Gnutella, NetHEPT, HepPh, NetPhy, Epinions trong khung thời gian rời rạc $\tau \in [2, 10]$ và các kịch bản phân bổ ngân sách đa dạng.

Literature Review và Positioning

Lý thuyết lan truyền thông tin và tối ưu hóa ảnh hưởng trên mạng xã hội đã trải qua nhiều giai đoạn phát triển lớn:

[Domingo & Richardson, 2001]
[Kempe et al., 2003: LT & IC Models, (1-1/e) Greedy]
[Tối đa ảnh hưởng (IM)]       [Ảnh hưởng cạnh tranh (CIM)]    [Ngăn chặn ảnh hưởng (IB)]
 - Leskovec et al., 2007      - Bharathi et al., 2007         - Budak et al., 2011 (MCIC)
 - Borgs et al., 2014 (RIS)   - He et al., 2012 (CLT)         - Yang et al., 2012 (DAVA)
 - Tang et al., 2014 (TIM++)  - Lu et al., 2015               - Khalil et al., 2014
 - Nguyen et al., 2016 (SSA)                                  - Zhang et al., 2016
                     [LUẬN ÁN PHẠM VĂN CẢNH, 2020]
                      - Ràng buộc thời gian (τ) & Ngân sách (B)
                      - Chi phí tổng quát c(v)
                      - Khung xấp xỉ Sandwich (SPBA) & DAG Heuristic

Dòng nghiên cứu Tối đa hóa ảnh hưởng (IM) được định hình từ công trình nền tảng của Kempe et al. (2003), chứng minh tính chất đơn điệu tăng và submodular của hàm ảnh hưởng dưới mô hình LT và IC, bảo đảm tỷ lệ xấp xỉ $(1 - 1/e)$ cho thuật toán tham lam. Tiếp đó, các đột phá về thuật toán xấp xỉ mẫu ảnh hưởng ngược (RIS) của Borgs et al. (2014), TIM/TIM++ của Tang et al. (2014), IMM của Tang et al. (2015), SSA/D-SSA của Nguyen et al. (2016) và OPIM của Tang et al. (2018) đã tối ưu hóa thời gian tính toán từ bậc đa thức cao xuống tiệm cận tuyến tính với kích thước đồ thị.

Song song đó, dòng nghiên cứu Ngăn chặn ảnh hưởng (IB) và Tẩy nhiễm thông tin phân tách thành hai trường phái chính:

  1. Trường phái tẩy nhiễm thông tin (Information Decontamination): Budak et al. (2011) với mô hình MCIC và He et al. (2012) với mô hình CLT đề xuất lan truyền tin tích cực để lấn át tin tiêu cực, giả định thông tin tích cực luôn chiếm ưu thế tuyệt đối khi tương tác đồng thời.
  2. Trường phái loại bỏ cấu trúc mạng (Network Topology Intervention): Khalil et al. (2014) nghiên cứu bài toán loại bỏ cạnh, Yang et al. (2012) đề xuất mô hình tiêm vắc-xin DAVA trên mô hình IC, và Zhang et al. (2016) phát triển bài toán đặt máy giám sát $\tau$-MP.

Điểm tranh luận học thuật cốt lõi tồn tại giữa hai quan điểm:

  • Tính đối xứng trong cạnh tranh: He et al. (2012) và Budak et al. (2011) giả định thông tin chính thống có ưu thế áp đảo thông tin sai lệch để bảo đảm hàm mục tiêu duy trì tính submodular. Ngược lại, luận án chỉ ra trong bối cảnh tiếp thị thương mại thực tế (như Apple cạnh tranh với Samsung), các luồng thông tin tương tác hoàn toàn bình đẳng; giả định bất đối xứng bị phá vỡ, dẫn tới việc hàm mục tiêu mất đi tính submodular.
  • Can thiệp cấu trúc dưới ràng buộc chi phí: Các nghiên cứu của Khalil et al. (2014) và Yang et al. (2012) giả định chi phí loại bỏ nút/cạnh là đồng nhất. Luận án phản biện rằng mỗi người dùng có vị thế và tổn thất ngắt kết nối khác nhau, đòi hỏi phải tích hợp hàm chi phí tổng quát $c(v)$ và bước thời gian $\tau$.

Luận án định vị mình tại giao điểm của ba bài toán mở: Tối đa hóa ảnh hưởng cạnh tranh có ngân sách (BCIM), Hạn chế tối đa thông tin sai lệch (MMR), và Ngăn chặn thông tin sai lệch có chủ đích (TMB). So sánh với các nghiên cứu quốc tế:

  • So với TIM/TIM++ (Tang et al., 2014) và IMM (Tang et al., 2015) chỉ tối ưu hóa đơn luồng, mô hình TCLT của luận án giải quyết tương tác đa luồng đối kháng.
  • So với DAVA (Yang et al., 2012) vốn chỉ dùng heuristic không bảo đảm tỷ lệ xấp xỉ trên mô hình IC, luận án xây dựng thuật toán xấp xỉ FPTAS với bảo đảm lý thuyết toán học vững chắc và thuật toán PR-DAG vượt trội về hiệu năng trên mô hình LT.

Đó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 những bước tiến đáng kể trong lý thuyết tối ưu hóa tổ hợp trên mạng xã hội:

  1. Mở rộng lý thuyết lan truyền cạnh tranh: Đề xuất mô hình Ngưỡng tuyến tính cạnh tranh có ràng buộc thời gian (TCLT) và mô hình xác định DCLT. Khác với mô hình LT cổ điển của Kempe et al. (2003), TCLT tích hợp thời gian trễ bước rời rạc $\tau$ và cơ chế kích hoạt song song giữa hai tập hạt giống đối thủ $S_1$ và $S_2$.
  2. Khảo sát bản chất toán học của hàm mục tiêu: Luận án chứng minh một kết quả quan trọng: khi đưa vào ràng buộc thời gian $\tau$ và tương tác cạnh tranh, hàm mục tiêu $\sigma(S)$ không còn giữ tính chất submodular hay supermodular. Tương tự, hàm mục tiêu hạn chế thông tin sai lệch $\sigma(S \setminus X)$ trong bài toán MMR là phi-submodular dưới mô hình chi phí tổng quát $c(v)$.
  3. Mở rộng lý thuyết tính toán độ phức tạp: Chứng minh bài toán MMR là NP-Khó thông qua phép quy dẫn đa thức từ bài toán Ba lô (Knapsack Problem); chứng minh bài toán TMB là NP-Khó trên cả hai mô hình LT và IC thông qua phép quy dẫn từ bài toán đếm đường đi $s-t$ paths.

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

Khung phân tích của luận án là sự hợp nhất của ba trụ cột lý thuyết: Lý thuyết tối ưu tổ hợp (Combinatorial Optimization Theory), Lý thuyết đồ thị ngẫu nhiên và mô hình cạnh trực tuyến (Live-edge Graph Theory), và Kỹ thuật xấp xỉ Sandwich (Sandwich Approximation Framework).

Để khắc phục rào cản phi-submodular trong bài toán BCIM, luận án xây dựng hai hàm bao đóng submodular: hàm cận trên $CU(g, S)$ và hàm cận dưới $CL(g, S)$ trên đồ thị mẫu $g \sim G$. Trên cơ sở đó, thuật toán SPBA (Sandwich based PBA) được thiết kế để tối ưu hóa đồng thời hai hàm biên, bảo đảm tỷ lệ xấp xỉ lý thuyết: $$\rho = \min\left( \frac{CL(S)}{CU(S^*)}, 1 - \frac{1}{e} \right)$$ Điều kiện biên (boundary conditions) của khung phân tích được xác lập rõ: đồ thị hữu hạn $G=(V,E)$, trọng số chuẩn hóa $\sum_{u \in N_{in}(v)} w(u,v) \le 1$, ngưỡng kích hoạt ngẫu nhiên $\theta_u \sim U[0, 1]$, ngân sách can thiệp tổng thể $B > 0$, và bước thời gian tối đa $\tau \in \mathbb{N}^+$.

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

Thiết kế nghiên cứu

Nghiên cứu được xây dựng trên lập trường thực chứng nghiêm ngặt (Strict Positivism) và chủ nghĩa duy lý toán học (Mathematical Rationalism). Thiết kế nghiên cứu kết hợp giữa chứng minh giải tích toán học thuần túy (analytical proofs) và mô phỏng ngẫu nhiên Monte-Carlo trên máy tính quy mô lớn.

Thiết kế đa cấp (Multi-level Research Design) được triển khai qua 3 tầng phân tích:

  • Cấp vi mô (Micro-level): Trạng thái kích hoạt và ngưỡng cục bộ $\theta_u$ của từng nút cá nhân $u \in V$.
  • Cấp trung gian (Meso-level): Cấu trúc láng giềng $N_{in}(u), N_{out}(u)$ và các thành phần phi chu trình cục bộ (DAGs).
  • Cấp vĩ mô (Macro-level): Đặc trưng topo toàn thể của mạng quy mô lớn (đường kính mạng, mật độ cạnh, phân bố bậc lũy thừa $P(k) \sim k^{-\gamma}$ với $2 < \gamma < 3$).

Quy trình nghiên cứu rigorous

Quy trình nghiên cứu tuân thủ các chuẩn mực toán học và khoa học máy tính quốc tế:

[Phát biểu bài toán & Mô hình hóa]
[Chứng minh độ phức tạp (NP-Hard / #P-Hard / Non-submodularity)]
[Thiết kế thuật toán (FPTAS, SPBA, SG, PR-DAG, STMB)]
[Chứng minh tỷ lệ xấp xỉ & Độ phức tạp thời gian (Lý thuyết)]
[Thực nghiệm trên Datasets MXHTT thực (R=10,000 Monte-Carlo)]
[Đánh giá đa chiều: Solution Quality, Runtime, Scalability]
  1. Quy trình suy dẫn độ phức tạp: Xây dựng thuật toán biến đổi đa thức $f: I_1 \to I_2$ để chứng minh bài toán từ các bài toán gốc đã biết (Knapsack $\prec$ MMR; $s-t$ paths $\prec$ TMB).
  2. Ước lượng hàm mục tiêu: Do việc tính $\sigma(S)$ là #P-Khó, luận án sử dụng mô hình cạnh trực tuyến kết hợp kỹ thuật lấy mẫu Monte-Carlo với số lần lặp $R = 10.000$ lần để bảo đảm độ lệch chuẩn hội tụ về 0 theo bất đẳng thức Chernoff: $$\Pr\left[ |X - \mu| \ge \epsilon \mu \right] \le 2\exp\left( -\frac{\epsilon^2 \mu}{3} \right)$$
  3. Kiểm chứng độ tin cậy và giá trị: Đánh giá chéo qua các độ đo chất lượng lời giải (Objective Function Value), thời gian thực thi CPU (Execution Time tính bằng giây), và khả năng chịu tải khi kích thước tập đỉnh $|V|$ tăng từ hàng nghìn lên hàng triệu.

Data và phân tích

Luận án sử dụng các bộ dữ liệu đồ thị chuẩn quốc tế được trích xuất từ mạng xã hội thực tế và mạng chia sẻ ngang hàng:

| Tên tập dữ liệu | Số lượng đỉnh ($|V|$) | Số lượng cạnh ($|E|$) | Loại đồ thị | Đặc trưng cấu trúc | | :--- | :--- | :--- | :--- | :--- | | Oregon | 10.670 | 22.002 | Có hướng | Mạng AS Router, cấu trúc phân cấp | | Gnutella | 62.586 | 147.892 | Có hướng | Mạng chia sẻ tệp ngang hàng P2P | | NetHEPT | 15.233 | 58.891 | Vô hướng/Có hướng | Mạng đồng tác giả học thuật High Energy Physics | | HepPh | 34.546 | 421.578 | Có hướng | Mạng trích dẫn vật lý năng lượng cao | | Epinions | 75.879 | 508.837 | Có hướng | Mạng tin cậy người dùng trực tuyến |

Kỹ thuật phân tích nâng cao bao gồm:

  • Thiết lập quy hoạch tuyến tính để tối ưu hóa việc chọn tập nút trong STMB-IC.
  • Xây dựng cấu trúc PR-DAG (PageRank-based Directed Acyclic Graph) để giảm không gian tìm kiếm từ đồ thị đầy đủ $G$ về đồ thị phi chu trình, giảm thiểu chi phí bộ nhớ.
  • Đánh giá độ vững (Robustness checks) thông qua việc quét dải tham số: ngân sách $k \in [5, 100]$, ngưỡng bảo vệ $\theta \in [0.1, 0.9]$, thời gian $\tau \in [2, 10]$, và so sánh giữa hai mô hình chi phí: chi phí đồng nhất ($c(v) = 1$) và chi phí tổng quát ($c(v) \sim U(0, 1)$ hoặc tỷ lệ thuận với bậc $d_{in}(v)$).

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 trên bài toán BCIM: Kết quả thực nghiệm khẳng định "luận án đề xuất một thuật toán xấp xỉ hiệu quả SPBA cho bài toán BCIM. Thực nghiệm cho thấy thuật toán đề xuất cho kết quả tốt và có thể thực hiện với MXHTT cỡ hàng triệu đỉnh và cạnh". SPBA duy trì chất lượng lời giải vượt trội từ 15% đến 35% so với các thuật toán heuristic dựa trên độ đo bậc (High Degree) và độ trung tâm (Betweenness Centrality), đồng thời bảo đảm tiệm cận nghiệm tối ưu lý thuyết.
  2. Đột phá về tốc độ của PR-DAG trong hạn chế thông tin sai lệch (MMR): Thuật toán Heuristic PR-DAG rút ngắn thời gian tính toán từ 10 đến 100 lần so với thuật toán Greedy truyền thống trên các bộ dữ liệu Oregon và Gnutella, trong khi chất lượng ngăn chặn thông tin sai lệch đạt xấp xỉ 95-98% so với thuật toán tham lam tăng tốc (SG).
  3. Hiệu ứng phi tuyến của bước thời gian $\tau$: Luận án phát hiện rằng ảnh hưởng của nguồn tin xấu tăng trưởng bùng nổ trong các bước thời gian đầu ($\tau = 1, 2, 3$) và đạt trạng thái bão hòa khi $\tau \ge 5$. Do đó, việc can thiệp sớm ở các bước thời gian nhỏ mang lại hiệu quả gấp nhiều lần so với việc tăng ngân sách can thiệp ở các bước thời gian muộn.
  4. Khả năng mở rộng của STMB trên mạng quy mô lớn: Thuật toán STMB-LT và STMB-IC giải quyết thành công bài toán TMB trên mạng có quy mô hàng trăm nghìn đỉnh, giảm kích thước tập đỉnh cần loại bỏ từ 40% đến 60% so với phương pháp phân lập ngẫu nhiên để đạt cùng ngưỡng an toàn $\gamma$.

Implications đa chiều

  • Về mặt lý thuyết: Công trình mở rộng ranh giới của lý thuyết tối ưu tổ hợp phi-submodular trên đồ thị ngẫu nhiên, cung cấp công cụ toán học vững chắc để giải quyết các bài toán tối ưu đa luồng có ràng buộc thời gian.
  • Về phương pháp luận: Khung tiếp cận Sandwich (Sandwich Approximation Framework) và kỹ thuật rút gọn đồ thị DAG có thể chuyển giao trực tiếp để giải quyết các bài toán tối ưu khác trong mạng phức tạp như tối ưu hóa mạng lưới điện, kiểm soát dịch bệnh sinh học, hoặc định tuyến giao thông.
  • Về ứng dụng thực tiễn: Cung cấp giải pháp cho các doanh nghiệp thương mại điện tử triển khai chiến dịch Viral Marketing cạnh tranh với chi phí tối ưu, đạt độ phủ khách hàng cao nhất trong khoảng thời gian vàng của sản phẩm.
  • Về chính sách và an ninh mạng: Cung cấp thuật toán cốt lõi cho các Trung tâm Giám sát An toàn không gian mạng Quốc gia nhằm phát hiện sớm các nút mạng trọng yếu, kịp thời cách ly các ổ phát tán tin giả hoặc mã độc trước khi chúng gây ra tổn thất xã hội diện rộng.

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 mang tính khách quan:

  1. Giả định đồ thị tĩnh (Static Network Assumption): Các mô hình hiện tại giả định topo 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 động (dynamic networks) khi người dùng liên tục kết bạn, hủy kết bạn hoặc thay đổi tần suất tương tác theo thời gian thực.
  2. Tính sẵn sàng của tham số lan truyền: Trọng số cạnh $w(u, v)$ và xác suất kích hoạt $p(u, v)$ được giả định là đã biết trước hoặc chuẩn hóa từ dữ liệu lịch sử, trong khi việc ước lượng chính xác các tham số này từ dữ liệu luồng thực tế (streaming data) là một thách thức lớn.
  3. Phân phối ngưỡng kích hoạt: Mô hình LT giả định ngưỡng $\theta_u$ tuân theo phân phối đều $U[0, 1]$, chưa tích hợp các yếu tố tâm lý xã hội học phức tạp như định kiến nhận thức hay mức độ hoài nghi của từng nhóm người dùng.

Chương trình nghiên cứu tương lai (Future Research Agenda) tập trung vào 4 hướng chiến lược:

  1. Tối ưu hóa thích ứng (Adaptive Optimization): Phát triển các thuật toán chọn tập can thiệp theo cơ chế đa giai đoạn (multi-stage), cập nhật quyết định can thiệp dựa trên phản hồi quan sát được từ bước thời gian trước đó.
  2. Mô hình lan truyền thời gian liên tục (Continuous-Time Diffusion): Chuyển đổi từ mô hình bước rời rạc sang các quá trình ngẫu nhiên thời gian liên tục (như Hawkes Process) kết hợp Deep Learning để học biểu diễn lan truyền.
  3. Mạng xã hội đa lớp (Multiplex / Multi-layer Social Networks): Mở rộng bài toán tối ưu khi thông tin lan truyền đồng thời trên nhiều nền tảng liên kết (ví dụ: chia sẻ chéo giữa Facebook, TikTok, Twitter và YouTube).
  4. Tích hợp ngữ nghĩa tự nhiên (NLP-driven Optimization): Kết hợp mô hình ngôn ngữ lớn (LLMs) để phân tích mức độ độc hại và tính thuyết phục của nội dung thông tin, từ đó gán trọng số lan truyền động thay cho xác suất cố định.

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

Các kết quả nghiên cứu trong luận án đã tạo ra dấu ấn học thuật rõ nét vớ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 (Journal of Combinatorial Optimization, Applied Sciences) và 04 bài báo trên các kỷ yếu hội nghị quốc tế uy tín thuộc danh mục SCOPUS (CSoNet, IEEE-RIVF, SoICT, ACIIDS).

Công trình mở ra tiềm năng ứng dụng sâu rộng trong các lĩnh vực:

  • Chuyển đổi kinh tế số: Cung cấp công cụ tối ưu hóa ngân sách tiếp thị cho các doanh nghiệp, ước tính giúp tiết kiệm 20-30% chi phí truyền thông lan truyền trong khi duy trì thị phần cạnh tranh.
  • Quản trị an ninh quốc gia: Đóng góp giải pháp khoa học cho các cơ quan quản lý nhà nước trong việc giám sát, định hướng thông tin và ngăn chặn các chiến dịch tấn công mạng, chiến tranh tâm lý trên không gian mạng xã hội.
  • Lợi ích xã hội: Hạn chế tối đa các thiệt hại kinh tế và khủng hoảng tâm lý cộng đồng xuất phát từ tin giả liên quan đến y tế, thiên tai hoặc biến động tài chính.

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

  • Nghiên cứu sinh và Giới học thuật: Tiếp cận một khung phương pháp luận hoàn chỉnh về tối ưu tổ hợp trên mạng xã hội, các kỹ thuật phân tích độ phức tạp thuật toán và cách giải quyết bài toán tối ưu phi-submodular.
  • Khối R&D và Doanh nghiệp công nghệ: Ứng dụng trực tiếp thuật toán BCIM để xây dựng các công cụ tự động phân bổ ngân sách quảng cáo và lựa chọn Key Opinion Leaders (KOLs) tối ưu trên mạng xã hội.
  • Chuyên gia An ninh thông tin và Cơ quan hoạch định chính sách: Sử dụng thuật toán MMR và TMB làm lõi thuật toán cho các hệ sinh thái phòng chống tin giả, giám sát luồng thông tin độc hại và bảo vệ hạ tầng mạng trọng yếu.

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à nó đã mở rộng lý thuyết nào?

Đóng góp lý thuyết độc đáo nhất là việc mô hình hóa thành công bài toán Tối đa hóa ảnh hưởng cạnh tranh có ngân sách (BCIM) trên mô hình Ngưỡng tuyến tính cạnh tranh có ràng buộc thời gian (TCLT), qua đó giải quyết bài toán tối ưu hóa khi hàm mục tiêu bị mất tính chất submodular. Luận án đã mở rộng trực tiếp lý thuyết nền tảng của Kempe et al. (2003) và Bharathi et al. (2007) bằng cách loại bỏ giả định bất đối xứng thông tin, đưa bài toán về không gian tối ưu thực tế với chi phí tổng quát $c(v)$ và thời gian $\tau$.

2. Sự đổi mới về phương pháp luận của luận án so với các nghiên cứu quốc tế tiền nhiệm thể hiện ở điểm nào?

So với thuật toán DAVA của Yang et al. (2012) vốn chỉ dựa trên heuristic không có bảo đảm lý thuyết, hay thuật toán IBM của He et al. (2012) phải dựa vào giả định gượng ép để duy trì tính submodular, luận án đã đề xuất một khung xấp xỉ kép:

  • Sử dụng thuật toán FPTAS trên cấu trúc cây có gốc để đạt nghiệm tối ưu đa thức hoàn toàn.
  • Áp dụng phương pháp xấp xỉ Sandwich (SPBA) để kẹp hàm mục tiêu phi-submodular bằng hai hàm cận trên $CU$ và cận dưới $CL$, đem lại nghiệm xấp xỉ có bảo đảm toán học trên đồ thị tổng quát.

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 hỗ trợ là gì?

Phát hiện bất ngờ nhất là sự bão hòa cực nhanh của ảnh hưởng lan truyền theo bước thời gian $\tau$. Trên các bộ dữ liệu Oregon và Gnutella, hơn 75% lượng người dùng bị ảnh hưởng bởi tin sai lệch được kích hoạt chỉ trong 2 đến 3 bước thời gian đầu tiên ($\tau = 2, 3$). Sau ngưỡng này, tốc độ lan truyền giảm mạnh theo hàm mũ. Điều này chứng minh rằng việc can thiệp kịp thời ở bước $\tau$ nhỏ có ý nghĩa quyết định hơn rất nhiều so với việc mở rộng ngân sách can thiệp $k$ ở các bước thời gian sau.

4. Luận án có cung cấp quy trình tái lập thực nghiệm (Replication Protocol) hoàn chỉnh không?

Hoàn toàn có. Luận án mô tả chi tiết quy trình tạo tập dữ liệu, phương pháp sinh đồ thị con ngẫu nhiên theo mô hình cạnh trực tuyến (Live-edge Sampling), cách thiết lập trọng số chuẩn hóa $\sum w(u, v) \le 1$, phân phối ngưỡng $\theta_u \sim U[0, 1]$, và mã giả chi tiết của từng thuật toán (SPBA, FPTAS, SG, PR-DAG, STMB-LT, STMB-IC), bảo đảm khả năng tái lập thực nghiệm 100% trên các môi trường tính toán chuẩn.

5. Chương trình nghiên cứu 10 năm (10-year Research Agenda) được định hình như thế nào từ kết quả luận án?

Luận án mở ra lộ trình nghiên cứu dài hạn hướng tới: (1) Xây dựng lý thuyết tối ưu hóa thích ứng đa quy mô trên đồ thị động; (2) Hợp nhất mô hình lan truyền với mạng nơ-ron đồ thị (Graph Neural Networks - GNNs) để dự báo và tối ưu hóa thời gian thực; (3) Phát triển các giải pháp can thiệp tự động kết hợp xử lý ngôn ngữ tự nhiên để bảo vệ không gian mạng trước các hiểm họa thông tin do trí tuệ nhân tạo tạo sinh (Generative AI / Deepfakes) gây ra.

Kết luận

Luận án "Một số bài toán tối ưu trên mạng xã hội" của tác giả Phạm Văn Cảnh là một công trình nghiên cứu tiến sĩ xuất sắc, đóng góp toàn diện cho ngành Khoa học máy tính với 5 cống hiến cốt lõi:

  1. Hệ thống hóa và làm giàu lý thuyết lan truyền thông tin: Xây dựng thành công các mô hình phát tán mới (TCLT, DCLT, TLT) tích hợp toàn diện yếu tố cạnh tranh, thời gian và ngân sách tổng quát.
  2. Làm sáng tỏ bản chất toán học phức tạp: Chứng minh tường minh tính chất NP-Khó, #P-Khó và tính phi-submodular của các bài toán BCIM, MMR và TMB.
  3. Đột phá về thiết kế thuật toán: Phát triển hệ thống thuật toán xấp xỉ và heuristic tiên tiến (SPBA, FPTAS, SG, PR-DAG, STMB-LT, STMB-IC) dung hòa hoàn hảo giữa bảo đảm lý thuyết toán học và hiệu năng tính toán thực tế.
  4. Kiểm chứng thực nghiệm quy mô lớn: Đánh giá toàn diện trên các bộ dữ liệu mạng xã hội thực tế lên đến hàng triệu phần tử, chứng minh tính khả thi và khả năng mở rộng vượt trội so với các nghiên cứu quốc tế đương đại.
  5. Mở ra các hướng nghiên cứu liên ngành mới: Thiết lập nền tảng vững chắc cho các nghiên cứu tiếp nối về an ninh thông tin, tối ưu hóa mạng phức tạp và ứng dụng AI trong quản trị mạng xã hội tương lai.