[리뷰] Structural Patterns and Generative Models of Real-world Hypergraphs

Mar 19, 2024

[리뷰] Structural Patterns and Generative Models of Real-world Hypergraphs

Contents

Abstract Introduction Background and Related Work Multi-Level Decomposition Observations P1. Giant connected component P2. Heavy-tailed degree distribution P3. Small diameter P4. High clustering coefficient P5. Skewed singular values Hypergraph Generators 5.1. Intuition behind HyperPA 5.2.Details of HyperPA 5.3.Baseline models 5.4.Empirical evaluation Conclusions

Abstract

Graphs have been utilized as a powerful tool to model pairwise relationships between people or objects.

그래프는 사람이나 물체 사이의 짝지어진 관계를 모델링하는 데 강력한 도구로 사용되어 왔습니다.

이 문장은 그래프 이론이 사회 네트워크, 컴퓨터 네트워크, 생물학적 네트워크 등 다양한 분야에서 복잡한 관계를 표현하는 데 널리 사용되고 있음을 설명합니다.

Such structure is a special type of a broader concept referred to as hypergraph, in which each hyperedge may consist of an arbitrary number of nodes, rather than just two.

이러한 구조는 각 하이퍼에지가 두 개가 아닌 임의의 수의 노드로 구성될 수 있는, 하이퍼그래프라고 불리는 더 넓은 개념의 특별한 유형입니다.

하이퍼그래프는 전통적인 그래프에서의 에지가 두 노드만 연결하는 것과 달리, 여러 노드를 동시에 연결할 수 있는 개념을 도입합니다. 이는 복잡한 다자간 관계를 표현할 수 있게 해 줍니다.

A large number of real-world datasets are of this form – for example, lists of recipients of emails sent from an organization, users participating in a discussion thread or subject labels tagged in an online question.

대부분의 실세계 데이터셋이 이 형태를 취하고 있습니다 - 예를 들어, 조직에서 보낸 이메일의 수신자 목록, 토론 스레드에 참여하는 사용자들, 온라인 질문에 태그된 주제 레이블 등입니다.

하이퍼그래프가 실제 세계 데이터를 모델링하는 데 얼마나 적합한지를 보여주는 예시들입니다. 이러한 데이터는 복잡한 다중 관계를 나타내며, 하이퍼그래프를 사용하여 효과적으로 표현할 수 있습니다.

However, due to complex representations and lack of adequate tools, little attention has been paid to exploring the underlying patterns in these interactions.

그러나 복잡한 표현과 적절한 도구의 부재로 인해, 이러한 상호작용에서 기저하는 패턴을 탐색하는 데에는 거의 주목을 받지 못했습니다.

하이퍼그래프의 복잡성으로 인해, 이를 분석하고 이해하는 데 필요한 연구와 도구 개발이 충분히 이루어지지 않았음을 지적합니다.

In this work, we empirically study a number of real-world hypergraph datasets across various domains.

이 연구에서, 우리는 다양한 분야에 걸친 실제 세계 하이퍼그래프 데이터셋을 실증적으로 연구합니다.

연구자들이 실제 데이터를 사용하여 하이퍼그래프의 구조적 패턴을 분석하고 이해하는 작업을 수행했음을 나타냅니다.

In order to enable thorough investigations, we introduce the multi-level decomposition method, which represents each hypergraph by a set ofpairwise graphs. Each pairwise graph, which we refer to as a k-level decomposed graph, captures the interactions between pairs of subsets of k nodes.

철저한 조사를 가능하게 하기 위해, 우리는 각 하이퍼그래프를 일련의 쌍으로 이루어진 그래프 집합으로 표현하는 다중 레벨 분해 방법을 소개합니다. 이 쌍으로 이루어진 그래프는 우리가 k-레벨 분해 그래프라고 부르며, k개 노드의 부분 집합 쌍 사이의 상호작용을 포착합니다.

하이퍼그래프의 복잡한 구조를 단순화하여 분석할 수 있는 방법을 제시합니다. 이는 하이퍼그래프의 다양한 층위에서 노드 간 상호작용을 더 명확하게 이해할 수 있게 해줍니다.

We empirically find that at each decomposition level, the investigated hypergraphs obey five structural properties.

우리는 실증적으로, 조사된 하이퍼그래프가 각 분해 레벨에서 다섯 가지 구조적 속성을 따른다는 것을 발견했습니다.

연구에서 발견한 구조적 속성들은 하이퍼그래프의 공통적인 특성들을 나타내며, 이는 향후 하이퍼그래프 연구에 중요한 기준점을 제공합니다.

These properties serve as criteria for evaluating how realistic a hypergraph is, and establish a foundation for the hypergraph generation problem.

이러한 속성들은 하이퍼그래프가 얼마나 현실적인지를 평가하는 기준으로 작용하며, 하이퍼그래프 생성 문제에 대한 기반을 마련합니다.

하이퍼그래프의 질을 평가하고 생성하는 데 있어 이러한 구조적 속성들이 중요한 역할을 한다는 것을 강조합니다. 이는 보다 현실적인 하이퍼그래프 모델을 개발하는 데 기여할 수 있습니다.

We also propose a hypergraph generator that is remarkably simple but capable of fulfilling these evaluation metrics, which are hardly achieved by other baseline generator models.

우리는 또한 이러한 평가 지표를 충족시킬 수 있는 놀랍도록 간단하지만 효과적인 하이퍼그래프 생성기를 제안합니다. 이는 다른 기본 생성 모델에서 거의 달성되지 않는 것입니다.

새로운 하이퍼그래프 생성기가 기존의 모델보다 우수하며, 간단함에도 불구하고 현실적인 하이퍼그래프를 생성할 수 있는 능력을 가지고 있음을 나타냅니다. 이는 향후 하이퍼그래프 생성과 관련된 연구에 큰 기여를 할 수 있습니다.

이 요약은 하이퍼그래프의 구조적 패턴을 실증적으로 분석하고, 이를 기반으로 새로운 하이퍼그래프 생성기를 제안하는 연구의 내용을 간략하게 소개합니다. 연구는 실제 세계 데이터셋을 사용하여 하이퍼그래프의 공통적인 구조적 특성을 밝히고, 이를 충족시키는 새로운 모델을 개이 요약은 하이퍼그래프의 구조적 패턴을 실증적으로 분석하고, 이를 기반으로 새로운 하이퍼그래프 생성기를 제안하는 연구의 내용을 간략하게 소개합니다. 연구는 실제 세계 데이터셋을 사용하여 하이퍼그래프의 공통적인 구조적 특성을 밝히고, 이를 충족시키는 새로운 모델을 개발하는 데 초점을 맞추고 있습니다.

Introduction

"In our digital age, interactions that involve a group of people or objects are ubiquitous."

"디지털 시대에 우리가 살면서, 사람이나 객체의 그룹에 관련된 상호작용이 어디에나 있습니다."

이 문장은 현대 사회에서 그룹 간의 상호작용이 일상적이며, 다양한 형태로 존재한다는 점을 강조합니다.

"These associations arise from various domains, ranging from academic communities, online social networks to pharmaceutical practice."

"이러한 연결은 학술 공동체, 온라인 소셜 네트워크부터 약학 실습에 이르기까지 다양한 영역에서 발생합니다."

다양한 분야에서 그룹 간의 상호작용이 중요한 역할을 한다는 것을 설명하고 있습니다.

"In particular, research papers are often published by the collaborations of several coauthors, social networks involve group communications, and several related medications may be applied as a treatment rather than just two."

"특히, 연구 논문은 종종 여러 공동 저자들의 협력으로 출판되며, 소셜 네트워크는 그룹 커뮤니케이션을 포함하고, 두 가지가 아닌 여러 관련 약물이 치료로 사용될 수 있습니다."

구체적인 예를 들어 그룹 간의 상호작용의 다양성을 보여줍니다.

"Such structures can be represented as hypergraphs, which is a generalization of the usual notion of graphs."

"이러한 구조는 보통의 그래프 개념을 일반화한 것인 하이퍼그래프로 표현될 수 있습니다."

하이퍼그래프가 복잡한 그룹 간의 관계를 모델링하는데 적합한 도구임을 설명합니다.

"In hypergraphs, each node can be a person or an object. However, each hyperedge acts as an interaction of an arbitrary number of nodes."

"하이퍼그래프에서 각 노드는 사람이나 객체가 될 수 있습니다. 그러나, 각 하이퍼에지는 임의의 수의 노드들 간의 상호작용으로 작동합니다."

하이퍼그래프의 기본 구성 요소와 그들이 어떻게 상호작용을 나타내는지 설명합니다.

"For example, if each node represents an author, a hyperedge can be treated as a research paper which was published by a group of authors."

"예를 들어, 각 노드가 저자를 대표한다면, 하이퍼에지는 여러 저자에 의해 출판된 연구 논문으로 간주될 수 있습니다."

하이퍼그래프를 이용한 모델링의 구체적인 예를 들어 설명합니다.

"A hyperedge also reveals the subset interactions among the elements of each subset, which this work pays special attention to."

"하이퍼에지는 또한 각 부분집합의 요소들 사이의 부분집합 상호작용을 드러내며, 이 연구는 이에 특별한 주의를 기울입니다."

연구의 주요 관심사 중 하나가 부분집합 간의 상호작용을 이해하는 것임을 강조합니다.

"A subset interaction among nodes (e.g.,{a,b}) is defined as their co-appearance as a subset of ahyperedge (e.g.,{a,b,c,d})."

"노드들 사이의 부분 집합 상호작용(예: {a,b})은 하이퍼에지의 부분 집합으로서의 그들의 공동 출현으로 정의됩니다(예: {a,b,c,d})."

부분 집합 상호작용의 정의와 하이퍼그래프 내에서 이러한 상호작용이 어떻게 중요한 역할을 하는지 설명합니다.

"The freedom of number of nodes involved in each hyperedge and subset interactions naturally contribute to the complexity of hypergraphs."

"각 하이퍼에지와 부분 집합 상호작용에 관련된 노드의 수의 자유로움은 자연스럽게 하이퍼그래프의 복잡성에 기여합니다."

하이퍼그래프가 복잡한 구조를 가질 수 있는 이유 중 하나가 다양한 수의 노드가 하이퍼에지를 구성할 수 있기 때문임을 나타냅니다.

"While pairwise graphs have been extensively studied in terms of mining structures, discovering hidden characteristics as well as evolutionary patterns, little attention has been paid to defining and addressing analogous problems in hypergraphs."

"쌍으로 이루어진 그래프가 구조 마이닝, 숨겨진 특성 발견, 진화 패턴 등 다양한 측면에서 광범위하게 연구되었지만, 하이퍼그래프에서 유사한 문제를 정의하고 해결하는 데는 거의 주목하지 않았습니다."

이 문장은 하이퍼그래프에 대한 연구가 상대적으로 부족하다고 지적하면서, 이 연구가 하이퍼그래프를 이해하고 분석하는 새로운 방법론을 제시한다는 점을 강조합니다.

"Due to the complexity of subset interactions, any single representation of hypergraphs relying on pairwise links would suffer from information loss."

"부분 집합 상호작용의 복잡성 때문에, 쌍으로 이루어진 링크에만 의존하는 하이퍼그래프의 단일 표현은 정보 손실을 겪게 됩니다."

하이퍼그래프의 다중 노드 상호작용을 쌍으로 이루어진 링크로만 나타내려고 할 때 정보가 충분히 표현되지 않는 문제를 설명합니다.

"Given that most existing graph data structures only capture relationships between pairs of nodes, and more importantly, most patterns discovered are based on pairwise links-based measurements, directly applying the existing results in pairwise graphs to hypergraphs constitutes a challenge."

