Core-periphery Models for Hypergraphs
This work addresses the challenge of efficiently analyzing core-periphery patterns in large hypergraphs, which is incremental as it extends existing graph concepts to hypergraphs with improved scalability.
The authors tackled the problem of modeling core-periphery structure in hypergraphs by introducing a random hypergraph model and developing a scalable statistical inference algorithm with near-linear runtime, which outperformed baselines on datasets with up to ~10^5 hyperedges from sources like Microsoft Academic Graph.
We introduce a random hypergraph model for core-periphery structure. By leveraging our model's sufficient statistics, we develop a novel statistical inference algorithm that is able to scale to large hypergraphs with runtime that is practically linear wrt. the number of nodes in the graph after a preprocessing step that is almost linear in the number of hyperedges, as well as a scalable sampling algorithm. Our inference algorithm is capable of learning embeddings that correspond to the reputation (rank) of a node within the hypergraph. We also give theoretical bounds on the size of the core of hypergraphs generated by our model. We experiment with hypergraph data that range to $\sim 10^5$ hyperedges mined from the Microsoft Academic Graph, Stack Exchange, and GitHub and show that our model outperforms baselines wrt. producing good fits.