ネットワークトポロジーに潜む位相空間
情報を学んだ事のある人間であれば、ネットワークトポロジーという言葉を聞いた事があるだろう。これは、ネットワーク上でサーバやスイッチ等がどのように接続されているかを示す用語である。
また、トポロジーというのは数学の位相を意味するということは、数学を深く学んでいない人でも何となく聞いた事があるだろう。
そこで思ったのだが、ネットワークトポロジーと言うからには、そこに何らかの位相空間があるはずである。しかし、いろいろ調べてみても、どうにも情報界隈でキチッと決められた位相構造の定義は無いように思われる。そもそも情報、特にネットワークを専門とする人で、位相空間をしっかり学んだことがある人は少ないような気がするし、この状況はある意味当然なのかもしれない。ただ単に、ネットワーク上でのノードの繋がり方が何となく位相空間っぽいと思った人が名付けたのかもしれない。
以上を鑑みて、ここ最近ネットワークの中にはどのような位相構造があるのかを数学的視点から真面目に考えていたのだが、考えがまとまってきたので記事にしてみたいと思う。*1
まず、ここで扱うネットワークとはどのようなものか定義する。ネットワークとは、有限なn個( )のノードを持ち、ノードの間がエッジで接続されているものであるとする。任意の2つのノードを直接つなぐエッジはあっても良いしなくても良い。また、任意の2つのエッジは、ノード以外の点で共有点を持たないこととする。1つのエッジが大きくよじれて、自分自身とクロスすることもないとする。さらに、ここでは純粋にノード間の繋がり方のみに注目したいので、全てのエッジの長さは1とする。これにより、ネットワークは距離空間となる。これはよくある議論で、ノード間のホップ数を距離とするのである。(この距離の考え方は後で拡張する。)
次に、数学における位相空間の定義に触れたいと思う。位相空間とは、ざっくり言うと「集合に対して開集合となる部分集合を定義することで作られる空間」である。開集合を定義するというのは、慣れないとちょっと不思議に思うかもしれない。ユークリッド空間では距離の概念があったから、開集合は自然に定義された。しかし、位相空間の考え方は、距離の定義されていない一般の集合に対して、逆にどのような部分集合が開集合であるかを決めてやることで、距離空間と似たような議論ができるようにするというものである。つまり、開集合さえ決まれば位相構造が決まると言っても過言ではない。
そこで、以下の2点を解決すれば、ネットワークの位相構造を決めることができる。
- ネットワークはどのような集合で表現できるか？
- ネットワークを表す集合において、どのような部分集合が開集合になるか？
まずパッと思いつくのは、i番目のノードをaiとした時、とするものである。このようにネットワークを離散的に捉えるのはよくある手法であるが、この場合、エッジはどのように表現されるのだろうか？
最初に考えたのは、開集合の決め方によってノード間の接続を表現する方法である。位相空間における開集合は、点の近傍を表していると捉えることができるので、ある点に接続されている全ての点とその点自体から成る集合を開集合とするのである。
一見するとこれは良さそうに見えるのだが、開集合の公理から、開集合同士の共通部分、および和集合も開集合になるため、ほとんどのケースでXは離散位相空間になってしまう。これでは全ての点がバラバラになってしまい、ネットワーク内の連結が表現できない。
調べてみると、エッジをノードと同じように集合の要素として扱うことを考えた人もいるようである。しかし、自分には長さを持つエッジをノードと同一視しているのがどうにも気持ち悪く、納得できなかった（追記2を参照）。興味のある方は以下を参照して頂きたい。
グラフ構造で位相空間のイメージをつかむ - Qiita
次に考えたのが、ネットワークをエッジも含めて3次元ユークリッド空間内に埋め込む方法である。ネットワークとは実際の空間にあるモノ同士の接続なのだから、3次元ユークリッド空間内にノードを表す点、及びエッジを表現する、点の間をつなぐ曲線を配置することができる。エッジの長さが全て1という制約はあるが、エッジは好きにたわませれば良いので、ノード数が有限であればこのような集合を構成することは可能である。
では、ここにどのような開集合系を定義することができるだろうか？ここで定義した集合はユークリッド空間の部分集合なので、私は最初次の定理を利用することができると考えた。
位相空間Aが集合Bを部分集合として含むとする。Aの任意の開集合Uに対して、
はBの開集合となる。
一度はこれで決着かと思われたが、実はこの開集合系にはまだネットワークを表現するには不自然な点がある。例えば、以下のようにエッジがたわんだネットワークを考えよう。
ここで、点のε近傍
を考えると、これは開集合である。そのため、UかつXは開集合である。しかし、そうなると以下の図の赤色で示す部分がXのε近傍となる。
ノード間の距離はエッジに沿って考えるのが自然なので、上のような集合がε近傍となるのは不自然である。
次に考えたのが、ノードを表すある点からエッジを表す曲線に沿って長さε未満の部分をε近傍とする方法である。以下に例を示す。
ここで再び開集合の公理より、開集合同士の交わりは再び開集合になるので、ノードの真ん中にポツンと開集合ができてしまう。
ここではこのような開集合も受け入れることとする。
また、(あまり意味はないが)位相空間足り得るためには、エッジの途中の点の近傍というものも考える必要がある。例えば、点と
を繋ぐエッジにおいて、
から距離d(d<ε)だけ離れた点を取ると、ここでのε近傍は以下のようになる。
また、もともとはノード間でしか距離は考えていなかったが、近傍を考えるためにはエッジの途中の点の間にも距離が生まれるが、これも認めることにする。
ここで考えたようなε近傍が本当に開集合かどうかを調べるのは簡単である。ネットワークの集合をXとすると、ε近傍として決めた曲線Vを薄く包み込むような3次元ユークリッド空間上の開集合Uを考えれば、（追記1を参照）。は先ほど述べた定理により開集合である
さて、先ほどからやたらとε近傍にこだわっていたわけだが、ε近傍だけが開集合ではない。しかし、距離空間において、ε近傍を全て集めたものは開基と呼ばれ、これらの和集合を全て集めたものを加えてやれば、それが開集合系を成すことが知られている。その意味で、ε近傍だけを定義すればほとんど開集合系を定めたことになる。
以上により、ひとまずネットワークを表現する集合、及びその開集合系を定めることができた。
さて、ここからは私の自己満足である。上で定義したネットワークの位相構造は、エッジがグニャグニャと(ある程度自由に)曲がることができて、どうにも汚い印象がある。例えるなら、整理されていないサーバラックの裏側を覗いたような残念な気持ちになるのである。これをもう少し"綺麗に"配線することは出来ないだろうか？
最も綺麗な配線は、全てのエッジを真っ直ぐな線分にすることである。しかし、全てのエッジの長さが1であるという制約を考えると、ノードの数が増えた場合にこれは実現不可能である。もしノード数が3つなら正三角形の、4つなら正四面体の各頂点にノードを配置することで実現できるのだが・・・
そこで考えた。次元を上げたらどうなるか？今、2次元空間では3つの点、3次元空間では4つの点を、互いに長さ1の線分で繋ぐことができるのだから、n次元空間ではn+1個の点を長さ1の線分で繋げられるのではないか？
調べてみたら、この予想はなんと正しいことがわかった。詳細な説明は以下のリンクを参照して欲しいが、ようはn次元空間での超正多面体を考えるのである。そして、その中でも全ての頂点が互いに辺で結ばれるような超正多面体はnがいくつであっても存在する。
http://eprints3.math.sci.hokudai.ac.jp/364/4/jin0804.pdf
具体的な形についても述べておく。n+1次元空間において、というn+1個の点を互いに結ぶことで、n次元の部分集合が得られる。これこそが上で述べたn次元の超正多面体となる。
この超多面体の頂点にノードを配置することで、全てのエッジを長さ1の線分として表し、かつノードも対称な形で配置できる。
さて、これで理想的なネットワークの位相構造を手に入れたのであるが、ここでやりたいことは、3次元ユークリッド空間上の汚いネットワークを、この綺麗なネットワークに対応付けることである。そうすれば、3次元ユークリッド空間上の全てのネットワークに対して標準形のようなものを与えることができる。
この対応を探すことは、まさに両者の間の位相同型写像を探すことに他ならない。位相同型写像とは、連続な全単射であり、かつ逆写像も連続であるような写像のことである。証明は省くが、何次元の空間であろうと点は点(0次元)であり、線は線(1次元)なのだから、両者が位相同型であることはほとんど明らかであろう。
以上、ネットワークトポロジーを3次元ユークリッド空間上に埋め込む形で定義し、かつその標準形を高次元のユークリッド空間上に与えた。数学を学んだことで、情報の世界で長年謎だった問題が解決され、数学を学ぶモチベーションがさらに高まった。これからも数学に強いエンジニアを目指し、日々数学を学んでいきたい。
追記1
ネットワーク集合自体はユークリッド空間に埋め込まれているとは言え、この集合上で考える距離はもはや通常の意味での距離とは異なるため、近傍もユークリッド空間とは違うものになる。そのため、ユークリッド空間の開集合との共通部分だということを利用して開集合であることを主張するのは誤りだと気づいた。素直にノード上をたどった長さを距離として、それを用いて開集合を決めるのが自然であろう。
追記2
本稿を書いてからずっと悩んでいたが、やはり離散的な構造であるグラフを連続的な空間に埋め込むというのは、なんとも美しくないような気がしてきた。悔しいが、リンクを貼った先の記事で紹介されているような位相の入れ方がよいのかもしれない。ただし、やるならとことん抽象的にやるべきである。すなわち、ノードとエッジはどちらも本質的には区別のない点であると捉え、ノードに対応する点の近傍にはそれとつながるエッジを含め、エッジに対応する点の近傍はそのエッジのみから成る集合であるとする。そうして、ノードだのエッジだのの区別がなくなった点に対して、今度は逆に開集合として自分自身だけが含まれるようなものが存在する点はエッジであり、そうでない点はノードであると考えるのである。紹介した記事とほとんど同じことを言っているようだが、ノードとエッジを本質的に区別するのは位相構造のみであるという立場を強く強調しておきたい。
*1:本記事に記載している内容は私が自力で考えて導き出したものであり、これが必ずしも正解とは限らない。そういう考え方もあるのだと思って頂ければ幸いである。