"대부분의 기존 그래프 데이터 구조가 노드 쌍 간의 관계만을 포착하고, 더 중요하게는 발견된 대부분의 패턴이 쌍 기반 링크 측정에 기반하기 때문에, 쌍으로 이루어진 그래프에서의 기존 결과를 하이퍼그래프에 직접 적용하는 것은 도전이 됩니다."

이 문장은 기존 그래프 분석 방법과 도구가 하이퍼그래프의 복잡성을 적절히 다루기에는 한계가 있음을 설명하고 있습니다.

"Here we investigate several hypergraph datasets among various domains."

"여기서 우리는 다양한 영역의 여러 하이퍼그래프 데이터셋을 조사합니다."

연구자들이 다양한 분야에서 하이퍼그래프 데이터를 분석하여 일반적인 패턴과 특성을 탐색한다는 점을 강조합니다.

"We introduce the multi-level decomposition of hypergraphs, which captures relationships between subsets of nodes."

"노드의 부분 집합 간의 관계를 포착하는 하이퍼그래프의 다중 레벨 분해를 소개합니다."

하이퍼그래프를 분석하고 이해하기 위한 새로운 방법론인 다중 레벨 분해 방법을 설명합니다.

"This offers a set of pairwise link representations convenient for analysis while guaranteeing to recover the original hypergraphs."

"이는 분석하기에 편리한 쌍으로 이루어진 링크 표현의 집합을 제공하면서 원래의 하이퍼그래프를 복원할 수 있는 보장을 제공합니다."

다중 레벨 분해 방법이 하이퍼그래프의 상세한 분석을 가능하게합니다하면서, 원본 데이터와 분석 결과 간의 연결성을 유지합니다.

"In the most elementary type of decomposition, referred to as 'node-level decomposed graph' in this paper, two nodes are linked if they appear in at least one hyperedge together."

"이 논문에서 '노드 레벨 분해 그래프'로 언급된 가장 기본적인 분해 유형에서, 두 노드가 적어도 하나의 하이퍼에지에 함께 나타난다면 연결됩니다."

다중 레벨 분해 방법론 중 가장 기본적인 형태를 설명하며, 이는 하이퍼그래프의 복잡한 구조를 단순화하여 분석하기 용이한 형태로 변환하는 방법입니다.

"This is the decomposition for k=1. In the k-level decomposed graph, a node is defined as a set of k nodes in the original hypergraph, and two nodes are connected if their union appears in a hyperedge."

"이것은 k=1일 때의 분해입니다. k-레벨 분해 그래프에서, 노드는 원래 하이퍼그래프의 k개 노드의 집합으로 정의되며, 두 노드의 합집합이 하이퍼에지에 나타나면 연결됩니다."

다중 레벨 분해 방법의 작동 원리를 설명하며, 이를 통해 하이퍼그래프 내의 복잡한 관계를 다양한 수준에서 살펴볼 수 있음을 나타냅니다.

"Using the multi-level decomposition, we find that the decomposed graphs of thirteen real-world hypergraphs generally obey the following well-known properties of real-world graphs, across different levels: (1) giant connected components, (2) heavy-tailed degree distributions, (3) small effective diameters, (4) high clustering coefficients, and (5) skewed singular-value distributions."

"다중 레벨 분해를 사용하여, 우리는 실제 세계의 하이퍼그래프들이 분해된 그래프에서 일반적으로 실세계 그래프의 잘 알려진 특성들을 다양한 레벨에서 따르는 것을 발견했습니다: (1) 거대 연결 구성요소, (2) 무거운 꼬리 정도 분포, (3) 작은 유효 직경, (4) 높은 클러스터링 계수, (5) 왜곡된 단일 값 분포."

이는 다중 레벨 분해 방법이 실제 세계 하이퍼그래프의 일반적인 구조적 특성을 분석하고 이해하는 데 유용함을 보여줍니다.

"This decomposition also reveals how well such subset interactions are connected, and this connectivity varies across different domains."

"이 분해는 또한 부분 집합 상호작용이 얼마나 잘 연결되어 있는지를 드러내며, 이러한 연결성은 다양한 영역에 걸쳐 다릅니다."

하이퍼그래프 내의 부분 집합 상호작용 간의 연결성을 분석할 수 있으며, 이러한 연결성이 분야에 따라 다르게 나타날 수 있음을 설명합니다.

"What could be the possible underlying principles for such patterns?"

"이러한 패턴에 대한 가능한 기본 원칙은 무엇일까요?"

이 문장은 연구자들이 하이퍼그래프에서 발견된 패턴의 근본적인 원인을 탐색하려는 의도를 나타냅니다. 이는 연구의 다음 단계에서 중요한 질문으로, 패턴이 왜 존재하는지에 대한 이해를 높이고자 합니다.

"Driven by this question, we propose a simple hypergraph generator model called HyperPA."

"이 질문에 의해, 우리는 HyperPA라는 간단한 하이퍼그래프 생성 모델을 제안합니다."

연구자들이 이 질문에 대응하여, 발견된 패턴을 재현할 수 있는 새로운 하이퍼그래프 생성 모델인 HyperPA를 소개합니다. 이 모델은 하이퍼그래프의 구조적 특성을 모사하는 데 사용됩니다.

"By some proper modifications of preferential attachment, which account for degree as a group, nodes can 'get rich' together while maintaining subset interactions."

"선호 첨부의 적절한 수정을 통해, 노드 그룹의 정도를 고려할 수 있으며, 노드들은 부분 집합 상호작용을 유지하면서 함께 '부유해질 수' 있습니다."

이 모델은 선호 첨부 메커니즘을 수정하여 노드 그룹이 공동으로 중요해지는 방식을 모델링합니다. 여기서 "부유해짐"은 네트워크에서 노드의 중요성이나 연결성이 증가하는 것을 의미합니다.

"Compared to two other baseline models, HyperPA shows more realistic results in reproducing the patterns discovered in real-world hypergraphs and resembling the connectivity of such subset interactions."

"두 개의 다른 기준 모델과 비교할 때, HyperPA는 실제 세계 하이퍼그래프에서 발견된 패턴을 재현하고, 그러한 부분 집합 상호작용의 연결성을 닮은 더 현실적인 결과를 보여줍니다."

HyperPA 모델이 기존 모델보다 실제 하이퍼그래프의 구조적 특성과 부분 집합 간의 연결성을 더 잘 재현한다는 점을 강조합니다.

"Findings in common properties of real-world hypergraphs and their underlying explanations can be significant for several reasons."

"실제 세계 하이퍼그래프의 공통 속성과 그에 대한 기본 설명을 발견하는 것은 여러 가지 이유로 중요할 수 있습니다."

이 문장은 연구 결과가 가지는 중요성을 강조합니다. 실제 하이퍼그래프의 공통적인 특성과 그 원인에 대한 이해는 여러 방면에서 유용할 수 있습니다.

"Anomaly detection: if some data significantly deviates from the set of common patterns, it is reasonable to raise an alarm for anomalies."

"이상 탐지: 일부 데이터가 공통 패턴 집합에서 크게 벗어난다면, 이상에 대한 경보를 울리는 것이 합리적입니다."

발견된 공통 패턴을 기반으로 이상 현상을 탐지할 수 있음을 설명합니다. 데이터가 일반적인 패턴에서 벗어나면 이상 상태로감지할 수 있다는 것을 의미합니다.

"Anonymization: by fully reproducing these patterns, organizations may synthesize datasets to avoid disclosing important internal information."

"익명화: 이러한 패턴을 완전히 재현함으로써, 조직은 중요한 내부 정보를 공개하지 않고 데이터셋을 합성할 수 있습니다."

이 연구가 제공하는 패턴 이해는 조직이 실제 데이터의 패턴을 유지하면서도 개인 정보나 민감한 정보를 보호할 수 있는 익명화된 데이터셋을 생성하는 데 도움이 될 수 있음을 시사합니다.

"Simulation: generated hypergraphs can be utilized for 'what-if' simulation scenarios when collecting large-size hypergraph datasets is costly and difficult."

"시뮬레이션: 큰 규모의 하이퍼그래프 데이터셋을 수집하는 것이 비용이 많이 들고 어려울 때, 생성된 하이퍼그래프는 '만약에' 시뮬레이션 시나리오에 사용될 수 있습니다."

생성된 하이퍼그래프를 사용하여 실제 상황에서 발생할 수 있는 다양한 시나리오를 모델링하고 시뮬레이션할 수 있음을 설명합니다. 이는 특히 데이터 수집이 어렵거나 비용이 많이 드는 경우에 유용합니다.

"In short, the main contributions of our paper are three-fold."

"간단히 말해서, 우리 논문의 주요 기여는 세 가지입니다."

연구의 주요 기여도를 요약하며, 다음 문장들에서 이 세 가지 기여도에 대해 자세히 설명합니다.

"Multi-level decomposition: a tool that facilitates easy and comprehensive analysis of subset interactions in hypergraphs."

"다중 레벨 분해: 하이퍼그래프 내의 부분 집합 상호작용을 쉽고 포괄적으로 분석할 수 있게 하는 도구입니다."

이 연구가 제안하는 다중 레벨 분해 방법이 하이퍼그래프 분석을 용이하게 하며, 복잡한 구조와 상호작용을 이해하는 데 큰 도움이 됨을 강조합니다.

"Patterns: five structural properties that are commonly held in thirteen real-world hypergraphs from diverse domains."

"패턴: 다양한 분야의 13개 실제 세계 하이퍼그래프에서 공통적으로 발견되는 다섯 가지 구조적 속성입니다."

연구를 통해 발견된 공통적인 구조적 속성들이 하이퍼그래프 분석에 중요한 기준이 됨을 나타냅니다.

"Hypergraph generator (HyperPA): a simple but powerful model that produces hypergraphs satisfying the above properties."

"하이퍼그래프 생성기 (HyperPA): 위에서 언급한 속성들을 만족시키는 하이퍼그래프를 생성하는 간단하지만 강력한 모델입니다."

HyperPA 모델이 실제 세계의 하이퍼그래프를 재현하는 데 효과적임을 강조하며, 연구의 핵심 기여 중 하나임을 나타냅니다.

"Reproducibility: We made the datasets, the code, and the full experimental results available at [GitHub link]."

"재현성: 우리는 데이터셋, 코드, 그리고 전체 실험 결과를[GitHub 링크]에서 사용할 수 있도록 했습니다."

이 연구는 데이터셋, 코드 및 실험 결과를 공개하여 연구의 재현성을 보장합니다. 이를 통해 다른 연구자들이 연구 결과를 검증하고 추가적인 연구를 수행할 수 있도록 지원합니다.

"The remaining sections of this paper are outlined as follow: Sect.2 provides a brief survey of related work. In Sect. 3, we introduce our decomposition tool which facilitates our understanding of structural properties of hypergraphs. Our empirical findings on real-world hypergraph datasets are presented in Sect. 4. Sect. 5 introduces hypergraph generators and demonstrates how these models perform in terms of reproducing the real-world patterns. We discuss and conclude our work in Sect. 6."

"이 논문의 나머지 부분은 다음과 같이 구성되어 있습니다: 제2장에서는 관련 연구에 대한 간략한 조사를 제공합니다. 제3장에서는 하이퍼그래프의 구조적 특성 이해를 용이하게 하는 우리의 분해 도구를 소개합니다. 실제 세계 하이퍼그래프 데이터셋에 대한 우리의 실증적 발견은 제4장에서 제시됩니다. 제5장에서는 하이퍼그래프 생성기를 소개하고 이 모델들이 실제 세계 패턴을 재현하는 방식에 대해 설명합니다. 우리는 제6장에서 우리의 작업에 대해 논의하고 결론을 내립니다."

