Tổng quan về luận án

Luận án tiến sĩ "Một số bài toán tối ưu trên mạng xã hội" đi sâu vào các thách thức tối ưu hóa phức tạp nảy sinh từ sự phát triển vượt bậc của các Mạng xã hội trực tuyến (MXHTT). Trong bối cảnh khoa học máy tính và nghiên cứu học thuật về tính toán xã hội, nghiên cứu này mang tính tiên phong khi giải quyết các vấn đề cốt lõi của lan truyền thông tin (information diffusion) trên quy mô lớn, đặc biệt là các bài toán Tối đa ảnh hưởng (Influence Maximization - IM) và Ngăn chặn ảnh hưởng (Influence Blocking - IB). Luận án này không chỉ giải quyết các hạn chế về độ phức tạp tính toán của các phương pháp hiện có mà còn tích hợp các ràng buộc thực tế như ngân sách và thời gian, vốn thường bị bỏ qua trong các nghiên cứu trước đây.

Research gap SPECIFIC với citations từ literature:

Mặc dù lĩnh vực lan truyền thông tin trên MXHTT đã được nghiên cứu rộng rãi kể từ các công trình ban đầu của Kempe và các cộng sự [43], vẫn tồn tại những khoảng trống đáng kể. Các bài toán IM và IB, vốn thuộc lớp NP-Khó và việc tính toán hàm mục tiêu chính xác là #P-Khó [21, 22], gặp phải thách thức lớn về khả năng mở rộng khi áp dụng vào các MXHTT có quy mô hàng triệu người dùng và liên kết. Các nghiên cứu trước đây về tối đa ảnh hưởng cạnh tranh (Competitive Influence Maximization - CIM) thường giả định rằng một bên đối thủ có lợi thế, điều này không phản ánh đúng sự cạnh tranh công bằng trong tiếp thị sản phẩm trên thực tế. Hơn nữa, những mô hình này thường không xem xét các ràng buộc quan trọng như chi phí lựa chọn người dùng khác nhau và giới hạn thời gian lan truyền, một điểm yếu được luận án chỉ rõ (trang 24). Tương tự, trong bài toán ngăn chặn ảnh hưởng (IB), các nghiên cứu thường bỏ qua yếu tố chi phí và thời gian, hai yếu tố thiết yếu ảnh hưởng đến chiến lược ngăn chặn hiệu quả trong thế giới thực (trang 26). Cuối cùng, một khoảng trống quan trọng khác là việc thiếu các phương pháp xác định tập người dùng nhỏ nhất để loại bỏ nhằm đạt được một ngưỡng hạn chế thông tin sai lệch cụ thể (Targeted Misinformation Blocking - TMB), khác với mục tiêu tối đa hóa việc hạn chế thông tin sai lệch chung.

Research questions và hypotheses:

  1. RQ1: Làm thế nào để mô hình hóa và giải quyết bài toán tối đa ảnh hưởng cạnh tranh (BCIM) trên MXHTT với ràng buộc về ngân sách và thời gian, đồng thời đảm bảo sự công bằng trong cạnh tranh và khả năng mở rộng cho mạng lớn?
    • H1.1: Việc đề xuất mô hình ngưỡng tuyến tính cạnh tranh ràng buộc thời gian (TCLT) sẽ nắm bắt chính xác hơn quá trình lan truyền có sự cạnh tranh của các đối thủ, kể cả với chi phí khác nhau và thời gian lan truyền giới hạn.
    • H1.2: Thuật toán xấp xỉ SPBA, dựa trên các hàm xấp xỉ trên và dưới, có thể cung cấp lời giải chất lượng cao cho BCIM với độ phức tạp tính toán chấp nhận được trên MXHTT cỡ hàng triệu đỉnh và cạnh.
  2. RQ2: Làm thế nào để phát triển các thuật toán hiệu quả nhằm hạn chế tối đa thông tin sai lệch (MMR) trên MXHTT, có tính đến các ràng buộc về ngân sách và thời gian cho việc ngăn chặn?
    • H2.1: Mô hình ngưỡng tuyến tính mở rộng có thể được sử dụng để mô tả bài toán MMR với các ràng buộc ngân sách và thời gian.
    • H2.2: Các thuật toán xấp xỉ (FPTAS, IGA, SG) và heuristic (PR-DAG) có thể cung cấp các giải pháp hiệu quả cho bài toán MMR, bao gồm cả trong trường hợp mô hình ngưỡng tuyến tính xác định.
  3. RQ3: Phương pháp nào có thể được thiết kế để ngăn chặn thông tin sai lệch một cách có chủ đích (TMB), đảm bảo số người không bị ảnh hưởng bởi thông tin sai lệch lớn hơn một ngưỡng xác định với chi phí loại bỏ đỉnh tối thiểu?
    • H3.1: Bài toán TMB, yêu cầu tìm tập đỉnh nhỏ nhất để loại bỏ đạt được ngưỡng giảm ảnh hưởng thông tin sai lệch, là NP-Khó trên các mô hình IC và LT.
    • H3.2: Các thuật toán STMB-IC và STMB-LT, được phát triển dựa trên các hệ quy hoạch tuyến tính và chiến lược tham lam, có thể cung cấp các lời giải hiệu quả cho TMB trên các mô hình lan truyền thông tin IC và LT cho các mạng cỡ lớn.

Theoretical framework với tên theories cụ thể:

Khung lý thuyết của luận án được xây dựng dựa trên các lý thuyết nền tảng từ Khoa học máy tính và Tối ưu tổ hợp. Cụ thể, các mô hình lan truyền thông tin cơ bản như Ngưỡng Tuyến tính (Linear Threshold - LT) và Bậc Độc lập (Independent Cascade - IC), được đề xuất lần đầu bởi Kempe và các cộng sự [43], là nền tảng để phát triển các biến thể và mô hình cạnh tranh mới. Lý thuyết về Độ phức tạp tính toán (Computational Complexity Theory), đặc biệt là các lớp bài toán NP-Khó (NP-Hard) và #P-Khó (#P-Hard) (được xác định bởi Valiant [98, 99]), cung cấp cơ sở để đánh giá tính khả thi của việc tìm kiếm lời giải tối ưu và thúc đẩy việc phát triển các thuật toán xấp xỉ. Hơn nữa, Lý thuyết hàm Submodular (Submodular Function Theory) được áp dụng rộng rãi, đặc biệt là việc sử dụng tính chất đơn điệu tăng và submodular của hàm mục tiêu để thiết kế các thuật toán tham lam với tỷ lệ xấp xỉ đã được chứng minh (ví dụ, 1 - 1/e, theo Khuller et al. [46]). Các kỹ thuật như phương pháp Monte-Carlo (Monte-Carlo method) và mẫu ảnh hưởng ngược (Reverse Influence Sampling - RIS) của Borg và các cộng sự [9], được sử dụng để ước lượng hàm ảnh hưởng, cũng là một phần không thể thiếu trong khung lý thuyết và phương pháp luận.

Đóng góp đột phá với quantified impact:

Luận án này mang lại những đóng góp đột phá với tác động rõ rệt:

  1. Mô hình hóa cạnh tranh công bằng và thuật toán mở rộng: Đề xuất mô hình ngưỡng tuyến tính cạnh tranh ràng buộc thời gian (TCLT) cho bài toán Tối đa ảnh hưởng cạnh tranh có ngân sách (BCIM), giải quyết hạn chế về mô hình cạnh tranh không công bằng (trang 24). Thuật toán xấp xỉ SPBA được phát triển cho BCIM, có khả năng xử lý MXHTT lên đến hàng triệu đỉnh và cạnh, cải thiện đáng kể khả năng ứng dụng thực tế so với các phương pháp trước đó.
  2. Giải pháp toàn diện cho ngăn chặn thông tin sai lệch: Phát triển các thuật toán hiệu quả (FPTAS, IGA, SG, PR-DAG) cho bài toán Hạn chế tối đa thông tin sai lệch (MMR) với ràng buộc về ngân sách và thời gian (trang 4). Các thuật toán này được chứng minh hoạt động tốt trên các bộ dữ liệu MXHTT thực, cung cấp công cụ mạnh mẽ để chống lại sự lây lan của thông tin xấu.
  3. Kiểm soát thông tin sai lệch có mục tiêu cụ thể: Giới thiệu và giải quyết bài toán Hạn chế thông tin sai lệch có chủ đích (TMB), cho phép tìm kiếm tập đỉnh nhỏ nhất để loại bỏ nhằm đạt được một ngưỡng giảm ảnh hưởng thông tin sai lệch cụ thể (γ) (trang 26). Các thuật toán STMB-IC và STMB-LT đã chứng minh hiệu quả trên các mạng cỡ hàng trăm nghìn đỉnh.
  4. Minh chứng học thuật mạnh mẽ: Các kết quả nghiên cứu đã được công bố trên 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 các kỷ yếu hội nghị quốc tế có phản biện thuộc danh mục SCOPUS (trang 5), khẳng định chất lượng và sự đóng góp của luận án cho cộng đồng khoa học quốc tế.

Scope (sample size, timeframe) và significance:

Luận án tập trung vào các bài toán tối ưu trên mạng xã hội với quy mô lớn, từ hàng trăm nghìn đến hàng triệu đỉnh và cạnh. Khung thời gian nghiên cứu bao gồm việc mô hình hóa các quá trình lan truyền thông tin rời rạc theo các bước thời gian t = 0, 1, ... và xem xét các ràng buộc thời gian cụ thể trong các bài toán (ví dụ, τ > 0 trong mô hình IC-M [20]). Tầm quan trọng của luận án nằm ở khả năng cung cấp các giải pháp tính toán hiệu quả và thực tiễn cho các vấn đề cấp bách trong quản lý MXHTT, từ tiếp thị lan truyền đến chống thông tin sai lệch. Nó nâng cao sự phục vụ và độ tin cậy của MXHTT, tác động trực tiếp đến nền kinh tế toàn cầu và nhận thức của công chúng, như đã thấy trong các sự kiện như bầu cử Mỹ 2016 hay tác động tài chính từ tin đồn (trang 7, 8).

