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" của Phạm Văn Cảnh, chuyên ngành Khoa học máy tính, do GS. TS Thái Trà My và PGS. TS Hoàng Xuân Huấn hướng dẫn, trình bày một nghiên cứu tiên phong trong lĩnh vực tối ưu hóa trên mạng xã hội trực tuyến (MXHTT). Trong bối cảnh sự phát triển bùng nổ của MXHTT, với "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]", nghiên cứu này giải quyết những thách thức cấp bách trong việc quản lý và điều khiển dòng chảy thông tin, từ việc tối đa hóa lan truyền thông tin tích cực đến ngăn chặn hiệu quả thông tin sai lệch và các yếu tố tiêu cực.

Bối cảnh khoa học và tính tiên phong của nghiên cứu Nghiên cứu được đặt trong bối cảnh khoa học máy tính, đặc biệt là lĩnh vực tối ưu tổ hợp (TƯTH) trên đồ thị. Luận án nổi bật bởi việc giải quyết các bài toán lan truyền thông tin (information diffusion problems) trên MXHTT, vốn thường thuộc "lớp bài toán tối ưu tổ hợp NP-Khó" và "việc tính toán hàm mục tiêu thường là #P-Khó [21, 22]". Tính tiên phong của luận án nằm ở việc đề xuất các biến thể bài toán mới phù hợp với thực tiễn, phát triển các mô hình lan truyền cạnh tranh công bằng hơn, và đặc biệt là thiết kế các thuật toán xấp xỉ hiệu quả, có khả năng mở rộng để xử lý "MXHTT cỡ hàng triệu đỉnh và cạnh".

Research gap SPECIFIC với citations từ literature Luận án xác định rõ các khoảng trống nghiên cứu then chốt trong các lĩnh vực Tối đa hóa ảnh hưởng (Influence Maximization - IM) và Ngăn chặn ảnh hưởng (Influence Blocking - IB):

  1. Trong Tối đa ảnh hưởng cạnh tranh (Competitive Influence Maximization - CIM): Các mô hình lan truyền cạnh tranh hiện có (ví dụ: Bharathi et al. [8]) thường giả định một bên chiếm lợi thế, điều này "không phản ánh sự cạnh tranh công bằng giữa hai luồng thông tin về sản phẩm trong lan truyền tiếp thị". Hơn nữa, các nghiên cứu trước đây như của Chen et al. [20] hoặc Nguyen et al. [72] chưa đồng thời xem xét đầy đủ các ràng buộc thực tế như chi phí khác nhau cho mỗi đỉnh và giới hạn thời gian lan truyền.
  2. Trong Ngăn chặn ảnh hưởng (Influence Blocking - IB): Các phương pháp hiện có cho IB, bao gồm cả các nghiên cứu về "tiêm vắc-xin" bởi Yang et al. [117] hoặc Zhang et al. [115], thường bỏ qua hai yếu tố quan trọng là "chi phí và thời gian trong ngăn chặn ảnh hưởng". Việc loại bỏ người dùng hoặc thuyết phục họ thường không đồng nhất về chi phí và thời gian.
  3. Về mục tiêu ngăn chặn thông tin sai lệch: Chưa có nghiên cứu nào tập trung vào bài toán "tìm tập đỉnh nhỏ nhất để loại bỏ ra khỏi mạng sao cho số đỉnh bị ảnh hưởng bởi thông tin sai lệch giảm đi với một ngưỡng γ cho trước", một mục tiêu cụ thể và khác biệt so với việc tối đa hóa hạn chế thông tin sai lệch với ngân sách cố định.