이 문장은 논문의 구조를 설명하며, 각 섹션에서 다루는 주제와 내용에 대한 개요를 제공합니다. 이는 독자가 논문의 전체적인 흐름을 이해하고 관심 있는 부분으로 쉽게 이동할 수 있게 도와줍니다.

이 서론 부분은 하이퍼그래프의 중요성과 복잡성을 강조하고, 이를 분석하기 위한 새로운 접근 방법을 제시합니다. 다중 레벨 분해 방법과 HyperPA 생성 모델은 실제 하이퍼그래프의 패턴을 이해하고 재현하는 데 중요한 도구로, 연구의 핵심 기여를 구성합니다. 또한, 연구의 재현성을 보장하기 위해 사용된 데이터셋, 코드, 실험 결과를 공개함으로써, 이 분야의 추가적인 연구와 발전을 촉진합니다. 이러한 기여는 하이퍼그래프 분석 및 모델링에 관심 있는 연구자와 실무자에게 유용한 자원을 제공합니다.

Background and Related Work

"Graph properties: Many empirical studies have been conducted to explore common properties of real-world pair-wise graphs based on predefined measurements."

그래프 속성: 실제 세계의 쌍으로 이루어진 그래프의 공통 속성을 탐색하기 위해 많은 실증적 연구가 수행되었습니다.

이는 기존의 그래프 연구가 주로 쌍으로 이루어진 그래프의 특성을 중심으로 진행되었음을 나타냅니다. 이러한 연구는 그래프의 정적 및 동적 속성을 이해하는 데 중요한 기초를 제공합니다.

"There are two main types of these properties: static and dynamic."

이러한 속성에는 두 가지 주요 유형이 있습니다: 정적 및 동적.

정적 속성은 특정 시점에서의 그래프 상태를, 동적 속성은 시간에 따른 그래프의 변화를 나타냅니다.

"Static properties are revealed from a snapshot of the graphs at a particular time, and they include degree distribution, diameter, distribution of eigenvalues, and more."

정적 속성은 특정 시간에 그래프의 스냅샷에서 드러나며, 그것들은 정도 분포, 지름, 고유값 분포 등을 포함합니다.

정적 속성은 그래프의 구조적 특성을 기반으로 하며, 그래프 분석에서 중요한 기준을 제공합니다.

"Dynamic properties examine the evolution of a graph over a period of time."

동적 속성은 시간에 따른 그래프의 진화를 검토합니다.

동적 속성은 그래프가 시간에 따라 어떻게 변화하는지를 관찰함으로써, 네트워크의 성장 패턴이나 변화하는 동태를 이해하는 데 도움을 줍니다.

"Graph generative models: In conjunction, numerous graph generator models have been developed to produce synthetic graphs satisfying these commonly held patterns."

그래프 생성 모델: 이와 관련하여, 이러한 일반적으로 발견되는 패턴을 만족시키는 합성 그래프를 생성하기 위해 다수의 그래프 생성 모델이 개발되었습니다.

그래프 생성 모델은 이론적 연구나 시뮬레이션을 통해 실제 그래프의 속성을 모사할 수 있는 합성 그래프를 생성하는 데 사용됩니다. 이러한 모델들 중 일부는 실제와 유사한 정도 분포를 재현하는 데 중점을 두고 있습니다.

"Others exploit locality to generate communities within the graph."

다른 모델들은 그래프 내에서 커뮤니티를 생성하기 위해 지역성을 활용합니다.

지역성을 이용한 그래프 생성 모델은 그래프 내에서 자연스럽게 형성되는 커뮤니티나 클러스터를 모델링하는 데 초점을 맞춥니다.

"In (Leskovec et al., 2005; Akoglu et al., 2008), dynamic patterns of graph evolution are recaptured."

(Leskovec et al., 2005; Akoglu et al., 2008)에서는 그래프 진화의 동적 패턴이 다시 포착됩니다.

이는 시간에 따른 그래프의 변화와 성장을 이해하기 위한 연구의 예로, 그래프가 어떻게 발전해 가는지에 대한 통찰을 제공합니다.

"Hypergraphs are used for representing various entities in diverse fields, including biology, medicine, social networks, and web."

하이퍼그래프는 생물학, 의학, 소셜 네트워크, 웹을 포함한 다양한 분야에서 여러 엔티티를 나타내는 데 사용됩니다.

하이퍼그래프의 다양한 응용 분야와 중요성을 강조하는 문장입니다. 복잡한 다중 관계를 효과적으로 표현할 수 있는 하이퍼그래프의 사용 사례들을 소개합니다.

"To better analyze and process hypergraphs, there has been an increasing interest in extending studies on graphs to hypergraphs."

하이퍼그래프를 더 잘 분석하고 처리하기 위해, 그래프에 대한 연구를 하이퍼그래프로 확장하는 데 대한 관심이 증가하고 있습니다.

하이퍼그래프 연구의 중요성과 그 분야에서의 연구 확장 필요성을 나타냅니다. 기존 그래프 이론을 넘어서 하이퍼그래프의 특성과 동작을 이해하려는 노력을 설명합니다.

"In our work, we study the general patterns of real-world hypergraphs, encompassing the wide range of extensions studied in graphs with a strong emphasis on ‘subset interactions’."

우리의 작업에서, 우리는 ‘부분 집합 상호작용’에 강한 강조를 두고 그래프에서 연구된 다양한 확장을 포괄하는 실제 세계 하이퍼그래프의 일반적인 패턴을 연구합니다.

이 문장은 연구의 목적과 방향성을 요약합니다. 실제 세계 하이퍼그래프에서 발견되는 패턴과 그 패턴들이 어떻게 부분 집합 간의 상호작용과 관련이 있는지를 탐구하는 것이 주된 초점입니다.

Multi-Level Decomposition

"In this section, we introduce the multi-level decomposition, which is our method for analyzing hypergraphs."

이 섹션에서는 하이퍼그래프를 분석하는 우리의 방법인 다중 레벨 분해를 소개합니다.

다중 레벨 분해는 하이퍼그래프의 복잡성을 단순화하여 분석할 수 있는 새로운 접근 방법을 의미합니다.

"Our motivation for the multi-level decomposition is that it is not straightforward to investigate the properties of hypergraphs in their raw form."

다중 레벨 분해를 도입한 우리의 동기는 하이퍼그래프의 속성을 그들의 원형태로 바로 조사하기가 간단하지 않기 때문입니다.

하이퍼그래프는 복잡한 구조로 인해, 직접 분석하기 어렵기 때문에, 더 접근하기 쉬운 방식을 모색하는 것이 필요합니다. 이러한 동기에서 다중 레벨 분해 방법이 제안되었습니다.

"We instead seek a way to analyze hypergraphs through the lens of ordinary graphs."

대신 우리는 일반 그래프의 관점을 통해 하이퍼그래프를 분석하는 방법을 찾습니다.

이는 하이퍼그래프를 일반적인 그래프로 변환함으로써, 기존에 잘 알려진 그래프 분석 기법을 적용할 수 있게 하는 전략입니다.

"By transforming hypergraphs into graphs, we can adopt the various properties studied in graphs for hypergraphs."

하이퍼그래프를 그래프로 변환함으로써, 우리는 그래프에서 연구된 다양한 속성들을 하이퍼그래프에 적용할 수 있습니다.

이 변환 과정은 하이퍼그래프 분석을 용이하게 하며, 그래프 이론의 기존 연구 성과를 활용할 수 있게 합니다.

Hypergraphs and subset interactions

"A hypergraph is defined as G=(V,E), where V is a set of nodes and E⊂2^V is a set of hyperedges."

하이퍼그래프는 G=(V,E)로 정의되며, 여기서 V는 노드의 집합이고 E⊂2^V는 하이퍼에지의 집합입니다.
하이퍼그래프는 전통적인 그래프와 다르게, 하나의 에지가 두 개 이상의 노드를 연결할 수 있는 구조를 가지고 있음을 설명합니다.

"Each hyperedge e⊆V is a set of |e| nodes that have appeared as a group."

각 하이퍼에지 e⊆V는 그룹으로 나타난 |e|개의 노드의 집합입니다.
하이퍼에지는 노드들이 특정 그룹이나 커뮤니티를 형성할 때 이를 나타내는 역할을 합니다.

Multi-level decomposition

"Given a hypergraph G=(V,E), the multi-level decomposition of G is defined as a set of k-level decomposed graphs for every k∈ {1,...,max e∈E(|e|)}"

하이퍼그래프 G=(V,E)가 주어졌을 때, G의 다중 레벨 분해는 모든 k∈ {1,...,max e∈E(|e|)}에 대한 k-레벨 분해 그래프의 집합으로 정의됩니다.
다중 레벨 분해는 하이퍼그래프를 여러 단계의 더 단순한 그래프로 나누는 과정을 말합니다. 이를 통해 하이퍼그래프의 복잡한 구조를 단계별로 이해할 수 있습니다.

Advantages of using decomposedgraphs:

"Subset interaction: decomposed graphs reveal subset interactions between subsets of nodes."

부분 집합 상호작용: 분해 그래프는 노드의 부분 집합 간의 상호작용을 드러냅니다.
이는 하이퍼그래프 내의 복잡한 연결 관계를 더 명확하게 이해할 수 있도록 돕습니다.

"Pairwise graph representation: decomposed graphs can be easily analyzed with existing measurements for pairwise graphs."

쌍으로 이루어진 그래프 표현: 분해 그래프는 쌍으로 이루어진 그래프에 대한 기존 측정 방법으로 쉽게 분석할 수 있습니다.
이는 분해된 그래프를 통해 하이퍼그래프의 구조를 전통적인 그래프 분석 방법으로 탐색할 수 있음을 의미합니다.

"No information loss: the original hypergraph can be recovered from the decomposed graphs."

정보 손실 없음: 원본 하이퍼그래프는 분해 그래프로부터 복구될 수 있습니다.
이는 다중 레벨 분해 방법이 하이퍼그래프의 정보를 보존하면서도 분석을 용이하게 한다는 장점을 강조합니다.

"Notice that the notion of k-level decomposition is a generalization of an existing concept: when k=1, the decomposed graph corresponds to the widely-used pairwise projected graph."

k-레벨 분해의 개념은 기존 개념의 일반화입니다: k=1일 때, 분해 그래프는 널리 사용되는 쌍으로 이루어진 투영 그래프에 해당합니다.

이는 다중 레벨 분해가 기존에 알려진 그래프 분석 방법을 확장한 것임을 나타내며, 이를 통해 하이퍼그래프의 다양한 구조적 특성을 다룰 수 있음을 설명합니다.

"In our study, we focus on k-level decomposed graphs with k∈{1,2,3,4}, as most hyperedges in real-world hypergraphs are of sizes only up to 4."

우리의 연구에서는 대부분의 실제 세계 하이퍼그래프의 하이퍼에지 크기가 4까지인 것을 고려하여, k∈{1,2,3,4}인 k-레벨 분해 그래프에 초점을 맞춥니다.

실제 하이퍼그래프에서 관찰되는 하이퍼에지의 크기 분포를 바탕으로, 분석의 효율성과 실용성을 높이기 위한 선택을 설명합니다.

“For simplicity, we call them node-level, edge-level, triangle-level, and 4 clique-level decomposed graphs, respectively.”

간단히, 우리는 이들을 node-level, edge-level, triangle-level, 4clique-level decomposed graph로 각각 부르겠습니다.

