スモールワールド

連携講座の関係で、NTTコミュニケーション科学基礎研究所の山田武士先生がNAISTで講演をされていたので見に行った。
スモールワールドネットワークの話から始まって、スケールフリーネットワークGoogleページランクアルゴリズムの原理などの話。最後はネットワークの可視化の話まで行ったがちょっと詰め込みすぎな気がした。


スモールワールドの話では、知り合いを大体6人くらい辿れば全世界の人達と繋がれるという話から始まった。
友達は大抵自分の近所の人で、自分の友達が別の友達の友達だったりする(共通の友達を持つ;クラスタがある)可能性が高い。
にも関わらず少ないステップ数で遠くの人とも繋がれるというのは、近所の人達と繋がりやすい一方で、ある確率で遠くの人とも繋がるからだという。


ニューロンの発火の連鎖は少ないステップで遠くのニューロンまで及ぶというのは良く聞く話だ。
よく考えたら神経回路網も樹状突起で近所のニューロンと接続し、軸索を通して遠くのニューロンと接続しているのでスモールワールドを形成するはず。
スモールワールドはクラスタを形成しやすいから脳の機能局在が起こり、スモールワールドのネットワークはsparseになるからsparse graph codeとの関連が出てくるのかー。
神経科学や符号理論を理解するのにネットワーク科学が使えるというのはなかなか面白いと思った。

スモールワールドネットワークで新聞記事の検索を高速化する話もあったが、こういうネットワークだとloopy belief propagationのような確率伝搬アルゴリズムも高速化されるのだろうか。