Distances in Higher-Order Networks and the Metric Structure of Hypergraphs

Entropy. 2023. Vol. 25. No. 6. Article 923.

Vasilyeva E., Romance M., Ivan Samoylenko, Kovalenko K., Musatov D., Raigorodskii A. M., Boccaletti S.

We explore the metric structure of networks with higher-order interactions and introduce a novel definition of distance for hypergraphs that extends the classic methods reported in the literature. The new metric incorporates two critical factors: (1) the inter-node distance within each hyperedge, and (2) the distance between hyperedges in the network. As such, it involves the computation of distances in a weighted line graph of the hypergraph. The approach is illustrated with several ad hoc synthetic hypergraphs, where the structural information unveiled by the novel metric is highlighted. Moreover, the method’s performance and effectiveness are shown through computations on large real-world hypergraphs, which indeed reveal new insights into the structural features of networks beyond pairwise interactions. Namely, using the new distance measure, we generalize the definitions of efficiency, closeness and betweenness centrality for the case of hypergraphs. Comparing the values of these generalized measures with their analogs calculated for the hypergraph clique projections, we show that our measures provide significantly different assessments on the characteristics (and roles) of the nodes from the information-transferability point of view. The difference is brighter for hypergraphs in which hyperedges of large sizes are frequent, and nodes relating to these hyperedges are rarely connected by other hyperedges of smaller sizes.

Keywords: теория графов, complex networks, гиперграф, hypergraphs, Complex networks and Data Mining, Multilayer network, метрики оценки расстояний, Модели сложных сетей

Publication based on the results of: Research on information inequality of access to higher education and assessment of the efficiency of the college admission system in Russia (2023)