이러한 접근 방식은 하이퍼그래프의 복잡한 구조를 체계적으로 분석하고, 하이퍼그래프 내에서의 노드 간 상호작용 및 이들의 그룹화 현상을 이해하는 데 도움을 줍니다. 다중 레벨 분해를 통해 하이퍼그래프의 구조적 특성을 다루는 동시에, 기존의 그래프 이론과 분석 방법을 활용할 수 있는 기반을 마련합니다.

Observations

In this section, we demonstrate that the following structural patterns hold in each level of decomposed graphs of real hypergraphs:

P1. Giant connected component

P2. Heavy-tailed degree distribution

P3. Small effective diameter

P4. High clustering coefficient

P5. Skewed singular values

These patterns, which are described in detail in the following subsections, are supported by our observations in thirteen real hypergraph datasets of medium to large sizes. Details on the datasets can be found in Appendix A, and the complete set of observations is available in (app, 2020). Below, we provide the intuition behind them and present a random hypergraph model that we use as the null model.

Intuition behind the patterns. Consider the coauthorship data as an example: in our node-level decomposed graph, each node represents an author, and two nodes are connected if and only if these two authors have coauthored at least one paper before. Therefore, this node-level decomposition can be interpreted as an author network. Such node-level decomposed graphs are not “real” graphs since they are obtained by decomposing the original hypergraphs. However, they represent pairwise relationships as real-world graphs do, and by this interpretation, we deduce that the node-level decomposed graphs of real-world hypergraphs will exhibit the five patterns (i.e., P1-P5), which are well-known for real-world graphs (Leskovec et al., 2005; Leskovec et al., 2010; Faloutsos et al., 1999; Broder et al., 2000; Milgram, 1967; Albert et al., 1999; Bollobás and Riordan, 2004; Yin et al., 2017; Kumar et al., 2000). We further suspect that these patterns also hold at higher levels of decomposition.

Null Model: Random Hypergraphs (Null.): In order to show P3 and P4 are not random behavior of any hypergraph, we use a random hypergraph corresponding to each real hypergraph as the null model. Specifically, given a hypergraph, the null model is constructed by randomly choosing nodes to be contained in each hyperedge, while keeping its original size.

[Kor]

이 섹션에서는 실제 하이퍼그래프의 분해된 그래프 각 레벨에서 다음과 같은 구조적 패턴이 유지됨을 보여줍니다:

P1. 거대 연결 구성요소

P2. 무거운 꼬리의 정도 분포

P3. 작은 유효 직경

P4. 높은 클러스터링 계수

P5. 치우친 단일 값들

이 패턴들은 중간에서 큰 규모의 13개 실제 하이퍼그래프 데이터셋에서의 관찰을 통해 지지되며, 이는 다음 소섹션에서 자세히 설명됩니다. 데이터셋에 대한 자세한 정보는 부록 A에서 찾을 수 있으며, 관찰의 전체 세트는 (app, 2020)에서 이용 가능합니다. 이러한 패턴들 뒤에 있는 직관을 제공하고, null 모델로 사용하는 무작위 하이퍼그래프 모델을 소개합니다.

패턴의 직관을 이해하기 위해, 예를 들어 공저 데이터를 봅시다: 노드 레벨 분해 그래프에서, 각 노드는 저자를 나타내고, 두 노드는 이 두 저자가 과거에 적어도 한 편의 논문을 공동 집필했다면 연결됩니다. 따라서, 이 노드 레벨 분해는 저자 네트워크로 해석될 수 있습니다. 이러한 노드 레벨 분해 그래프는 원본 하이퍼그래프를 분해하여 얻은 것이기 때문에 "실제" 그래프는 아닙니다. 그러나, 그들은 실제 세계의 그래프가 하는 것처럼 쌍으로 이루어진 관계를 나타냅니다. 이러한 해석을 통해, 우리는 실제 세계 하이퍼그래프의 노드 레벨 분해 그래프가 실제 세계 그래프에서 잘 알려진 다섯 가지 패턴(P1-P5)을 보일 것이라고 추론합니다. 우리는 이러한 패턴이 분해의 더 높은 레벨에서도 유지될 것이라고 추측합니다.

Null 모델: 무작위 하이퍼그래프 (Null.): P3와 P4가 어떤 하이퍼그래프의 무작위 행동이 아님을 보이기 위해, 우리는 각 실제 하이퍼그래프에 해당하는 무작위 하이퍼그래프를 null 모델로 사용합니다. 구체적으로, 하이퍼그래프가 주어지면, null 모델은 각 하이퍼에지에 포함될 노드를 무작위로 선택하면서 그것의 원래 크기를 유지하여 구성됩니다.

이 설명은 실제 하이퍼그래프에서 관찰되는 구조적 패턴들이 우연이 아니라 근본적인 속성임을 보여주려는 시도입니다. 노드 레벨 분해를 통해 얻어진 그래프가 실제 그래프처럼 쌍방 관계를 나타내며, 이를 통해 실제 하이퍼그래프의 복잡한 구조를더 잘 이해할 수 있도록 복잡한 하이퍼그래프의 구조를 단순화하는 방법으로 분해된 그래프를 사용합니다. 이러한 분해를 통해 우리는 하이퍼그래프가 일반적인 그래프와 유사한 구조적 특성을 공유한다는 것을 발견할 수 있으며, 이는 하이퍼그래프 분석에 새로운 접근 방식을 제공합니다. 또한, null 모델을 사용함으로써 특정 패턴이 무작위적인 결과가 아니라 실제 구조적 특성으로 인한 것임을 입증할 수 있습니다.

P1. Giant connected component

This property means that there is a connected component comprising of a large proportion of nodes, and this proportion is significantly larger (specifically, at least 70 times larger) than that of the second largest connected component. The majority of nodes in a network are connected to each other (Kang et al., 2010). This property serves as a basis for the other properties. For example, without a giant connected component (i.e, the graph is “shattered” into small connected communities), diameter would clearly be small as a consequence, not as an independent property of the dataset.

Table 1. Size of the largest connected component, as the proportion of the total number of nodes (including the degree-zero nodes), in each dataset at each decomposition level. The red numbers indicate that the graph no longer retains a giant connected component. In the case of NDC-classes, the size of the second largest connected component at triangle and 4clique levels is 0.11 and 0.04. According to the description in Sect. 4.1, a giant connected component does not exist.

Level	Node	Edge	Triangle	4clique
ㅤ	(k=1)	(k=2)	(k=3)	(k=4)
coauth-DBLP	0.86	0.57	0.05	0.0006
coauth-Geology	0.72	0.5	0.06	0.0005
coauth-History	0.22	0.002	0.002	0.001
DAWN	0.89	0.98	0.91	0.52
email-Eu	0.98	0.98	0.86	0.41
NDC-classes	0.54	0.62	0.27	0.19
NDC-substances	0.58	0.82	0.36	0.02
tags-ask-ubuntu	0.99	0.99	0.79	0.21
tags-math	0.99	0.99	0.91	0.35
tags-stack-overflow	0.99	0.99	0.92	0.42
threads-ask-ubuntu	0.65	0.09	0.02	0.01
threads-math	0.86	0.61	0.03	0.0004
threads-stack-overflow	0.86	0.32	0.004	3e−5

In Table 1, we report the size of the largest connected component at all decomposition levels. The connectivity of subset interactions, represented as the highest level for which the decomposed graph maintains a giant connected component, varies among datasets. In particular, while the co-authorship datasets are shattered at the triangle level, the online-tags datasets retain giant connected components until the 4clique level. Note that while our decomposition is only up to the 4clique level, there are many hyperedges of sizes at least 5, implying that when the graph is shattered, it consists of several isolated cliques, not just isolated nodes.

There is a positive correlation between the distribution of hyperedge sizes and whether the graph is shattered at the edge-level decomposition. Take the proportion of unique hyperedges of sizes at most 2 as the feature. Datasets with this feature greater than 75% are shattered, and the others retain giant connected components. At the triangle level, 6 (out of 13) datasets have giant connected components. Except for email-Eu and NDC-classes, the datasets where the proportion of hypergedges of sizes at most 3 is larger than 60% are shattered at this level. The others possess a giant connected component.

이 섹션에서는 실제 하이퍼그래프의 분해된 그래프들이 각 레벨에서 다음과 같은 구조적 패턴을 유지함을 보여줍니다:

거대 연결 구성요소: 네트워크 내 대다수의 노드들이 서로 연결된 한 개의 큰 구성요소를 포함하며, 이 구성요소는 두 번째로 큰 연결 구성요소보다 훨씬 큰 비율(구체적으로 최소 70배 이상)을 차지합니다. 대부분의 노드가 서로 연결되어 있다는 이 속성은 다른 속성의 기초가 됩니다. 예를 들어, 거대 연결 구성요소가 없다면(즉, 그래프가 작은 연결 커뮤니티로 "분해"되어 있다면), 직경은 결과적으로 작게 될 것이며, 이는 데이터셋의 독립적인 속성이 아닙니다.

Table 1에서는 각 분해 레벨의 각 데이터셋에서 전체 노드 수(정도가 0인 노드 포함)에 대한 가장 큰 연결 구성요소의 크기 비율을 보고합니다. 빨간 숫자는 그래프가 더 이상 거대 연결 구성요소를 유지하지 않는다는 것을 나타냅니다. NDC-classes의 경우, 삼각형 및 4클리크 레벨에서 두 번째로 큰 연결 구성요소의 크기는 각각 0.11과 0.04입니다. 4.1절의 설명에 따르면, 거대 연결 구성요소는 존재하지 않습니다.

데이터셋 간에 분해된 그래프가 거대 연결 구성요소를 유지하는 최고 레벨로 나타나는 부분 집합 상호작용의 연결성은 다양합니다. 특히, 공저 데이터셋은 삼각형 레벨에서 분해되는 반면, 온라인 태그 데이터셋은 4클리크 레벨까지 거대 연결 구성요소를 유지합니다. 분해가 4클리크 레벨까지만 이루어졌음에도 불구하고, 적어도 5의 크기를 가진 많은 하이퍼에지가 있어, 그래프가 분해될 때 여러 개의 격리된 클릭으로 구성된다는 것을 시사합니다.

하이퍼에지 크기 분포와 그래프가 에지 레벨 분해에서 분해되는지 여부 사이에는 긍정적인 상관관계가 있습니다. 최대 2 크기의 유니크 하이퍼에지 비율을 특징으로 합니다. 이 특징이 75% 이상인 데이터셋은 분해되며, 나머지는 거대 연결 구성요소를 유지합니다. 삼각형 레벨에서 13개 데이터셋 중 6개가 거대 연결 구성요소를 가집니다. email-Eu와 NDC-classes를 제외하고, 최대 3 크기의 하이퍼에지 비율이 60% 이상인 데이터셋은 이 레벨에서 분해됩니다. 나머지는 거대 연결 구성요소를 보유합니다.

이 내용은 하이퍼그래프의 특정 구조적 특성이 어떻게 각 분해레벨에서 실제로 관찰될 수 있는지 설명하고 있습니다. 거대 연결 구성요소의 존재는 네트워크 내 대다수의 노드가 서로 연결되어 있음을 의미하며, 이는 네트워크의 다른 구조적 속성의 기반이 됩니다. 예를 들어, 거대 연결 구성요소가 없으면, 즉 그래프가 작은 연결된 커뮤니티로 "분해"되어 있다면, 그 결과로서 직경이 작아질 것입니다. 이는 데이터셋의 독립적인 속성이 아니라 결과적인 속성입니다.

