[カテゴリー別保管庫] ネットワークの科学(small-world, scale-free)

2004年07月21日

■ はてなアンテナのリンクはスケールフリーネットワークだった。

pooneil2004-07-21 ガヤ、サンクス。なるほど、scale-free（3/17,3/31,4/6にて言及あり）の話でしたねこれは。というわけで7/20の図1を確率密度分布に変換して(各月の総リンク数で縦軸を割る)、縦軸横軸を両方ともlogスケールにしたものが今日の図3の左です。横軸はあるサイトがアンテナに登録されている数k、縦軸は被リンク数kのサイトの全サイトに占める割合P(k)です*1。7月分重ねてありますがどれも同じ傾向ですので色分けしておりません。きれいな直線的関係(power law)を示しているのがわかります。

ここで解説を。WWWのようなネットワークの個々の頂点vertexが他のvertexと何個繋がっているか(k)の確率密度分布(P(k))は以下のようなpower lawによって説明できることがわかっています。 

P(k) ~ k-γ
log10(P(k)) = log10(k) - γ
 (実際にはintersectの項が入るが、WWWでは0になるらしい)

参考文献：Science '99 "Emergence of Scaling in Random Networks."

なお、このpower lawはネットワークが(1)元からあるネットワークに新しい結合が付加されてゆく、(2)新しい結合はランダムに付加されるのではなくて、よりkの大きいところにより多く新しい結合ができる("rich-get-richer phenomenon")、という二つの性質を持っているときに成り立ち、ランダムな結合では成り立ちません。ですので、ryasudaさん、リンクの分布がpoisson-likeであると書いたのは私の早とちりでした。全員がランダムにリンクしたらポワソン分布になるのはその通りだと思います。実際にpoisson分布だったらどんなプロットになるか作ってみたのが図の右側です*2。縦軸横軸は左図と同じです。実際のはてなアンテナのデータではλ=3(kの期待値=2.8より)ですので、それでプロットしたのが赤い線、λを10.^(-10:0.1:1)でふってみたのが青線です。どのようなλであれ、poisson分布の時にはk>100であるような頂点はほとんどありえません（P(k=100) < 10^(-100)）。k>100のようなサイトは"rich-get-richer phenomenon"によって形成されるのであって、偶然にはほとんど作りえないということがわかります*3。この二つの対比(左のpower lawと右のpoisson分布)こそがはてなアンテナの被リンク数が上記の(1)(2)の性質を持っていることの証拠となるでしょう。

左の図に戻ります。1月から7月までのそれぞれの月のデータはほとんど同じパターンを作っており、これはガヤが指摘するようなscale-freeであることの証拠といえるのかもしれません。また、各月のデータでlinear regressionして得たslopeからこのネットワークのγを推定することができますが、intersect=0の条件(横軸縦軸ともに10^0を通る)の元で、2.10±0.02 (mean±SD)となります。これは上記のScience '99でのWWWの例でのγが2.1±0.1であるのと劇的な一致を示します。実のところ、はてなアンテナの被リンク数とは、WWWのリンク数のような双方向的なものではなくて、はてなダイアリーを使ってないけどはてなアンテナだけは使っているという人もいるのにもかかわらず。自分で計算しておいて驚いてみたり。

*1：k=0のデータは除外して計算しております。

*2：ネットワークでは結合のない頂点はないものと見なされますので、結合数k=0のものは除いて、1<=k<∞でΣP(k)=1となるようにnormalizeし直してあります。

*3：なお、Watts and StrogatzのNature '98でのsmall-world networkはlocalに繋がったランダムなネットワークの結合のある一定の割合を遠い場所につなぎ直したものですので、この場合P(k)の分布はランダム結合の場合と同じであり、scale-free power lawは成り立たない、ということがScience '99に書かれています。Scale-freeとsmall-worldは似ているようで微妙に違ったものであるようです。

コメントする (4)
# ガヤ

いま実験の待ち時間中。いや、これまたやってくれますね。しかもきれいな図になりました。K=1を見ていなかったので、もしかしたらSingle-Scaleになるかと思いましたが見事です。ところで、あまり詳しく覚えていませんが、上記のScience論文では“rich-get-richer”の部分で、Linearモデルを使っていた（つまりK=100はK=1よりも100倍の「客寄せ効果」がある、といういう単比例で計算していた）と思うのですが、この仮定がおそらく「正しくない」だろうということは、今回の図でもプロットが末広がりになっている（しかも、Kが大きいほど予想される直線よりも右方向にバラけている）ことから想像できます。つまり、K=100はK=1よりも100倍以上は魅力的なサイトだってことですね。この方が我々の直感に合っているかと思うわけです。

# ryasuda

なるほど、面白いですね。Journal citationとかも似たような感じなのかな。

# ガヤ

