6533b829fe1ef96bd128ad1d

RESEARCH PRODUCT

Social Influence Maximization in Hypergraphs

Carmine SpagnuoloGennaro CordascoPrzemysław SzufelAlessia Antelmi

subject

Hypergraphsocial networksSelection (relational algebra)Computer scienceGeneralizationScienceQC1-999hypergraphGeneral Physics and Astronomy02 engineering and technologyAstrophysicsArticlehigh-order networkSet (abstract data type)influence diffusion020204 information systems0202 electrical engineering electronic engineering information engineeringDiscrete mathematicshigh-order networks; hypergraphs; influence diffusion; social networks; target set selectionPhysicsQMaximizationQB460-466high-order networkshypergraphstarget set selectionGraph (abstract data type)020201 artificial intelligence & image processingNode (circuits)Heuristics

description

This work deals with a generalization of the minimum Target Set Selection (TSS) problem, a key algorithmic question in information diffusion research due to its potential commercial value. Firstly proposed by Kempe et al., the TSS problem is based on a linear threshold diffusion model defined on an input graph with node thresholds, quantifying the hardness to influence each node. The goal is to find the smaller set of items that can influence the whole network according to the diffusion model defined. This study generalizes the TSS problem on networks characterized by many-to-many relationships modeled via hypergraphs. Specifically, we introduce a linear threshold diffusion process on such structures, which evolves as follows. Let H=(V,E) be a hypergraph. At the beginning of the process, the nodes in a given set S⊆V are influenced. Then, at each iteration, (i) the influenced hyperedges set is augmented by all edges having a sufficiently large number of influenced nodes

yearjournalcountryeditionlanguage
2021-06-23
10.3390/e23070796http://hdl.handle.net/11591/460056