Table 1에서는 각 분해 레벨에서 전체 노드 수(0도의 노드 포함)에 대한 가장 큰 연결 구성요소의 크기 비율을 보고하고 있습니다. 빨간색 숫자는 그래프가 더 이상 거대 연결 구성요소를 유지하지 않음을 나타냅니다. 예를 들어, NDC-classes의 경우, 삼각형 및 4클리크 레벨에서 두 번째로 큰 연결 구성요소의 크기는 각각 0.11과 0.04입니다. 이는 거대 연결 구성요소의 존재 여부가 데이터셋마다 다르며, 특히 공저 데이터셋은 삼각형 레벨에서 분해되는 반면, 온라인 태그 데이터셋은 4클리크 레벨까지 거대 연결 구성요소를 유지한다는 것을 보여줍니다.

분해가 4클리크 레벨까지만 이루어졌음에도 불구하고, 적어도 5의 크기를 가진 많은 하이퍼에지가 존재한다는 사실은, 그래프가 분해될 때 여러 개의 격리된 클릭으로 구성된다는 것을 의미합니다. 하이퍼에지 크기 분포와 그래프가 에지 레벨에서 분해되는지 여부 사이에는 긍정적인 상관관계가 있습니다. 최대 2 크기의 유니크 하이퍼에지 비율이 높은 데이터셋은 분해되며, 그렇지 않은 데이터셋은 거대 연결 구성요소를 유지합니다.

이 분석은 하이퍼그래프의 구조적 속성과 이러한 속성이 하이퍼그래프의 다양한 분해 레벨에서 어떻게 나타나는지에 대한 깊은 이해를 제공합니다. 거대 연결 구성요소의 존재는 네트워크의 중심성과 연결성을 나타내는 중요한 지표로, 이러한 구성요소의 크기와 분포는 네트워크의 전반적인 구조와 기능을 이해하는 데 중요한 역할을 합니다.

P2. Heavy-tailed degree distribution

Table 2. Properties of node-level decomposed graphs of all datasets. The diameter and clustering coefficient are compared against a null model. Average and standard deviation of 10 random hypergraphs are reported. All node-level decomposed graphs possess a diameter relatively small to the number of nodes. Almost all of them have clustering coefficients significantly higher than that of the null model.

Dataset	# Nodes	Eff. diameter	ㅤ	Clust. coeff.	ㅤ
ㅤ	ㅤ	Real	Null.	Real	Null.
coauth-DBLP	1,924,991	6.8	6.7 ±9e−3	0.60	0.31 ±1e−4
coauth-Geology	1,256,385	7.1	6.8 ±8e−3	0.57	0.42 ±2e−4
coauth-History	1,014,734	11.9	17 ±0.19	0.24	0.26 ±2e−4
DAWN	2,558	2.6	1.85 ±8e−5	0.64	0.30 ±9e−5
email-Eu	998	2.8	1.85 ±7e−5	0.49	0.36 ±5e−4
NDC-classes	1,161	4.6	2.6 ±6e−3	0.61	0.32 ±2e−3
NDC-substances	5,311	3.5	2.5 ±9e−3	0.40	0.17 ±6e−4
tags-ask-ubuntu	3,029	2.4	1.9 ±2e−5	0.61	0.14 ±7e−5
tags-math	1,629	2.1	1.8 ±1e−4	0.63	0.46 ±2e−4
tags-stack-overflow	49,998	2.7	1.9 ±2e−6	0.63	0.03 ±1e−6
threads-ask-ubuntu	125,602	4.7	11.9 ±0.042	0.11	0.19 ±7e−4
threads-math	176,445	3.7	4.9 ±4e−3	0.32	0.12 ±1e−4
threads-stack-overflow	2,675,995	4.5	5.9 ±2e−3	0.18	0.12 ±2e−5

Figure 4. Representative plots for the degree and singular-value distributions of decomposed graphs at 4 decomposition levels. They are heavy-tailed, and specifically on the log-log scale, tails often approximate a straight line.

Table 3. Loglikehood ratio when fitting the degree and singular-value distributions to each of three heavy-tailed distributions versus the exponential distribution. In most cases, there exists at least one positive ratio, implying that both distributions are heavy-tailed. Due to underflow problems, the results for truncated power-law are not available in some cases.

Measure	Degree	ㅤ	ㅤ	Singular values	ㅤ	ㅤ
Heavy-tail distribution	pw	trunpw	lgnorm	pw	trunpw	lgnorm
Node-level decomposed graphs	ㅤ	ㅤ	ㅤ	ㅤ	ㅤ	ㅤ
coauth-DBLP	1108	1108	1108	3.4	3.6	6.4
coauth-Geology	10.77	11.3	11.3	-2.3	-	11.3
coauth-History	429	430	429.9	-1	-0.07	0.3
DAWN	-4.9	-0.5	0.3	16.8	16.8	22
email-Eu	-15.3	-1.3	-1.1	-1.3	-0.14	0.4
NDC-classes	2.17	18.9	14.3	1.2	1.3	1.3
NDC-substances	-8	24.8	20.5	7.5	7.5	11.8
tags-ask-ubuntu	-1.4	6.1	4.9	9.5	9.5	9.5
tags-math	-11.4	0.37	-1.1	9.9	9.9	9.9
tags-stack-overflow	202.8	245.1	241.8	6	6	6.1
threads-ask-ubuntu	2322	2330	2326	2.3	2.3	5.7
threads-math	67574	67751	67725	6.6	6.6	11.4
threads-stack-overflow	2486	2549	2543	2.1	2.1	2.1
Edge-level decomposed graphs	ㅤ	ㅤ	ㅤ	ㅤ	ㅤ	ㅤ
coauth-DBLP	5616	5735	5718	1.3	1.3	4.5
coauth-Geology	122.1	123.3	123.4	122.1	123.3	123.4
DAWN	4025	4389	4303	0.5	0.6	0.5
email-Eu	10.9	11.8	11.5	-1.3	-0.14	0.4
NDC-classes	44.9	44.9	44.9	1.2	1.3	1.3
NDC-substances	10.9	21.8	19.4	10.9	-	0.3
tags-ask-ubuntu	36.1	41.3	39.7	-0.6	0.14	0.05
tags-math	20.4	24	23.6	-1.3	0.01	-0.1
tags-stack-overflow	394268	395917	395852	-1.5	-	-0.15
threads-math	1524	1534	1528	0.44	0.44	3
threads-stack-overflow	4760	4785	4775	-2.6	-0.3	4.3
Triangle-level decomposed graphs	ㅤ	ㅤ	ㅤ	ㅤ	ㅤ	ㅤ
DAWN	1392	1426	1417	3.3	3.3	3.3
email-Eu	6.8	6.9	6.8	-1.2	-0.12	0.4
NDC-substances	0.6	0.6	0.6	-4	-0.5	12.6
tags-ask-ubuntu	378.6	383.2	381	-0.4	0.15	0.3
tags-math	96.4	100.8	99.3	-0.03	0.001	-0.001
tags-stack-overflow	33198	33351	33319	-0.5	0.1	0.1
4clique-level decomposed graphs	ㅤ	ㅤ	ㅤ	ㅤ	ㅤ	ㅤ
DAWN	372.6	377.8	374.4	0.04	0.2	0.2
email-Eu	-2	0.15	-0.19	-0.8	-0.07	0.4
tags-ask-ubuntu	21.5	21.5	25.9	-0.36	-0.04	0.54
tags-math	107.5	107.5	112	-0.06	-	0.13
tags-stack-overflow	31.6	31.6	31.6	31.6	31.6	31.6

The degree of a node is defined as the number of its neighbors. This property means that the degree distribution is heavy-tailed, i.e decaying at a slower rate than the exponential distribution (exp.). This can be partially explained by the “rich gets richer”: high-degree nodes are more likely to form new links (Newman, 2001). Besides visual inspection, we confirm this property by the following two tests:

Lilliefors test (Lilliefors, 1969) is applied at significance level 2.5% with the null hypothesis that the given distribution follows exp.

The likelihood method in (Clauset et al., 2009; Alstott and Bullmore, 2014) is used on the given distribution to compute the likelihood ratio of a heavy-tailed distribution (power-law, truncated power-law or lognormal) against exp. If >0, the given distribution is more similar to a heavy-tailed distribution than exp.

In Fig. 4, we illustrate that for each dataset, at the decomposition level in which there is a giant connected component, the degree distribution is heavy-tailed. Applying the two tests, in all cases, either is rejected or (both claims hold in most cases), indicating evidence for heavy-tailed degree distribution. The loglikelihood ratios are reported in Table 3. Except for email-Eu at the node level, in all cases, at least one heavy-tailed distribution has a positive ratio, implying that the degree distribution is more similar to that distribution than it is to exp.

노드의 차수는 그 노드의 이웃 수로 정의됩니다. 이 속성은 차수 분포가 무거운 꼬리를 가지고 있다는 것을 의미하는데, 즉 지수 분포(exp.)보다 느린 속도로 감소한다는 것입니다. 이 현상은 "부자는 더 부자가 된다"는 현상으로 부분적으로 설명될 수 있습니다: 높은 차수의 노드는 새로운 연결을 형성할 가능성이 더 높습니다. 시각적 검사 외에도, 우리는 다음 두 가지 테스트를 통해 이 속성을 확인합니다:

Lilliefors 검정은 주어진 분포가 지수 분포를 따른다는 귀무 가설 에 대해 2.5%의 유의 수준에서 적용됩니다.

주어진 분포에 대해 무거운 꼬리 분포(파워 로, 절단 파워 로 또는 로그 정규)와 지수 분포에 대한 우도비 을 계산하기 위해 사용되는 우도 방법입니다. 인 경우, 주어진 분포는 지수 분포보다 무거운 꼬리 분포와 더 유사합니다.

각 데이터셋에 대해, 거대 연결 구성요소가 있는 분해 레벨에서 정도 분포가 무거운 꼬리를 가진다는 것을 보여주는 그림을 제시합니다. 두 테스트를 적용한 모든 경우에서 이 기각되거나 인데(대부분의 경우 두 주장이 모두 유지됨), 이는 무거운 꼬리 정도 분포에 대한 증거를 나타냅니다. 로그 우도비는 표에서 보고됩니다. 노드 레벨에서 email-Eu를 제외한 모든 경우에 적어도 하나의 무거운 꼬리 분포가 양의 비율을 가지며, 이는 정도 분포가 지수 분포보다 그 분포와 더 유사함을 의미합니다.

이 설명은 네트워크 내 노드의 정도 분포가 어떻게 특정 패턴을 따르며, 이러한 패턴이 실제 데이터 분석에서 어떻게 확인되는지를 보여줍니다. 무거운 꼬리 분포는 네트워크 내 몇몇 노드가 상당히 많은 연결을 가지고 있음을 나타내며, 이는 네트워크의 중심성과 연결성에 대한 중요한 정보를 제공합니다. Lilliefors 검정과 우도 방법을 사용하는 것은 이러한 분포가 우연이 아니라 네트워크의 근본적인 속성임을 통계적으로 확인하는 데 도움이 됩니다.

P3. Small diameter

Decomposed graphs are usually not completely connected, and it makes diameter subtle to define. We adopt the definition in(Leskovec et al., 2005), where the effective diameter is the minimum distance such that approximately 90% of all connected pairs are reachable by a path of length at most . This property means that the effective diameter in real datasets is relatively small, and most connected pairs can be reachable by a small distance (Watts and Strogatz, 1998). Note that the null model also possesses this characteristic, and comparing real-world datasets and the corresponding null model in this aspect does not yield consistent results. The effective diameters at the 4 decomposition levels are highlighted in Tables 2 and 4.

