P2Pネットワークのグラフ化に成功 108
ストーリー by yoosee
情報の気脈 部門より
情報の気脈 部門より
Anonymous Coward曰く、"Internet Watchによると、ネットコンサルティング会社の株式会社ネットアークが、WinnyなどのP2Pファイル交換による「P2Pファイル交換ネットワーク」を解析し、全容をグラフ化することに成功したそうだ（ニュースリリース）。
おもしろそうだったので見てみたら、案の定、粘菌というか胞子というか血管というか神経というか、木の枝というか川の流れというか、そんな感じのマンデルブロー集合的なグラフになっていて、ちょっとほほえましいかんじさえした。生命とはよくしたものである（感嘆）"
座標軸は? (スコア:2, 興味深い)
物理的な距離ではないだろうし、やっぱりIPアドレス?
あちこちに無用な線の交差とかがあって、わざとごちゃごちゃさせてるようにも見受けられるんですよねぇ。
あと、トラフィックに応じて線の色とか太さとか変えないと「グラフ化」というには弱いような。
つーか、各々のP2Pソフトの解説を読む限りでは、WinMXなら今回のグラフのようになるかもしれませんが、Winnyではこういう形ではなくてメッシュ状になるような気がするんですよねぇ。
学術的に答えてみた（笑） (スコア:5, 参考になる)
＞物理的な距離ではないだろうし、やっぱりIPアドレス?
ネットワークのグラフ化というのはかなり研究されている分野なのですが、自然界に
存在するネットワークというのはすべてこの例のような形のグラフになることが知ら
れています。
これらのグラフはBarabasiらによって名付けられた"scale-free"な特徴を持
っており、scale-free networkと呼ばれています。つまり、グラフの構造は物
理的な距離には依存せず、各ノードが持っている辺の数（の分布）にだけ依存する
という法則があり、その辺の数の分布はk^(-b)の形のグラフになっています。（こ
こでkは辺の数、bは各ネットワークに特徴的なパラメタだが、ほとんどのネットワー
クが2から3の間に収まる）
例えば、航空便のネットワークであるとか、WWWのリンクであるとか、HIVを広げ
たsexualなネットワークであるとか、遺伝子間の相互作用とか、俳優間の共演関
係だとか、枚挙に暇がありません。
この性質から言えることは、ほとんどのノードは辺を１つしか持っていなくて、kが
大きくなるほどその数の辺を持つノードの数は等比級数的に少なくなっていくので
すが、それは逆に、古典的なモデルで説明されるよりもはるかに大きい比率で
平均値よりもずっと大きなkを持つノードが存在しているという意味でもあります。
このようなことが明らかになって、古典的なモデル(Erdos-Renyiモデル）で議論
されたネットワークの性質というのがかなりの部分ご破算になってしまったという
歴史があります。（Erdos-Renyiは1959,Barabasiの論文は1999）
長々と説明しましたが、scale-free networkでは各ノードの位置を物理的な意味
合いで決定するのは無意味なので、ただグラフを描きやすいようにしているだけです。
まあ逆に言えばこういうグラフになるのは分かりきっているので、何を今更、という
感想ではありますが。
＞あちこちに無用な線の交差とかがあって、わざとごちゃごちゃさせてるようにも見受けられるんですよねぇ。
グラフをきれいに描くというのは実は非常に難しい問題で、NP困難であることが
知られています。早い話が、こちらの線が交差しないようにとすれば今度はあちら
が絡まって、きれいなグラフに整えるのはとても難しいのです。
数万ノードのネットワークをわかりやすく描く、実用的な時間で解けるアルゴリズム
があればいろいろな分野で応用可能なのですが、まだまだ決定的なものはない
ですね。工業的にも有用なので、そういうアイデアがあれば是非。（笑）
今回のネットワークはそう複雑な描き方をしているとは思いませんが、まあまあなの
ではないでしょうか。
＞あと、トラフィックに応じて線の色とか太さとか変えないと「グラフ化」というには弱いような。
それは多分簡単にできますけれど、やれば見た目が複雑になるだけであまり意味が
ないのですよね。実際のところ。
まあそれだけグラフの描画は工学的に難しい問題だということで。
kaho
Re:学術的に答えてみた（笑） (スコア:1)
> 色々と解説を探してたんだけど...。やっぱ意味薄？
グラフ化する意味は、多分20世紀にはあったんですよ。
その頃はまだ自然界のネットワークがscale-free networkとは知られていなかったので、
このような形になるとは考えられていませんでしたから。
> なんで多くのニュースサイトがこの話題を取り上げるんだろう？
> ニュースとして取り上げる価値のある情報とは思えない。
> 「意味無さそうだけど、他サイトも扱いそうだから...」ってな発想なのかな。
それはこういうグラフに描いたからと言ってそれだけでは意味がないので、一般の人は
見慣れていないからなのかもしれませんね。
でもメディアは学術的価値を自分で検証できることはほぼ絶対にないので、何か検索に
かかりそうなキーワードでもあればプレスリリースをそのまま掲載してしまうのではな
いでしょうか。
これって古典的なSEO?（笑）
kaho
Re:学術的に答えてみた（笑） (スコア:2, 参考になる)
レイヤからはかなり離れた高レベルの経験則だから、
scale-freeでないネットワークが出て来ても全然不思議は無い。
むしろ、背後の具体的な法則によらないで、自然界から
ファイル交換まで同じ構造になると考える方が「不自然」。
たまに統計力学とか中心極限定理みたいな「不自然」なことも
あるんだが、「scale-freeになって当り前」なんて言えるのは、
統計力学や中心極限定理くらいに「なぜそうなるか」が
分かってからのことでしょ？
統計力学や中心極限定理だって例外があるんだから、
scale-free networkに例外があっても不思議は無い。
ましてWinnyなんて、ネットワーク構造に対する作者の意図とか
通信インフラの広まり具合なんて要素が絡んでいる。
Re:学術的に答えてみた（笑） (スコア:2, 参考になる)
> レイヤからはかなり離れた高レベルの経験則だから、
> scale-freeでないネットワークが出て来ても全然不思議は無い。
鋭いですね。
経験則であることはその通りで、自然界のネットワークがscale-free networkになるというのは
いってみればZiphの法則 [u-tokyo.ac.jp]のようなものです。つまり「そういうものだ」と思われてはいるがその
原因は理解されていません。
そうなる原因を数学的に示すことができれば、もう工学の範囲を超えた重要な研究になるかと
思いますが、私の知る範囲ではその解明は進んでいないようです。
しかし今回のプレスリリースはWinnyノードだけを集めたわけでもなく、結局tracerouteの結果
を可視化したという、これまでに報告されていた、インターネットの解析の部分集合でしかない
ので、全く新規性はありません。
方法論の時点で結果が見えていて、そして考察としても何もこれまでの知識に加えるものがなか
ったわけで、研究的な価値は０に等しいと言っていいと思います。
> ましてWinnyなんて、ネットワーク構造に対する作者の意図とか
> 通信インフラの広まり具合なんて要素が絡んでいる。
ルーターの設置やぶら下げるノードの数もいろいろな要素がからんでいますよね。にもかかわら
ず経験則から離れてはいないのは前世紀から知られていたことです。
自然界のネットワークはそれぞれ様々な制約をうけているはずなのに、観測されるものは大抵
同じ構造だ、ということを説明したつもりで、そこにケチをつけられてしまうと最初からの堂々
巡りに・・・
kaho
Re:学術的に答えてみた（笑） (スコア:1)
＞を可視化したという、これまでに報告されていた、インターネットの解析の部分集合でしかない
これが全てなんですね？
Winnyのネットワークの図を描いたのであれば
従来の法則どおりの形状になっているかが確認できる意味で少しは有用なんでしょうが・・・・
物理的な構造が、法則どおりの構造にもかかわらず
実Winnyのネットワークは違っていたらと思うとワクワクしますが
・・・それは、誰かが解析してくれるのを待ちますか。
Re:座標軸は? (スコア:2, 参考になる)
全てのノードがグローバルIPを持っているのならばそうかもしれませんが、
グローバルIPのノードにいくつかのプライベートIPのノードがぶら下がる
しかないからあーいう構造になっているのでは？
＃P2Pソフトの開発に携わっているのでAC
Re:座標軸は? (スコア:1, オフトピック)
激しくオフトピですが、もし京都府警あたりが
「なに、P2Pソフトを開発している？じゃ逮捕だ」などと
このACさんをしょっ引こうとしてログの提出を求められたら
オリバーさんはそれに応じるのでしょうか？
べつにこのACさんに対して私が悪意を持っている訳ではなくて
何というかこう漠然とした不安を覚えてしまうので…。
And now for something completely different...
悪意そのもの (スコア:1, 興味深い)
あなたのようなことを言い続けると、本当に 「P2P = 逮捕されて当然」という世論が醸成されてしまう。
Re:悪意そのもの (スコア:1)
反論があるならば論拠を明確にして論旨に対して行うべき。
法律により必要な場合を除きってことらしいですね (スコア:1)
腐乱化…もといFlanker
Re:座標軸は? (スコア:1, 興味深い)
P2Pソフトといってもファイル共有ではなくGroove系のツールなので、違法性は
ほとんどないとは思うのですが、やはりイメージというのは大事なようで・・・。
ウチは大学の研究室で研究の一環のような形で開発しているのですが、
Winny開発者逮捕の時にはウチでもちょっとした騒ぎになり、この件について
何らかのコメントを出すかどうか臨時の検討会が開かれる騒ぎになりました。
あれ以後、P2Pに対するイメージはますます悪くなり、外からのお客さんに
「おたくは大丈夫なの？」と言われることが多くなったような気がします。
＃なんだか特定されかねないのでAC
Re:座標軸は? (スコア:1)
私が言わんとしたところは「P2Pソフトを開発してます」と
発言してしまうと、京都府警(あるいはそれに類する団体等)が
マークして、後々なにかの折に強権的になるのではないか。
「/.-Jというサイトでも匿名で開発を示唆していた。その証拠を
出せ」とオリバー氏に“要請”をするのではないか。
それが私の当初の発言
>このACさんをしょっ引こうとしてログの提出を求められたら
>オリバーさんはそれに応じるのでしょうか？
>べつにこのACさんに対して私が悪意を持っている訳ではなくて
>何というかこう漠然とした不安を覚えてしまうので…。
にあった「漠然とした不安」の意味するところでした。
私は元ACさんが逮捕されるべきと思ったのではなく、
むしろ物言えば唇が寒くなりそうな昨今、「P2Pソフトを
開発していると発言したばかりに京都府警に言いがかりを
付けられ、不当逮捕される恐れは無いのだろうか」と思ったのです。
この点、多くの皆さんに誤解を与えてしまったのは私の筆力のなさ、
舌足らずであったためと反省しております。
「P2Pってだけで十把一絡げに逮捕とか言うな馬鹿野郎」と
お叱り・ご指摘は尤もな事と思います。しかし一方で
47氏こと金子氏の逮捕事件以来、「本当に大丈夫かな…」
という、これまた「漠然とした不安」を私は覚えるのです。
And now for something completely different...
Re:座標軸は? (スコア:1)
#略語を書く時に脳内で展開できてればこんな問題は起き難いかと…
凛々しく、あほらしく。
Re:座標軸は? (スコア:1)
＞生まない状況では「IP 教えて」と言います。
むしろ、「アドレス」は冗長な部分だから文脈があるなら略したいところですよねぇ。
IPアドレス、MACアドレス、メールアドレス
IP ((DHCPで繋ごうとして)で、もらえるIPは？)
MAC (それのMACなんぼ？)
アドレス (メール送るわ、アドレス教えて。)
やはり人間、長い単語は使いたくないようです。
# ちなみにマクドナルドはマクドなので、紛らわしくないのです。
Re:座標軸は?(オフトピ) (スコア:2, 興味深い)
一般的(?)な英語では
メールアドレス＝郵便番号込みの実住所
eメールアドレス＝電子メールアドレス
なのだそうです。
Re:座標軸は? (スコア:1, 参考になる)
一般的には、辺同士の交差が少なくなるように、またノード同士の距離がなるべく均等にばらつくように調整します。
グラフのトポロジーを自動的に視覚化(2次元に配置してレンダリング)するツールとしては、私はGraphViz [att.com]を愛用してます。きれいな出力を得るには、それなりにチューニングが必要ですけど。
データさえあれば(これが重要？)、この絵を描くこと自体は既存の技術で簡単にできると思います。
Re:座標軸は? (スコア:1)
> 物理的な距離ではないだろうし、やっぱりIPアドレス?
>
> あちこちに無用な線の交差とかがあって、わざとごちゃごちゃさせてるようにも見受けられるんですよねぇ。
自動的に配置しようとすると、こんな感じでは。
わざとやるにも手間でしょう。
自分でやるとすると、
2ch各板不徹底図解 [asahi-net.or.jp] あたりが参考になると思います。
Re:座標軸は? (スコア:2, 参考になる)
2ch各板不徹底図解 [asahi-net.or.jp]
Re:座標軸は? (スコア:1)
Winnyは相互の接続を作る手が掛かりに、任意のクラスタワードを元にして同好の志を集めてグループ化していますから。枝分かれの根元の部分を決めるには、これが一番都合が良いのではないかと思います。
で、あとはその各クラスタに対してtracerouteをかける……と。
--- どちらなりとご自由に --- --
看板に偽りあり？ (スコア:2, 興味深い)
例えばhttpdのアクセスログからIPアドレスを抜き出して同様に
tracerouteした結果をグラフにしても同じようなものが出来上がる
ことは想像に難くないわけで、この図を「P2Pネットワークのグラフ」
と言ってしまうにはかなり無理があると思います。どちらかというと
ISP間のバックボーン図に産毛（エンドユーザー）をつけたもの
じゃないかと。
もちろん商売的にはそんなつまらないタイトルより、「P2Pの
なんちゃらグラフ」なんてつけたほうが注目されやすいんでしょうが、
そういう行為は後々批判の対象になることが少なくないってことを
この会社は知っておくべきでしょうね。
#JAROって何JAROなgesaku
Re:看板に偽りあり？ (スコア:2, 興味深い)
■関連記事
・ ネットアーク、法人向けP2Pファイル交換の無料診断サービス（2003/12/05）
・ ネットアーク、企業・大学向けにP2P監視サービスを提供開始（2003/10/01）
・ WinnyやWinMX利用者の58％がADSLを利用している～ネットアーク調査（2003/09/01）
・ ネットアーク、8月1日時点でのWinnyとWinMXの利用者数は56万ノード（2003/08/04）
だもんねぇ。
とにかく、何らかの注目を受ける必要があったわけで。
メルコのトピックスのように、いずれ日経産業新聞とかが抜けた報道してくれたりするのを期待してみよう。
Re:看板に偽りあり？ (スコア:1)
ごめん、メルコ。
ACにすべきかIDにすべきか…。お詫びなのでIDか??
Re:看板に偽りあり？ (スコア:1)
P2P クライアントの（論理的な）ネットワークを表したのではなくて、
「P2P を使っているマシン間の（物理的な？）ネットワーク」を表しているのだと思っていたのですが……
枝が集中しているあたりは、多分ISPのゲートウェイとかIXとかなんだと。
トラフィックの集中のチェックとか言う話をしているあたり、何となくそういう印象を受けたのですが……
多分、（可能かどうかはさておき）インターネットの全接続マシンをグラフ化した場合、件のグラフはその部分グラフになってるんじゃないかなーと思っています。
# 認識違いかなぁ……
目新しくない。 (スコア:2, 参考になる)
マップギャラリーのアドレス書くの忘れてました。 (スコア:1)
マンデルブロー集合的 (スコア:2)
>そんな感じのマンデルブロー集合的なグラフになっていて、
「マンデルブロー集合的」→「フラクタル」と言いたいのではないかとお察しします。
マンデルブロー集合ってのは、漸化式Z(n+1)=Z(n)*Z(n)+Cを繰り返したときに
発散しない複素数Cの集合のことで、いわゆるフラクタルな式の1つと言えますが、
フラクタルっぽい事象の１つを指してマンデルブロー集合的と言うのはちょっと
違うかなーと。ザクを見てゲルググっぽいよねと言うみたいな。
Re:マンデルブロー集合的 (スコア:1)
http://slashdot.jp/comments.pl?sid=68987&cid=238510
に近い。
記事のキャプションには (スコア:1, すばらしい洞察)
Re:記事のキャプションには (スコア:4, 参考になる)
「グラフの中心」というのはちゃんと定義されている概念です。
あるノードから他のノードにたどり着くためにいくつのノードをたどらなければならないか（これを一応『距離』と呼びます）ということは幅優先検索で簡単に測定できますが、あるノードをとったときに自分以外の全てのノードへの距離を測り、その平均が一番小さいノードがそのグラフの『中心』となります。
こちら [slashdot.jp]でも触れましたが、自然界のネットワークは全てこのような構造で、このタイプのグラフでは中心となるのは最も辺の数が多いノードになるのはほぼ自明です。
しかし、そもそもtracerouteでネットワークを分析したものは今資料を見た限りでも
なんていうそのものずばりなものがあります。
論文自体はみていませんが、
が私の知っている中では一番古い学術論文ですが、多分tracerouteでしょう。
まあ、だから、このプレスリリース、かなり恥ずかしいですよね。
kaho
Re:記事のキャプションには (スコア:1)
ところでこのP2P FINDERってのはWinnyを立ち上げておいて定期的にnetstatしておいて、結果をtraceroute→neato（グラフ作成）するものだと思っていいでしょうか（笑）
SIGGRAPH (スコア:1, 興味深い)
SIGGRAPHってこんなん [ascii24.com]
Re:SIGGRAPH (スコア:1)
脳とは言わないまでも、神経細胞間のインパルスを可視化したような感じの、
なんとなく、癒されるような動画になりそうな気がします。
吟醸しか飲まない豚
P2Pネットワークのブラフ化に成功 (スコア:1)
NNTPのグラフ化なら… (スコア:1)
昔はネットニュースというものがありまして（いまでもありますが），
こいつはちゃんと記事に経路情報が着くので配信されてきた記事だけ
をつかってニュースサーバを頂点とするなかなかおもしろいグラフが
描けたものでした．
love && peace && free_software
t-nissie
Re:NNTPのグラフ化なら… (スコア:1)
2003年12月19日の Newsfeed map はこんな感じです [google.co.jp]
1998年6月には1300ホストあった [google.co.jp]のが、2003年末では76ホスト…
昔話にされても仕方ないですねぇ…
Newsfeed map とか posters も今年に入ってからは流れなくなってますし…
ツリー？ (スコア:0)
Re:ツリー？ (スコア:1)
ツリー（状）になっているのは末端だけですね。
# しかし所々にある、枝分かれせずに延びている部分は一体……
ツリーよりも (スコア:0)
ここの人たちは、同じ相手としかやりとりしてない、ってことかな？
Re:ツリーよりも (スコア:1)
これまでのところ長さがどんな情報を持っているか分かりませんが、単に表示上の都合で、近くにマル（ノード）を描くと重なってしまうので、適当に離れた所に置くようなロジックになっているのかも。
＃現実界の量（物理量）でないものを可視化するのはそれなりに工夫が必要で。
traceroute? (スコア:0)
>具体的には、ネットアークが2004年6月に集計したP2Pファイル交換ノードに対する「traceroute」結果のグラフ化に成功。
tracerouteだと単にIPルーティングの木構造しかグラフにできないんじゃないかと思うのですが、なにかもっとすごいことをしているのでしょうか。
子鯖、親鯖の関係とかはわかりませんよね？
Re:traceroute? (スコア:0)
トラフィック経路に観点を置いているわけだから、それでいいんじゃない?
Re:traceroute? (スコア:1)
ICMPを使ったtracerouteでは、IPレベルのルーティングしか分からない。
MXやnyがどういうプロトコル使ってるのか知らんが、
P2P的トラフィック経路を知るには、各ノードからP2Pな
プロトコルでtraceroute（的なこと）をしないといけないんぢゃ？
Re:traceroute? (スコア:1)
じゃ、『P2Pの』ってつける必要なくない？
別に何も新しいものじゃなくて、単なるIPレベルの
論理トポロジと同じ絵になるんではないのだろうか。
＃IPレベルでは、トラフィックが集中するノード（MXでは鯖っていうの？）が枝の根元になるわけじゃないでしょ。
何か激しくネタな気がするんだけど。
Re:traceroute? (スコア:1)
「P2Pの」ってつける意味があるんですよ。
＃でも、ファイル交換って言ってる時点でアウトだと思う
Re:traceroute? (スコア:1)
あはは (スコア:0)
ソース(と設計)が手元に無いとはいえ、時間かかり杉の感が。
シミュレーショングラフ置いときますね (スコア:1)
シミュレータソースとシミュレーション [archive.org]
IDENTIFICATION DIVISION.
AUTHOR YUKI-KUN.
Flash画像 (スコア:1)
どんどん拡大できれば面白かったのになあ。
円グラフや棒グラフは拡大する意味がいまいち…。
使い方が逆だ、逆。
#まあネタ元としてはそれが商売のタネだから出せないんだろうが
Re:ゲーム脳おじさん (スコア:1)
・・・。
えーと。
ごめん、どっちも失礼でした。
にゃにゃ(=－_－=)