Webとマーケティング　授業資料（８）

グラフというモデルについて

様々な繋がりを表現するモデル、グラフについて考えてみましょう。

オイラーとケーニヒスベルグの橋

ソーシャルグラフは、コミュニティなど様々な人の結びつきを、抽象化して記述したものです。

元々グラフとは、数学の世界で、「繋がっているもの」を抽象化してモデルとするために生み出された考え方で、その起源は18世紀にまで遡ります。
1736年に、スイスの数学者、レオンハルト・オイラー(Leonhard Euler)によって、通称「ケーニヒスベルグの橋渡り」と呼ばれる問題を例として、明らかにされました。

プロイセン王国の首都ケーニヒスベルグ（現カリーニングラード・Königsberg）という街には、プレーゲル川という大きな川が流れており、川の中州にあるクナイプホッフ島に向けて、七つの橋が掛けられていた。それらの橋を2度通らずに、全て渡って元の場所に帰ってくることができるか。

これが「ケーニヒスベルクの橋渡り」として知られている、元々の問題設定です。

図に示すのは、当時のケーニヒスベルグの地図です。これを見ると、川と橋の関係と、問題設定がより具体的に理解できるでしょう。
そもそも「地図」とは、元々の地形をそのまま表現したものではなく、実際の地形を一定の規則に基づいて表現したものです。

同じ場所をGoogle Map（http://maps.google.co.jp）の航空写真で見た、現在の様子が次の図です。そこでは、川の流れや橋だけではなく、街にある建物や緑地帯など、様々なものを見ることができます。

しかし地図からはそうした現実にある細々としたものは省略されているため、その街の道路や地形などを把握するという目的に適ったものとなっています。地図のように、何らかの目的のために、物事を抽象化して表現したものを、「モデル」と呼ぶわけです。

この地図からクナイプホッフ島の部分を切り取り①、ここから、橋と川だけに焦点を当て、さらに陸の広さや形、橋の具体的な位置などを抽象化して行くと、陸の部分を頂点とし橋を辺とする、より抽象化した図②になります。

このように、地図をより抽象化して行くと、実際のケーニヒスベルグの街の様子からは離れて行きます。しかし逆に、問題そのものはより理解しやすくなるはずです。

オイラーはこの問題に対して、さらに陸の広さや形、橋の具体的な位置などを抽象化して、⓷のように、陸の部分を頂点とし橋を辺とする、より抽象化した図を作りました。

繋がりのあるモノを、点と線によってできた図形に抽象化して考えるこうしたモデルを「グラフ（Graph）」と呼び、点の部分を「ノード（node）」、辺を「アーク（arc）」と呼びます。

この点を結ぶ辺が、一筆書き可能ならば、橋をすべてわたる道が存在するということとなります。元々の地図と比べると、グラフの表現の抽象度の高さがわかるでしょう。
一見すると①と③が同じものを表現しているようには思えませんが、この問題だけを考える場合には、明らかに③に示されたモデルの方が有効と言えます。

ただし、図のままではコンピュータで処理をできないため、行列を用いてグラフを表現することもあります。ケーニヒスベルグの橋で考えると、陸を示す点は4つありますが、それぞれを順番にA～Dで示すと、陸相互を結んでいる橋の数を、④の表のように示すことができます。

各点の交点の数字は、橋の数を示しています。例えばA列B行は、ノードAとBを結ぶアークの数であり、B列A行とは同じ橋を示しています。
またA列A行は、同じ陸に帰って来る橋ですが、この問題には存在していなません。図③と表④は、同じグラフを示しています。
このようにして表現された行列は、図式表現されたグラフよりも、計算などの処理が行いやすいので、コンピュータではしばしば使われます。

この抽象度の高いグラフを使うことで、橋の姿だけではなく、何かが繋がっている状態を表現できるということが重要です。
例えば関係や構造といった言葉で表現されている様々な現象は、基本的に何らかの繋がりを含んでいると言っていいでしょう。
通信ネットワークはもちろんのこと、人間関係や企業活動、人々の購買行動など社会的事象だけでなく、遺伝子の構造や伝染病の拡散など生物学的な事象や、言葉の語彙の繋がりなど、様々な「繋がり」のある事象に対して、グラフに基づいたモデルを使って、問題を考察することができます。

こうした手法を「ネットワーク分析(Network Analysis)」と呼び、実際に、社会学や経済学、経営学、人類学、歴史学、心理学、さらには医学や言語学など、様々な分野で用いられています。
特に社会的な関係により結びつけられた個人や組織からなる社会的な構造を「社会的ネットワーク（Social Network）」と呼び、そこでは、グラフのことを「ソシオグラム(Sociogram)」と呼んでいます。

このように、繋がりのあるものをグラフとして表現すると、数学的に処理することが容易になり、そのネットワークの特徴を明らかにすることができます。
グラフは点と線から構成されますが、点は何らかの存在や実態を表し、線は点の間の何らかの結びつきや繋がりを意味します。
点を「ノード（Node）」と呼びますが、「ポイント（Point）」や「頂点（Vertex）」という呼び方もあります。
さらに線のうち、方向性を持たないものを「辺(Edge)」と呼び、辺で構成されるグラフを無向グラフと呼びます。また、矢印のように方向性を持つものを「弧(Arc)」と呼び、弧で構成されるグラフを有向グラフと呼びます。
線を、特に社会ネットワークの分野では、「紐帯（Tie）」と呼びます。
紐帯、読めますか？

人のグラフとその特徴

ソーシャルグラフは、このグラフモデルを使って、特に人々の様々な社会的繋がり関係を表現したものです。
そこでは個々の人がノード（点）となり、人々の間の繋がりがアーク（線）として表現されます。そして、その線に従って情報が伝わっていくものと考えます。

一般にソーシャルグラフは、無向グラフで表現されるが、有向グラフを使えば、情報の流れや知り合い関係などが表現できます。
ソーシャルメディアで言えば、Twitterは一方的にアークを貼ることができるが、FacebookやMixiでは、関係を成立させるために承認が必要であり、そこでは有向グラフが双方向に貼られる構造を取ります。

ソーシャルグラフとは、基本的にそれだけのものでしかありません。
しかしそれによって、表現され理解できるものは、とてつもなく大きいのです。

この写真は、Google maps中からの引用ですが、前述のケーニヒスベルグの街にあるプレーゲル川の岸から、中州にあるクナイプホッフ島とそこにかかる橋のうちのひとつの、現在の様子を写したものです。このように、陸地のある地点からみると、そこから繋がっている所しか見えません。
例えばこの島の反対側の様子や、他にいくつの橋が島のどこに繋がっているのかなどは、全くわかりません。
つまり一つのノードからは、そこから直接繋がっている他のノードしか見えません。
人間の関係でも、基本的には自らの知り合いしか把握できません。
しかし、ソーシャルグラフとして表現すると、その人間の関係を、あたかも地図のように、俯瞰して見ることができるのです。

では、ソーシャルグラフでは、何が明らかになるのでしょうか。人間の関係は、どういうものなのでしょうか。次に続きます。