분해된 그래프들은 보통 완전히 연결되어 있지 않으며, 이는 직경을 정의하기 어렵게 만듭니다. 우리는 Leskovec et al., 2005에서의 정의를 채택하는데, 여기서 유효 직경은 대략 90%의 모든 연결된 쌍이 최대 $d$의 경로 길이로 도달 가능한 최소 거리 $d$입니다. 이 속성은 실제 데이터셋에서 유효 직경이 상대적으로 작고, 대부분의 연결된 쌍이 작은 거리로 도달 가능함을 의미합니다. null 모델 또한 이 특성을 가지고 있으며, 이 측면에서 실제 세계 데이터셋과 해당 null 모델을 비교하는 것은 일관된 결과를 제공하지 않습니다. 4개의 분해 레벨에서의 유효 직경은 표 2와 4에 강조되어 있습니다.

이 설명은 유효 직경이 네트워크 내에서 노드 간의 평균적인 최소 거리를 나타내며, 대부분의 노드 쌍이 상대적으로 짧은 경로로 서로 연결될 수 있음을 나타냅니다. 이는 실제 세계 네트워크의 경우 많은 노드 쌍이 서로 빠르게 도달할 수 있다는 것을 의미하며, 이러한 속성이 네트워크의 효율적인 정보 전달과 밀접하게 관련되어 있음을 시사합니다. 그러나, 실제 데이터와 null 모델 사이의 비교를 통해 얻은 결과가 일관되지 않다는 점은, 실제 네트워크의 구조적 특성이 단순한 무작위성 이상의 복잡한 요인에 의해 결정될 수 있음을 보여줍니다. 이러한 관점에서 네트워크의 구조적 특성을 분석하는 것은 네트워크 이론과 그 응용에 있어 중요한 연구 주제입니다

P4. High clustering coefficient

We make use of the clustering coefficient (Watts and Strogatz, 1998), defined as the average of local clustering coefficients of all nodes. The local clustering coefficient of each node is defined as:

This property means that the statistic in the real datasets is significantly larger than that in the corresponding null models. As communities result in a large number of triangles, this property implies the existence of many communities in the network.

In Table 2, clustering coefficients of the datasets are compared against that of the corresponding null model at the node-level decomposition. From the edge level, the decomposed graph of the null model is almost shattered into small isolated cliques. As a result, the clustering coefficient is unrealistically high, making it no longer valid to compare this statistic to that of the real-world data. Results at the edge or higher-level decompositions are reported in Table 4.

우리는 클러스터링 계수 를 사용하는데, 이는 모든 노드의 로컬 클러스터링 계수의 평균으로 정의됩니다. 각 노드 의 로컬 클러스터링 계수 는 다음과 같이 정의됩니다:

이 속성은 실제 데이터셋에서의 통계가 해당 null 모델에서의 통계보다 현저히 크다는 것을 의미합니다. 커뮤니티가 많은 수의 삼각형을 결과로 하기 때문에, 이 속성은 네트워크 내에 많은 커뮤니티가 존재함을 시사합니다.

표 2에서는 노드 레벨 분해에서 데이터셋의 클러스터링 계수가 해당 null 모델의 클러스터링 계수와 비교됩니다. 에지 레벨에서, null 모델의 분해된 그래프는 거의 작은 격리된 클릭으로 분해됩니다. 결과적으로, 클러스터링 계수는 비현실적으로 높아져, 실제 세계 데이터의 통계와 비교하는 것이 더 이상 유효하지 않습니다. 에지 또는 더 높은 레벨의 분해에서의 결과는 표 4에 보고됩니다.

이 설명은 클러스터링 계수가 네트워크 내에서 노드들 사이의 밀접한 연결 정도를 나타내는 지표로 사용됨을 보여줍니다. 실제 데이터와 null 모델 사이의 비교를 통해 네트워크의 구조적 복잡성과 커뮤니티 형성 경향을 평가할 수 있습니다. 그러나, null 모델의 클러스터링 계수가 현저히 높게 나타나는 경향은 실제 데이터와의 비교 분석을 어렵게 만들며, 이는 연구자들이 네트워크 구조를 이해하고 해석하는 데 주의를 기울여야 함을 시사합니다.

P5. Skewed singular values

This property means the singular-value distribution is usually heavy-tailed, and it is verified in the same manner as the pattern P2. In all cases where a giant connected component is retained, either is rejected or the log likelihood ratio , implying that the singular-value distributions are heavy-tailed. Specifically, as seen in Table3, except for tags-stack-overflow at the edge level, in all cases, at least one heavy-tailed distribution has a positive ratio. Some representative plots for singular-value distributions of real datasets are provided in Fig. 4.

To support the patterns P1-P5, we could provide only some representative results in Tables 2-4, and Fig. 4 due to the space limit. The complete set of figures and numerical data can be found in (app, 2020).

Table 4. Numerical properties of edge or higher-level decomposed graphs of real-world datasets. As the decomposition level increases, fewer datasets retain giant connected components, and the properties of such datasets are reported in the table. In them, small diameters and high clustering coefficients are observed.

Measure	Nodes	Connect.	Eff.	Clust.
ㅤ	ㅤ	Comp.	Diam.	Coeff.
Edge-level decomposed graphs	ㅤ	ㅤ	ㅤ	ㅤ
coauth-DBLP	5,906,196	0.57	18.6	0.93
coauth-Geology	3,175,868	0.50	16.4	0.94
DAWN	72,288	0.98	3.9	0.72
email-Eu	13,499	0.98	5.71	0.81
NDC-classes	2,658	0.62	6.6	0.94
NDC-substances	12,882	0.812	9.4	0.89
tags-ask-ubuntu	126,518	0.98	4.5	0.75
tags-math	88,367	0.99	3.9	0.71
tags-stack-overflow	4,083,464	0.99	3.9	0.78
threads-math	782,102	0.61	7.4	0.94
threads-stack-overflow	15,108,684	0.32	12	0.97
Triangle-level decomposed graphs	ㅤ	ㅤ	ㅤ	ㅤ
DAWN	257,416	0.91	5.3	0.87
email-Eu	24,993	0.86	10.3	0.89
NDC-substances	20,729	0.36	9.4	0.96
tags-ask-ubuntu	248,596	0.79	7.8	0.89
tags-math	222,853	0.91	6.7	0.85
tags-stack-overflow	10,725,751	0.92	6.5	0.88
4clique-level decomposed graphs	ㅤ	ㅤ	ㅤ	ㅤ
DAWN	284,755	0.52	8.1	0.89
email-Eu	24,772	0.41	15.3	0.89
tags-ask-ubuntu	145,676	0.22	17.1	0.74
tags-math	156,129	0.35	14.8	0.71
tags-stack-overflow	7,887,748	0.42	13	0.76

이 속성은 특이값 분포가 보통 무거운 꼬리를 가진다는 것을 의미하며, 이는 패턴 P2와 같은 방식으로 검증됩니다. 거대 연결 구성요소가 유지된 모든 경우에서, 이 기각되거나 로그 우도비 이며, 이는 특이값 분포가 무거운 꼬리를 가진다는 것을 의미합니다. 구체적으로, 표[3]에서 볼 수 있듯이, tags-stack-overflow의 에지 레벨을 제외한 모든 경우에 적어도 하나의 무거운 꼬리 분포가 양의 비율을 가집니다. 실제 데이터셋의 특이값 분포에 대한 몇 가지 대표적인 그림이 그림 [4]에 제공됩니다.

패턴 P1-P5를 지원하기 위해, 우리는 공간 제한으로 인해 표[2]-[4]와 그림[4]에서 일부 대표적인 결과만 제공할 수 있습니다. 그림과 수치 데이터의 전체 세트는 (app, [2020])에서 찾을 수 있습니다.

표 4는 실제 세계 데이터셋의 에지 또는 더 높은 레벨 분해 그래프의 수치적 속성을 보여줍니다. 분해 레벨이 증가함에 따라 거대 연결 구성요소를 유지하는 데이터셋이 줄어들고, 이러한 데이터셋의 속성이 표에 보고됩니다. 이들에서는 작은 직경과 높은 클러스터링 계수가 관찰됩니다.

이 설명은 특이값 분포의 중요성과 그것이 실제 데이터셋에서 어떻게 나타나는지, 그리고 이러한 패턴을 확인하기 위해 사용된 통계적 테스트의 역할을 강조합니다. 또한, 네트워크의 구조적 특성이 레벨에 따라 어떻게 변화하는지를 관찰하는 것은 네트워크 이론과 그 응용에 있어 중요한 의미를 가집니다.

Hypergraph Generators

We have shown that five common properties of real-world pairwise graphs are revealed at different levels of decomposition of real-world hypergraphs. In this section, we present HyperPA, our proposed hypergraph generator model. By analyzing several statistics, we demonstrate that HyperPA can exhibit the known properties at several levels of decomposition. Compared to two baseline models, HyperPA demonstrates a better performance in terms of satisfying the properties at all considered decomposition levels.

[KR]

우리는 실제 세계의 쌍으로 이루어진 그래프들이 가지고 있는 다섯 가지 공통 속성이 실제 세계 하이퍼그래프의 다양한 분해 레벨에서 드러남을 보여주었습니다. 이 섹션에서는 우리가 제안한 하이퍼그래프 생성 모델인 HyperPA를 소개합니다. 여러 통계를 분석함으로써, HyperPA가 여러 분해 레벨에서 알려진 속성들을 나타낼 수 있음을 보여줍니다. 두 가지 기준 모델과 비교했을 때, HyperPA는 고려된 모든 분해 레벨에서 속성들을 만족시키는 면에서 더 나은 성능을 보입니다.

이 내용은 HyperPA가 하이퍼그래프의 구조적 특성과 동적 성장 과정을 모델링할 수 있는 능력을 갖추고 있음을 시사합니다. 실제 세계의 복잡한 네트워크 구조를 이해하고 모방하기 위한 도구로서, HyperPA와 같은 생성 모델의 개발은 네트워크 과학, 사회학, 생물학 등 다양한 분야에서의 응용 가능성을 열어줍니다. 이러한 모델은 실제 데이터에서 관찰되는 특정 패턴이나 현상이 우연에 의한 것인지, 아니면 네트워크의 내재적인 속성에 의한 것인지를 분석하는 데에도 유용하게 사용될 수 있습니다.

HyperPA가 다른 기준 모델과 비교하여 모든 분해 레벨에서 더 나은 성능을 보인다는 점은, 하이퍼그래프의 다양한 구조적 특성을 효과적으로 포착하고 재현할 수 있는 알고리즘의 설계와 구현에 있어 중요한 고려 사항을 제공합니다. 이는 또한 하이퍼그래프 생성 모델의 발전 방향과 연구에 있어 중요한 지표가 될 수 있습니다.

5.1. Intuition behind HyperPA

The main idea behind our HyperPA is to take the subset interactions in decomposed graphs into consideration. Recall that the null-model without such consideration in Sect. 4 is shattered into isolated cliques without a giant connected component once it is decomposed into higher decomposition levels.

Intuitively, in order to reproduce the desired patterns in multi-level decomposed graphs, the generation process should have the following characteristics:

For heavy-tailed degree distribution, “the rich should get richer” (Barabási and Albert, 1999). However, in order to recapture such pattern at higher decomposition levels, groups of nodes should “get rich” together rather than individually.

In order to lead to a high clustering coefficient, communities of correlated nodes should form. As an analogy, in research publications, authors tend to collaborate with those who are on the same field or affiliation, rather than any authors.

However, several pairs of nodes among the communities should also be connected in order for the graph to have a giant connected component and a small effective diameter.

[KR]

HyperPA 모델의 주요 아이디어는 분해된 그래프 내의 부분 집합 상호작용을 고려하는 것입니다. 4절에서 고려되지 않은 null 모델은 더 높은 분해 레벨로 분해되면 거대 연결 구성요소 없이 고립된 클릭으로 분해됩니다.

