Many real-world interactions (e.g., researcher collaborations and email communication) occur among multiple entities. These group interactions are naturally modeled as hypergraphs. In graphs, transitivity is helpful to understand the connections between node pairs sharing a neighbor, and it has extensive applications in various domains. Hypergraphs, an extension of graphs, are designed to represent group relations. However, to the best of our knowledge, there has been no examination regarding the transitivity of real-world group interactions. In this work, we investigate the transitivity of group interactions in real-world hypergraphs. We first suggest intuitive axioms as necessary characteristics of hypergraph transitivity measures. Then, we propose a principled hypergraph transitivity measure HyperTrans, which satisfies all the proposed axioms, with a fast computation algorithm Fast-HyperTrans. After that, we analyze the transitivity patterns in real-world hypergraphs distinguished from those in random hypergraphs. Lastly, we propose a scalable hypergraph generator THera. It reproduces the observed transitivity patterns by leveraging community structures, which are pervasive in real-world hypergraphs.
현실세계의 많은 상호작용은 여러 개체들 간 발생한다(예시: 공동연구 및 이메일 커뮤니케이션). 이러한 그룹 상호작용은 하이퍼그래프를 이용하여 자연스럽게 모델링 할 수 있다. 추이성은 그래프에서 같은 이웃을 갖는 노드쌍 간 연결관계를 이해하는 데 중요한 역할을 한다. 그래프를 확장한 하이퍼그래프는 그룹 상호작용을 표현하기 위하여 사용된다. 그러나 현실세계의 그룹 상호작용의 추이성은 아직 분석된 바가 없다. 본 연구에서 우리는 현실세계의 그룹 상호작용의 추이성을 탐구한다. 우리는 먼저 하이퍼그래프 추이성 측도가 갖추어야 하는 조건을 제시한다. 이어서 앞서 제시한 조건을 모두 만족하는 하이퍼그래프 추이성 측도를 제안한다. 그리고 랜덤 하이퍼그래프와 차별화되는 현실세계의 그룹 상호작용 추이성 패턴을 분석한다. 마지막으로 현실세계의 하이퍼그래프에서 많이 관 되는 커뮤니티 구조를 활용하여, 관측한 추이성 패턴을 재현 가능한 확장성 있는 하이퍼그래프 생성기를 제시한다.
