日本の中心はどの県だ？グラフ理論（ネットワーク）の基本的な諸概念

Ｑ：これは何の構造を表しているでしょう？

グラフ理論

上の構造のように、頂点（ノードともいいます）の集まりと、２つの頂点をつなぐ辺（エッジともいいます）の集まりでできたもののことを「グラフ」あるいは「ネットワーク」と呼び*1、このような構造を研究する分野こそが「グラフ理論（Graph theory）」です。今回はそんなグラフを使うと、身近なものの新たな側面が見えてくる話。

（余談ですが「グラフ」という用語は、数学だと関数のグラフとか円グラフみたいなやつもあって検索精度が悪いです。グラフ理論に関してわからないことがあった場合に「グラフ　○○」や「グラフ理論　○○」とググるよりも、「ネットワーク　○○」とググったほうが得たい情報にリーチしやすいというライフハックが知られています）

さて、冒頭のグラフです。グラフ理論の知識なんかひとつもなくても、このグラフから読み取れることはいくつもあります。例えば「右上と左にしっぽみたいなのがあるな」とか、「基本的に三角形ばっかで構成されてるけど四角形が二箇所だけあるな」とか、「ひとつの頂点から伸びてる辺は８本が最大だな」とか、「辺が交差するところはないんだな」とか、「右下あたりに上下対称な構造があるな」とか。

読み取れるだけ読み取ったところで、なんの構造だかお分かりいただけたでしょうか。正解はこちらです。どん。

「日本地図」までならわかった方も多いかもしれません。ていうか記事タイトルでなんか言ってるしね。より十分な解答は「陸で接する都道府県どうしを繋いだもの」でした。ご自身のお住まいの都道府県でご確認ください。頂点が「都道府県」を、辺が「県境」を表しているわけです。

ここでは「陸で接する」を「陸路で渡れる」と定義しているため、人工物でしか繋がっていない「北海道〜青森」「千葉〜神奈川」「兵庫〜徳島」「山口〜福岡」間にも辺があることにご留意ください。それぞれ青函トンネル、東京湾アクアライン、大鳴門橋、関門トンネルです（ほんとのほんとに余談ですが、「岡山〜香川」「広島〜愛媛」は実は陸で接している部分があります。瀬戸内海の小島上に県境があるのです）。

このグラフは実際の県の位置は関係なく、「どのように繋がっているか」という情報だけを抜き出したものといえます。この「どのように繋がっているか」にいろいろな考察を与えることのできる道具が、グラフ理論だというわけです。

自治体隣接グラフ

さて、答えがわかってみると、さっき読み取っておいた要素にも意味を与えることができそうです。つまり「右上と左にしっぽみたいなのがある」のはそれぞれ一県としか接していない北海道と長崎のことだし、「ひとつの頂点から伸びてる辺は８本が最大」は日本でもっとも多い８県と接する長野県のことだったわけです。頂点から伸びる辺の本数のことは「次数（Degree）」といい、「このグラフの最大次数は８」という言い方をすることができます。

「右下あたりに上下対称な構造がある」のはグラフ化してはじめて見えたことですね。実際に県境がどういう形をしているかは置いといて、繋がり方だけを抜き出して考えているためシンプルになり、逆に構造が見えやすくなっている部分もあるというわけです。関東平野の県境には実は対称な構造があったと。

「辺が交差するところはない」ようなグラフは「平面グラフ（Plane graph）」と呼ばれます。浮遊大陸や地底王国でもない限り、地図上の隣接関係をグラフ化したものは必ず平面グラフになります。

逆に以下のようなグラフはどうあがいても（頂点をどう移動させても）平面グラフにはなりえないことが知られています。

しかしこれらのグラフは一本でも辺を取り除くと平面グラフになるので、気になった人は辺が交差しないような頂点の配置の仕方を考えてみるとよいでしょう。

「基本的に三角形ばっかで構成されてるけど四角形が２箇所だけある」のも興味深いですね。上のグラフのように地図上の陸での隣接関係をグラフ化したとき、四角形が出現する理由は２つあって、一つは「４県の間に水域がある場合」と「４県が一点で接する場合」です。瀬戸内海に表れている四角形は前者に該当します。

実はアメリカを見てみるとこれが両方ともあるんですね。それぞれミシガン湖とフォー・コーナーズであり、フォー・コーナーズではユタ、コロラド、ニューメキシコ、アリゾナが一点で接しています。

ここまでほとんど数学使ってないのに、「都道府県の隣接の構造」をグラフ化しただけでいろいろと面白い事実が判明したわけですが、せっかくなのでもう少し数学の力も借りながら見ていくことにしましょう。

グラフの半径、直径、中心、周辺