원하는 패턴을 다중 레벨 분해된 그래프에서 재현하기 위해서, 생성 과정은 다음과 같은 특성을 가져야 합니다:

무거운 꼬리의 정도 분포를 위해, "부자는 더 부자가 되어야 한다"(Barabási and Albert, 1999). 그러나 더 높은 분해 레벨에서 이러한 패턴을 다시 포착하기 위해서는 노드의 그룹이 개별적으로가 아닌 함께 "부유해져야" 합니다.

높은 클러스터링 계수로 이어지기 위해서는, 상관 관계가 있는 노드들의 커뮤니티가 형성되어야 합니다. 비유하자면, 연구 출판물에서 저자들은 임의의 저자들보다는 같은 분야나 소속의 사람들과 협업하는 경향이 있습니다.

그러나 그래프가 거대 연결 구성요소와 작은 유효 직경을 가지려면 커뮤니티 사이의 여러 쌍의 노드도 연결되어야 합니다.

이러한 접근 방식은 네트워크 내에서 관찰되는 복잡한 구조와 패턴을 모델링하는 데 필수적입니다. HyperPA는 노드 간의 상호작용과 그들이 형성하는 커뮤니티의 동적 성장을 고려함으로써 실제 네트워크의 다양한 구조적 특성을 재현할 수 있는 능력을 보여줍니다. 이 모델은 네트워크 과학뿐만 아니라 사회학, 생물학 등 여러 분야에서의 응용 가능성을 가지고 있으며, 실제 데이터를 기반으로 한 네트워크의 구조적 및 동적 특성의 이해를 돕습니다.

5.2.Details of HyperPA

We describe our proposed generator HyperPA, whose pseudocode is provided in Algorithm 1. HyperPA repeatedly introduces a new node to the hypergraph, and forms new hyperedges. When a node is added, HyperPA creates new hyperedges where is sampled from a predetermined distribution . For each new hyperedge introduced by this new node, its size is sampled from a predetermined distribution . When choosing other nodes to fill in this new hyperedge, it takes into consideration all groups containing nodes. Among all such groups, the chance of being chosen for each group is proportional to its degree. The degree of each group is defined as the number of hyperedges containing that group.

HyperPA uses 3 statistics: the number of nodes , the distribution of hyperedge sizes and the distribution of the number of new hyperedges per new node . We obtain them from the real dataset whose patterns HyperPA is trying to reproduce. Regarding , we sort hyperedges according to timestamps, and reassign nodes into new node ids based on this chronological order. We then learn by accounting, for each (new) node id , , where is the number of hyperedges consisting of nodes with ids less than or equal to .

알고리즘 설명

이 알고리즘은 'HyperPA: Hypergraph generator based on Preferential Attachment'라는 이름의 제안된 모델을 설명하고 있습니다. 이는 선호 부착 기반의 하이퍼그래프 생성기로, 주어진 조건에 따라 합성 하이퍼그래프를 생성하는 과정을 나타냅니다. 세부적으로 알고리즘의 각 단계를 설명해보겠습니다.

초기화 단계:

하이퍼그래프 (H)를 초기화합니다. 이때, 최대 하이퍼에지 크기 (\bar{m})의 절반 값에 해당하는 (⌊\bar{m}/2⌋)개의 서로 겹치지 않는 크기 2의 하이퍼에지를 (H)에 추가합니다.

추가된 모든 하이퍼에지의 부분 집합에 대한 degree(차수)를 계산합니다.하이퍼에지

추가 단계:

