소개

본 기사에서는, 일반적인 그래프 이론의 기본적인 것에 대해 이해를 전제로, 하이퍼그래프(Hypergraph)에 대해 해설합니다.
일반적인 그래프 이론에 대해서는 @ drken 님의 기사 등을 참조하면 됩니다.
이번에 일반 그래프와 하이퍼그래프를 명시적으로 부르기 위해 전자를 일반 그래프, 후자를 하이퍼그래프라고 부르기로 하겠습니다.

하이퍼그래프

하이퍼그래프란 그래프 이론에서 다루어지는 일반 그래프를 일반화(확장)한 것입니다. 일반 그래프에서 가장자리는 두 개의 정점을 연결하지만 하이퍼그래프에서는 가장자리에 임의의 정점을 포함(연결)할 수 있습니다.
하이퍼그래프 $H$는 정점 집합 $X$와 하이퍼 엣지(Hyperedge)라고 불리는 비어 있지 않은 $X$의 부분 집합 $E$를 사용하여 $H=(X, E)$로 나타냅니다. 일반적인 그래프와 달리 그림이 어려우므로 집합론 용어로 나타날 수 있습니다.
또, 노드 집합의 크기를 「하이퍼그래프의 위수」(order of the hypergraph), 엣지 집합의 크기를 「하이퍼그래프의 크기」(size of the hypergraph)라고 부릅니다.

구체적인 예

예를 들어, 다음과 같은 하이퍼그래프를 생각해 봅시다.
(이미지는 wikipedia에서 참조) 그런데, 하이퍼그래프 $H$는 노드 집합 $E$와 하이퍼 에지 집합 $E$를 이용해 $H=(X, E)$로 표현되는 것이었다. 이때 노드 집합 $X$는 $X=\{v_1, v_2, v_3, v_4, v_5, v_6, v_7\}$로 표현할 수 있습니다. 다음으로 하이퍼 엣지에 주목합니다. 예를 들어, 그림에서 녹색으로 둘러싸인 $e_3$에 주목해 봅시다. $e_3$는 노드 $v_3, v_5, v_6$를 포함합니다. 즉 $e_3=\{v_3, v_5, v_6\}$입니다. 이 때, 확실히 $e_3$는 $X$의 부분 집합이 되어 있는 것을 알 수 있습니다. 마찬가지로 다른 하이퍼 에지도 $X$의 부분 집합이라는 것을 알 수 있습니다. 이 하이퍼 그래프는 노드 수가 7이고 하이퍼 에지 수가 4이기 때문에, 위수 7에서 크기 4의 하이퍼 그래프가 됩니다. 균일한 하이퍼그래프 일반 그래프의 가장자리는 두 요소로 구성된 노드의 서브 세트이지만 하이퍼 그래프는 임의의 크기의 서브 세트입니다. 그러나, 연구에 있어서 하이퍼 엣지가 가지는 노드수(사이즈·농도)가 같은 수인 것이 바람직하다. 이러한 하이퍼그래프를 k 균일한 하이퍼그래프 또는 k 하이퍼그래프라고 합니다. k는 하이퍼 에지의 크기를 포함합니다. 즉, 일반 그래프는 2 균일 하이퍼 그래프라고도 할 수 있습니다. 예를 들어,
는 일반 그래프이지만,

와 같이 생각하면 하이퍼 에지의 크기가 2인 하이퍼그래프라고 생각할 수 있으며, 2 균일 하이퍼그래프라고도 할 수 있습니다.

(앞으로도 보기 흉한 필기의 그래프가 몇 장인가 나와 있습니다만 용서해 주세요 )

단순 하이퍼그래프(Simple Hypergraph)

일반 그래프와 마찬가지로 루프가 없고 다중 변이 없는 그래프를 말합니다.

$e_1$는 사이즈가 1의 하이퍼 엣지(루프)로, $e_2$와 $e_3$는 모두 $\{v_2, v_3, v_4\}$를 나타내므로 이중변(다중변)이 됩니다. 이들과 같은 하이퍼 에지를 포함하는 하이퍼 그래프는 단순 하이퍼 그래프가 아닙니다.
반대로 이러한 하이퍼 에지를 허용하는 그래프를 비단순 하이퍼그래프(Non-simple hypergraph)나 다중 하이퍼그래프(Multi hypergraph)라고 합니다.

d정칙 하이퍼그래프(d-regular hypergraph)

모든 노드의 차수가 $d$인 하이퍼그래프입니다.

이미지의 하이퍼그래프는 $\{v_1, v_2, ..., v_7\}$ 모두가 두 개의 하이퍼 에지에 포함됩니다. 즉 모든 노드의 차수가 2입니다. 이러한 하이퍼그래프를 2정규 하이퍼그래프라고 합니다.

이중 그래프 모델

하이퍼그래프는 노드 집합과 하이퍼 에지 집합으로 구성된 일반 이중 그래프(Bipartite graph)로 나타낼 수도 있습니다.
예를 들어, 이전의 하이퍼그래프를 생각할 때,
하이퍼 엣지와 그 하이퍼 엣지가 포함한 노드간에 엣지를 접속하는 것으로써 이하와 같은 일반 2부 그래프를 할 수 있습니다.

이와 같이 하이퍼 그래프를 2 부 그래프 모델로 변환하는 것을 스타 전개 (Star expantion)라고합니다.

연결 행렬

노드 집합 $V$를 $V=\{v_1, v_2, ..., v_n\}$, 하이퍼 에지 집합 $E$를 $E=\{e_1, e_2, ..., e_m\}$ 그러면 하이퍼그래프는 $n\times m$의 연결 행렬 $A=(a_{ij})$로 나타낼 수 있습니다. $a_{ij}$는

a_{ij} = \left\{
\begin{array}{ll}
1 & if\ v_i \in e_j  \\
0 & else
\end{array}
\right.

로 표시됩니다.
방금 전의 하이퍼 그래프로 실제로 생각해 봅시다.
우선 $e_1$에 주목합니다. $e_1$는 $v_1, v_2, v_3$를 포함합니다. 즉, $j=1$일 때 $i=1, 2, 3$는 $1$, 그 이외의 i는 $0$입니다. 즉, 연결 행렬의 첫 번째 열은 \begin{bmatrix} 1 \\ 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} 됩니다. 마찬가지로 $ e_2 $에 대해 생각하면 두 번째 열 \begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} 되는 것을 알 수 있습니다. 이것을 $e_4$까지 반복하면 연결 행렬을 알 수 있습니다. A = \begin{bmatrix} 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 0\\ 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix} 또한 하이퍼그래프 연결 행렬의 쌍은 $A$의 전치 $A^t$입니다. 기타 용어 빈 하이퍼 그래프 (Empty hypergraph) ... 하이퍼 에지가없는 하이퍼 그래프 하이퍼그래프 응용 하이퍼그래프는 데이터 모델 및 정규화로 널리 사용됩니다. 대표적인 학습 기법으로는 스펙트럼 그래프 이론을 하이퍼그래프 라플라시안으로 확장하는 하이퍼그래프 라플라시안 클러스터링 등이 있습니다. 그 밖에도 게임 이론이나 최적화 등에 응용되고 있는 것 같습니다. 끝에 이번에 하이퍼그래프의 기초적인 개념과 용어에 대해 썼습니다. 하이퍼 그래프에 관한 일본어 사이트가 전혀 없기 때문에, 더 늘려 주면 기쁘다고 생각합니다… 참고 Wikipedia 하이퍼그래프
Wikipedia 하이퍼그래프