実はグラフには「半径」「直径」「中心」「周辺」など、まるで円みたいな諸概念があります。そう！　これさえあれば「日本の中心」が！　そしてゆくゆくは「世界の中心」が求められるのですよ！　助けてください！　誰か！

中心を定義するためにまずは「離心数（Eccentricity）」というものを考えます。もう一度日本地図グラフを載せておきますので適宜確認しながらお読みください。

例として石川県のことを考えます。一度県境を通過することを「一歩」と呼ぶことにすると、石川県からお隣の富山県までは一歩、東京都までは最短で４歩でたどり着くことができます（ちなみに北陸新幹線はこの定義だと６歩かけて東京まで行っています）。そして、石川県から、長崎県や北海道など他のすべての頂点に対してそれぞれ何歩でたどり着けるかを考えたとき、その中でもっとも大きい歩数が「（石川県の）離心数」です。つまりその頂点における「最大歩数」ってことですね。

例えば石川県の場合だと、長崎県、鹿児島県、宮崎県までたどり着くのに最短で９歩かかり、他の県まではそれより短い歩数で行けるので、石川県の離心数は「９」ということになります。頂点ごとに決定される値なのですね。これが神奈川県だとその離心数は11、福岡県だと13になってます。

本当は、沖縄のように辺が繋がっておらず、どこへもたどり着けない頂点がグラフ内に存在する場合は、すべての頂点の離心数は無限大になってしまいます。

これはなぜかと言えば、まずどの頂点から考えても、その頂点から沖縄までの最短歩数は無限大と定義されます。０ではなく。もし０と定義したとすると「沖縄まで０歩で行ける」ことになり、めっちゃ行きやすいことになってしまいます。「無限大」と定義してあるのは「沖縄まで陸路で行くには無限歩かかる（つまり、行けない）」みたいなノリなのですね。

で、離心数とは最大歩数のものを取るわけだったので、他が何歩だろうと無限大が最大になってしまうというわけです。そのためここから先は申し訳ないですが、「※一部地域を除く」でやらせていただきますのでご了承ください。

沖縄以外の都道府県の離心数（最大歩数）を表にしてみました。

この中で、もっとも大きい値のことをそのグラフの「直径（Diameter）」、もっとも小さい値を「半径（Radius）」、そして、もっとも大きい離心数をもつ頂点の集合のことを「周辺（Periphery）」、もっとも小さい離心数をもつ頂点の集合のことを「中心（Center）」と呼びます。

この中だと離心数として一番大きいのは北海道、長崎、宮崎、鹿児島がもつ「15」ですね。「日本の直径は15」なわけです。日本の直径は15。ふむ。

そしてこの15という離心数を持つ頂点の集合、すなわち北海道、長崎、宮崎、鹿児島の４道県が「周辺」です。周辺だけあって確かに国防の要の４県だなって感じがします。

半径は福井、滋賀、三重、京都、奈良、和歌山の６府県がもつ「８」です。日本の半径は８。

そしてここにおいてついに日本の中心が判明しましたね！　これらの６府県こそが、実は日本の中心だったというわけなんです。いいなあ。福井中心かよ。福井県民の人「どうも日本の中心から来ました」って言えるじゃん。いいなあ。

それにしても、たしかに直径は直径っぽいし、中心は中心っぽい概念なのでうまい名付け方だなと思います。

実は、ただ単に「うまい名付け方」というだけではなく、これはもう直径は直径だし中心は中心そのものじゃねーかと思える配置の仕方があります。それがこちら。

つまり「『同じ離心数を持つ頂点』が『同じ円上に乗る』ような、同心円上に配置した」わけですね。これを見ればもう確かに直径は直径、中心は中心と呼ぶしかないなって感じです。

東京23区でもやってみました。

中央の円に乗っている頂点の離心数は３、一番外側は５なので、この図からは例えば「港区、千代田区からはどこの区へも３歩以内で行ける」とか、「どこの区からどこの区へも５歩以内で行ける」とかこれまた興味深いことを読み取ることができます。正しい境目が表示された地図からはこれらのことを読み取るのは大変なので、グラフというものの効果、便利さがここに現れています。

例えば以下の地図を使って世田谷から葛飾まで5歩でたどり着く経路を見つけるのはけっこう手間です。

画像はwikipediaより

グラフばんざい。

中心性尺度（次数中心性、媒介中心性、近接中心性）

日本の中心が見つかってよかったね満足満足、てことでこの記事を終えてもいいのですが、やっぱり「日本の中心が６コもある」ってのが気になりませんか？　気になるんです。せっかくなら唯一つの中心を見つけたい。というわけで導入されるのが（いや別にもともとそんな理由で導入されたわけではないですが*2）「中心性尺度（Centrality）」です。

あるネットワークにおいてどのノード（頂点）が一番重要か？を測るのが中心性尺度と言えます。その「重要さ」にもいろいろ考えられるため、それに応じて中心性尺度にもいろいろな種類があります。