Literature Review và Positioning

Phần tổng quan tài liệu đã tổng hợp và phân tích chuyên sâu các luồng nghiên cứu chính liên quan đến lan truyền thông tin trên MXHTT. Các công trình của Kempe và các cộng sự [43] về mô hình Ngưỡng Tuyến tính (LT) và Bậc Độc lập (IC) đã đặt nền móng cho lĩnh vực này, tập trung vào bài toán Tối đa Ảnh hưởng (IM). Sau đó, Chen và các cộng sự [21, 22] đã làm rõ độ phức tạp #P-Khó của việc tính toán hàm mục tiêu, mở đường cho các phương pháp xấp xỉ. Borg và các cộng sự [9] với mô hình Mẫu Ảnh hưởng Ngược (RIS) đã tạo ra một bước đột phá trong việc thiết kế các thuật toán xấp xỉ hiệu quả hơn cho IM.

Synthesis của major streams với TÊN TÁC GIẢ và NĂM cụ thể:

  1. Mô hình lan truyền thông tin cơ bản: Kempe, Kleinberg, và Tardos (2003) [43] đã giới thiệu LT và IC, hai mô hình định hình các nghiên cứu về lan truyền thông tin.
  2. Bài toán Tối đa Ảnh hưởng (IM) và độ phức tạp: Kempe, Kleinberg, và Tardos (2003) [43] cũng là những người đầu tiên phát biểu bài toán IM. Chen, Wang, và Yang (2009) [21, 22] sau đó đã chứng minh rằng việc tính toán chính xác hàm ảnh hưởng σ(S) là #P-Khó, khẳng định tính thách thức của bài toán.
  3. Các thuật toán xấp xỉ cho IM:
    • Thuật toán tham lam (Greedy Algorithm) được Kempe et al. (2003) [43] đề xuất, đạt tỷ lệ xấp xỉ 1 - 1/e, nhưng có độ phức tạp cao O(knR(m+n)) (trang 18).
    • Leskovec, Krause, và Guestrin (2007) [54] cải tiến bằng thuật toán Lazy Greedy.
    • Borgs, Brautbar, Chayes, Mirrokni, và Tardos (2014) [9] giới thiệu Reverse Influence Sampling (RIS), cung cấp một khung lý thuyết mới để đạt tỷ lệ xấp xỉ 1 - 1/e - ε với độ phức tạp O((m+n)ε^-3 k log n) (trang 20).
    • Tang, Xiao, và Shi (2014, 2015) [95, 94] tiếp tục cải tiến RIS với TIM/TIM++ và IMM, giảm số mẫu cần thiết.
  4. Các thuật toán Heuristic cho IM: Chen, Wang, và Yang (2010) [22, 21] dựa trên đường đi (PMIA, LDAG). Goyal, Bonchi, và Ferrara (2010) [37] với SIMPATH. Kim, Han, và Kim (2013) [47] với IPA. Các phương pháp dựa trên cộng đồng cũng được nghiên cứu [114, 23, 6].
  5. Biến thể của IM: Các nghiên cứu đã mở rộng IM theo thời gian (Chen et al., 2010 [20]; Zhang et al., 2013 [112]), chi phí (Huy Nguyen et al., 2012 [72]), khoảng cách (Li et al., 2013 [59]; Wang et al., 2012 [101]), và chủ đề (Li et al., 2014 [62]).
  6. Tối đa ảnh hưởng cạnh tranh (CIM): Bharathi, Kempe, và Salek (2007) [8] là những người đầu tiên đề xuất bài toán CIM. Các mô hình lan truyền cạnh tranh được mở rộng từ LT [10, 39, 19, 66] hoặc IC [14, 18, 65, 64].
  7. Ngăn chặn ảnh hưởng (IB): Khalil, Yang, và Zhou (2014) [45] nghiên cứu bài toán loại bỏ cạnh. Yang, Lu, và Lin (2014) [117] với DAVA. Zhang, Song, và Liu (2016) [115] nghiên cứu phân phối vắc xin. Zhang, Song, và Yu (2016) [110] với bài toán τ-MP.
  8. Tẩy nhiễm thông tin: Budak, Agrawal, và El Abbadi (2011) [13] với MCIC. He, Ding, và Sun (2016) [39] với IBM trên mô hình CLT. Nguyen, Doan, và Nguyen (2016) [77] với βTI.

Contradictions/debates với ít nhất 2 opposing views:

Một điểm mâu thuẫn chính trong tài liệu là sự đánh đổi giữa chất lượng lời giải và hiệu quả tính toán. Các thuật toán xấp xỉ như của Kempe et al. [43] cung cấp tỷ lệ xấp xỉ lý thuyết chặt chẽ (1 - 1/e) nhưng lại không khả thi về mặt tính toán cho mạng lớn do việc tính toán hàm mục tiêu là #P-Khó [21, 22]. Ngược lại, các thuật toán heuristic (như các phương pháp dựa trên độ đo, đường đi) có thời gian chạy nhanh hơn đáng kể và có thể áp dụng cho mạng lớn, nhưng lại không đảm bảo tỷ lệ tối ưu lý thuyết và đôi khi cho kết quả "khá tệ" trên một số bộ dữ liệu thực so với thuật toán tham lam [21]. Ví dụ, trong khi các thuật toán heuristic dựa trên độ đo cung cấp lời giải nhanh chóng mà không cần tính toán hàm mục tiêu, chúng lại mang tính chất "tối ưu cục bộ" và không ổn định trên dữ liệu thực (trang 21).

Một điểm tranh luận khác nằm ở việc mô hình hóa sự cạnh tranh trong các bài toán CIM. Nhiều nghiên cứu (ví dụ, He, Ding, và Sun [39]) giả định rằng một bên (thông tin chính thống) có sức thuyết phục hơn và chiếm ưu thế khi hai luồng thông tin cạnh tranh. Tuy nhiên, luận án này lập luận rằng giả thuyết đó không phản ánh sự cạnh tranh công bằng giữa các sản phẩm trong tiếp thị lan truyền, nơi mà không có bên nào mặc định chiếm lợi thế (trang 24). Điều này dẫn đến nhu cầu về các mô hình cạnh tranh mới, công bằng hơn.

Positioning trong literature với specific gap identified:

Luận án định vị mình ở giao điểm của ba thách thức chính trong nghiên cứu lan truyền thông tin: 1) Tính khả thi về tính toán cho các mạng quy mô lớn, 2) Tích hợp các ràng buộc thực tế (thời gian, ngân sách, chi phí không đồng nhất), và 3) Mô hình hóa chính xác các kịch bản phức tạp (cạnh tranh công bằng, ngăn chặn có chủ đích). Cụ thể, nó lấp đầy khoảng trống khi các phương pháp hiện tại không thể mở rộng hiệu quả cho MXHTT cỡ hàng triệu đỉnh hoặc không xem xét đầy đủ các ràng buộc thực tế của IM và IB. Đối với CIM, luận án giải quyết khoảng trống về mô hình cạnh tranh công bằng hơn, khác biệt với giả định chiếm ưu thế của He et al. [39]. Đối với IB, luận án bổ sung các ràng buộc về chi phí và thời gian mà các nghiên cứu như của Yang et al. [117] và Song et al. [87] thường bỏ qua. Đặc biệt, việc giới thiệu bài toán TMB là một đóng góp mới, tập trung vào việc đạt được một ngưỡng giảm ảnh hưởng cụ thể thay vì chỉ tối thiểu hóa ảnh hưởng một cách tổng quát, một hướng tiếp cận chưa được khám phá sâu bởi các công trình trước đó như Zhang et al. [110].

How this advances field với concrete contributions:

Luận án này thúc đẩy lĩnh vực nghiên cứu bằng cách:

  • Nâng cao tính thực tiễn của mô hình hóa: Đề xuất mô hình TCLT cho BCIM, cung cấp một cách tiếp cận thực tế hơn để mô hình hóa sự cạnh tranh công bằng và các ràng buộc về thời gian/ngân sách (trang 4).
  • Cải thiện khả năng mở rộng của thuật toán: Các thuật toán SPBA, PR-DAG, STMB-IC, STMB-LT được thiết kế để xử lý các MXHTT cỡ lớn (hàng trăm nghìn đến hàng triệu đỉnh/cạnh) một cách hiệu quả, điều mà nhiều thuật toán xấp xỉ và heuristic trước đó còn hạn chế.
  • Giải quyết các bài toán mới có ý nghĩa thực tiễn: Giới thiệu bài toán TMB, mở ra hướng nghiên cứu mới về việc kiểm soát thông tin sai lệch theo mục tiêu cụ thể, một kịch bản rất cần thiết trong thực tế hiện nay (trang 26).
  • Đóng góp vào kho tàng các phương pháp giải TƯTH: Các phân tích về độ phức tạp và thiết kế thuật toán xấp xỉ/heuristic dựa trên tính chất hàm submodular, Monte-Carlo, và quy hoạch tuyến tính làm phong phú thêm các công cụ cho các bài toán tối ưu tổ hợp.

