Ginestra Bianconi, Sergey N. Dorogovtsev

Hypergraphs are able to capture interactions between two or more nodes and for this reason they are raising significant attention in the context of opinion dynamics, epidemic spreading, synchronization and game theory. However hypergraph robustness to random damage is not yet widely explored. While the hypegraph structure can be always encoded in a factor graph, i.e. a bipartite network between nodes and hyperedges, here we reveal that percolation on hypegraphs is distinct from percolation on their corresponding factor graphs when nodes are randomly damaged. Notably, we show that the node percolation threshold on hypergraphs exceeds node percolation threshold on factor graphs. Furthermore we show that differently from what happens in ordinary graphs, containing only edges of cardinality 2, on hypergraphs the node percolation threshold and hyperedge percolation threshold do not coincide, with the node percolation threshold exceeding the hyperedge percolation threshold. These results are obtained within a message-passing theory valid in the locally tree-like approximation of the factor graph. In the same approximation we analytically predict the phase diagram and the critical properties of hypegraph percolation on random hypergraphs and on multiplex hypergraphs. We compare the results obtained for hypergraph percolation with the ones for percolation on factor graphs and we validate our results with Monte Carlo simulations and message-passing predictions on random hypergraphs and on the real hypergraph of US Senate committees.

Read the full article at: arxiv.org

• Papers