ryasudaさん、さすが鋭いですね。PNAS 97(2000)11149-11152には「the network of citations of scientific papers are scale-freethat is, they have a distribution of connectivities that decays with a power law tail」という記述がありますよ。

# pooneil

なるほど、「予想される直線よりも右方向にバラけている」、これ面白いですね。まず、この辺の値の全体に占める割合は非常に小さいため(< 10^(-4))、どうしてもバラけるのは本当でしょうね。で、ガヤの言う通りに線形性がないとするとプロットは右曲がりになるというわけですね。ちょっと誤差が大きすぎて本当かどうかわからないけれど、その右方向にバラけているやつはじつは主にid:hatenadiary、つまり<A HREF=”http://d.hatena.ne.jp/hatenadiary/”>「はてなスタッフのはてなダイアリーに関する記述」</A>なのです。よってそのような特殊かつ中心的なステータスにあるサイト(しかもネットワーク形成の一番最初からあったっぽい)がネットワークの中でどんな動態を示すのか、というふうに捉えられるのかもしれません。ほかにもScale-freeの例として俳優の共演ネットワークがScience ’99には挙げられていました。これはsmall worldの方でも挙げられている例です。そうなると、俳優の共演ネットワークはscale-freeなのか、small-worldなのか、それとも両立しうるのか。Scale-freeになるような(1)と(2)の性質を持って自己組織化したネットワークはsmall-worldなのか、というあたりに興味が出てきます。どっかですでに扱われているのでしょうけど。

2004年04月06日

■ Trends in Neurosciences

"Interneuron Diversity series: Circuit complexity and axon wiring economy of cortical interneurons."
György Buzsáki @ The State University of New Jersey。
shima’sLog 4/5より。
ちょうどSmall-world and scale-free networkについてメモしてたらGyörgy Buzsákiだ。運命かも（ちがう（<-それもう使った））。
Buzsákiのinterneuronがoscillaitionを作っているという話はこれまでも言われているもののはず。要はそれがSmall-worldであることの特性によってより経済的に実現されていることにあるらしい。話はInterneuronについてに絞られてるようだ。Small-worldとしての脳の私のイメージはarea内でのintrinsicなconnection(interneuronによるもの及びhorizontal connectionによるもの)がネットワーク内でclusterしているのをprojecting neuronによるarea間pronjectionがshort cutしている、というものなのだけれど、どうだろう？

2004年03月31日

■ Gouldさんの日記3/30から。