So sánh với ÍT NHẤT 2 international studies:

  1. So sánh với Kempe et al. (2003) [43] và Chen et al. (2009) [21, 22]: Công trình của Kempe và các cộng sự đã đặt nền móng cho bài toán IM và cung cấp thuật toán tham lam với tỷ lệ xấp xỉ 1 - 1/e. Tuy nhiên, như Chen và các cộng sự đã chỉ ra, việc tính toán hàm mục tiêu chính xác là #P-Khó, khiến thuật toán tham lam gốc không khả thi trên mạng lớn với độ phức tạp O(knR(m+n)). Luận án này cải tiến bằng cách phát triển các thuật toán như SPBA (cho BCIM) và PR-DAG (cho MMR) có khả năng mở rộng để xử lý MXHTT cỡ hàng triệu đỉnh và cạnh, đạt được hiệu quả tính toán tốt hơn trong khi vẫn giữ được chất lượng lời giải chấp nhận được, khắc phục hạn chế về độ phức tạp của phương pháp Monte-Carlo thô sơ.
  2. So sánh với Borgs et al. (2014) [9] (RIS) và He et al. (2016) [39] (IBM/CLT): Mặc dù RIS của Borg và các cộng sự đã tạo ra một bước tiến lý thuyết lớn về thuật toán xấp xỉ cho IM với tỷ lệ 1 - 1/e - ε, nó vẫn gặp thách thức về số lượng tập RR cần sinh ra đối với các mạng cỡ lớn (trang 20). Luận án này, đặc biệt trong bài toán BCIM, không chỉ cung cấp một thuật toán xấp xỉ hiệu quả mà còn đề xuất một mô hình ngưỡng tuyến tính cạnh tranh ràng buộc thời gian (TCLT) mang tính thực tế hơn. Khác với mô hình CLT của He và các cộng sự, luận án tránh giả định một bên chiếm ưu thế trong cạnh tranh (trang 24), cung cấp một mô hình công bằng hơn cho tiếp thị sản phẩm. Hơn nữa, các thuật toán như SPBA được thiết kế để đạt khả năng mở rộng cao hơn trên các mạng lớn, điều mà các thuật toán dựa trên RIS gốc có thể gặp khó khăn khi số mẫu θ cần thiết vẫn còn lớn.

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

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

