Social Influence Maximization in Hypergraphs.

Area of Science:

• Complex Systems
• Network Science
• Algorithmic Game Theory

Background:

• The Target Set Selection (TSS) problem is crucial in information diffusion research, with significant commercial applications.
• The standard TSS problem operates on graphs, aiming to identify a minimal set of nodes to influence an entire network via a linear threshold model.
• Existing models often simplify complex relationships, necessitating extensions for more realistic network structures.

Purpose of the Study:

• To generalize the minimum Target Set Selection problem to hypergraphs, accommodating many-to-many relationships.
• To introduce and analyze a novel linear threshold diffusion process on hypergraphs.
• To address the computational complexity of the generalized problem by developing and evaluating heuristic approaches.

Main Methods:

• Definition of a linear threshold diffusion model on hypergraphs, involving influenced nodes and hyperedges.
• Formalization of the minimum Target Set Selection problem on hypergraphs (TSSH).
• Development of four heuristic algorithms to approximate solutions for the NP-hard TSSH problem.
• Extensive empirical evaluation of the heuristics on real-world network datasets.

Main Results:

• The proposed diffusion model effectively captures information spread in hypergraph structures.
• The TSSH problem is shown to be NP-hard, confirming its computational difficulty.
• The developed heuristics provide viable approaches for finding near-optimal target sets in hypergraphs.
• Performance analysis demonstrates the effectiveness of the heuristics across diverse real-world networks.

Conclusions:

• Generalizing TSS to hypergraphs provides a more powerful framework for modeling complex diffusion processes.
• The introduced heuristics offer practical solutions for the computationally challenging TSSH problem.
• This research advances the understanding of influence maximization in complex network structures.