새로운 하이퍼에지의 수 (n')에 대해 반복합니다.

(n') 개수만큼 반복하여, 각각의 반복에서 새로운 하이퍼에지의 크기 (s)를 하이퍼에지 크기 분포 (P_s)에서 샘플링합니다.
만약 (s=1)이면, 단일 노드로 구성된 하이퍼에지를 (H)에 추가합니다.
그렇지 않고 모든 (s-1) 크기의 그룹이 0 degree를 가지면, (s-1)개의 노드를 무작위로 선택하고, 이 노드들과 새 노드를 포함하는 하이퍼에지를 (H)에 추가합니다.
그 외의 경우에는, degree에 비례하는 확률로 (s-1) 크기의 그룹을 선택하고, 이 그룹과 새 노드를 포함하는 하이퍼에지를 (H)에 추가합니다.

도수 업데이트 단계:

새롭게 형성된 모든 하이퍼에지의 모든 부분 집합의 degree를 1 증가시킵니다.

이 알고리즘은 선호 부착 메커니즘을 기반으로 하여, 노드 간 연결의 확률이 해당 노드의 연결 정도(degree)에 비례하여 증가하는 특성을 가진 합성 하이퍼그래프를 생성합니다. 이러한 방식은 복잡한 네트워크에서 관찰되는 스케일-프리(scale-free) 네트워크의 특성을 모방하는 데 유용합니다.

HyperPA preserves subset interactions, in the sense that most of the times, all of the nodes chosen to fill in a new hyperedge are those from the same previous hyperedge. In order to compare against HyperPA, we examine two baseline models, NaivePA and Subset Sampling, in the following subsections. They exhibit no or weak subset interactions, respectively.

In Algorithm 1, most of the times when >1, lines 12-13 are executed (a proof is given in Appendix C.2), where HyperPA chooses a group of nodes based on its degree. As preferential attachment is conducted in a group-like manner, nodes “get rich” together, and when decomposed, they form communities, leading to a high clustering coefficient. When a new node is introduced, it forms multiple hyperedges. Since these hyperedges involve nodes from different communities, the introduction of a new node can potentially connect several communities, leading to a giant connected component and a small effective diameter.

[KR]

HyperPA는 신규 노드를 하이퍼그래프에 반복적으로 도입하고 새로운 하이퍼에지를 형성하는 생성기 모델입니다. 신규 노드가 추가될 때, HyperPA는 미리 결정된 분포 에서 샘플링된 개의 새로운 하이퍼에지를 생성합니다. 이 새로운 하이퍼에지 각각에 대해, 그 크기 는 미리 결정된 분포 에서 샘플링됩니다. 새로운 하이퍼에지를 채우기 위해 다른 노드를 선택할 때, 노드를 포함하는 모든 그룹을 고려합니다. 그러한 모든 그룹 중에서, 각 그룹이 선택될 확률은 그 그룹의 정도에 비례합니다. 그룹의 정도는 해당 그룹을 포함하는 하이퍼에지의 수로 정의됩니다.

HyperPA는 3가지 통계를 사용합니다: 노드 수 , 하이퍼에지 크기의 분포 및 신규 노드 당 새로운 하이퍼에지 수의 분포 . 이 모델은 실제 데이터셋의 패턴을 재현하려고 시도하는 동안 이러한 통계를 실제 데이터셋에서 얻습니다. 에 관해서는, 하이퍼에지를 타임스탬프 순으로 정렬하고, 이 시간 순서에 기반하여 노드들에 새로운 노드 ID를 재할당합니다. 그런 다음 각 새로운 노드 ID 에 대해, 를 계산함으로써 를 학습합니다, 여기서 는 ID가 이하인 노드로 구성된 하이퍼에지의 수입니다.

알고리즘에서 대부분의 경우 일 때, HyperPA는 그 정도에 기반하여 노드 그룹을 선택합니다. 선호적 연결이 그룹 방식으로 수행됨에 따라, 노드들은 함께 "부유해집니다", 그리고 분해될 때, 그들은 커뮤니티를 형성하여 높은 클러스터링 계수로 이어집니다. 새로운 노드가 도입될 때, 그것은 여러 하이퍼에지를 형성합니다. 이러한 하이퍼에지들은 서로 다른 커뮤니티의 노드들을 포함하기 때문에, 새로운 노드의 도입은 여러 커뮤니티를 연결할 수 있는 잠재력을 가지고 있어, 거대 연결 구성요소와 작은 유효 직경으로 이어질 수 있습니다.

HyperPA는 새로운 하이퍼에지를 채우는 데 있어 대부분 같은 이전 하이퍼에지에서 온 노드들을 선택함으로써 부분 집합 상호작용을 보존합니다. HyperPA와 비교하기 위해, 두 기준 모델인 NaNaivePA 및 Subset Sampling을 검토합니다. 이들은 각각 부분 집합 상호작용을 전혀 보여주지 않거나 약하게 보여줍니다.

이 설명을 통해 HyperPA 모델이 실제 데이터의 패턴을 여러 분해 레벨에서 재현할 수 있는 방법과 그 과정에서 고려해야 할 주요 특성들에 대한 이해를 돕고자 합니다. HyperPA는 '부자는 더 부자가 된다'는 원리를 넘어 그룹 단위에서의 상호작용을 고려하여 더 복잡한 네트워크 구조를 모델링합니다. 이는 실제 네트워크의 다양한 특성, 특히 커뮤니티 형성과 거대 연결 구성요소의 존재 같은 중요한 속성들을 잘 반영할 수 있도록 합니다.

5.3.Baseline models

5.3.1.Baseline preferential attachment for hypergraphs

We consider a naive extension of preferential attachment to hypergraphs. In this model, when filling in each hyperedge of each new node, existing nodes are chosen independently with a chance proportional to their individual degrees (instead of choosing groups of nodes based on degrees of groups). We refer to this model as NaivePA. Its pseudocode is provided in Appendix B.1.

[KR]

5.3.1. 하이퍼그래프를 위한 기본 선호도 첨부

이 모델은 선호도 첨부(preferential attachment)의 단순한 확장을 하이퍼그래프에 적용합니다. 이 모델에서는 새로운 노드의 각 하이퍼에지를 채울 때, 기존 노드들이 그들의 개별 정도에 비례하는 확률로 독립적으로 선택됩니다(그룹의 정도에 기반하여 노드 그룹을 선택하는 대신). 이 모델을 NaivePA라고 합니다. 그 가상 코드는 부록 [B.1]에서 제공됩니다.

5.3.2.Subset Sampling

This model, namely Subset Sampling, is inspired by Correlated Repeated Unions (Benson et al., 2018b), which was introduced to recapture temporal patterns in hyperedges. In Subset Sampling, when a new hyperedge is formed, previous hyperedges are sampled, and then with a certain probability, their elements are chosen independently to fill in the new hyperedge. The pseudocode and details of Subset Sampling can be found in Appendix B.2.

Subset Sampling preserves subset interactions to some degree, as some nodes in the same previous hyperedge can co-appear in the new hyperedge. However, as demonstrated in Table 6, the subset interactions captured by Subset Sampling are often not connected well enough, making decomposed graphs easily shattered into isolated cliques without retaining a giant connected component.

[KR]

5.3.2. 부분 집합 샘플링

이 모델, 즉 Subset Sampling은 하이퍼에지의 시간적 패턴을 재현하기 위해 도입된 Correlated Repeated Unions에 영감을 받았습니다. 부분 집합 샘플링에서는 새로운 하이퍼에지가 형성될 때, 이전 하이퍼에지들이 샘플링되고, 그런 다음 일정 확률로 그 요소들이 독립적으로 선택되어 새 하이퍼에지를 채웁니다. 부분 집합 샘플링의 가상 코드와 세부 사항은 부록 [B.2]에서 찾을 수 있습니다.

부분 집합 샘플링은 어느 정도 부분 집합 상호작용을 보존합니다. 왜냐하면 같은 이전 하이퍼에지의 일부 노드들이 새 하이퍼에지에서 공동으로 나타날 수 있기 때문입니다. 그러나 표 [6]에서 보여지듯이, 부분 집합 샘플링에 의해 포착된 부분 집합 상호작용은 종종 충분히 잘 연결되지 않아, 분해된 그래프가 거대 연결 구성요소를 유지하지 않고 쉽게 고립된 클릭으로 분해됩니다.

이 섹션은 하이퍼그래프의 복잡한 연결 구조를 모델링하기 위한 두 가지 접근 방식을 설명하며, 기본 모델이 어떻게 다양한 분해 레벨에서 하이퍼그래프의 구조적 패턴을 재현하는 데 사용될 수 있는지에 대한 통찰력을 제공합니다.

5.4.Empirical evaluation

We empirically investigate the properties of generated hypergraphs at four levels of decomposition. To facilitate comprehensive evaluation, we consider the following four datasets, which exhibit the 20 patterns most clearly (4 decomposed graphs × 5 patterns) to test the three generators on: DAWN, email-Eu, tags-ask-ubuntu, and tags-math. The generators are evaluated on how well they can reproduce the patterns in the real datasets.

We applied the proposed and baseline hypergraph generators to reproduce the real-world hypergraphs. For each considered real hypergraph, the distribution of the sizes of hyperedges, the distribution of the number of new hyperedges per new node, and the exact number of nodes are directly learned. Note that , and are the control variables exclusive to hypergraphs that are not directly relevant to how groups of nodes interact with each other, and thus they are out of the scope of this research.

In this paper, we make use of these variables learned directly from the real hypergraphs. Thus, for each real dataset, there are 3 corresponding synthetic datasets, generated by HyperPA, Subset Sampling and NaivePA using the statistics , and obtained from the real dataset. Generating hypergraphs without explicitly accounting for these 3 variables is left as a topic for future research.

We measure the statistics from the decomposed graphs of the generated hypergraphs and calculate the scores for the 3 generators:

P1. Giant Conn. Comp.: if the decomposed graph at that level of the generated hypergraph retains a giant connected component (as described in Sect. 4.1), 1 point is given.

P2. Heavy-tailed Degree Dist.: the similarity between the generated degree distribution and the real distribution is measured by the Kolmogorov-Smirnov D-statistic, defined as where are the cumulative degree distributions of the corresponding real and generated decomposed graphs. 1 point is given to the generator having the D-statistic smaller than 0.2.

P3. Small Diameter: we want the generated effective diameter to be close to the real value . As the pattern P3. is ‘small effective diameter’, should not be too large. At the same time, ′ being too small may be the sign of the decomposed graph being shattered without a ‘giant connected component’. We adopt a heuristic of the acceptance range as (, ). If is in the acceptance range, 1 point is given.

P4. High Clustering Coeff.: as the pattern P4. is ‘high clustering coefficient’, it is desirable for the generated clustering coefficient not to be too small compared to the real value . However, being too large may imply that the graph is shattered into isolated cliques. As the clustering coefficient is bounded above by 1, we adopt a heuristic of the acceptance range as (, ). If is in the acceptance range, 1 point is given.

P5. Skewed Singular Val.: similar to P2., the similarity between the singular-value distributions of the real and generated datasets is measured by the Kolmogorov-Smirnov D-statistic. 1 point is given to the generator having the D-statistic smaller than 0.2.

Results of the generators are compared visually in Fig. 2 and numerically in Tables 5 and 6. The total scores from the two tables for HyperPA, NaivePA and Subset Sampling are 64, 49 and 57, respectively. Note that our proposed model, HyperPA achieved the highest score. Without accounting for subset interactions, variables , and are not sufficient to reproduce the patterns, as NaivePA and Subset Sampling fail to do so even when utilizing , and .

[KR]

이 섹션에서는 실제 하이퍼그래프의 분해된 그래프에서 다른 레벨에서 드러나는 다섯 가지 공통 속성을 재현하기 위해 제안된 생성기 모델인 HyperPA를 소개합니다. 이를 위해, DAWN, email-Eu, tags-ask-ubuntu, tags-math와 같이 20가지 패턴(4개의 분해된 그래프 × 5가지 패턴)을 가장 명확하게 보여주는 네 개의 데이터셋을 고려합니다. 생성기는 실제 데이터셋에서의 패턴을 얼마나 잘 재현할 수 있는지에 대해 평가됩니다.

실제 하이퍼그래프를 재현하기 위해 제안된 생성기 및 기준 생성기를 적용했습니다. 각 실제 하이퍼그래프에 대해, 하이퍼에지 크기의 분포 , 신규 노드 당 새로운 하이퍼에지의 수의 분포 , 그리고 노드의 정확한 수 은 직접 학습됩니다. , , 그리고 은 하이퍼그래프에만 고유한 제어 변수로서, 노드 그룹이 서로 어떻게 상호작용하는지와는 직접적으로 관련이 없으며, 따라서 이 연구의 범위를 벗어납니다.

이 연구에서는 실제 하이퍼그래프에서 직접 학습된 이러한 변수들을 사용합니다. 따라서 각 실제 데이터셋에 대해, HyperPA, Subset Sampling 및 NaivePA에 의해 생성된 3개의 상응하는 합성 데이터셋이 있습니다. 이 3개의 변수를 명시적으로 고려하지 않고 하이퍼그래프를 생성하는 것은 향후 연구의 주제로 남겨집니다.

생성된 하이퍼그래프의 분해된 그래프에서 통계를 측정하고 3개의 생성기에 대한 점수를 계산합니다:

P1. 거대 연결 구성요소: 생성된 하이퍼그래프의 해당 레벨에서 분해된 그래프가 거대 연결 구성요소를 유지하면 1점이 주어집니다.

P2. 무거운 꼬리 정도 분포: 생성된 정도 분포와 실제 분포 간의 유사성은 Kolmogorov-Smirnov D-통계량으로 측정되며, D-통계량이 0.2보다 작은 생성기에 1점이 주어집니다.

P3. 작은 직경: 생성된 유효 직경 이 실제 값 에 가까워야 합니다. 가 (, )의 수용 범위에 있으면 1점이 주어집니다.

P4. 높은 클러스터링 계수: 생성된 클러스터링 계수 가 실제 값 에 비해 너무 작지 않아야 합니다. 가 (, )의 수용 범위에 있으면 1점이 주어집니다.

P5. 치우친 단일 값: 실제 및 생성된 데이터셋의 단일 값 분포 간 유사성은 Kolmorov-Smirnov D-통계량으로 측정되며, D-통계량이 0.2보다 작은 생성기에 1점이 주어집니다.

생성기의 결과는 그림[2]에서 시각적으로 비교되며, 표[5]와 표[6]에서 수치적으로 비교됩니다. HyperPA, NaivePA 및 Subset Sampling의 총 점수는 각각 64, 49, 57입니다. 제안된 모델인 HyperPA가 가장 높은 점수를 달성했습니다. 부분 집합 상호작용을 고려하지 않는 한, , , 변수만으로는 실제 패턴을 재현하기 충분하지 않으며, NaivePA와 Subset Sampling은 , , 을 사용함에도 불구하고 이를 실패합니다.

이 요약은 HyperPA 모델이 실제 하이퍼그래프에서 관찰되는 패턴을 여러 분해 레벨에서 어떻게 재현할 수 있는지에 대한 실증적 조사를 설명하고 있습니다. 생성기의 평가는 실제 데이터셋에서 관찰된 패턴을 얼마나 잘 재현할 수 있는지를 기반으로 합니다. 각 실제 하이퍼그래프에 대해 학습된 변수(, , )를 사용하여, 각 실제 데이터셋에 대해 세 가지 상응하는 합성 데이터셋이 생성됩니다. 그리고 이 생성된 하이퍼그래프의 분해된 그래프에서의 통계를 측정하여 3개의 생성기에 대한 점수를 계산합니다.

제안된 모델인 HyperPA는 가장 높은 점수를 달성하여 실제 하이퍼그래프의 패턴을 재현하는 데 있어서 뛰어난 성능을 보였습니다. 이는 HyperPA가 실제 네트워크의 복잡한 구조적 패턴을 모델링하는 데 효과적인 도구임을 시사합니다.

Table 5.D-statistics between the distributions of real and synthetic datasets generated by the 3 models. We generated each dataset 5 times and report the average. 1 point is given for each D-statistic smaller than 0.2 and the total scores are computed at the end. HyperPA achieved the highest score.

Table 6.Graph statistics of real and synthetic datasets at all 4 decomposition levels. The scores for the generators are listed at the end. HyperPA achieved the highest score.

Conclusions

In summary, our contributions in this work are threefold.

Multi-level decomposition: First, we propose the multi-level decomposition as an effective means of investigating hypergraphs. The multi-level decomposition has several benefits: (1) it captures the group interactions within the hypergraph, (2) its graphical representation provides convenience in leveraging existing tools, and (3) it represents the original hypergraph without information loss.

Patterns in real hypergraphs: Then, we present a set of common patterns held in 13 real-world hypergraphs. Specifically, we observe the following structural properties consistently at different decomposition levels (1) giant connected components, (2) heavy-tailed degree distributions, (3) small effective diameters, (4) high clustering coefficients, and (5) skewed singular-value distributions. The connectivity of subset interactions, however, varies among domains of datasets, illustrated by the level of decomposition that shatters the dataset into small connected components.

Realistic hypergraph generator: Lastly, we introduce HyperPA, a hypergraph generator that is simple but capable of reproducing the patterns of real-world hypergraphs across different decomposition levels. By maintaining the connectivity of subset interactions of nodes in the hypergraphs, HyperPA shows better performance in reproducing the patterns than two other baseline models.

Reproducibility: We made the datasets, the code, and the full experimental results available at https://github.com/manhtuando97/KDD-20-Hypergraph.

[KR]

이 작업에서 우리의 기여는 세 가지로 요약됩니다.

다중 레벨 분해: 먼저, 하이퍼그래프를 조사하는 효과적인 수단으로 다중 레벨 분해를 제안합니다. 다중 레벨 분해는 여러 이점을 가집니다: (1) 하이퍼그래프 내의 그룹 상호작용을 포착하고, (2) 그래픽 표현을 통해 기존 도구를 활용하기에 편리함을 제공하며, (3) 정보 손실 없이 원본 하이퍼그래프를 대표합니다.

실제 하이퍼그래프의 패턴: 그 다음으로, 13개 실제 세계 하이퍼그래프에서 유지되는 일련의 공통 패턴을 제시합니다. 구체적으로, 다양한 분해 레벨에서 일관되게 관찰되는 다음 구조적 속성들을 관찰합니다: (1) 거대 연결 구성요소, (2) 무거운 꼬리의 정도 분포, (3) 작은 유효 직경, (4) 높은 클러스터링 계수, 그리고 (5) 치우친 단일값 분포. 그러나, 부분 집합 상호작용의 연결성은 데이터셋의 도메인에 따라 다르며, 데이터셋을 작은 연결된 구성요소로 분해하는 분해 레벨로 나타냅니다.

현실적인 하이퍼그래프 생성기: 마지막으로, 다양한 분해 레벨에서 실제 세계 하이퍼그래프의 패턴을 재현할 수 있는 단순하지만 효과적인 하이퍼그래프 생성기인 HyperPA를 소개합니다. 하이퍼그래프에서 노드의 부분 집합 상호작용의 연결성을 유지함으로써, HyperPA는 다른 두 기준 모델보다 패턴을 재현하는 성능이 더 우수합니다.

재현 가능성: 데이터셋, 코드 및 전체 실험 결과를 https://github.com/manhtuando97/KDD-20-Hypergraph에서 이용할 수 있도록 제공했습니다.

이 요약은 하이퍼그래프 연구에 대한 실질적인 기여와 그 응용의 가능성을 강조하며, 연구 커뮤니티에 이를 재현하고 확장할 수 있는 기회를 제공합니다.