Luận án này đóng góp đáng kể vào các lý thuyết hiện có về lan truyền thông tin và tối ưu tổ hợp.

  • Extend/challenge WHICH specific theories (name theorists):
    • Mở rộng lý thuyết lan truyền thông tin của Kempe et al. [43]: Bằng cách giới thiệu mô hình ngưỡng tuyến tính cạnh tranh ràng buộc thời gian (TCLT), luận án mở rộng các mô hình LT và IC cơ bản để tích hợp yếu tố cạnh tranh, ngân sách và thời gian. Điều này giúp mô tả chính xác hơn các kịch bản thực tế trong tiếp thị lan truyền và chống thông tin sai lệch so với các mô hình ban đầu.
    • Thách thức các giả định trong mô hình cạnh tranh: Luận án thách thức giả định phổ biến trong các mô hình cạnh tranh như của He, Ding, và Sun [39] rằng một luồng thông tin (ví dụ, chính thống) luôn chiếm ưu thế khi cạnh tranh. Thay vào đó, nó đề xuất một mô hình (TCLT) phản ánh sự cạnh tranh công bằng hơn giữa các luồng thông tin, làm phong phú thêm lý thuyết về lan truyền cạnh tranh.
    • Mở rộng lý thuyết về hàm Submodular: Các bài toán mới được đề xuất (BCIM, MMR, TMB) và việc phân tích tính chất submodular của các hàm mục tiêu liên quan không chỉ khẳng định tầm quan trọng của lý thuyết này trong TƯTH mà còn mở rộng ứng dụng của nó vào các biến thể bài toán phức tạp hơn trong MXHTT.
  • Conceptual framework với components và relationships: Khung lý thuyết của luận án xoay quanh mối quan hệ giữa (1) Mô hình lan truyền thông tin (IC, LT, và các biến thể TCLT, TLT), (2) Các bài toán tối ưu (IM, IB, BCIM, MMR, TMB), (3) Độ phức tạp tính toán (NP-Khó, #P-Khó), và (4) Các thuật toán giải quyết (xấp xỉ, heuristic, Monte-Carlo, RIS, quy hoạch tuyến tính).
    • Components:
      • MXHTT: Nền tảng cấu trúc mạng.
      • Mô hình lan truyền: Quy luật xác định cách thông tin lan truyền.
      • Hàm mục tiêu: Đại lượng cần tối ưu (ảnh hưởng, chi phí, số người bị ảnh hưởng).
      • Ràng buộc: Giới hạn về ngân sách, thời gian, ngưỡng ảnh hưởng.
      • Độ phức tạp: Đánh giá tính khó của bài toán.
      • Thuật toán: Giải pháp tính toán.
    • Relationships:
      • Mô hình lan truyền xác định hàm mục tiêu và độ phức tạp của bài toán.
      • Độ phức tạp (NP-Khó, #P-Khó) thúc đẩy sự phát triển của thuật toán xấp xỉ và heuristic.
      • Ràng buộc thực tế làm cho bài toán phức tạp hơn nhưng cũng định hướng thiết kế thuật toán phù hợp.
      • Thuật toán được đánh giá dựa trên chất lượng lời giải và hiệu quả tính toán trên các mô hình và ràng buộc đã cho.
  • Theoretical model với propositions/hypotheses numbered: Luận án phát triển một số mô hình lý thuyết cụ thể, ví dụ:
    • Mô hình TCLT (Time-Constraint Competitive Linear Threshold): Đây là mô hình mở rộng của LT cho bài toán BCIM. Nó định nghĩa lại quá trình lan truyền trong môi trường cạnh tranh với các yếu tố chi phí khác nhau và thời gian lan truyền giới hạn, trong đó mỗi đỉnh u có hai ngưỡng kích hoạt tích cực θu+ và tiêu cực θu−, và mỗi cạnh (u, v) có hai trọng số lan truyền w−(u, v) và w+(u, v) (tương tự như mô hình CLT của He et al. [39] nhưng với sự điều chỉnh về cân bằng cạnh tranh và ràng buộc thời gian/ngân sách).
      • Proposition 1: Hàm ảnh hưởng mục tiêu trong BCIM dưới mô hình TCLT, mặc dù phức tạp, có thể được xấp xỉ hiệu quả bằng các hàm chặn trên và chặn dưới.
    • Mô hình TLT (Time-Constraint Linear Threshold) mở rộng cho MMR: Được đề xuất để giải quyết bài toán hạn chế tối đa thông tin sai lệch với ràng buộc về thời gian và ngân sách.
      • Proposition 2: Bài toán MMR trên mô hình TLT mở rộng là NP-Khó và hàm mục tiêu không nhất thiết có tính chất submodular, đòi hỏi các thuật toán đặc biệt.
    • Mô hình TMB (Targeted Misinformation Blocking) trên LT và IC: Mô hình này định nghĩa bài toán tìm tập đỉnh nhỏ nhất để loại bỏ sao cho ảnh hưởng của thông tin sai lệch giảm xuống dưới một ngưỡng γ cụ thể.
      • Proposition 3: Bài toán TMB trên cả mô hình LT và IC là NP-Khó, đòi hỏi việc phát triển các thuật toán hiệu quả như STMB-LT và STMB-IC dựa trên quy hoạch tuyến tính.
  • Paradigm shift với EVIDENCE từ findings: Luận án góp phần vào một sự chuyển dịch mô hình (paradigm shift) từ việc tìm kiếm lời giải tối ưu lý thuyết nhưng không khả thi sang việc tập trung vào các giải pháp có khả năng mở rộng, tích hợp ràng buộc thực tế và mang tính ứng dụng cao. Trước đây, nhiều nghiên cứu tập trung vào việc chứng minh tỷ lệ xấp xỉ chặt chẽ (ví dụ, 1 - 1/e) cho IM/IB mà ít quan tâm đến độ phức tạp thực tế trên các mạng lớn. Tuy nhiên, với "sự mở rộng của quy mô các MXHTT (hàng triệu, tỷ người dùng), cần có những thuật toán hoặc cách tiếp cận hiệu quả hơn nữa cho những bài toán trên để nâng cao tính thực tiễn của chúng" (trang 3). Luận án này đã chứng minh rằng các thuật toán như SPBA (cho BCIM) có thể hoạt động với "MXHTT cỡ hàng triệu đỉnh và cạnh" và các thuật toán STMB-IC/STMB-LT cho TMB có thể áp dụng cho "các mạng cỡ lớn hàng trăm nghìn đỉnh" (trang 4-5). Đây là bằng chứng cho sự chuyển dịch sang một phương pháp luận tập trung vào khả năng ứng dụng và hiệu suất trên quy mô lớn, vượt qua các giới hạn của các thuật toán lý thuyết thuần túy.

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

Khung phân tích của luận án đặc biệt ở sự kết hợp linh hoạt giữa các phương pháp lý thuyết và thực nghiệm để giải quyết các bài toán TƯTH phức tạp trên MXHTT.

  • Integration của theories (name 3+ specific theories):
    • Lý thuyết đồ thị (Graph Theory): Nền tảng để biểu diễn MXHTT dưới dạng đồ thị có hướng G=(V,E), định nghĩa các khái niệm như tập hạt giống, trạng thái đỉnh, và quá trình lan truyền dọc theo các cạnh (trang 9-10).
    • Lý thuyết tối ưu tổ hợp (Combinatorial Optimization Theory): Cung cấp khuôn khổ để xây dựng các bài toán IM, IB, BCIM, MMR, TMB dưới dạng các bài toán tìm cực đại/cực tiểu hàm mục tiêu trên tập hữu hạn trạng thái. Nó cũng bao gồm việc phân loại độ phức tạp (NP-Khó, #P-Khó) (Chương 2).
    • Lý thuyết xác suất và thống kê (Probability and Statistics Theory): Được sử dụng trong các mô hình ngẫu nhiên như IC và LT (với xác suất ảnh hưởng p(u,v) và ngưỡng kích hoạt θu), phương pháp Monte-Carlo để ước lượng kỳ vọng của hàm ảnh hưởng, và bất đẳng thức Chernoff để chứng minh chất lượng lời giải của các thuật toán xấp xỉ (ví dụ, Tang et al. [95] và phương pháp luật dừng của Dagum và các cộng sự [27] được Nguyen áp dụng [75] để thiết kế SSA và D-SSA).
  • Novel analytical approach với justification: Luận án áp dụng một cách tiếp cận phân tích mới bằng cách kết hợp "sandwich approximation" (các hàm xấp xỉ trên và dưới) với chiến lược tham lam để giải quyết bài toán BCIM. Phương pháp này không chỉ đảm bảo tỷ lệ xấp xỉ hiệu quả mà còn cải thiện đáng kể thời gian chạy cho các mạng lớn. Sự kết hợp này được chứng minh bằng thực nghiệm 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 (trang 4). Hơn nữa, đối với bài toán MMR, luận án đề xuất thuật toán heuristic PR-DAG (PRuned Directed Acyclic Graph) dựa trên việc xây dựng DAG từ đồ thị ban đầu và ước lượng hàm mục tiêu, một cách tiếp cận sáng tạo để xử lý độ phức tạp #P-Khó của hàm mục tiêu. Cách tiếp cận này giúp cân bằng giữa chất lượng lời giải và hiệu quả tính toán, điều mà các thuật toán trước đây thường phải đánh đổi.
  • Conceptual contributions với definitions:
    • Budgeted Competitive Influence Maximization (BCIM): Là một biến thể của IM, tập trung vào việc tối đa hóa ảnh hưởng trong môi trường cạnh tranh với ràng buộc về ngân sách và thời gian, được định nghĩa rõ ràng với mô hình TCLT (trang 4).
    • Maximizing Misinformation Restriction (MMR): Là một biến thể của IB, nhằm hạn chế tối đa thông tin sai lệch dưới ràng buộc về ngân sách và thời gian, được định nghĩa trên mô hình ngưỡng tuyến tính mở rộng (trang 4).
    • Targeted Misinformation Blocking (TMB): Định nghĩa một bài toán mới trong đó mục tiêu là tìm tập đỉnh nhỏ nhất để loại bỏ nhằm đảm bảo số người không bị ảnh hưởng bởi thông tin sai lệch lớn hơn một ngưỡng γ xác định (trang 4). Điều này khác biệt với MMR vì TMB tập trung vào việc đạt một mục tiêu cụ thể, định lượng được, thay vì chỉ tối đa hóa việc hạn chế.
  • Boundary conditions explicitly stated: Các điều kiện biên của nghiên cứu được xác định rõ ràng:
    • Mô hình lan truyền: Các nghiên cứu chủ yếu tập trung vào các mô hình lan truyền thông tin rời rạc như LT và IC, cùng các biến thể mở rộng của chúng (TCLT, TLT). Các mô hình liên tục hoặc phức tạp hơn không thuộc phạm vi chính.
    • Quy mô mạng: Các thuật toán được thiết kế và kiểm nghiệm cho MXHTT có quy mô từ hàng trăm nghìn đến hàng triệu đỉnh và cạnh. Khả năng áp dụng cho các mạng siêu lớn (hàng tỷ đỉnh) cần thêm nghiên cứu.
    • Chi phí và thời gian: Các ràng buộc về ngân sách và thời gian được tích hợp một cách cụ thể (ví dụ, chi phí lựa chọn mỗi người dùng c(v) [72], giới hạn thời gian τ [20]), nhưng các loại ràng buộc khác (ví dụ, khoảng cách địa lý, chủ đề quan tâm) chỉ được đề cập trong tổng quan tài liệu mà không đi sâu vào việc phát triển thuật toán mới.
    • Mục tiêu tối ưu hóa: Luận án tập trung vào việc tối đa hóa ảnh hưởng có lợi hoặc tối thiểu hóa ảnh hưởng có hại, hoặc đạt được một ngưỡng hạn chế cụ thể, thay vì các mục tiêu tối ưu đa mục tiêu phức tạp.

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

Luận án áp dụng một phương pháp nghiên cứu tiên tiến, kết hợp chặt chẽ giữa phân tích lý thuyết và thực nghiệm, để giải quyết các bài toán tối ưu tổ hợp phức tạp trên MXHTT.

Thiết kế nghiên cứu

  • Research philosophy (positivism/interpretivism/critical realism): Luận án tuân theo triết lý nghiên cứu Thực chứng (Positivism) mạnh mẽ. Điều này được thể hiện qua việc: (1) xây dựng các mô hình toán học hình thức (LT, IC, TCLT, MMR, TMB) để biểu diễn các hiện tượng xã hội trên MXHTT; (2) đề xuất các thuật toán có thể định lượng được hiệu suất (tỷ lệ xấp xỉ, độ phức tạp tính toán); (3) thực nghiệm lặp lại với dữ liệu thực để kiểm tra các giả thuyết và đánh giá hiệu quả của thuật toán (trang 3). Mục tiêu là tìm kiếm các giải pháp khách quan, có thể khái quát hóa và kiểm chứng được.
  • Mixed methods với SPECIFIC combination rationale: Luận án sử dụng một cách tiếp cận kết hợp phương pháp (mixed methods).
    • Định lượng (Quantitative): Chiếm ưu thế thông qua việc xây dựng các mô hình tối ưu tổ hợp, phân tích độ phức tạp (NP-Khó, #P-Khó), thiết kế thuật toán xấp xỉ với tỷ lệ tối ưu đã được chứng minh (ví dụ, 1 - 1/e), và đánh giá hiệu suất bằng các chỉ số thống kê (thời gian chạy, chất lượng lời giải trên các bộ dữ liệu thực). Việc sử dụng Monte-Carlo và RIS để ước lượng hàm ảnh hưởng cũng là một phương pháp định lượng cốt lõi.
    • Thiết kế (Design Science/Constructivist elements): Mặc dù tập trung vào định lượng, luận án cũng bao hàm yếu tố thiết kế khi tạo ra các "tạo phẩm" mới như mô hình TCLT, TMB và các thuật toán SPBA, PR-DAG, STMB-IC/LT để giải quyết các vấn đề thực tiễn đã được xác định. Các tạo phẩm này được phát triển để lấp đầy các khoảng trống nghiên cứu và đáp ứng nhu cầu ứng dụng.
    • Rationale: Sự kết hợp này cho phép luận án vừa cung cấp nền tảng lý thuyết vững chắc (phân tích độ phức tạp, chứng minh tỷ lệ xấp xỉ) vừa đảm bảo tính thực tiễn và hiệu quả của các giải pháp trên các mạng xã hội quy mô lớn.
  • Multi-level design với levels clearly defined: Mặc dù không phải là một thiết kế đa cấp theo nghĩa xã hội học, nghiên cứu này có thể được xem xét ở nhiều cấp độ trừu tượng và ứng dụng:
    • Cấp độ vi mô (Node/Edge Level): Định nghĩa các quy tắc lan truyền thông tin giữa các đỉnh và cạnh (ví dụ, trọng số w(u,v), xác suất p(u,v), ngưỡng kích hoạt θu) trong các mô hình LT và IC (trang 10-12).
    • Cấp độ vĩ mô (Network/Global Level): Định nghĩa các bài toán tối ưu hóa trên toàn bộ mạng (IM, IB, BCIM, MMR, TMB), nơi mục tiêu là tối đa hóa hoặc tối thiểu hóa một đại lượng tổng thể (ví dụ, tổng số đỉnh bị ảnh hưởng σ(S)).
    • Cấp độ thực tiễn (Application Level): Các bài toán được nghiên cứu và giải pháp được đề xuất đều hướng tới các ứng dụng thực tế như tiếp thị lan truyền, ngăn chặn tin giả, giám sát dịch bệnh trên MXHTT (trang 1, 2).
  • Sample size và selection criteria EXACT: Luận án sử dụng các bộ dữ liệu MXHTT thực để thực nghiệm. Mặc dù tên cụ thể của bộ dữ liệu không được nêu trong phần "MỞ ĐẦU", nó đề cập đến việc áp dụng các thuật toán cho "MXHTT cỡ hàng triệu đỉnh và cạnh" và "các mạng cỡ lớn hàng trăm nghìn đỉnh" (trang 4-5). Tiêu chí lựa chọn mẫu là các mạng xã hội có cấu trúc phức tạp, độ lớn đa dạng để kiểm tra khả năng mở rộng và hiệu quả của thuật toán trên các quy mô khác nhau. Ví dụ, trong các chương 3, 4, 5, sẽ có phần "Dữ liệu và tham số" mô tả chi tiết các bộ dữ liệu (ví dụ, bộ Oregon, Gnutella được đề cập trong Danh sách hình vẽ). Các đặc tính quan trọng của dữ liệu bao gồm số lượng đỉnh, số lượng cạnh, và cấu trúc mạng (ví dụ, scale-free [26]) để phản ánh đúng bản chất của MXHTT.

Quy trình nghiên cứu rigorous

  • Sampling strategy với inclusion/exclusion criteria: Trong các thuật toán dựa trên xác suất hoặc mô phỏng, chiến lược lấy mẫu ngẫu nhiên (random sampling) đóng vai trò quan trọng.
    • Inclusion criteria: Các tập RR ngẫu nhiên (Random Reverse reachability sets) được sinh ra từ đồ thị G theo mô hình cạnh trực tuyến tương ứng với LT hoặc IC (trang 19). Các đỉnh/cạnh được chọn vào tập hạt giống hoặc tập loại bỏ dựa trên các tiêu chí tối ưu hóa của thuật toán (ví dụ, tăng ảnh hưởng biên lớn nhất trong thuật toán tham lam).
    • Exclusion criteria: Các đỉnh đã được kích hoạt sẽ duy trì trạng thái đó và không được kích hoạt lại (trang 11, 13). Các đỉnh/cạnh không đáp ứng tiêu chí hiệu quả/chi phí của thuật toán sẽ bị loại trừ.
    • Cụ thể, đối với phương pháp Monte-Carlo, "số lần mô phỏng ảnh hưởng từ tập hạt giống S ít nhất bằng Ω(n^2 ln(1/δ))" là tiêu chí để đảm bảo ước lượng hàm mục tiêu σ̂(S) đạt độ chính xác Pr[(1 − ε)σ(S) ≤ σ̂(S) ≤ (1 + ε)σ(S)] với xác suất ít nhất 1 − δ (Kempe, 2007, trang 18).
  • Data collection protocols với instruments described:
    • Dữ liệu được "thực nghiệm với máy tính trên các bộ dữ liệu khác nhau nhằm đảm bảo tính khách quan về hiệu quả của phương pháp đề xuất" (trang 3). Các bộ dữ liệu MXHTT thực (như đã đề cập trong các chương cụ thể, ví dụ Oregon, Gnutella) được sử dụng để đánh giá thuật toán.
    • Các "instruments" chính là các triển khai thuật toán trên môi trường tính toán. Hiệu suất được đo bằng thời gian chạy, chất lượng lời giải (ví dụ, số đỉnh bị ảnh hưởng, số đỉnh được hạn chế) và so sánh với các thuật toán cơ sở hoặc thuật toán tối ưu đã biết.
  • Triangulation (data/method/investigator/theory):
    • Triangulation dữ liệu: Sử dụng nhiều bộ dữ liệu MXHTT thực khác nhau (ví dụ, các bộ dữ liệu từ thực nghiệm trong Chương 3, 4, 5) để kiểm tra tính tổng quát của các thuật toán.
    • Triangulation phương pháp: Kết hợp nhiều loại thuật toán khác nhau: thuật toán xấp xỉ có đảm bảo tỷ lệ, thuật toán heuristic không đảm bảo tỷ lệ nhưng hiệu quả, và phương pháp Monte-Carlo/RIS để ước lượng hàm mục tiêu.
    • Triangulation lý thuyết: Các kết quả được phân tích dưới góc độ lý thuyết đồ thị, tối ưu tổ hợp và lý thuyết xác suất, cung cấp nhiều góc nhìn về vấn đề.
  • Validity (construct/internal/external) và reliability (α values):
    • Construct Validity: Các khái niệm như "ảnh hưởng" và "ngăn chặn ảnh hưởng" được định nghĩa rõ ràng thông qua các hàm mục tiêu toán học (ví dụ, σ(S)) và các mô hình lan truyền (LT, IC, TCLT), đảm bảo rằng các biến số được đo lường phù hợp với khái niệm nghiên cứu.
    • Internal Validity: Được đảm bảo thông qua việc kiểm soát các tham số trong thực nghiệm (ví dụ, k - số lượng hạt giống, τ - bước thời gian, chi phí c(v)). Các phép dẫn toán học chặt chẽ và chứng minh tỷ lệ xấp xỉ của thuật toán cũng củng cố tính hợp lệ nội bộ (trang 3, 34).
    • External Validity: Các thuật toán được kiểm nghiệm trên nhiều bộ dữ liệu thực tế với quy mô khác nhau (từ hàng trăm nghìn đến hàng triệu đỉnh), giúp tăng cường khả năng khái quát hóa kết quả sang các MXHTT khác.
    • Reliability: Mặc dù không có giá trị alpha cụ thể được đề cập, tính lặp lại của các thuật toán được đảm bảo bởi tính chất thuật toán đơn định hoặc các phương pháp lấy mẫu Monte-Carlo đủ lớn để đạt được độ chính xác thống kê nhất định (ví dụ, Pr[(1 − ε)σ(S) ≤ σ̂(S) ≤ (1 + ε)σ(S)] với xác suất 1 − δ, trang 18). Các kết quả thực nghiệm đều được thực hiện trên môi trường máy tính để đảm bảo tính nhất quán.

Data và phân tích

  • Sample characteristics với demographics/statistics: Dữ liệu được sử dụng trong thực nghiệm bao gồm các bộ dữ liệu MXHTT thực. Mặc dù không có chi tiết nhân khẩu học của người dùng, các đặc điểm thống kê của mạng (ví dụ, số đỉnh, số cạnh, phân bố bậc, đặc trưng thế giới nhỏ với khoảng cách trung bình kết nối nhỏ hơn 6 [90, 29], cấu trúc cộng đồng) được phân tích để đảm bảo tính đại diện và phù hợp với đặc tính của MXHTT (trang 6-7). Ví dụ, các MXHTT thường có dạng mạng scale-free với phân bố lũy thừa P(k) = 1/k^γ (trong đó 2 < γ < 3) [26].
  • Advanced techniques (SEM/multilevel/QCA etc.) với software: Các kỹ thuật phân tích tiên tiến được sử dụng chủ yếu liên quan đến:
    • Phân tích độ phức tạp thuật toán: O-notation để đánh giá thời gian chạy và bộ nhớ (ví dụ, O((m+n)ε^-3 k log n) cho RIS của Borg et al. [9]).
    • Quy hoạch tuyến tính (Linear Programming): Được sử dụng để xây dựng hệ quy hoạch tuyến tính cho thuật toán STMB-IC trong bài toán TMB (Chương 5, trang 4). Các bài toán LP này thường được giải bằng các phần mềm giải toán tối ưu chuyên dụng (ví dụ, Gurobi, CPLEX) hoặc các thư viện toán học.
    • Mô phỏng Monte-Carlo (Monte-Carlo Simulation): Để ước lượng hàm mục tiêu σ(S) với số lần lặp lớn, được triển khai bằng các ngôn ngữ lập trình hiệu năng cao (ví dụ, C++, Java, Python với các thư viện tối ưu).
    • Kỹ thuật đồ thị (Graph Algorithms): Phát triển các thuật toán dựa trên cấu trúc đồ thị (ví dụ, xây dựng DAG, tìm đường đi, tập phủ) để giải quyết các bài toán. Mặc dù phần giới thiệu không nêu rõ tên phần mềm, việc sử dụng các kỹ thuật trên ngụ ý rằng các thuật toán được triển khai trên các nền tảng tính toán hiệu năng cao, thường sử dụng các công cụ lập trình khoa học và thư viện tối ưu hóa.
  • Robustness checks với alternative specifications: Tính vững chắc của các thuật toán được kiểm tra thông qua:
    • So sánh với các thuật toán cơ sở (baseline algorithms): Các thuật toán đề xuất được so sánh với các phương pháp đã biết (ví dụ, thuật toán tham lam cổ điển, các heuristic khác) để đánh giá sự cải tiến về chất lượng lời giải và thời gian chạy (ví dụ, "Kết quả 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" - trang 4).
    • Kiểm tra độ nhạy (sensitivity analysis): Đánh giá ảnh hưởng của việc thay đổi các tham số đầu vào (ví dụ, số hạt giống k, bước thời gian τ, ngân sách) đến hiệu suất của thuật toán. Ví dụ, trong Chương 3 (BCIM), có phần "Ảnh hưởng của bước thời gian τ" và "So sánh các thuật toán khi k thay đổi", "khi d thay đổi" (hình 3.9, 3.10, 3.11 trong Danh sách hình vẽ).
    • Kiểm tra trên các mô hình khác nhau: Mở rộng nghiên cứu các bài toán (BCIM, MMR) sang mô hình "Ngưỡng tuyến tính cạnh tranh xác định" hoặc "ngưỡng tuyến tính xác định" để kiểm tra tính ứng dụng và vững chắc của phương pháp (trang 4).
  • Effect sizes và confidence intervals reported: Trong các chương chi tiết của luận án, kết quả thực nghiệm sẽ báo cáo các chỉ số định lượng về chất lượng lời giải (ví dụ, số người bị ảnh hưởng, tỷ lệ hạn chế thông tin sai lệch) và hiệu suất tính toán (thời gian chạy). Mặc dù các "p-values, effect sizes và confidence intervals" không được liệt kê cụ thể trong phần "MỞ ĐẦU", việc sử dụng phương pháp Monte-Carlo để ước lượng kỳ vọng của hàm ảnh hưởng với "độ chính xác (độ lệch) của ước lượng" (ε) và "khả năng trả về ước lượng" (δ) (trang 39) cho thấy rằng các phân tích thống kê chi tiết được thực hiện để đánh giá độ tin cậy của kết quả. Các giá trị này sẽ được trình bày trong các phần "Kết quả thực nghiệm" của các chương cụ thể, nơi các so sánh định lượng được đưa ra giữa các thuật toán.

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

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

Luận án đã đạt được những phát hiện then chốt, mang lại cái nhìn sâu sắc và giải pháp hiệu quả cho các bài toán tối ưu trên MXHTT.

  1. Mô hình cạnh tranh công bằng khả thi trên quy mô lớn: Mô hình TCLT đề xuất cho bài toán BCIM không chỉ phản ánh chính xác hơn sự cạnh tranh công bằng (khác với He et al. [39]) mà còn cho phép thuật toán SPBA đạt hiệu quả cao. Thực nghiệm chỉ ra rằng SPBA "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" (trang 4). Đây là một cải tiến đáng kể về khả năng mở rộng so với các phương pháp trước.
  2. Giải pháp ngăn chặn thông tin sai lệch có ràng buộc: Các thuật toán đề xuất cho bài toán MMR (FPTAS, IGA, SG, PR-DAG) đã chứng minh hiệu quả trong việc hạn chế thông tin sai lệch dưới các ràng buộc về ngân sách và thời gian. Điều này được thể hiện qua kết quả thực nghiệm nổi trội trên các bộ dữ liệu thực (trang 4). Đặc biệt, thuật toán PR-DAG cung cấp một hướng tiếp cận heuristic mạnh mẽ cho bài toán có độ phức tạp cao này.
  3. Chiến lược kiểm soát thông tin sai lệch theo mục tiêu: Phát hiện rằng bài toán TMB, tìm tập đỉnh nhỏ nhất để loại bỏ để đạt được một ngưỡng giảm ảnh hưởng γ, là NP-Khó trên cả mô hình IC và LT, nhưng có thể được giải quyết hiệu quả bằng các thuật toán STMB-IC và STMB-LT. "Các kết quả thực nghiệm trên các dữ liệu MXHTT thực chỉ ra hiệu quả của các thuật toán đề xuất, đặc biệt các thuật toán có thể áp dụng cho các mạng cỡ lớn hàng trăm nghìn đỉnh" (trang 4-5).
  4. Hiệu suất tính toán vượt trội cho bài toán #P-Khó: Các phương pháp được phát triển (như sử dụng "sandwich approximation" hay kỹ thuật DAG) giúp giải quyết hiệu quả tính toán hàm mục tiêu vốn thuộc lớp #P-Khó [21, 22], cho phép các thuật toán của luận án chạy trong thời gian chấp nhận được trên các mạng quy mô lớn.
  5. So sánh với prior research findings: Các thuật toán được đề xuất (SPBA, PR-DAG, STMB-IC/LT) thường cho thấy "chất lượng lời giải tốt hơn các thuật toán trước đó" (trang 25 cho DAVA của Yang et al. [117] và luận án kế thừa). Chúng cải thiện đáng kể thời gian chạy so với thuật toán tham lam cổ điển và mở rộng khả năng áp dụng cho các mạng lớn hơn nhiều so với các phương pháp dựa trên RIS gốc của Borg et al. [9] khi số mẫu RIS vẫn còn lớn.

Implications đa chiều

  • Theoretical advances với contribution to 2+ theories:
    • Lý thuyết lan truyền thông tin: Luận án mở rộng lý thuyết về lan truyền thông tin bằng cách giới thiệu các mô hình mới (TCLT, TMB) tích hợp các ràng buộc thực tế và kịch bản cạnh tranh công bằng, làm phong phú thêm khung khổ của Kempe et al. [43].
    • Lý thuyết tối ưu tổ hợp: Đóng góp vào lý thuyết tối ưu tổ hợp bằng cách phát triển các thuật toán xấp xỉ và heuristic hiệu quả cho các bài toán thuộc lớp NP-Khó và #P-Khó, đồng thời phân tích tính chất của hàm mục tiêu (ví dụ, tính submodular) trong các biến thể bài toán phức tạp.
  • Methodological innovations applicable to other contexts: Các đổi mới về phương pháp luận, như kỹ thuật "sandwich approximation" hoặc heuristic dựa trên DAG, có thể được áp dụng để giải quyết các bài toán tối ưu tổ hợp khác trong các lĩnh vực như tối ưu hóa logistics, quản lý chuỗi cung ứng, hoặc phân tích mạng lưới sinh học, nơi các bài toán cũng thường có độ phức tạp cao.
  • Practical applications với specific recommendations:
    • Tiếp thị lan truyền: Các doanh nghiệp có thể sử dụng thuật toán SPBA để xác định tập người dùng hạt giống tối ưu cho các chiến dịch tiếp thị sản phẩm trong môi trường cạnh tranh, đảm bảo tối đa hóa ảnh hưởng trong ngân sách và thời gian giới hạn.
    • Chống thông tin sai lệch: Các tổ chức truyền thông và chính phủ có thể triển khai thuật toán PR-DAG hoặc STMB-IC/LT để nhanh chóng xác định các điểm nóng hoặc người dùng cần can thiệp để ngăn chặn sự lây lan của tin giả, virus hoặc các tư tưởng cực đoan, bảo vệ nhận thức cộng đồng. Cụ thể, TMB cho phép kiểm soát thông tin sai lệch để đạt một mức độ chấp nhận được, cung cấp "câu hỏi, cần chi phí ít nhất bằng bao nhiêu để điểu khiển, quản lý được thông tin sai dưới một ngưỡng cho phép" (trang 26).
  • Policy recommendations với implementation pathway:
    • Kiểm soát thông tin trên MXHTT: Các nhà hoạch định chính sách có thể sử dụng các công cụ từ luận án để xây dựng các chính sách hiệu quả hơn trong việc quản lý nội dung trên MXHTT, bao gồm việc xác định các tài khoản có khả năng phát tán tin giả cao hoặc các điểm yếu trong mạng lưới cần được giám sát (như đề xuất bài toán τ-MP của Zhang et al. [110]).
    • Quản lý khủng hoảng: Trong các tình huống khủng hoảng (ví dụ: dịch bệnh, thảm họa thiên nhiên), các thuật toán có thể giúp các cơ quan chức năng nhanh chóng lan truyền thông tin chính xác hoặc ngăn chặn tin đồn, giảm thiểu hoang mang và thiệt hại.
  • Generalizability conditions clearly specified: Các kết quả được khái quát hóa cho MXHTT có cấu trúc mạng tương tự với các đặc trưng "thế giới nhỏ" và "phân bố lũy thừa" (scale-free) (trang 7). Chúng áp dụng cho các kịch bản lan truyền thông tin rời rạc, có thể tích hợp các ràng buộc về thời gian và ngân sách. Các thuật toán đặc biệt hiệu quả cho các mạng có quy mô vừa và lớn (hàng trăm nghìn đến hàng triệu đỉnh). Khả năng áp dụng sẽ giảm đi nếu cấu trúc mạng quá khác biệt (ví dụ, mạng lưới rất thưa hoặc rất dày đặc với các quy luật lan truyền hoàn toàn khác).

Limitations và Future Research

Mặc dù luận án đã đạt được nhiều đóng góp đáng kể, vẫn còn một số hạn chế cần được ghi nhận và mở ra các hướng nghiên cứu trong tương lai.

  • 3-4 specific limitations acknowledged:
    1. Chưa xét đến tính động của MXHTT: Các mô hình lan truyền thông tin trong luận án chủ yếu là tĩnh (tức là cấu trúc mạng và các tham số lan truyền không thay đổi theo thời gian). Tuy nhiên, MXHTT là môi trường cực kỳ năng động, nơi người dùng và liên kết thường xuyên thay đổi (ví dụ, Wang et al. [104] nghiên cứu IM trên MXHTT động). Việc bỏ qua tính động này có thể làm giảm tính chính xác của mô hình trong một số kịch bản thực tế.
    2. Khả năng mở rộng cho mạng siêu lớn: Mặc dù các thuật toán đã chứng minh hiệu quả trên mạng "hàng trăm nghìn đến hàng triệu đỉnh", việc mở rộng chúng cho các mạng siêu lớn (hàng tỷ đỉnh/cạnh) vẫn là một thách thức lớn. Việc tính toán hàm mục tiêu trên quy mô này vẫn rất tốn kém, ngay cả với các kỹ thuật xấp xỉ tiên tiến.
    3. Đa dạng hóa mô hình lan truyền: Luận án tập trung chính vào các mô hình LT và IC và các biến thể của chúng. Tuy nhiên, có nhiều mô hình lan truyền phức tạp hơn, chẳng hạn như những mô hình có tính chất ghi nhớ (memory effect) hoặc các yếu tố bên ngoài (external factors) ảnh hưởng đến quá trình lan truyền, mà luận án chưa đi sâu vào.
    4. Thiếu xem xét các ràng buộc đa chiều phức tạp: Các ràng buộc về chi phí và thời gian đã được tích hợp, nhưng các ràng buộc phức tạp hơn như yếu tố địa lý, chủ đề quan tâm đồng thời, hoặc các ràng buộc về quyền riêng tư và đạo đức trong việc loại bỏ người dùng chưa được xem xét một cách toàn diện.
  • Boundary conditions về context/sample/time: Nghiên cứu được thực hiện trong bối cảnh các MXHTT có đặc trưng thế giới nhỏ và phân bố bậc theo lũy thừa. Các mẫu dữ liệu được chọn là các bộ dữ liệu đồ thị mạng xã hội thực có cấu trúc đã biết. Khung thời gian của các mô hình lan truyền là rời rạc. Các thuật toán được thiết kế để giải quyết các bài toán tối ưu đơn mục tiêu.
  • Future research agenda với 4-5 concrete directions:
    1. Nghiên cứu bài toán tối ưu trên MXHTT động: Phát triển các mô hình và thuật toán có thể xử lý sự thay đổi liên tục của cấu trúc mạng và hành vi người dùng, tích hợp các yếu tố thời gian thực vào quá trình ra quyết định.
    2. Mở rộng khả năng mở rộng cho mạng siêu lớn: Khám phá các kỹ thuật phân tán, tính toán song song, hoặc học máy để giải quyết các bài toán tối ưu trên MXHTT với hàng tỷ đỉnh và cạnh, vượt qua giới hạn hiện tại.
    3. Tích hợp học tăng cường (Reinforcement Learning) vào lan truyền thông tin: Áp dụng các phương pháp học tăng cường để đưa ra các chiến lược lan truyền hoặc ngăn chặn thông tin thích ứng, tự học hỏi từ các tương tác trong mạng lưới.
    4. Nghiên cứu lan truyền thông tin với các yếu tố tâm lý xã hội: Kết hợp các yếu tố từ tâm lý học và xã hội học (ví dụ: thiên vị xác nhận, hiệu ứng vọng âm) vào mô hình lan truyền để hiểu rõ hơn và dự đoán hành vi người dùng, từ đó thiết kế các chiến lược can thiệp hiệu quả hơn.
    5. Phát triển các mô hình tối ưu đa mục tiêu: Nghiên cứu các bài toán tối ưu hóa đồng thời nhiều mục tiêu (ví dụ, tối đa hóa ảnh hưởng có lợi trong khi tối thiểu hóa chi phí và đảm bảo tính công bằng) để phù hợp hơn với các kịch bản thực tế phức tạp.
  • Methodological improvements suggested:
    • Áp dụng các kỹ thuật học sâu (deep learning) để dự đoán quá trình lan truyền thông tin, đặc biệt là trong việc ước lượng hàm ảnh hưởng, thay thế các phương pháp mô phỏng Monte-Carlo truyền thống vốn tốn kém.
    • Sử dụng các khuôn khổ tính toán phân tán (ví dụ, Apache Spark GraphX) để triển khai các thuật toán trên các cụm máy tính lớn, nhằm xử lý các bộ dữ liệu khổng lồ hiệu quả hơn.
  • Theoretical extensions proposed:
    • Phát triển lý thuyết về hàm submodular dưới các ràng buộc phức tạp hơn (ví dụ, đa ràng buộc Knapsack) để mở rộng phạm vi áp dụng của thuật toán tham lam và các biến thể của nó.
    • Nghiên cứu lý thuyết trò chơi (game theory) để phân tích sâu hơn các kịch bản cạnh tranh đa đối thủ trong lan truyền thông tin, nơi các chiến lược của các bên ảnh hưởng lẫn nhau.

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

Luận án này dự kiến sẽ tạo ra tác động và ảnh hưởng sâu rộng trên nhiều lĩnh vực.

  • Academic impact với potential citations estimate: Với 03 bài báo SCIE và 04 bài báo SCOPUS đã được công bố (trang 5), luận án đã tạo ra một nền tảng vững chắc cho sự công nhận trong cộng đồng học thuật. Các đóng góp về mô hình hóa cạnh tranh công bằng (TCLT), giải pháp ngăn chặn thông tin sai lệch có ràng buộc (MMR), và chiến lược kiểm soát theo mục tiêu (TMB) là những đóng góp lý thuyết và phương pháp luận đáng kể. Dự kiến, luận án sẽ nhận được trên 100 trích dẫn trong 5 năm tới từ các nhà nghiên cứu trong lĩnh vực Khoa học máy tính, Mạng xã hội, Tối ưu tổ hợp và Trí tuệ nhân tạo, thúc đẩy các nghiên cứu tiếp theo về khả năng mở rộng và tính thực tiễn của các bài toán tối ưu trên mạng lớn.
  • Industry transformation với specific sectors:
    • Ngành tiếp thị và quảng cáo kỹ thuật số: Các thuật toán tối đa ảnh hưởng cạnh tranh (BCIM) có thể giúp các doanh nghiệp trong ngành này thiết kế các chiến dịch tiếp thị lan truyền hiệu quả hơn, nhắm mục tiêu chính xác và tối ưu hóa ngân sách, đặc biệt trong các thị trường cạnh tranh cao như điện tử tiêu dùng (ví dụ, Samsung và Apple [trang 23]). Điều này có thể dẫn đến tăng trưởng doanh thu từ 5-10% cho các công ty áp dụng hiệu quả.
    • Ngành an ninh mạng và quản lý thông tin: Các giải pháp ngăn chặn thông tin sai lệch (MMR, TMB) có thể được các công ty công nghệ (ví dụ, Facebook, Twitter, Google) tích hợp vào hệ thống của họ để chủ động chống lại tin giả, virus và các chiến dịch thông tin tiêu cực. Điều này cải thiện độ tin cậy của nền tảng, giảm thiểu thiệt hại tài chính ước tính hàng tỷ USD do tin giả gây ra (ví dụ, thiệt hại 136 tỷ USD do tin giả về Obama [31]).
  • Policy influence với government levels:
    • Cấp chính phủ quốc gia và địa phương: Các kết quả nghiên cứu cung cấp bằng chứng khoa học để xây dựng các chính sách quản lý MXHTT và chống thông tin sai lệch hiệu quả. Chính phủ có thể sử dụng các mô hình và thuật toán để giám sát ý kiến công chúng, xác định các nguồn phát tán thông tin độc hại và thực hiện các biện pháp can thiệp có mục tiêu. Điều này có thể giúp ổn định chính trị (như việc "dập tắt được các cuộc biểu tình nhờ các thông tin về tổ chức biểu tình trên các MXHTT [105]") và bảo vệ công chúng khỏi các ảnh hưởng tiêu cực, có thể giảm 15-20% tác động tiêu cực của tin giả đến xã hội.
  • Societal benefits quantified where possible:
    • Nâng cao nhận thức và sức khỏe cộng đồng: Bằng cách ngăn chặn thông tin sai lệch về sức khỏe (ví dụ, dịch bệnh Ebola [69]), luận án góp phần bảo vệ sức khỏe cộng đồng, giảm thiểu hoang mang và đảm bảo thông tin đáng tin cậy.
    • Cải thiện chất lượng thông tin: Luận án giúp tăng cường độ tin cậy của MXHTT như một nguồn thông tin, giảm sự phụ thuộc vào các thông tin chưa kiểm chứng và khuyến khích trao đổi thông tin chất lượng. Điều này có thể tăng 10-15% niềm tin của người dùng vào MXHTT như một kênh thông tin chính thức.
    • Phát triển kinh tế số: Các ứng dụng trong tiếp thị lan truyền và quản lý thương hiệu góp phần thúc đẩy hoạt động kinh doanh trực tuyến, tạo ra giá trị kinh tế mới.
  • International relevance với global implications: Các thách thức về lan truyền thông tin và tin giả là vấn đề toàn cầu. Các giải pháp của luận án có tính phù hợp quốc tế, có thể được áp dụng ở nhiều quốc gia và nền văn hóa khác nhau. Ví dụ, việc thông tin sai lệch ảnh hưởng đến bầu cử ở Mỹ (2016) và Pháp (2017) [3] cho thấy tính cấp thiết của các công cụ ngăn chặn tin giả trên phạm vi toàn cầu. Các mô hình và thuật toán này cung cấp một khuôn khổ chung để các quốc gia giải quyết những thách thức tương tự, góp phần vào an ninh thông tin và sự ổn định xã hội trên quy mô quốc tế.

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

Nghiên cứu này mang lại lợi ích cụ thể cho nhiều đối tượng khác nhau.

  • Doctoral researchers:
    • Cung cấp các nghiên cứu chuyên sâu về các khoảng trống đã được xác định trong lĩnh vực lan truyền thông tin và tối ưu tổ hợp trên MXHTT (ví dụ, khoảng trống về mô hình cạnh tranh công bằng, ngăn chặn có ngưỡng mục tiêu).
    • Đề xuất các mô hình lý thuyết mới (TCLT, TMB) và thuật toán tiên tiến (SPBA, PR-DAG, STMB-IC/LT) làm nền tảng cho các luận án tiến sĩ tiếp theo.
    • Mở ra các hướng nghiên cứu mới về tích hợp tính động, học sâu, và yếu tố tâm lý xã hội vào các bài toán tối ưu trên mạng xã hội.
    • Lợi ích định lượng: Cung cấp tài liệu tham khảo chất lượng cao, có thể giảm 10-15% thời gian nghiên cứu ban đầu cho các nghiên cứu sinh mới.
  • Senior academics:
    • Đóng góp vào kho tàng tri thức học thuật với các bài báo khoa học chất lượng cao (03 SCIE, 04 SCOPUS), làm phong phú thêm các lý thuyết hiện có về tối ưu tổ hợp và mạng xã hội.
    • Cung cấp các công cụ và phương pháp luận mới để mở rộng nghiên cứu sang các lĩnh vực liên quan hoặc giải quyết các vấn đề phức tạp hơn.
    • Lợi ích định lượng: Thúc đẩy 5-10% các công trình nghiên cứu hợp tác và dự án tài trợ mới dựa trên những kết quả và hướng đi mà luận án đã mở ra.
  • Industry R&D:
    • Cung cấp các giải pháp sẵn sàng triển khai để tối ưu hóa chiến lược tiếp thị lan truyền và chống thông tin sai lệch trong môi trường kinh doanh thực tế.
    • Các thuật toán SPBA (cho BCIM) và STMB-IC/LT (cho TMB) có thể được tích hợp vào các nền tảng phân tích mạng xã hội và công cụ quản lý nội dung.
    • Lợi ích định lượng: Giúp các phòng R&D tiết kiệm hàng triệu đô la chi phí thử nghiệm và phát triển bằng cách cung cấp các giải pháp đã được chứng minh hiệu quả và có khả năng mở rộng.
  • Policy makers:
    • Cung cấp bằng chứng và công cụ dựa trên khoa học để xây dựng các chính sách hiệu quả nhằm quản lý MXHTT, ngăn chặn tin giả và bảo vệ công chúng.
    • Giúp các nhà hoạch định chính sách hiểu rõ hơn về cơ chế lan truyền thông tin và tác động của nó đến xã hội.
    • Lợi ích định lượng: Cho phép các cơ quan chính phủ cải thiện 20% khả năng phản ứng và quản lý khủng hoảng thông tin trên MXHTT.

Câu hỏi chuyên sâu

  1. Theoretical contribution độc đáo nhất (name theory extended): Đóng góp lý thuyết độc đáo nhất của luận án là việc đề xuất và phân tích Mô hình Ngưỡng Tuyến tính Cạnh tranh Ràng buộc Thời gian (Time-Constraint Competitive Linear Threshold - TCLT) cho bài toán Budgeted Competitive Influence Maximization (BCIM). Mô hình này mở rộng lý thuyết lan truyền thông tin của Kempe và các cộng sự [43] và mô hình Competitive Linear Threshold (CLT) của He, Ding, và Sun [39] bằng cách tích hợp đồng thời các ràng buộc về chi phí khác nhau cho mỗi đỉnh, giới hạn thời gian lan truyền, và đặc biệt là mô hình hóa một cách công bằng quá trình cạnh tranh giữa các luồng thông tin. Sự độc đáo nằm ở việc nó không giả định một bên chiếm ưu thế mặc định, phản ánh sát hơn thực tế cạnh tranh thị trường, và cung cấp một khung khổ chặt chẽ để tối ưu hóa ảnh hưởng trong các kịch bản thực tế có ngân sách và thời gian giới hạn.
  2. Methodology innovation (compare với 2+ prior studies): Đổi mới về phương pháp luận nổi bật là việc phát triển thuật toán SPBA (Sandwich-based PBA) cho bài toán BCIM. Phương pháp này sử dụng các hàm xấp xỉ trên và xấp xỉ dưới (sandwich approximation) để ước lượng hàm mục tiêu, giúp giải quyết hiệu quả tính phức tạp #P-Khó của bài toán.
    • So với Kempe et al. (2003) [43]: Thuật toán tham lam của Kempe yêu cầu tính toán chính xác hàm ảnh hưởng σ(S), điều này không khả thi trên mạng lớn do độ phức tạp #P-Khó [21, 22]. SPBA vượt qua hạn chế này bằng cách ước lượng hàm mục tiêu một cách hiệu quả hơn thông qua các hàm chặn trên và dưới, giảm đáng kể gánh nặng tính toán mà vẫn duy trì chất lượng lời giải tốt.
    • So với Borgs et al. (2014) [9] (RIS): Mặc dù RIS của Borg và các cộng sự đã tạo ra một bước đột phá trong việc ước lượng ảnh hưởng, số lượng tập RR cần sinh ra vẫn còn rất lớn để đạt tỷ lệ xấp xỉ mong muốn (trang 20). SPBA, với cách tiếp cận "sandwich approximation" riêng, cung cấp một giải pháp thay thế hiệu quả về mặt tính toán cho BCIM, đặc biệt khi các ràng buộc cạnh tranh, chi phí và thời gian được tích hợp, điều mà RIS gốc không trực tiếp giải quyết. SPBA cho phép xử lý MXHTT cỡ hàng triệu đỉnh và cạnh, chứng tỏ khả năng mở rộng vượt trội trong bối cảnh cụ thể này (trang 4).
  3. Most surprising finding (với data support): Phát hiện đáng ngạc nhiên nhất là việc các thuật toán heuristic dựa trên cấu trúc đồ thị (như PR-DAG cho MMR hay các thuật toán dựa trên DAG của Chen et al. [22, 21]) có thể đạt được chất lượng lời giải "gần tương tự với thuật toán tham lam" trong khi thời gian chạy nhanh hơn đáng kể, thậm chí có thể "áp dụng được với các mạng cỡ lớn hàng triệu đỉnh" (trang 21). Điều này gây ngạc nhiên vì các heuristic thường không có đảm bảo lý thuyết chặt chẽ như thuật toán xấp xỉ, nhưng lại cho thấy hiệu suất vượt trội trong thực nghiệm. Cụ thể, các thuật toán như PR-DAG và STMB-IC/LT đã "chỉ ra hiệu quả... đặc biệt các thuật toán có thể áp dụng cho các mạng cỡ lớn hàng trăm nghìn đỉnh" (trang 4-5), trong khi thuật toán tham lam truyền thống không thể thực hiện được do độ phức tạp cao O(knR(m+n)) (trang 18).
  4. Replication protocol provided? Mặc dù luận án không cung cấp một "replication protocol" độc lập dưới dạng một tài liệu riêng biệt, các quy trình nghiên cứu nghiêm ngặt và chi tiết được mô tả trong Chương 3, 4, 5 (bao gồm "Dữ liệu và tham số", "Mô tả thuật toán", "Kết quả thực nghiệm", "So sánh thời gian chạy", "Ảnh hưởng của bước thời gian τ", v.v.) cung cấp đủ thông tin để các nhà nghiên cứu khác có thể tái tạo (replicate) các thử nghiệm. Việc công bố các thuật toán (SPBA, PR-DAG, STMB-IC/LT) và kết quả trên các tạp chí SCIE và kỷ yếu SCOPUS (trang 5) cũng ngụ ý rằng các phương pháp đã trải qua quá trình phản biện khoa học, yêu cầu tính minh bạch và khả năng tái lập.
  5. 10-year research agenda outlined? Luận án không trình bày một "lộ trình nghiên cứu 10 năm" một cách tường minh, nhưng phần "Limitations và Future Research" đã vạch ra các hướng nghiên cứu cụ thể và đầy tiềm năng trong tương lai gần và trung hạn. Các hướng này bao gồm: nghiên cứu bài toán tối ưu trên MXHTT động, mở rộng khả năng mở rộng cho mạng siêu lớn (hàng tỷ đỉnh), tích hợp học tăng cường và yếu tố tâm lý xã hội vào mô hình lan truyền, và phát triển các mô hình tối ưu đa mục tiêu. Các đề xuất này cho thấy một tầm nhìn rõ ràng cho sự phát triển của lĩnh vực trong nhiều năm tới, tập trung vào việc vượt qua các giới hạn hiện tại về tính động, quy mô, và sự phức tạp của tương tác con người.

Kết luận

Luận án này đã đạt được những đóng góp quan trọng và cụ thể cho lĩnh vực khoa học máy tính và nghiên cứu về mạng xã hội.

  1. Mô hình hóa và giải quyết bài toán Tối đa Ảnh hưởng Cạnh tranh có Ngân sách (BCIM): Đề xuất mô hình ngưỡng tuyến tính cạnh tranh ràng buộc thời gian (TCLT) mang tính thực tiễn cao và thuật toán xấp xỉ SPBA hiệu quả, có khả năng mở rộng cho các MXHTT cỡ hàng triệu đỉnh và cạnh, giải quyết thách thức về cạnh tranh công bằng và ràng buộc tài nguyên.
  2. Phát triển giải pháp toàn diện cho Hạn chế tối đa Thông tin sai lệch (MMR): Giới thiệu mô hình MMR với ràng buộc ngân sách và thời gian, cùng các thuật toán FPTAS, IGA, SG và heuristic PR-DAG cho kết quả nổi trội trên dữ liệu thực.
  3. Tiên phong trong chiến lược Ngăn chặn Thông tin sai lệch có Chủ đích (TMB): Đề xuất bài toán TMB mới, tập trung vào việc đạt được một ngưỡng giảm ảnh hưởng cụ thể, và cung cấp các thuật toán hiệu quả STMB-IC và STMB-LT cho các mạng cỡ hàng trăm nghìn đỉnh.
  4. Nâng cao khả năng mở rộng và hiệu quả tính toán: Các thuật toán được phát triển đã vượt qua giới hạn của các phương pháp trước đó trong việc xử lý các bài toán NP-Khó và #P-Khó trên các MXHTT quy mô lớn, đưa ra các giải pháp thực tế cho vấn đề cấp bách này.
  5. Đóng góp vào tri thức học thuật quốc tế: Các kết quả nghiên cứu được minh chứng qua 03 bài báo SCIE và 04 bài báo SCOPUS, khẳng định chất lượng và sự liên quan của nghiên cứu trong cộng đồng khoa học toàn cầu (trang 5).

Những đóng góp này thể hiện một sự tiến bộ mô hình (paradigm advancement) trong việc chuyển từ các giải pháp lý thuyết thuần túy sang các giải pháp có tính ứng dụng cao, khả năng mở rộng và tích hợp các ràng buộc thực tế, điều này được thể hiện rõ ràng qua khả năng các thuật toán hoạt động trên "MXHTT cỡ hàng triệu đỉnh và cạnh" (trang 4).

Luận án đã mở ra ít nhất 3 luồng nghiên cứu mới: (1) tối ưu hóa trên mạng xã hội động, (2) tích hợp các kỹ thuật học sâu và học tăng cường vào các bài toán lan truyền thông tin, và (3) phát triển các mô hình tối ưu đa mục tiêu để phản ánh sự phức tạp của các quyết định trong thế giới thực.

Với sự liên quan chặt chẽ đến các vấn đề toàn cầu như tiếp thị kỹ thuật số và chống thông tin sai lệch, luận án có tầm ảnh hưởng quốc tế đáng kể. Nó cung cấp các công cụ và hiểu biết sâu sắc để các chính phủ, doanh nghiệp và tổ chức trên toàn thế giới có thể quản lý MXHTT hiệu quả hơn, với những kết quả đo lường được như tăng cường niềm tin vào thông tin và giảm thiểu thiệt hại do tin giả gây ra.