次数中心性

まずは「次数中心性（Degree centrality）」。とは言ってもこれ実はすでに出てきた概念で、これは単に次数のことです。つまり次数の値が次数中心性の値そのものであると。そのため、もっとも次数中心性が高いのは８の次数をもつ長野ということが言えます。

長野県だと場所的にだいたい日本の中心っぽい気もするのでいいのですが、定義としては例えば北海道に大量に自治体が隣接していた場合、そこが中心になります。たしかにそうなれば重要なノードではあるかもしれないけど、日本全体の中心かと言われると微妙です。

媒介中心性

次は「媒介中心性（Betweenness centrality）」。実際の計算は省略しますが、これは「グラフ内のすべての頂点から他のすべての頂点への最短経路を考えたとき、より多くの最短経路に含まれている頂点が高くなる」ような中心性です。

日本でこれが一番高くなるのは兵庫です。グラフを見れば分かる通り、中国地方以西から近畿地方以東へ行こうとするとき、必ず兵庫県を通らなくてはいけなくなっています。当然、多くの最短経路の中に含まれていることになります。

これは人間関係に置き換えると、多くの話は必ず一度兵庫県さんを通しておかないと伝えられない、兵庫県さんがいなくなっちゃうと組織が分断されちゃう、というようなことになるわけで、確かに重要度という意味では高いといえると思います。実際にネットワーク分析でよく使われているのもこの「媒介中心性」です。

逆にこれが低いのは「周辺」に属する４道県、それに加えて高知県も低くなっています。ていうか０です。高知県以外のどこかからどこかへ向かう最短経路で高知県を通るものは０。なんだか切ない。

近接中心性

今回、ここで採用したいのは「近接中心性（Closeness centrality）」です。これは「ある頂点から残りのすべての頂点への最短歩数の合計が小さければ小さいほど高くなる」ような中心性です。

例えば鳥取スタートだとすると、北海道までは10、青森は9、秋田は8...とすべての都道府県についてこれらを足していくことをするわけです。これが小さい、とは何を意味するかお分かりいただけるでしょうか。

つまり「どこの頂点へも（からも）少ない歩数でたどり着ける」ような頂点が高くなるってことですね。まさに中心というものをよく表していると思います。

具体的には「（歩数の合計が）小さいほど（中心性は）大きく」なるような指標にしなければならないので「最短歩数の合計の、逆数*3」がこの近接中心性となります。

実際に東京、大阪、京都で最短歩数の合計を計算してみると、東京は252、大阪はちょうど200、京都は176、ということで、京都に軍配が上がりました。

とはいえ京都はさっきの６つの中心県にも含まれていたので新鮮な驚きはありません。では日本で一番この近接中心性が高いのは一体どの県なのか！　こちらです！　ババーン！

 

三 重 県
（画像:Wikipedia）

おめでとうございます。三重県は日本の中心です。三重県の最短歩数の合計は173。これが175である２位の岐阜をちょっとだけひきはなしての勝利でした。

「日本の中心」というとだいたい人口重心とかで、それは長野だったり岐阜だったりにあるんですが、「三重が中心」というのはなかなか聞いたことがない気がします。これを期にお伊勢参りでもしてみようかな。

 

あれ……？　まてよ……？　「お伊勢参り」……？　

今よりずっと移動の便が悪かった江戸時代に、伊勢神宮に全国各地から参拝者が集結することができたのは、この近接中心性の高さが理由だったのかもしれません。

おわりに

世の中にグラフ構造で表現できるものはたくさんあります。人間関係もそうですし、しりとりみたいな言葉どうしの関係なんかもグラフで表せたりします。そんなグラフに出くわしたときに楽しくお使いいただける道具をいくつかご紹介してみました。もちろん、グラフ理論の道具はこれだけではありません。もっといろいろあります。ていうか中心性だけをとってもまだまだあります。それはすなわちまだまだいろいろ遊びがいがあるということなので、興味が沸いた方はそのへん調べてみると楽しいと思います。

それでは今回はこのへんで！　ええじゃないかええじゃないか！

Follow @motcho_tw

世界の中心で、愛をさけぶ スタンダード・エディション [DVD]

世界の中心で愛を叫んだけもの (ハヤカワ文庫 SF エ 4-1)

グラフ理論入門

*1:「グラフ」と「ネットワーク」、同じような使われ方をしていますが、ソーシャルネットワークやインフルエンザの伝播経路などの具体的な対象を表すときは「ネットワーク」、それらをモデル化した抽象的な対象に対しては「グラフ」を使うことが多いです

*2:もともとはソーシャルネットワーク分析のためのものらしいです

*3:もっと言うと、これに「頂点数-1」をかけたものが近接中心性であり、これは別々のグラフでも比べられるような指標にするためです