Gouldさんの日記3/30から。
(4/2アップデート)
ネットワークの形の研究が開く未来
で、それをつたってのスモールワールドとスケールフリーの基本論文およびWWW関連論文。
Nature '98 "Collective dynamics of 'small-world' networks"
Science '99 "Emergence of Scaling in Random Networks."
Nature '99 "Diameter of the World-Wide Web."
Science '00 "Power-Law Distribution of the World Wide Web."
PNAS '02 "Winners don't take all: Characterizing the competition for links on the web."
PNAS '02 "Growing and navigating the small world Web by local content."
Science '02 "Network Motifs: Simple Building Blocks of Complex Networks."
Science '03 "An Experimental Study of Search in Global Social Networks."
ほかにもニューロンのネットワークモデルでsmall-worldを使っている例:
"Fast Response and Temporal Coherent Oscillations in Small-World Networks."(PHYSICAL REVIEW LETTERS '00)
"Stability of a neural network model with small-world connections."(PHYSICAL REVIEW E '03)
"Harmony in the small-world."(Physica A '00)
"Self-sustained activity in a small-world network of excitable neurons."(?)
ほかにもゲノム関連やweb関連などはいろいろあるようだ。では神経ネットワークはどうか、ということになるのだが、これはどうだろう。近くへ投射するニューロンと、近くと遠くへ分枝を送るニューロンと、遠くへのみ分枝を送るニューロンとが多分あって、その結合は完全にランダムなわけでもなければ、完全に整然としているわけでもない。ただしこのことがNNがsmall worldであることを必ずしも保証しないわけだが。日本では理研("認知動力学研究チーム")がやってるらしい。


「カオス的な性質を持った発振器により構成されたネットワークは，その構造が組織化される過程において，スケールフリーとスモールワールドという2 つの特性を獲得することについてはすでに報告している。……また将来大脳皮質の構造を調べる際にこれらの知見を活用することも念頭に置いている。」

追記：上記のBarabasiの著書"Linked" の要約を発見。大脳中のニューロンでは（たぶん平均）14シナプスで任意のニューロンとつながっているそうだ。けっこう遠い。これのreferenceはなんだろうか。(線虫で2.6なのはもとのNature '98にあり。)

コメントする (2)
# ガヤ

ここら辺の話は実は大好きです（バレバレっすね）。「友達の友達が友達だった」系の話でしたら、ちょっと分野が異なりますが Science 298(2002)824-827も文献に混ぜてやってください。
あ、そうだ。上のリストには重要論文の一つ Nature 393(1998)440-442 が抜けてますのでこれも加えてしてくださいね。

# pooneil

サンクス。Nature’98はもちろん基本論文で、3/17にreferしといたので省略してたんだけど、せっかくなんでreferenceリストとして役に立つように追加しておきました。Science’02の方は今回調べてるときにどっかでタイトルだけ見ました。なるほど、ガヤの研究に関係ありそうかも。こっちも追加しときました。

2004年03月17日

■ ノイズ

「適度なノイズによって何かが最適化される状態」、ぐらいまで一般化して考えるといろいろあるだろうと思う。それはまさにbolzmanネットだし、たぶん化学の何らかの現象でも見られることだろう。不純物がないと結晶化が始まらない……ほんとのところはこれはどういう現象だったんだろう。
というのも、なんかのついでに昔読んだこれ（Collective dynamics of 'small-world' networks）を見つけたんだけれど、これも整然としたネットワークでもなく、完全にランダムなネットワークでのなくて、その中間で"it's a small world phenomenon"が見られる、という話だったからで。
これを"middle way"とまで言ったらさすがに危ない人か。

お勧めエントリ

  • 細胞外電極はなにを見ているか(1) 20080727 (2) リニューアル版 20081107
  • 総説 長期記憶の脳内メカニズム 20100909
  • 駒場講義2013 「意識の科学的研究 - 盲視を起点に」20130626
  • 駒場講義2012レジメ 意識と注意の脳内メカニズム(1) 注意 20121010 (2) 意識 20121011
  • 視覚、注意、言語で3*2の背側、腹側経路説 20140119
  • 脳科学辞典の項目書いた 「盲視」 20130407
  • 脳科学辞典の項目書いた 「気づき」 20130228
  • 脳科学辞典の項目書いた 「サリエンシー」 20121224
  • 脳科学辞典の項目書いた 「マイクロサッケード」 20121227
  • 盲視でおこる「なにかあるかんじ」 20110126
  • DKL色空間についてまとめ 20090113
  • 科学基礎論学会 秋の研究例会 ワークショップ「意識の神経科学と神経現象学」レジメ 20131102
  • ギャラガー＆ザハヴィ『現象学的な心』合評会レジメ 20130628
  • Marrのrepresentationとprocessをベイトソン流に解釈する (1) 20100317 (2) 20100317
  • 半側空間無視と同名半盲とは区別できるか？(1) 20080220 (2) 半側空間無視の原因部位は？ 20080221
  • MarrのVisionの最初と最後だけを読む 20071213

月別過去ログ

[2024]
2|
1|
[2023]
12|
11|
10|
9|
8|
7|
6|
5|
4|
3|
2|
1|
[2022]
12|
11|
10|
9|
8|
7|
6|
5|
4|
3|
2|
1|
[2021]
12|
11|
10|
9|
8|
7|
6|
5|
4|
3|
2|
1|
[2020]
12|
11|
10|
9|
8|
7|
6|
5|
4|
3|
2|
1|
[2019]
12|
11|
10|
9|
8|
7|
6|
5|
4|
3|
2|
1|
[2018]
12|
11|
10|
9|
8|
7|
6|
5|
4|
3|
2|
1|
[2017]
12|
11|
10|
9|
8|
7|
6|
5|
4|
3|
2|
1|
[2016]
12|
11|
10|
9|
8|
7|
6|
5|
4|
3|
2|
1|
[2015]
12|
11|
10|
9|
8|
7|
6|
5|
4|
3|
2|
1|
[2014]
12|
11|
10|
9|
8|
7|
6|
5|
4|
3|
2|
1|
[2013]
12|
11|
10|
9|
8|
7|
6|
5|
4|
3|
2|
1|
[2012]
12|
11|
10|
9|
8|
7|
6|
5|
4|
3|
2|
1|
[2011]
12|
11|
10|
9|
8|
7|
6|
5|
4|
3|
2|
1|
[2010]
12|
11|
10|
9|
8|
7|
6|
5|
4|
3|
2|
1|
[2009]
12|
11|
10|
9|
8|
7|
6|
5|
4|
3|
2|
1|
[2008]
12|
11|
10|
9|
8|
7|
6|
5|
4|
3|
2|
1|
[2007]
12|
11|
10|
9|
8|
7|
6|
5|
4|
3|
2|
1|
[2006]
12|
11|
10|
9|
8|
7|
6|
5|
4|
3|
2|
1|
[2005]
12|
11|
10|
9|
8|
7|
6|
5|
4|
3|
2|
1|
[2004]
12|
11|
10|
9|
8|
7|
6|
5|
4|
3|
2|
1|
[2003]
12|
11|
8|
7|
[2001]
10|
8|
6|
5|
4|
2|
[2000]
12|
9|
8|
7|
6|
3|
2|
1|
[1999]
9|
8|
7|