Information diffusion in complex networks: a model based on hypergraphs and its analysis

This work introduces the problem of social influence diffusion in complex networks, where vertices are linked not only through simple pairwise relationships to other nodes but with groups of nodes of arbitrary size. A challenging problem that arises in this domain is to determine a small subset of nodes S (a target-set) able to spread their influence in the whole network. This problem has been formalized and studied in different ways, and many viable solutions have been found for graphs. These have been applied to study several phenomena in research fields such as social, economic, biological, and physical sciences. In this contribution, we investigated the social influence problem on hypergraphs. As hypergraphs are mathematical structures generalization of graphs, they can naturally model the many-to-many relationships characterizing a complex network. Given a network represented by a hypergraph H=(V, E), we consider a dynamic influence diffusion process on H, evolving as follows. At the beginning of the process, the nodes in a given set S (Formula Presented) V are influenced. Then, at each iteration, the influenced hyperedges set is augmented by all hyperedges having a sufficiently large number of influenced nodes. Consequently, the set of influenced nodes is extended by all the nodes contained in a sufficiently large number of already influenced hyperedges. The process terminates when no new nodes can be influenced. The so defined problem is an inherent chicken-and-egg question as nodes are influenced by groups of other nodes (or hyperedges), while hyperedges (or group of nodes) are influenced by the nodes they contain. In this paper, we provide a formal definition of the influence diffusion problem on hypergraphs. We propose a set of greedy-based heuristic strategies for finding the minimum influence target set, and we present an in-depth analysis of their performance on several classes of random hypergraphs. Furthermore, we describe an experiment on a real use-case, based on the character co-occurrences network of the Game-of-Thrones TV Series.