「ほっ」と。キャンペーン

書評 - 「複雑ネットワーク」とは何か

『「複雑ネットワーク」とは何か』 増田直樹、今野紀雄著 講談社ブルーバックス を読んだ。

複雑ネットワーク(complex networks) についての優れた入門書だ。ネットで書評を検索しても大体同じ意見のようだ。前半でスモールワールドやスケールフリーネットーワークの理論的な解説がされている。明快な文章で、数式がなくても複雑ネットワークの特徴を解析するときのアイディアが直感的に分かるように書いてある。後半はスモールワールドやスケールフリーを現実の伝染病や通信ネットワークやニューロンやたんぱく質のネットワークに適用した応用例が解説してある。

コンピュータネットワークや、人間関係のネットワークなどを抽象化していくと、結局は頂点と枝を結んだ網の目になってしまう。その網の目も頂点の位置や枝の長さには本質的な意味はなく、頂点と頂点が結ばれているかどうかだけが問題になる。したがって、空間的な頂点の位置は勝手に変更しても網の目であるグラフの意味は変わらない。つまり、どんなネットワークでも、グラフの性質を変えずに頂点を全てひとつの円の上に並べてしまうことができる。

このように、ネットワークの頂点をひとつの円の上に並べてしまうことによって、グラフの一般的な性質を数学的に扱うことができる。別に円に固執する必要はないのだが、円に並べることで視覚的に直感的な理解ができる。

そうすると、複雑ネットワークの性質の指標として、2頂点間の距離、頂点のクラスタ性、頂点の次数などを考えることができる。

2頂点間の距離とは、ある頂点とある頂点が最少何本の枝を介して結合しているかということだ、枝の長さにはまったく考慮が払われない。また、クラスターとは3つの頂点が枝で結ばれて三角形をなしていることを言う。これは枝で結ばれたどの二つの頂点もそれ以外の頂点と結ばれていることを示し、内輪のつながりが強いことを示している。複雑ネットワークのうちクラスターが多く存在するものをクラスター性が高いという。クラスター係数は個々のネットワークの全ての頂点で作成可能な三角形の数を分母として、実際にそのネットワークに現れた三角形の数を割ったもので1から0までの値をとる。このクラスター係数を、ネットのクラスター性の指標とすることができる。

このクラスター性が適度に高く、かつ、2頂点間の平均距離が小さいものをスモールワールドと呼ぶ。このスモールワールドが現実のネットワークの性質に当てはまることが多いので、最近マーケティングなどでよく取りざたされている。実際、俳優が映画で共演したという関係で俳優のネットワークを調べると、最大6の距離(最小の繋がり)で全ての俳優と俳優が関係付けられてしまう。これは、クラスター主体のネットワークにわずかなショートカットの枝ができるだけで2頂点間の平均距離が激減するためだ。スモールワールドの平均距離が意外に小さいという性質を考えてみると、ブログなどの口コミ情報の伝播が思ったよりも速く広いことに説明がつく。

スモールワールドの頂点から出る枝の数を次数というが、この次数の分布についてそれが、ベキ分布であると考えたものがスケールフリーネットワークだ。スケールフリーとは統計的な平均や分散などが計測できない分布のことを言う。このようなスケールフリーの複雑ネットワークは、頂点の数が増殖していく場合にみられる。その際、次数の多い頂点には新しい枝ができやすく、次数の少ない頂点には枝がつきにくいと仮定したものがスケールフリーネットワークだ。実際の例としては、ホームページへのリンクを考えるとよい、人気の高いホームページには次々にリンクが増えていくが、不人気なホームページにはいつまでもリンクがつかない。

スケールフリーネットワークの一番の特徴は非常にたくさんの枝がつながるハブという頂点が出現することだ。コンピュータネットワークもスケールフリーネットワークだ。したがって、コンピュータネットワークが、ランダムに攻撃を受けてもあまり被害はないが、ハブを集中的に攻撃されると非常な混乱が起きる。伝染病の感染が広がる場合も似た性質があり、スーパースプレッダーというとくに広い範囲に病原体を感染させる個人がいることがある。

このように、ネットワークの性質を、スモールワールドやスケールフリーネットワークと考えることでその特徴を把握し、対策をとることができるのだ。たとえば伝染病の防疫の場合、ある人をランダムに取り出して免疫し、その友人を選んで免疫するというやり方でやがてハブとなる個人を免疫することができるようになる。この方法はリング接種とよばれ、実際に行われている。

通信や人間関係や伝染病の経路などさまざまなネットワークを頂点と枝のネットワークとして抽象化して把握することによっていろいろ面白いことが分かってきているようだ。
[PR]
by tnomura9 | 2007-03-30 22:59 | 話のネタ | Comments(3)
Commented by tnomura9 at 2007-04-29 14:43
トラックバックありがとうございました。記事を読ませていただきました。点と点のつながりという抽象的なネットワークが、広く応用されているのに驚きます。いろいろな分野で思考のツールとして使われているのを知り勉強になりました。
Commented by 通りすがり at 2008-07-14 13:50 x
こんにちは。ネットワークの研究開発をしている者で、最近はたまたま「スケールフリーネットワーク」について調査をしています。

第8段落に「次数の分布についてそれが、指数分布であると考えたものがスケールフリーネットワーク」とありますが、「指数分布」ではなく「ベキ分布」の間違いかと思われます。

以上、宜しくお願い致します。
Commented by tnomura9 at 2008-07-14 18:36
通りすがりさん、コメントありがとうございました。
指数分布ではなくベキ分布(Power law - Wikipedia)でした。修正します。
<< 歳をとると 書評 - 記憶と情動の脳科学 >>