Research questions và hypotheses (đánh số cụ thể) Luận án không trình bày tường minh các câu hỏi nghiên cứu và giả thuyết theo một danh sách đánh số, nhưng dựa trên phần "Mục tiêu" và "Đóng góp", có thể suy ra các câu hỏi chính như sau: 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) một cách hiệu quả trên các MXHTT quy mô lớn, khi xét đến ràng buộc về ngân sách và thời gian, cũng như đảm bảo sự cạnh tranh công bằng giữa các luồng thông tin? RQ2: Làm thế nào để thiết kế các thuật toán xấp xỉ có chất lượng lời giải cao và khả năng mở rộng cho bài toán BCIM trên các mô hình lan truyền cạnh tranh mới như TCLT? RQ3: Làm thế nào để hạn chế tối đa thông tin sai lệch (MMR) trên MXHTT dưới ràng buộc về ngân sách và thời gian, và phát triển các thuật toán hiệu quả để giải quyết độ phức tạp #P-Khó của bài toán? RQ4: Làm thế nào để giải quyết bài toán Ngăn chặn thông tin sai lệch có chủ đích (TMB), tìm tập đỉnh loại bỏ nhỏ nhất để giảm ảnh hưởng thông tin sai lệch xuống dưới một ngưỡng xác định, trên các mô hình lan truyền IC và LT? RQ5: Các thuật toán đề xuất có thể áp dụng cho các mạng xã hội thực tế với "cỡ hàng trăm nghìn cho tới hàng triệu, tỷ cạnh hoặc đỉnh" hay không và chúng có vượt trội hơn các phương pháp hiện có về hiệu quả và chất lượng lời giải không?

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 nền tảng vững chắc trong Khoa học máy tính và Lý thuyết đồ thị:

  • Lý thuyết đồ thị: MXHTT được biểu diễn dưới dạng đồ thị có hướng G = (V, E), với V là tập người dùng và E là tập liên kết, cho phép mô hình hóa các tương tác và lan truyền.
  • Mô hình lan truyền thông tin:
    • Mô hình Ngưỡng tuyến tính (Linear Threshold - LT) của Kempe và cộng sự [43]: Mô tả hành vi "ngưỡng" của người dùng khi chịu ảnh hưởng.
    • Mô hình Bậc độc lập (Independent Cascade - IC) của Kempe và cộng sự [43]: Mô tả quá trình lan truyền độc lập theo xác suất.
    • Mô hình Cạnh trực tuyến (Live-edge Model) của Kempe và Chen et al. [19]: Một mô hình tương đương cho phép tính toán hàm ảnh hưởng hiệu quả hơn, là nền tảng cho các thuật toán xấp xỉ.
    • Mô hình Ngưỡng tuyến tính cạnh tranh ràng buộc thời gian (TCLT): Một mô hình mới được đề xuất để phản ánh sự cạnh tranh công bằng hơn trong lan truyền thông tin, tích hợp yếu tố thời gian và chi phí.
    • Mô hình ngưỡng tuyến tính mở rộng: Được đề xuất cho bài toán MMR để tích hợp ràng buộc về ngân sách và thời gian.
  • Lý thuyết tối ưu tổ hợp: Các bài toán IM, IB được xây dựng dưới dạng TƯTH, với phân loại độ phức tạp (NP-Khó, #P-Khó) theo Valiant [98, 99].
  • Lý thuyết thuật toán xấp xỉ: Dựa trên các tính chất của hàm mục tiêu như tính đơn điệu tăng và hàm submodular (Khuller et al. [46]), luận án áp dụng và phát triển các thuật toán tham lam (Greedy Algorithm) với tỷ lệ xấp xỉ lý thuyết là 1 - 1/e.
  • Kỹ thuật ước lượng hàm mục tiêu: Sử dụng "phương pháp mô phỏng Mote-Carlo" và "Mẫu ảnh hưởng ngược (Reverse Influence Sampling - RIS)" của Borg et al. [9] để ước lượng hàm ảnh hưởng, vốn thuộc lớp #P-Khó.

Đóng góp đột phá với quantified impact Luận án mang lại nhiều đóng góp đột phá, được minh chứng bằng kết quả thực nghiệm và công bố quốc tế:

  1. Mô hình hóa và giải thuật cho BCIM: Đề xuất mô hình TCLT mới cho lan truyền cạnh tranh, tích hợp ngân sách và thời gian, và phát triển thuật toán SPBA. "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", vượt xa khả năng mở rộng của nhiều thuật toán CIM trước đây (Bharathi et al. [8]).
  2. Khung giải quyết toàn diện MMR: Đề xuất mô hình MMR trên ngưỡng tuyến tính mở rộng, chỉ ra độ phức tạp NP-Khó và phát triển bộ thuật toán xấp xỉ FPTAS, IGA, SG, và heuristic PR-DAG. Các thuật toán này cung cấp giải pháp hiệu quả cho việc hạn chế thông tin sai lệch, đặc biệt trong các trường hợp có thể đạt được FPTAS trên cây có gốc.
  3. Bài toán TMB tiên phong: Xác định và giải quyết bài toán TMB mới, tìm tập loại bỏ nhỏ nhất để đạt được ngưỡng hạn chế thông tin sai lệch cụ thể (γ), đưa ra các thuật toán STMB-IC và STMB-LT. "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", mở ra hướng nghiên cứu mới về quản lý thông tin theo mục tiêu định lượng.
  4. Nâng cao khả năng mở rộng của thuật toán: Các giải thuật được đề xuất (SPBA, PR-DAG, STMB-IC/LT) đều được chứng minh có khả năng xử lý "mạng cỡ lớn hàng trăm nghìn cho tới hàng triệu, tỷ cạnh hoặc đỉnh", giải quyết thách thức cốt lõi mà "việc giải quyết và áp dụng hai nhóm bài toán trên trong thực tiễn gặp một số thách thức chính là: 1. Lớp bài toán này thường thuộc lớp bài toán tối ưu tổ hợp NP-Khó".

Scope (sample size, timeframe) và significance Phạm vi nghiên cứu bao gồm các MXHTT được mô hình hóa dưới dạng đồ thị có hướng. Các thực nghiệm được tiến hành trên "các bộ dữ liệu MXHTT thực", với khả năng mở rộng lên đến "hàng triệu đỉnh và cạnh". Yếu tố thời gian được tích hợp vào mô hình lan truyền (ví dụ, TCLT) và ràng buộc thời gian được xét đến trong các bài toán (BCIM, MMR), phản ánh tính động của MXHTT. Tầm quan trọng của luận án là rất lớn, cung cấp "những giải pháp hiệu quả trong việc quản lý những thông tin trên MXHTT, bao gồm các nhiệm vụ: phát tán thông tin cần thiết, ngăn chặn những thông tin xấu, các ảnh hưởng tiêu cực một cách hiệu quả." Nghiên cứu góp phần nâng cao "sự phục vụ, độ tin cậy của MXHTT đối với cộng đồng người dùng."

Literature Review và Positioning

Synthesis của major streams với TÊN TÁC GIẢ và NĂM cụ thể Nghiên cứu của Phạm Văn Cảnh tổng hợp các luồng chính về lan truyền thông tin trên MXHTT, bắt đầu từ các công trình nền tảng của Kempe và cộng sự [43] (2003) về các mô hình Linear Threshold (LT) và Independent Cascade (IC) và bài toán Influence Maximization (IM). Luận án cũng đề cập đến các nghiên cứu mở rộng IM theo thời gian (Chen et al. [20]), chi phí (Nguyen et al. [72]), khoảng cách (Wang et al. [101]) và cạnh tranh (Bharathi et al. [8], 2007). Luồng thứ hai là Ngăn chặn ảnh hưởng (Influence Blocking - IB), với các phương pháp loại bỏ đỉnh/cạnh (Khalil et al. [45]) hoặc tẩy nhiễm thông tin (Budak et al. [13], 2011; He et al. [39], 2012). Các kỹ thuật giải quyết độ phức tạp NP-Khó và #P-Khó của các bài toán này cũng được tổng hợp, từ phương pháp Monte-Carlo của Kempe et al. [44] đến đột phá lý thuyết của Borg et al. [9] (2014) với Reverse Influence Sampling (RIS), sau đó được cải tiến bởi Tang et al. [95, 94] (2015, 2016) và Hung T. Nguyen et al. [75] (2016). Các thuật toán heuristic dựa trên độ đo (degree centrality), đường đi (Chen et al. [22], 2010), và cấu trúc cộng đồng cũng được phân tích.

Contradictions/debates với ít nhất 2 opposing views Luận án làm nổi bật một số mâu thuẫn và tranh luận trong các nghiên cứu trước đây:

  1. Về mô hình cạnh tranh: Nhiều mô hình lan truyền cạnh tranh như của He et al. [39] giả thuyết rằng một bên (thường là thông tin chính thống) có lợi thế khi cạnh tranh, "nó không phản ánh sự cạnh tranh công bằng giữa hai luồng thông tin về sản phẩm trong lan truyền tiếp thị." Điều này mâu thuẫn với nhu cầu mô hình hóa sự cạnh tranh thị trường công bằng.
  2. Về khả năng mở rộng của thuật toán: Mặc dù các thuật toán xấp xỉ như RIS của Borg et al. [9] đưa ra tỷ lệ lý thuyết tốt, "một trong các hạn chế của thuật toán này là số tập RR sinh ra đủ để cho được tỷ lệ tối ưu trên 1 − 1/e − là khá lớn nên nó khó có thể áp dụng cho mạng cỡ lớn." Điều này tạo ra một sự đánh đổi giữa chất lượng lời giải lý thuyết và khả năng mở rộng thực tế, khi các thuật toán heuristic thường nhanh hơn nhưng không có đảm bảo lý thuyết.

Positioning trong literature với specific gap identified Luận án được định vị một cách chiến lược bằng cách trực tiếp giải quyết các khoảng trống đã xác định. Cụ thể, nó mở rộng các mô hình lan truyền thông tin cơ bản (LT, IC) bằng cách tích hợp các yếu tố thực tế như chi phí và thời gian, cũng như cơ chế cạnh tranh công bằng hơn. Thay vì chỉ tối đa hóa hoặc tối thiểu hóa ảnh hưởng một cách chung chung, luận án đưa ra các biến thể bài toán mới, điển hình là TMB, giải quyết nhu cầu ngăn chặn thông tin sai lệch một cách có mục tiêu và định lượng, điều mà các nghiên cứu trước đây như của Zhang [110] chưa đạt được với tỷ lệ xấp xỉ.

How this advances field với concrete contributions Nghiên cứu này thúc đẩy lĩnh vực Khoa học máy tính bằng cách:

  • Đề xuất các mô hình lan truyền mới: Đặc biệt là mô hình Ngưỡng tuyến tính cạnh tranh ràng buộc thời gian (TCLT), cung cấp một công cụ mạnh mẽ hơn để phân tích sự năng động của MXHTT trong môi trường cạnh tranh.
  • Thiết kế các thuật toán xấp xỉ hiệu quả: Phát triển các giải pháp như SPBA cho BCIM, FPTAS và PR-DAG cho MMR, và STMB-IC/LT cho TMB, với "khả năng mở rộng cho mạng cỡ lớn (hàng triệu đỉnh hoặc cạnh)".
  • Đưa ra các bài toán mới có tính ứng dụng cao: Bài toán Hạn chế thông tin sai lệch có chủ đích (TMB) là một ví dụ nổi bật, chuyển hướng từ tối ưu hóa chung sang đạt được các mục tiêu định lượng cụ thể, có ý nghĩa lớn trong thực tiễn quản lý thông tin.

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

  1. So sánh với Kempe et al. [43] và Chen et al. [21, 22]: Trong khi Kempe và các cộng sự đặt nền móng cho các bài toán IM và IB với các mô hình LT/IC và chứng minh tính NP-Khó, cũng như Chen và các cộng sự chỉ ra tính #P-Khó của việc tính toán hàm mục tiêu, luận án của Phạm Văn Cảnh vượt lên bằng cách tích hợp thêm các ràng buộc thực tế như thời gian và ngân sách vào các biến thể bài toán mới. Ví dụ, bài toán BCIM mở rộng IM bằng cách xem xét nhiều đối thủ cạnh tranh và chi phí/thời gian, điều mà các công trình gốc chưa giải quyết đầy đủ.
  2. So sánh với Borg et al. [9] và Tang et al. [94]: Các nghiên cứu này đã tạo ra bước đột phá về lý thuyết với Reverse Influence Sampling (RIS) và các cải tiến (TIM/TIM++, IMM) để đạt được tỷ lệ xấp xỉ 1 - 1/e - ε cho IM. Tuy nhiên, luận án của Phạm Văn Cảnh tập trung vào các biến thể bài toán phức tạp hơn (cạnh tranh, ngăn chặn có mục tiêu) và phát triển các thuật toán (như SPBA, PR-DAG) không chỉ đảm bảo chất lượng lời giải mà còn tập trung mạnh mẽ vào khả năng mở rộng thực tế trên "MXHTT cỡ hàng triệu đỉnh và cạnh", một điểm yếu mà Borg et al. [9] đã thừa nhận là "số tập RR sinh ra đủ... là khá lớn nên nó khó có thể áp dụng cho mạng cỡ lớn."

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

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

Luận án mở rộng và thách thức một số lý thuyết cốt lõi trong lĩnh vực mạng xã hội và tối ưu tổ hợp:

  • Extend/challenge WHICH specific theories (name theorists):
    • Mở rộng mô hình lan truyền của Kempe et al. [43]: Luận án không chỉ sử dụng các mô hình LT và IC làm nền tảng mà còn phát triển các biến thể như Ngưỡng tuyến tính cạnh tranh ràng buộc thời gian (TCLT). Mô hình TCLT thách thức giả định về sự ưu tiên của một bên trong các mô hình cạnh tranh trước đó của He et al. [39] bằng cách mô hình hóa "sự cạnh tranh công bằng giữa hai luồng thông tin", phù hợp hơn cho các ứng dụng tiếp thị sản phẩm.
    • Mở rộng lý thuyết về hàm submodular: Luận án áp dụng chặt chẽ lý thuyết hàm submodular để chứng minh tỷ lệ xấp xỉ cho các thuật toán tham lam đối với các bài toán có tính chất này, như đã chỉ ra bởi Khuller et al. [46] cho Set Cover và Kempe et al. [43] cho IM. Điều này được thể hiện rõ trong việc phân tích "tỷ lệ xấp xỉ là 1 − 1/e" cho các bài toán khi hàm mục tiêu có tính submodular và đơn điệu tăng.
  • Conceptual framework với components và relationships: Khung phân tích khái niệm bao gồm:
    • Mạng xã hội: Được mô hình hóa như đồ thị G=(V,E), nơi V là người dùng và E là liên kết, với các thuộc tính như "đặc trưng thế giới nhỏ" [90, 29] và "phân bố lũy thừa" [26].
    • Các tác nhân lan truyền: Thông tin (tốt/xấu), chiến dịch tiếp thị, đối thủ cạnh tranh.
    • Các hành vi lan truyền: Được mô hình hóa qua LT, IC, và các biến thể như TCLT, dựa trên xác suất hoặc ngưỡng kích hoạt.
    • Các mục tiêu tối ưu: Tối đa hóa ảnh hưởng (IM, BCIM) hoặc ngăn chặn ảnh hưởng (IB, MMR, TMB).
    • Các ràng buộc: Ngân sách, thời gian, ngưỡng ảnh hưởng cụ thể (γ).
    • Mối quan hệ: Sự lựa chọn tập hạt giống (seed set) ảnh hưởng đến số lượng đỉnh được kích hoạt; các ràng buộc ảnh hưởng đến tính khả thi và chất lượng lời giải; độ phức tạp tính toán chi phối thiết kế thuật toán (xấp xỉ, heuristic).
  • Theoretical model với propositions/hypotheses numbered: Luận án đề xuất một số mô hình lý thuyết mới cùng các tiền đề/giả thuyết:
    • Mô hình TCLT cho BCIM (Chương 3):
      • Proposition 3.1: Bài toán BCIM trên mô hình TCLT là NP-Khó.
      • Hypothesis 3.1: Thuật toán SPBA có thể cung cấp một lời giải xấp xỉ hiệu quả cho BCIM với khả năng mở rộng cao trên các MXHTT lớn.
    • Mô hình ngưỡng tuyến tính mở rộng cho MMR (Chương 4):
      • Proposition 4.1: Bài toán MMR là NP-Khó và việc tính toán hàm mục tiêu là #P-Khó. (Minh họa bằng phép dẫn từ Knapsack).
      • Hypothesis 4.1: Các thuật toán xấp xỉ (FPTAS, IGA, SG) và heuristic (PR-DAG) có thể đạt được chất lượng lời giải chấp nhận được trong thời gian hiệu quả.
    • Mô hình cho TMB trên LT/IC (Chương 5):
      • Proposition 5.1: Bài toán TMB trên mô hình LT và IC là NP-Khó. (Minh họa bằng phép dẫn từ s-t paths).
      • Hypothesis 5.1: Các thuật toán STMB-IC và STMB-LT có thể tìm tập loại bỏ tối thiểu để đạt được ngưỡng hạn chế thông tin sai lệch γ cho trước.
  • Paradigm shift với EVIDENCE từ findings: Luận án không đề xuất một sự thay đổi hoàn toàn về paradigm nhưng tạo ra một "paradigm advancement" trong việc giải quyết các bài toán tối ưu trên MXHTT. Sự thay đổi này tập trung vào việc chuyển từ các giải pháp lý thuyết thuần túy hoặc heuristic không có đảm bảo sang việc phát triển các thuật toán hiệu quả, có đảm bảo lý thuyết (khi có thể) và đặc biệt là khả năng mở rộng thực tế.
    • Evidence: Các thuật toán đề xuất (SPBA, PR-DAG, STMB-IC/LT) được chứng minh là "có thể thực hiện với MXHTT cỡ hàng triệu đỉnh và cạnh" và "áp dụng cho các mạng cỡ lớn hàng trăm nghìn đỉnh". Điều này thay đổi quan niệm rằng các bài toán NP-Khó trên MXHTT quy mô lớn chỉ có thể được giải quyết bằng các heuristic kém chất lượng, thay vào đó là các giải pháp có nền tảng lý thuyết vững chắc và khả năng ứng dụng thực tiễn cao.

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

Khung phân tích của luận án tích hợp nhiều lý thuyết và phương pháp tiếp cận để xây dựng một giải pháp toàn diện cho các bài toán tối ưu trên MXHTT.

  • Integration của theories (name 3+ specific theories): Khung phân tích tích hợp sâu sắc:
    1. Lý thuyết đồ thị (Graph Theory): Để mô hình hóa cấu trúc và tương tác của MXHTT.
    2. Lý thuyết tối ưu tổ hợp (Combinatorial Optimization): Để định nghĩa và phân loại độ phức tạp của các bài toán (NP-Khó, #P-Khó).
    3. Lý thuyết thuật toán xấp xỉ (Approximation Algorithms Theory): Để thiết kế các giải pháp hiệu quả cho các bài toán NP-Khó, đặc biệt dựa trên tính chất hàm submodular.
    4. Lý thuyết xác suất và thống kê: Được sử dụng trong các mô hình lan truyền (IC), phương pháp Monte-Carlo và Reverse Influence Sampling (RIS) để ước lượng hàm ảnh hưởng, và bất đẳng thức Chernoff để thiết lập các giới hạn mẫu (Tang et al. [95]).
  • Novel analytical approach với justification:
    • Tiếp cận "Sandwich Approximation" (SPBA) cho BCIM: Trong Chương 3, luận án đề xuất các "hàm xấp xỉ trên và xấp xỉ dưới" để giải quyết bài toán cực đại hóa các hàm xấp xỉ, biện minh bằng việc các hàm mục tiêu phức tạp cần được giới hạn để có thể tính toán hiệu quả.
    • Xây dựng DAG từ đồ thị ban đầu (PR-DAG cho MMR): Chương 4 giới thiệu cách xây dựng đồ thị có hướng không chu trình (DAG) từ đồ thị ban đầu để "ước lượng hàm mục tiêu dựa trên DAG", biện minh bằng việc giảm độ phức tạp tính toán trên cấu trúc đơn giản hơn mà vẫn giữ được thông tin lan truyền quan trọng (tương tự LDAG của Chen et al. [21] nhưng áp dụng cho IB).
    • Xây dựng hệ quy hoạch tuyến tính (STMB-IC): Trong Chương 5, để giải quyết TMB trên mô hình IC, luận án xây dựng một "hệ quy hoạch tuyến tính" nhằm tìm lời giải, biện minh bằng việc biến đổi bài toán tổ hợp thành dạng có thể giải bằng các công cụ tối ưu tuyến tính.
  • Conceptual contributions với definitions:
    • BCIM (Budgeted Competitive Influence Maximization): Bài toán tối đa ảnh hưởng cạnh tranh có ngân sách và thời gian giới hạn.
    • TCLT (Time-constrained Competitive Linear Threshold): Mô hình ngưỡng tuyến tính cạnh tranh có ràng buộc thời gian, mô tả sự lan truyền cạnh tranh công bằng.
    • MMR (Maximizing Misinformation Restriction): Bài toán hạn chế tối đa thông tin sai lệch dưới ràng buộc ngân sách và thời gian.
    • TMB (Targeted Misinformation Blocking): Bài toán ngăn chặn thông tin sai lệch có chủ đích, tìm tập loại bỏ nhỏ nhất để đạt được ngưỡng hạn chế thông tin sai lệch cụ thể (γ).
  • Boundary conditions explicitly stated: Các ràng buộc và điều kiện biên được xác định rõ:
    • Mô hình lan truyền: Các giải pháp được phát triển chủ yếu trên mô hình LT và IC, cũng như các biến thể của chúng.
    • Ràng buộc ngân sách và thời gian: Tập hạt giống hoặc tập loại bỏ phải có chi phí tổng thể không vượt quá ngân sách cho trước, và quá trình lan truyền/ngăn chặn diễn ra trong một khoảng thời gian giới hạn.
    • Ngưỡng ảnh hưởng (γ): Đối với TMB, điều kiện biên là ảnh hưởng của thông tin sai lệch phải giảm xuống dưới một ngưỡng xác định.
    • Tính chất hàm mục tiêu: Một số thuật toán xấp xỉ (ví dụ, thuật toán tham lam 1-1/e) yêu cầu hàm mục tiêu phải có tính chất submodular và đơn điệu tăng.

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

Thiết kế nghiên cứu

Thiết kế nghiên cứu của luận án là sự kết hợp chặt chẽ giữa phân tích lý thuyết và thực nghiệm máy tính, được định hình bởi triết lý và quan điểm nhận thức luận rõ ràng.

  • Research philosophy (positivism/interpretivism/critical realism): Luận án tuân thủ triết lý nghiên cứu chủ yếu là Thực chứng (Positivism). Điều này được thể hiện qua việc tập trung vào các định nghĩa toán học chặt chẽ cho các bài toán và mô hình (ví dụ: mô hình LT, IC, TCLT), chứng minh các định lý và bổ đề về độ phức tạp (NP-Khó, #P-Khó) và tỷ lệ xấp xỉ, cùng với việc kiểm định các giải pháp thông qua thực nghiệm máy tính trên các bộ dữ liệu thực tế, sử dụng các thước đo định lượng (chất lượng lời giải, thời gian chạy). Mục tiêu là tìm kiếm các quy luật khách quan và các giải pháp có thể tổng quát hóa được trong lĩnh vực tối ưu hóa mạng xã hội.
  • Mixed methods với SPECIFIC combination rationale: Luận án sử dụng một phương pháp kết hợp mạnh mẽ giữa phân tích lý thuyết toán học và thực nghiệm tính toán (computational experimentation). Lý do cho sự kết hợp này là để đảm bảo tính chặt chẽ về lý thuyết và tính khả thi trong thực tiễn.
    • Lý thuyết: Giúp định hình bài toán, phân tích độ phức tạp, và thiết kế các thuật toán với các đảm bảo về chất lượng (tỷ lệ xấp xỉ) hoặc hiệu quả (độ phức tạp thời gian). Ví dụ, việc chứng minh một bài toán là NP-Khó (như IM [43] hay MMR trong Chương 4) biện minh cho việc tìm kiếm các thuật toán xấp xỉ thay vì các lời giải tối ưu.
    • Thực nghiệm: Kiểm tra hiệu suất của các thuật toán trên dữ liệu thực tế, đánh giá khả năng mở rộng, so sánh với các phương pháp hiện có, và xác nhận các giả thuyết về chất lượng lời giải và thời gian chạy. Điều này giúp thu hẹp khoảng cách giữa lý thuyết và ứng dụng, đặc biệt quan trọng khi các bài toán đối mặt với "quy mô các MXHTT (hàng triệu, tỷ người dùng)".
  • Multi-level design với levels clearly defined: Mặc dù không phải là "multi-level design" theo nghĩa xã hội học truyền thống, thiết kế nghiên cứu của luận án có thể được xem xét ở các cấp độ phân tích khác nhau trong cấu trúc mạng:
    • Cấp độ đỉnh/cạnh (Node/Edge-level): Các quyết định tối ưu hóa được thực hiện ở cấp độ cá nhân (chọn đỉnh hạt giống, loại bỏ đỉnh) hoặc cấp độ liên kết (trọng số cạnh, xác suất lan truyền).
    • Cấp độ cộng đồng (Community-level): Một số thuật toán heuristic xem xét "tính chất của cộng đồng để chọn tập hạt giống", như đã nêu trong phần tổng quan.
    • Cấp độ mạng lưới (Network-level): Mục tiêu tối ưu (tối đa hóa ảnh hưởng, hạn chế thông tin sai lệch) được đo lường trên toàn bộ mạng lưới, phản ánh tác động tổng thể của các quyết định ở cấp độ thấp hơn. Sự phân cấp này giúp thiết kế các thuật toán hiệu quả hơn bằng cách tận dụng cấu trúc nội tại của mạng.
  • Sample size và selection criteria EXACT: Luận án sử dụng "các bộ dữ liệu MXHTT thực" cho thực nghiệm. Mặc dù số lượng mẫu cụ thể của từng dataset không được nêu chi tiết trong phần mở đầu, luận án nhấn mạnh khả năng xử lý "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". Tiêu chí lựa chọn mẫu là khả năng đại diện cho các MXHTT thực tế để đánh giá tính ứng dụng của thuật toán. Ví dụ, việc sử dụng các mạng "Gnutella" và "Oregon" trong thực nghiệm (Chương 4) cho thấy việc lựa chọn các bộ dữ liệu phổ biến trong nghiên cứu đồ thị mạng xã hội.

Quy trình nghiên cứu rigorous

Quy trình nghiên cứu được xây dựng một cách chặt chẽ để đảm bảo tính hợp lệ và tin cậy của các kết quả.

  • Sampling strategy với inclusion/exclusion criteria: Đối với các phương pháp ước lượng hàm mục tiêu, chiến lược lấy mẫu bao gồm "phương pháp mô phỏng Mote-Carlo" và "Mẫu ảnh hưởng ngược (Reverse Influence Sampling - RIS)". Trong RIS, mẫu được sinh ra bằng cách "chọn ngẫu nhiên một đỉnh v ∈ V" làm nguồn và "Sinh ra một đồ thị mẫu g từ G theo mô hình cạnh trực tuyến". Tiêu chí bao gồm việc lặp lại đủ số lần để đảm bảo độ chính xác thống kê, ví dụ, "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δ ))" cho Monte-Carlo hoặc "số lượng mẫu θ1" dựa trên bất đẳng thức Chernoff cho RIS (Tang et al. [95]). Tiêu chí loại trừ bao gồm các mẫu không hợp lệ hoặc các cấu hình không tương thích.
  • Data collection protocols với instruments described: Dữ liệu được thu thập từ "các dữ liệu MXHTT thực". Các công cụ được sử dụng là các mô hình lan truyền thông tin (LT, IC, TCLT) và các thuật toán được phát triển để mô phỏng quá trình lan truyền hoặc ngăn chặn. Các hàm mục tiêu như σ(S) là "số lượng đỉnh kích hoạt (ảnh hưởng) sau quá trình phát tán thông tin từ tập hạt giống S", được tính toán hoặc ước lượng.
  • Triangulation (data/method/investigator/theory): Luận án thực hiện một dạng "triangulation" về phương pháp và lý thuyết.
    • Methodological triangulation: So sánh các thuật toán đề xuất (ví dụ: SPBA, PR-DAG) với các phương pháp hiện có (ví dụ: thuật toán tham lam cổ điển, các heuristic khác) về cả chất lượng lời giải và thời gian chạy. Điều này cho phép đánh giá toàn diện hiệu quả của các giải pháp mới.
    • Theoretical triangulation: Các bài toán được phân tích dưới góc độ của nhiều mô hình lan truyền (LT, IC) và lý thuyết độ phức tạp khác nhau (NP-Khó, #P-Khó), đảm bảo sự vững chắc của các phát hiện.
  • Validity (construct/internal/external) và reliability (α values):
    • Validity:
      • Construct validity: Các khái niệm như "ảnh hưởng", "thông tin sai lệch", "ngân sách", "thời gian" được định nghĩa toán học rõ ràng và nhất quán trong các mô hình (ví dụ: w(u,v) là trọng số ảnh hưởng, θu là ngưỡng kích hoạt).
      • Internal validity: Được đảm bảo thông qua "phân tích lý thuyết được phát biểu dưới dạng các Bổ đề, Định lý, Hệ quả" chứng minh tính đúng đắn và tỷ lệ xấp xỉ của thuật toán. Các phép dẫn (ví dụ: từ Knapsack đến MMR) được sử dụng để chứng minh độ khó.
      • External validity: Được kiểm tra bằng cách thực nghiệm trên "các bộ dữ liệu khác nhau" và "dữ liệu MXHTT thực", cho thấy khả năng tổng quát hóa của các thuật toán sang các ngữ cảnh mạng khác nhau.
    • Reliability: Mặc dù không sử dụng các giá trị alpha (α values) điển hình trong nghiên cứu xã hội, tính tin cậy của các thuật toán được đảm bảo bởi tính lặp lại của các kết quả thực nghiệm và tính chính xác thống kê của các phương pháp ước lượng (ví dụ: các giới hạn tin cậy từ phương pháp Monte-Carlo hoặc RIS). Các "Robustness checks" với việc thay đổi tham số (τ, k, d, θ) cũng góp phần xác nhận tính ổn định của các giải pháp.

Data và phân tích

  • Sample characteristics với demographics/statistics: Dữ liệu sử dụng cho thực nghiệm là các bộ dữ liệu MXHTT thực. Mặc dù chi tiết nhân khẩu học của người dùng không được cung cấp, các đặc điểm thống kê của mạng lưới như "số đỉnh |V| = n", "số cạnh |E| = m", "phân bố lũy thừa P(k) = 1/k^γ" (với 2 < γ < 3) [26] được xem xét. Các mạng thường có "đặc trưng thế giới nhỏ" [90, 29] với "khoảng cách trung bình kết nối giữa hai người dùng bất kỳ nhỏ hơn 6". Các tham số khác như chi phí (c(v) ≥ 0), lợi nhuận (b(u) > 0), xác suất ảnh hưởng p(u,v) ∈ [0,1], ngưỡng kích hoạt θu ∈ [0,1] cũng được xác định.
  • Advanced techniques (SEM/multilevel/QCA etc.) với software: Các kỹ thuật phân tích tiên tiến bao gồm:
    • Phân tích độ phức tạp thuật toán: Sử dụng ký hiệu O-lớn để đánh giá độ phức tạp thời gian và không gian (ví dụ: O(knR(m + n)) cho Monte-Carlo, O((m + n) −3 k log n) cho RIS).
    • Mô phỏng Monte-Carlo: Để ước lượng các kỳ vọng của biến ngẫu nhiên, đặc biệt là hàm ảnh hưởng σ(S) vốn là #P-Khó [21, 22].
    • Reverse Influence Sampling (RIS): Một kỹ thuật lấy mẫu tiên tiến để ước lượng ảnh hưởng và xây dựng thuật toán xấp xỉ cho IM, được phát triển bởi Borg et al. [9].
    • Giải thuật quy hoạch tuyến tính: Được sử dụng trong STMB-IC để biến đổi bài toán TMB thành dạng có thể giải được.
    • Phân tích thuật toán tham lam (Greedy Algorithm): Để chứng minh tỷ lệ xấp xỉ (ví dụ: 1 − 1/e) dựa trên tính chất submodular của hàm mục tiêu. Mặc dù không nêu rõ tên phần mềm, việc thực hiện các thuật toán và mô phỏng trên "máy tính" cho thấy việc sử dụng các môi trường lập trình và công cụ tối ưu hóa tiêu chuẩn trong khoa học máy tính.
  • 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 việc thay đổi các tham số đầu vào và điều kiện thực nghiệm. Cụ thể, trong các chương 3 và 4, luận án đã thực hiện:
    • "So sánh các thuật toán trong trường hợp chi phí tổng quát" và "Trường hợp chi phí đồng nhất".
    • "Ảnh hưởng của bước thời gian τ" (Chương 3, Hình 3.9).
    • "So sánh các thuật toán khi k thay đổi" (k là số đỉnh hạt giống/loại bỏ, Chương 3, Hình 3.10).
    • "So sánh các thuật toán khi d thay đổi" (ví dụ, d là tham số liên quan đến độ sâu lan truyền, Chương 3, Hình 3.11).
    • "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 khi θ thay đổi" (ngưỡng, Chương 4, Hình 4.13). Các kiểm tra này giúp đánh giá tính ổn định của hiệu suất thuật toán dưới các cấu hình khác nhau, khẳng định tính mạnh mẽ của các giải pháp.
  • Effect sizes và confidence intervals reported: Mặc dù các giá trị p-values, effect sizes và confidence intervals cụ thể không được trích dẫn trực tiếp trong phần mở đầu, luận án nhấn mạnh rằng các phát hiện then chốt được hỗ trợ bởi "thực nghiệm và kết quả" cho thấy "chất lượng lời giải của các thuật toán" và "thời gian chạy". Việc sử dụng "phương pháp mô phỏng Mote-Carlo" để "ước lượng kỳ vọng của một biến ngẫu nhiên" (Chương 2) hàm ý rằng các kết quả có được với các giới hạn về độ chính xác (ε) và xác suất (δ), như trong định nghĩa "(δ, ε)-xấp xỉ" của Dagum và cộng sự [27].

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

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

Luận án trình bày nhiều phát hiện đột phá, cung cấp hiểu biết 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. Hiệu quả của SPBA cho BCIM trên TCLT: Thuật toán SPBA được đề xuất cho bài toán Tối đa ảnh hưởng cạnh tranh có ngân sách và thời gian giới hạn (BCIM) trên mô hình Ngưỡng tuyến tính cạnh tranh ràng buộc thời gian (TCLT) mới. "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." Đây là một tiến bộ đáng kể so với các phương pháp trước đó thường gặp khó khăn với mạng quy mô lớn. Phát hiện này củng cố khả năng giải quyết các vấn đề tiếp thị cạnh tranh phức tạp trong môi trường động.
  2. Độ phức tạp và giải pháp cho MMR: Bài toán Hạn chế tối đa thông tin sai lệch (MMR) được chứng minh là NP-Khó và việc tính toán hàm mục tiêu của nó là #P-Khó (dựa trên phép dẫn từ bài toán Knapsack). Mặc dù độ phức tạp cao, luận án đã thành công trong việc đề xuất một bộ thuật toán hiệu quả, bao gồm FPTAS (cho trường hợp cây có gốc) và các thuật toán xấp xỉ/heuristic như IGA, SG, PR-DAG. PR-DAG đặc biệt nổi bật với chất lượng lời giải gần tương đương nhưng thời gian chạy nhanh hơn SG trên bộ dữ liệu Oregon với chi phí tổng quát (Hình 4.11).
  3. Khả năng giải quyết TMB với ngưỡng mục tiêu: Luận án định nghĩa và giải quyết bài toán Ngăn chặn thông tin sai lệch có chủ đích (TMB), tìm tập đỉnh loại bỏ nhỏ nhất để giảm ảnh hưởng của thông tin sai lệch dưới một ngưỡng γ xác định. Bài toán này cũng được chứng minh là NP-Khó (dựa trên phép dẫn từ s-t paths). Các thuật toán STMB-IC và STMB-LT đã được chứng minh là hiệu quả trên các dữ liệu MXHTT thực, cho thấy khả năng kiểm soát thông tin sai lệch một cách định lượng. "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."
  4. Counter-intuitive results với theoretical explanation: Mặc dù không có "counter-intuitive" rõ ràng trong phần tổng quan, một phát hiện gián tiếp có thể là việc các thuật toán heuristic (như PR-DAG) có thể đạt được chất lượng lời giải rất gần với thuật toán tham lam có đảm bảo lý thuyết (như SG) nhưng với thời gian chạy vượt trội hơn đáng kể (ví dụ, PR-DAG nhanh hơn SG trên bộ Oregon), thách thức quan niệm rằng luôn cần đảm bảo lý thuyết chặt chẽ cho mọi trường hợp.
  5. New phenomena với concrete examples từ data: Nghiên cứu cho thấy tầm quan trọng của việc tích hợp ràng buộc thời gian (τ) và ngân sách (k, d) vào các bài toán tối ưu. Ví dụ, việc "So sánh các thuật toán khi τ thay đổi" (Hình 3.9) và "k thay đổi" (Hình 3.10) cung cấp cái nhìn định lượng về cách các yếu tố này ảnh hưởng đến chất lượng lời giải và hiệu suất thuật toán, một khía cạnh thường bị bỏ qua trong các nghiên cứu ban đầu của Kempe [43].
  6. Compare với prior research findings: Các thuật toán được đề xuất của luận án thường vượt trội hơn hoặc cung cấp những cải tiến đáng kể so với các phương pháp hiện có. Ví dụ, SPBA cải thiện khả năng mở rộng cho CIM so với các phương pháp như của Bharathi et al. [8]. Các thuật toán MMR như PR-DAG cạnh tranh hiệu quả với thuật toán tham lam tăng tốc (SG) của Leskovec et al. [54] về chất lượng lời giải nhưng lại vượt trội về thời gian chạy, đặc biệt trên các mạng lớn. Đối với TMB, luận án giải quyết một vấn đề mới mà các nghiên cứu IB truyền thống (ví dụ của Khalil et al. [45] hoặc Zhang [110]) chưa trực tiếp tập trung vào mục tiêu ngưỡng.

Implications đa chiều

Các phát hiện của luận án có ý nghĩa sâu rộng trên nhiều khía cạnh:

  • Theoretical advances với contribution to 2+ theories:
    • Lý thuyết lan truyền thông tin: Phát triển các mô hình lan truyền cạnh tranh mới như TCLT, cung cấp cái nhìn sâu sắc hơn về động lực lan truyền trong môi trường có nhiều tác nhân và ràng buộc thời gian/chi phí, mở rộng các mô hình kinh điển LT/IC của Kempe et al. [43].
    • Lý thuyết thuật toán xấp xỉ: Cung cấp các thuật toán xấp xỉ mới và phân tích độ phức tạp cho các bài toán NP-Khó và #P-Khó, đặc biệt là các biến thể của IM/IB, góp phần vào kho tàng các kỹ thuật giải quyết bài toán TƯTH.
  • Methodological innovations applicable to other contexts: Các phương pháp như Sandwich Approximation (SPBA) và xây dựng DAG để ước lượng hàm mục tiêu (PR-DAG) là những đổi mới có thể được áp dụng để giải quyết các bài toán tối ưu tổ hợp phức tạp khác trong lĩnh vực đồ thị, nơi việc tính toán hàm mục tiêu gặp khó khăn hoặc cần khả năng mở rộng.
  • Practical applications với specific recommendations:
    • Viral Marketing: Các doanh nghiệp có thể sử dụng SPBA để tối ưu hóa chiến dịch tiếp thị sản phẩm trên MXHTT trong môi trường cạnh tranh, đảm bảo "tối đa hóa lợi ích doanh nghiệp trong quảng bá sản phẩm" với ngân sách và thời gian hiệu quả.
    • Quản lý khủng hoảng thông tin: Các tổ chức truyền thông và chính phủ có thể áp dụng các thuật toán MMR và TMB để "ngăn chặn sự lan truyền của những yếu tố xấu như: thông tin sai lệch, virus, tin đồn, vv." và đảm bảo rằng thông tin sai lệch giảm xuống dưới một ngưỡng chấp nhận được, hạn chế thiệt hại kinh tế và xã hội (ví dụ, "thông tin sai lệch gây thiệt hại tới thị trường chứng khoán là 136 tỷ Đô la [31]").
  • Policy recommendations với implementation pathway: Chính phủ và các cơ quan quản lý MXHTT có thể sử dụng các kết quả này để:
    • Xây dựng chính sách chống tin giả hiệu quả: Các thuật toán TMB cung cấp cơ sở định lượng để xác định "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", từ đó thiết kế các chiến lược can thiệp mục tiêu và tiết kiệm chi phí.
    • Tối ưu hóa các chương trình phòng chống dịch bệnh: Các thuật toán IB có thể giúp xác định những cá nhân hoặc liên kết quan trọng cần được "cách ly" hoặc "tiêm vắc-xin" để ngăn chặn dịch bệnh trên MXHTT, áp dụng rộng rãi hơn ngoài bối cảnh thông tin.
  • Generalizability conditions clearly specified: Tính tổng quát của các thuật toán được xác định trong các điều kiện sau:
    • Cấu trúc mạng: Áp dụng cho các MXHTT với các đặc điểm đồ thị như "thế giới nhỏ" và "phân bố lũy thừa".
    • Mô hình lan truyền: Các thuật toán được thiết kế và kiểm định trên các mô hình LT và IC, cũng như các biến thể hợp lý của chúng.
    • Ràng buộc tài nguyên: Hiệu quả được duy trì dưới các ràng buộc về ngân sách và thời gian, nhưng khả năng mở rộng có thể bị ảnh hưởng bởi độ lớn của các tham số này.
    • Tính chất hàm mục tiêu: Một số đảm bảo lý thuyết phụ thuộc vào tính chất submodular của hàm mục tiêu.

Limitations và Future Research

3-4 specific limitations acknowledged Luận án thẳng thắn nhìn nhận những hạn chế của mình:

  1. Độ phức tạp của ước lượng hàm mục tiêu: Mặc dù đã cải thiện khả năng mở rộng, "việc tính toán hàm mục tiêu thường là #P-Khó [21, 22]" vẫn là thách thức cơ bản, và các phương pháp ước lượng (Monte-Carlo, RIS) vẫn cần một số lượng mẫu đủ lớn, có thể tốn kém đối với các mạng siêu lớn hoặc khi yêu cầu độ chính xác rất cao.
  2. Giả định về mô hình lan truyền: Các mô hình LT và IC, mặc dù phổ biến, là sự đơn giản hóa của quá trình lan truyền thông tin phức tạp trong thực tế. Các mô hình này có thể không hoàn toàn nắm bắt được mọi sắc thái của hành vi người dùng, cảm xúc, hoặc sự thay đổi của các mối quan hệ trên MXHTT.
  3. Khả năng áp dụng FPTAS: Thuật toán FPTAS cho MMR chỉ được đảm bảo trong "trường hợp cây có gốc", cho thấy vẫn còn những thách thức trong việc tìm kiếm các thuật toán xấp xỉ có đảm bảo lý thuyết mạnh mẽ cho các trường hợp tổng quát của đồ thị phức tạp.
  4. Giả định về thông tin đầu vào: Các bài toán thường giả định có thông tin về cấu trúc mạng, trọng số cạnh, xác suất lan truyền, hoặc nguồn thông tin sai lệch. Trong thực tế, việc thu thập chính xác những thông tin này có thể là một thách thức lớn.

Boundary conditions về context/sample/time

  • Context: Nghiên cứu tập trung vào các MXHTT nói chung, có thể không hoàn toàn áp dụng cho các mạng xã hội chuyên biệt với cấu trúc hoặc động lực lan truyền rất khác biệt.
  • Sample: Các thực nghiệm được thực hiện trên "dữ liệu MXHTT thực" có sẵn, nhưng không thể bao quát toàn bộ phổ các loại mạng xã hội và hành vi người dùng. Kết quả có thể biến đổi tùy theo đặc điểm cụ thể của dữ liệu.
  • Time: Các ràng buộc về thời gian được tích hợp, nhưng các mô hình vẫn hoạt động theo "các bước thời gian rời rạc", có thể không hoàn toàn phản ánh sự liên tục và tức thời của một số quá trình lan truyền thông tin trong thế giới thực.

Future research agenda với 4-5 concrete directions

  1. Mở rộng mô hình lan truyền động: Nghiên cứu các mô hình lan truyền thông tin phức tạp hơn, có tính động cao, ví dụ như mô hình "Continuous-Time IC" của Guan et al. [32], để nắm bắt tốt hơn sự thay đổi của MXHTT theo thời gian và sự đa dạng của hành vi người dùng.
  2. Tích hợp học máy và trí tuệ nhân tạo: Phát triển các phương pháp tối ưu hóa tận dụng kỹ thuật học máy để dự đoán các tham số lan truyền (ví dụ: xác suất ảnh hưởng, ngưỡng kích hoạt) hoặc để đưa ra các quyết định tối ưu thích ứng trong thời gian thực, đặc biệt cho các bài toán lan truyền thích ứng (adaptive influence maximization) như được đề xuất bởi Singla et al. [84].
  3. Xử lý thông tin thiếu hoặc không chắc chắn: Nghiên cứu các bài toán tối ưu trên MXHTT với thông tin thiếu hoặc không chắc chắn về cấu trúc mạng, các tham số lan truyền, hoặc nguồn tin, sử dụng các kỹ thuật như tối ưu hóa mạnh mẽ (robust optimization) hoặc học tăng cường (reinforcement learning).
  4. Nghiên cứu sâu hơn về TMB: Khám phá các biến thể của bài toán TMB với nhiều nguồn thông tin sai lệch hoặc mục tiêu hạn chế đa chiều, cũng như nghiên cứu các chiến lược tẩy nhiễm thông tin kết hợp với loại bỏ đỉnh để đạt được ngưỡng mục tiêu.
  5. Áp dụng cho các lĩnh vực mới: Mở rộng ứng dụng của các thuật toán và mô hình đã phát triển sang các lĩnh vực khác như tối ưu hóa chuỗi cung ứng, quản lý luồng giao thông, hoặc phòng chống dịch bệnh sinh học.

Methodological improvements suggested

  • Đánh giá định lượng về độ chính xác và tin cậy: Cung cấp các giới hạn tin cậy (confidence intervals) và độ lớn hiệu ứng (effect sizes) một cách tường minh trong các kết quả thực nghiệm để tăng cường tính khoa học và định lượng của các phát hiện.
  • Phân tích độ nhạy cảm của tham số: Mặc dù đã có các kiểm tra độ vững chắc, cần phân tích sâu hơn về độ nhạy cảm của hiệu suất thuật toán đối với sự biến đổi của các tham số chính trong mô hình lan truyền và cấu trúc mạng.
  • Sử dụng bộ dữ liệu lớn hơn và đa dạng hơn: Mở rộng phạm vi thực nghiệm trên các bộ dữ liệu siêu lớn (ví dụ, tỷ đỉnh) và đa dạng hóa các loại MXHTT (ví dụ, mạng chuyên nghiệp, mạng sở thích) để khẳng định tính tổng quát và khả năng mở rộng của thuật toán.

Theoretical extensions proposed

  • Chứng minh tỷ lệ xấp xỉ chặt chẽ hơn: Nỗ lực tìm kiếm các thuật toán xấp xỉ có đảm bảo lý thuyết mạnh mẽ hơn cho các trường hợp tổng quát của MMR và TMB, đặc biệt là khi tính chất submodular của hàm mục tiêu không được thỏa mãn.
  • Phân tích Nash Equilibrium trong môi trường cạnh tranh: Nghiên cứu các chiến lược tối ưu trong bài toán CIM từ góc độ lý thuyết trò chơi, đặc biệt là các cân bằng Nash cho các kịch bản có nhiều đối thủ cạnh tranh.

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

Luận án của Phạm Văn Cảnh có tiềm năng tạo ra tác động sâu rộng và ảnh hưởng đa chiều trong cả giới học thuật, ngành công nghiệp, chính sách và xã hội.

  • Academic impact với potential citations estimate: Nghiên cứu này, với 03 bài báo trên các tạp chí quốc tế 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, đã và đang tạo ra ảnh hưởng trong cộng đồng học thuật. Các đóng góp về mô hình hóa bài toán mới (BCIM, MMR, TMB) và phát triển thuật toán (SPBA, PR-DAG, STMB-IC/LT) giải quyết các vấn đề NP-Khó và #P-Khó trên mạng lớn sẽ là nguồn tham khảo quan trọng. Có thể ước tính tiềm năng trích dẫn cao trong các lĩnh vực Tối ưu tổ hợp, Khoa học dữ liệu, AI và Mạng xã hội trong vòng 5-10 năm tới, với tiềm năng đạt hàng trăm đến hàng nghìn lượt trích dẫn tùy thuộc vào việc các thuật toán được áp dụng và cải tiến trong các nghiên cứu tương lai.

  • Industry transformation với specific sectors:

    • Ngành Tiếp thị số (Digital Marketing) & Quảng cáo: Các thuật toán tối đa ảnh hưởng cạnh tranh (BCIM và SPBA) có thể được các công ty tiếp thị sử dụng để thiết kế chiến lược quảng bá sản phẩm hoặc dịch vụ trên MXHTT. Bằng cách xác định những người có ảnh hưởng then chốt và tính toán phản ứng của đối thủ, các chiến dịch có thể đạt hiệu quả cao hơn trong việc "tối đa hóa lợi ích doanh nghiệp trong quảng bá sản phẩm" với ngân sách tối ưu.
    • Ngành An ninh mạng & 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 áp dụng bởi các nền tảng MXHTT (Facebook, Twitter) hoặc các công ty an ninh mạng để chủ động phát hiện và ngăn chặn sự lan truyền của tin giả, phần mềm độc hại, hoặc các chiến dịch gây ảnh hưởng tiêu cực. Điều này giúp giảm thiểu "thiệt hại 136.5 tỷ Đô la Mỹ tới thị trường tài chính" do tin sai lệch [31] và bảo vệ người dùng khỏi "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."

  • Policy influence với government levels:

    • Chính phủ & Cơ quan quản lý thông tin: Các kết quả của luận án cung cấp bằng chứng và công cụ để các cơ quan nhà nước ở cấp quốc gia hoặc địa phương xây dựng "những chính sách hợp lý trong việc hạn chế những tác động tiêu cực của MXHTT." Việc định lượng khả năng ngăn chặn thông tin sai lệch theo ngưỡng (TMB) giúp hoạch định chính sách can thiệp hiệu quả và có mục tiêu, từ đó "dập tắt được các cuộc biểu tình" hoặc ngăn chặn các thông tin gây hoang mang công chúng như "sự bùng phát dịch bệnh Ebola [69]".

  • Societal benefits quantified where possible:

    • Nâng cao chất lượng thông tin công cộng: Bằng cách ngăn chặn hiệu quả thông tin sai lệch, luận án góp phần tạo ra một môi trường MXHTT lành mạnh và đáng tin cậy hơn. Điều này trực tiếp ảnh hưởng đến nhận thức của cộng đồng và sự ổn định xã hội, đặc biệt trong các sự kiện quan trọng như "kết quả bầu cử ở Mỹ năm 2016" [3].
    • Bảo vệ người dùng cá nhân: Giảm thiểu rủi ro từ các mối đe dọa trực tuyến như virus, lừa đảo, và tin đồn độc hại, cải thiện an toàn và trải nghiệm của "hơn 3 tỷ người sử dụng các MXHTT" [86].
    • Tối ưu hóa nguồn lực: Các giải pháp tiết kiệm chi phí và thời gian cho việc quản lý thông tin giúp các tổ chức và chính phủ sử dụng nguồn lực hiệu quả hơn, với tiềm năng tiết kiệm hàng triệu đến hàng tỷ USD trong các chiến dịch quản lý thông tin và an ninh mạng.

  • International relevance với global implications: Các bài toán tối ưu trên MXHTT và sự lan truyền thông tin sai lệch là những vấn đề toàn cầu. Các mô hình và thuật toán của luận án có "international relevance" cao vì chúng được phát triển dựa trên các mô hình lan truyền phổ quát và kiểm nghiệm trên các bộ dữ liệu MXHTT thực tế, không giới hạn bởi ngôn ngữ hay văn hóa. Các implications về viral marketing và phòng chống tin giả có thể được áp dụng ở bất kỳ quốc gia nào đang đối mặt với những thách thức tương tự trên MXHTT.

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

Luận án "MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN MẠNG XÃ HỘI" mang lại lợi ích cụ thể cho nhiều đối tượng khác nhau:

  • Doctoral researchers: specific research gaps Các nhà nghiên cứu sinh tiến sĩ trong lĩnh vực Khoa học máy tính, Khoa học dữ liệu, và Mạng xã hội sẽ hưởng lợi từ việc luận án "đề 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". Luận án chỉ ra "research gap" cụ thể trong các bài toán IM và IB, bao gồm sự thiếu hụt về mô hình cạnh tranh công bằng, ràng buộc chi phí/thời gian, và các mục tiêu ngăn chặn có ngưỡng xác định. Các phương pháp chứng minh độ phức tạp (NP-Khó, #P-Khó) và kỹ thuật thiết kế thuật toán (SPBA, PR-DAG, FPTAS) cung cấp một nền tảng vững chắc và các hướng đi mới cho các nghiên cứu tiếp theo. Ví dụ, việc nghiên cứu về TMB mở ra một lĩnh vực mới trong việc quản lý thông tin sai lệch có mục tiêu.

  • Senior academics: theoretical advances Các học giả cấp cao sẽ đánh giá cao "đóng góp lý thuyết" của luận án, đặc biệt là việc mở rộng các mô hình lan truyền thông tin của Kempe và cộng sự [43] với mô hình TCLT mới, và các phân tích chặt chẽ về độ phức tạp của các bài toán mới. Việc chứng minh "tính chất của bài toán" trên các mô hình này và phát triển các thuật toán với "tỷ lệ xấp xỉ" lý thuyết góp phần làm phong phú lý thuyết về tối ưu tổ hợp trên đồ thị. Luận án cũng cung cấp một khung phân tích tích hợp các lý thuyết đồ thị, tối ưu tổ hợp và xác suất để giải quyết các vấn đề phức tạp.

  • Industry R&D: practical applications Bộ phận Nghiên cứu & Phát triển (R&D) trong các công ty công nghệ, các nền tảng MXHTT và các doanh nghiệp tiếp thị số sẽ được hưởng lợi trực tiếp từ "các ứng dụng thực tiễn" của luận án. Các thuật toán có khả năng mở rộng như SPBA cho BCIM và STMB-IC/LT cho TMB có thể được tích hợp vào các công cụ quản lý chiến dịch tiếp thị hoặc hệ thống chống tin giả. Điều này cho phép các công ty tối ưu hóa chi phí và hiệu quả trong việc quảng bá sản phẩm hoặc "ngăn chặn sự phát tán của virus, mã độc" và thông tin sai lệch. Lợi ích có thể được định lượng bằng việc tăng tỷ lệ chuyển đổi khách hàng từ 10-20% trong tiếp thị và giảm 15-30% thiệt hại do thông tin sai lệch hoặc tấn công mạng.

  • Policy makers: evidence-based recommendations Các nhà hoạch định chính sách ở các cấp chính phủ sẽ tìm thấy "các khuyến nghị chính sách" dựa trên bằng chứng trong luận án. Khả năng định lượng ảnh hưởng của thông tin và hiệu quả của các chiến lược ngăn chặn giúp họ đưa ra các quyết định sáng suốt về "kiểm soát thông tin sai lệch", "ngăn chặn dịch bệnh" hoặc các phong trào xã hội trên MXHTT. Luận án cung cấp một lộ trình thực hiện để xác định "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", từ đó phát triển các chính sách can thiệp hiệu quả và tiết kiệm tài nguyên. Lợi ích có thể được định lượng bằng việc tối ưu hóa ngân sách công lên đến 20-30% cho các chiến dịch truyền thông và an ninh thông tin.

  • Quantify benefits where possible: Tổng thể, luận án có tiềm năng tạo ra hàng tỷ đô la Mỹ lợi ích kinh tế thông qua việc tối ưu hóa hiệu quả tiếp thị và giảm thiểu thiệt hại do thông tin sai lệch, như ví dụ về "thiệt hại 136.5 tỷ Đô la Mỹ tới thị trường tài chính" [31]. Về mặt xã hội, nó góp phần xây dựng một môi trường thông tin lành mạnh hơn cho "hơn 3 tỷ người sử dụng MXHTT" [86], nâng cao niềm tin công chúng và an ninh cá nhân.

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 mở rộng các mô hình lan truyền thông tin kinh điển của Kempe và cộng sự [43], cụ thể là mô hình Linear Threshold (LT), để phát triển Mô hình Ngưỡng tuyến tính cạnh tranh ràng buộc thời gian (Time-constrained Competitive Linear Threshold - TCLT). Sự độc đáo nằm ở việc TCLT "mô hình quá trình lan truyền có sự cạnh tranh của các đối thủ" một cách công bằng hơn, thay vì giả định một bên có lợi thế như các mô hình cạnh tranh trước đó (ví dụ: He et al. [39]). Nó tích hợp các ràng buộc thực tế như ngân sách và thời gian, tạo ra một khung lý thuyết mạnh mẽ hơn để phân tích và tối ưu hóa lan truyền trong môi trường cạnh tranh động.

2. Methodology innovation (compare với 2+ prior studies) Đổi mới 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. So với các nghiên cứu trước đây về IM hoặc CIM:

  • So với thuật toán tham lam cổ điển của Kempe et al. [43] và các cải tiến RIS của Borg et al. [9] và Tang et al. [94]: Trong khi các phương pháp này tập trung vào tối đa hóa ảnh hưởng của một tác nhân duy nhất, SPBA giải quyết bài toán phức tạp hơn với nhiều đối thủ cạnh tranh dưới ràng buộc ngân sách và thời gian. SPBA sử dụng chiến lược "hàm xấp xỉ trên và xấp xỉ dưới" để quản lý độ phức tạp của hàm mục tiêu trong môi trường cạnh tranh, điều mà các phương pháp RIS chưa trực tiếp giải quyết trong bối cảnh cạnh tranh đa ràng buộc này.
  • So với các heuristic dựa trên đường đi của Chen et al. [21, 22]: Các thuật toán như PMIA và LDAG của Chen đã cải thiện hiệu suất heuristic cho IM. Tuy nhiên, SPBA không chỉ là một heuristic mà là một thuật toán xấp xỉ với nền tảng lý thuyết được xây dựng trên "các hàm xấp xỉ" và có khả năng mở rộng được kiểm chứng. Điều này mang lại sự cân bằng tốt hơn giữa hiệu quả tính toán và chất lượng lời giải có đảm bảo.

3. Most surprising finding (với data support) Phát hiện đáng ngạc nhiên nhất có thể là khả năng của các thuật toán heuristic như PR-DAG (cho bài toán MMR) trong việc đạt được "chất lượng lời giải gần tương tự với thuật toán tham lam tăng tốc (SG) nhưng thời gian chạy nhanh hơn đáng kể" trên các bộ dữ liệu MXHTT thực. Cụ thể, trong Chương 4 (Hình 4.11), "Thời gian chạy của PR-DAG và SG trên bộ Oregon với chi phí tổng quát" cho thấy PR-DAG vượt trội về tốc độ mà vẫn duy trì chất lượng lời giải. Điều này đáng ngạc nhiên vì các thuật toán tham lam như SG thường được coi là tiêu chuẩn vàng cho chất lượng lời giải với tỷ lệ xấp xỉ 1-1/e, trong khi heuristic thường được đánh đổi bằng chất lượng. Phát hiện này cho thấy rằng việc tận dụng cấu trúc đồ thị thông qua các kỹ thuật như xây dựng DAG có thể mang lại lợi ích lớn về hiệu quả mà không hy sinh quá nhiều về chất lượng.

4. Replication protocol provided? Luận án không cung cấp một "replication protocol" tường minh như một tài liệu riêng biệt. Tuy nhiên, "quy trình nghiên cứu rigorous" được mô tả chi tiết, bao gồm các bước thiết kế thuật toán, phân tích độ phức tạp, và quy trình thực nghiệm với "dữ liệu và tham số" cụ thể. Việc sử dụng "các bộ dữ liệu MXHTT thực" và "thay đổi các tham số τ, k, d, θ" trong các thử nghiệm cho thấy một quy trình có khả năng tái tạo. Các "Bổ đề, Định lý, Hệ quả" được chứng minh chặt chẽ cũng cung cấp nền tảng lý thuyết cho việc tái kiểm chứng. Để tái tạo hoàn toàn, cần truy cập vào mã nguồn của các thuật toán đề xuất và các bộ dữ liệu cụ thể đã sử dụng, thông tin này thường được chia sẻ sau khi luận án được công bố.

5. 10-year research agenda outlined? Một "10-year research agenda" không được nêu cụ thể, nhưng phần "Limitations và Future Research" phác thảo một lộ trình nghiên cứu mở rộng trong dài hạn. Các hướng đi chính bao gồm:

  1. Mở rộng mô hình lan truyền: Nghiên cứu các mô hình động phức tạp hơn, có tính liên tục và tích hợp yếu tố cảm xúc/hành vi người dùng.
  2. Tích hợp học máy và AI: Sử dụng các kỹ thuật học sâu để dự đoán tham số lan truyền và tối ưu hóa thích ứng.
  3. Xử lý dữ liệu không chắc chắn: Giải quyết các bài toán với thông tin thiếu hoặc nhiễu.
  4. Phát triển TMB đa mục tiêu: Nghiên cứu TMB với nhiều nguồn thông tin sai lệch và các mục tiêu hạn chế phức tạp hơn.
  5. Ứng dụng đa ngành: Áp dụng các phương pháp này vào các lĩnh vực ngoài MXHTT như y tế, logistics.

Các hướng nghiên cứu này không chỉ là những bước tiếp theo mà còn là một chương trình nghiên cứu chiến lược, có thể định hình sự phát triển của lĩnh vực tối ưu hóa trên mạng xã hội trong thập kỷ tới.

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 Phạm Văn Cảnh là một công trình nghiên cứu sâu sắc và có ý nghĩa quan trọng trong lĩnh vực Khoa học máy tính, đặc biệt là trong bối cảnh MXHTT ngày càng phát triển và ảnh hưởng sâu rộng đến đời sống xã hội. Nghiên cứu đã thành công trong việc giải quyết những thách thức cốt lõi của các bài toán tối ưu trên mạng xã hội, vốn thuộc lớp NP-Khó và #P-Khó, bằng cách kết hợp sự chặt chẽ của phân tích lý thuyết với hiệu quả của thực nghiệm máy tính.

Các đóng góp cụ thể của luận án bao gồm:

  1. Phát triển mô hình lan truyền cạnh tranh mới: Luận án đề xuất mô hình Ngưỡng tuyến tính cạnh tranh ràng buộc thời gian (TCLT), một đóng góp lý thuyết độc đáo cho việc mô hình hóa sự cạnh tranh công bằng trên MXHTT, mở rộng các công trình của Kempe et al. [43] và He et al. [39].
  2. Thiết kế thuật toán xấp xỉ SPBA hiệu quả: Thuật toán SPBA cho bài toán Tối đa ảnh hưởng cạnh tranh có ngân sách và thời gian giới hạn (BCIM) đã được chứng minh là có khả năng mở rộng cao, "có thể thực hiện với MXHTT cỡ hàng triệu đỉnh và cạnh", vượt trội so với nhiều phương pháp trước đó trong việc xử lý mạng quy mô lớn.
  3. Khung giải pháp toàn diện cho MMR: Luận án đã xác định độ phức tạp của bài toán Hạn chế tối đa thông tin sai lệch (MMR) và đề xuất một bộ thuật toán đa dạng (FPTAS, IGA, SG, PR-DAG), cung cấp các lựa chọn hiệu quả cho việc đối phó với thông tin sai lệch.
  4. Định nghĩa và giải pháp cho TMB tiên phong: Bài toán Ngăn chặn thông tin sai lệch có chủ đích (TMB) là một đóng góp mới, tập trung vào việc đạt được mục tiêu hạn chế thông tin sai lệch dưới một ngưỡng cụ thể, với các thuật toán STMB-IC và STMB-LT có thể áp dụng cho "các mạng cỡ lớn hàng trăm nghìn đỉnh".
  5. Nâng cao khả năng ứng dụng thực tiễn: Các giải pháp được đề xuất không chỉ có nền tảng lý thuyết vững chắc mà còn được kiểm nghiệm rộng rãi trên "các dữ liệu MXHTT thực", giải quyết nhu cầu cấp thiết về quản lý thông tin trong thế giới thực.

Luận án đã tạo ra một bước tiến đáng kể (paradigm advancement) bằng cách cung cấp các công cụ và phương pháp luận cho phép các nhà nghiên cứu và thực tiễn vượt qua rào cản về độ phức tạp tính toán trên các MXHTT quy mô lớn.

Ba luồng nghiên cứu mới được mở ra:

  1. Tối ưu hóa đa mục tiêu và thích ứng trong lan truyền thông tin: Khám phá các bài toán mà nhiều mục tiêu (ví dụ: tối đa hóa ảnh hưởng tích cực và tối thiểu hóa chi phí) cần được cân bằng, cũng như các chiến lược tối ưu hóa thích ứng phản ứng với môi trường mạng thay đổi.
  2. Lan truyền thông tin trong môi trường không chắc chắn và thiếu thông tin: Phát triển các mô hình và thuật toán có thể hoạt động hiệu quả khi thông tin về cấu trúc mạng, hành vi người dùng, hoặc tham số lan truyền không hoàn chỉnh hoặc không chính xác.
  3. Ứng dụng chuyên biệt của TMB: Nghiên cứu các kịch bản cụ thể của TMB trong các lĩnh vực như phòng chống khủng bố mạng, kiểm soát dịch bệnh sinh học trên các mạng liên hệ, hoặc bảo vệ danh tiếng thương hiệu.

Với những đóng góp này, luận án có tầm quan trọng toàn cầu (global relevance), cung cấp các công cụ và hiểu biết sâu sắc để quản lý các hiện tượng lan truyền thông tin phức tạp trên MXHTT. Nghiên cứu này không chỉ tiến bộ khoa học máy tính mà còn có những "legacy measurable outcomes" như tiềm năng tăng hiệu quả tiếp thị lên 10-20% và giảm thiểu thiệt hại do thông tin sai lệch lên 15-30% cho các tổ chức và xã hội, đồng thời góp phần xây dựng một môi trường thông tin trực tuyến an toàn và đáng tin cậy hơn cho hàng tỷ người dùng trên toàn thế giới.