Cực đại ảnh hưởng với nhiều chủ đề: Bài toán cực đại ảnh hưởng với
nhiều chủ đề [26] là một biến thể của bài toán cực đại ảnh hưởng, trong đó mỗi
đỉnh của đồ thị đại diện cho một người dùng và mỗi chủ đề sẽ ứng với một tập
hợp các đỉnh thuộc lời giải. Với sự đa dạng về thông tin trên mạng xã hội hiện nay,
các nhóm người dùng có xu hướng chỉ quan tâm đến một hoặc một vài chủ đề
nhất định, việc tiếp nhận và lan truyền thông tin vì thế mà cũng trở nên phức tạp
hơn do cùng một lúc nhiều chủ đề được lan truyền trong cộng đồng. Mục tiêu của
bài toán là chọn ra một tập con người dùng sao cho mục tiêu lan truyền thông tin
đến họ sẽ ảnh hưởng lớn nhất đến nhiều chủ đề khác nhau.
Việc có thêm yếu tố nhiều chủ đề (sau đây được gọi là k chủ đề để giúp cho
việc giải thích được dễ dàng hơn) sẽ tạo ra thách thức không nhỏ trong việc xây
dựng mô hình lan truyền thông tin, lời giải và hàm mục tiêu, cụ thể:
+ Lời giải bài toán có thêm tính chất k chủ đề có nghĩa là các tập đỉnh được
lựa chọn trong tập lời giải sẽ được phân nhóm theo chủ đề, không có sự trùng lặp
giữa hai nhóm bởi vì một đỉnh chỉ được chọn lan truyền một chủ đề duy nhất.
+ Mô hình lan truyền thông tin sẽ có tính chất k chủ đề, việc lan truyền từ
người dùng này đến người dùng khác sẽ có thêm yếu tố dựa trên chủ đề tác động.
+ Việc tính toán hàm mục tiêu sẽ cần tính thêm yếu tố ảnh hưởng của chủ
đề được lan truyền, hàm tính toán sẽ phức tạp hơn.