はじめに
本記事では、一般的なグラフ理論の基本的なことについて理解を前提に、ハイパーグラフ(Hypergraph)について解説します。
一般的なグラフ理論については、@drkenさんの記事などを参照すると良いです。
今回、通常のグラフとハイパーグラフを明示的に呼び分けるために、前者を一般グラフ、後者をハイパーグラフと呼び分けることにします。
ハイパーグラフ
ハイパーグラフとは、グラフ理論にて扱われる一般グラフを一般化(拡張)したものです。一般グラフではエッジは2つの頂点を接続しますが、ハイパーグラフではエッジが任意個の頂点を含む(接続する)ことができます。
ハイパーグラフ$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のハイパーグラフとなります。
一様なハイパーグラフ
一般グラフのエッジは2要素からなるノードの部分集合であることに対してハイパーグラフは任意の大きさの部分集合となります。しかしながら、研究においてハイパーエッジが持つノード数(サイズ・濃度)が同し数であることが望ましいことがよくあります。
このようなハイパーグラフを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です。このようなハイパーグラフを2正則ハイパーグラフと呼びます。
二部グラフモデル
ハイパーグラフは、ノード集合とハイパーエッジ集合から成る一般二部グラフ(Bipartite graph)として表すこともできます。
例として、先程のハイパーグラフを考えたとき、
ハイパーエッジとそのハイパーエッジが含むノード間にエッジを接続することにより以下のような一般二部グラフができます。
また，このようにハイパーグラフを二部グラフモデルに変換することを「スター展開」(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$となります。つまり、接続行列の1列目は
\begin{bmatrix}
1 \\
1 \\
1 \\
0 \\
0 \\
0 \\
0
\end{bmatrix}
となります。同様に$e_2$についても考えると、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)…ハイパーエッジを持たないハイパーグラフ
ハイパーグラフの応用
ハイパーグラフはデータモデルや正則化として広く使用されています。代表的な学習手法として、スペクトラルグラフ理論をハイパーグラフラプラシアンで拡張するハイパーグラフラプラシアンクラスタリングなどがあります。
その他にも、ゲーム理論や最適化などに応用されているようです。
終わりに
今回、ハイパーグラフの基礎的な概念や用語について書かせていただきました。
ハイパーグラフに関する日本語サイトが全然ないので、もっと増えてくれると嬉しいなと思っています…(私は英語がろくに読めないので)