Reciprocity in directed hypergraphs: measures, findings, and generators

【Author】 Kim, Sunwoo; Choe, Minyoung; Yoo, Jaemin; Shin, Kijung

【Source】DATA MINING AND KNOWLEDGE DISCOVERY

【影响因子】5.406

【Abstract】Group interactions are prevalent in a variety of areas. Many of them, including email exchanges, chemical reactions, and bitcoin transactions, are directional, and thus they are naturally modeled as directed hypergraphs, where each hyperarc consists of the set of source nodes and the set of destination nodes. For directed graphs, which are a special case of directed hypergraphs, reciprocity has played a key role as a fundamental graph statistic in revealing organizing principles of graphs and in solving graph learning tasks. For general directed hypergraphs, however, even no systematic measure of reciprocity has been developed. In this work, we investigate the reciprocity of 11 real-world hypergraphs. To this end, we first introduce eight axioms that any reasonable measure of reciprocity should satisfy. Second, we propose HyperRec, a family of principled measures of hypergraph reciprocity that satisfy all the axioms. Third, we develop FastHyperRec, a fast and exact algorithm for computing the measures. Fourth, using them, we examine 11 real-world hypergraphs and discover patterns that distinguish them from random hypergraphs. Lastly, we propose ReDi, an intuitive generative model for directed hypergraphs exhibiting the patterns.

【Keywords】Reciprocity; Directed hypergraph; Hypergraph generator; Graph mining

【发表时间】2023 2023 AUG 8

【收录时间】2023-08-21

【文献类型】实验仿真

【主题类别】

区块链治理-技术治理-交易网络分析