犀角(Diceros Horn) 2005 10

とくながの「書き散らかし」です

ここは研究・調査・開発などの記録がメインのページです。 日常の雑事、読書記録は はてなダイアリー の方に書いています。よろしければそちらもどうぞ。
←October→
Sun Mon Tue Wed Thu Fri Sat
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31          
犀角(Diceros Horn) の RSS

Copyright © 1998-2006 TOKUNAGA Ken-ichi iam[at mark]tokunagakenichi[dot]net

あなたはこのサイトの11110100010111000111人目の訪問者です(ただし2進数)。

Valid XHTML 1.1!

Sun, 30 Oct 2005

Eigen Analysis of Networks

Journal of Social Structure に Eigen Analysis of Networks というレビューがありました。これで NEGOPY というソフトウェアの存在を知って探して みたんだけど、動かなかった・・・・・。

posted at 19:17 | category: /Math/GraphTheory | 固定リンク(Eigen Analysis of Networks )

ワッツ＆ストロガッツのスモールワールドシミュレータ（３）

隣接行列の固有値を小さい順にグラフにプロットしてみました。 Watts Storogatz Simulator 2005/10/29 版 です。使い方は同じです。

kの値を3にすると、初期状態のレギュラーネットワークそれぞれのノードから 前後に合計6個のリンクが出ることになる。 この状態で、確率pを0にして randomize する、すなわちリンクのつけかえをせずに 固有値の分布だけを見ると、小さい値はほぼ等差数列(直線がフィットしそう)で あるが、上位3割ぐらいはそれから外れていて、直線にもフィットしそうにない。 確率pを0.2位にしてリンクの付替を繰り返すと、距離の平均値がほぼ一定の値に 落ち着くと同時に、固有値の分布もほぼ全体が一つの直線にフィットするようになる。

この現象は確かランダム行列の話と関わっている記憶があるが、今はちょっと わからないので、宿題。線形から離れるところを定量的に評価できれば、それが ランダムネスの一つの指標になるだろうし、それと距離平均の関係を調べても 面白そう。

posted at 01:07 | category: /Math/GraphTheory | 固定リンク(ワッツ＆ストロガッツのスモールワールドシミュレータ（３）)

Fri, 28 Oct 2005

ワッツ＆ストロガッツのスモールワールドシミュレータ（２）

少し変えました。 Watts Storogatz Simulator 2005/10/28 版 です。例によって Java Web Start で起動します。

  • 隣接行列の最大固有値を表示するようにした。
  • 最大固有値での固有ベクトルの成分の値（つまりはPagerankもどき）で頂点の色を塗わけてみた。
  • JSplitPane を使ってみた。
  • スペルミスなどを直した（恥）。
使い方は前と同じです。

posted at 08:36 | category: /Math/GraphTheory | 固定リンク(ワッツ＆ストロガッツのスモールワールドシミュレータ（２）)

Sun, 23 Oct 2005

ワッツ＆ストロガッツのスモールワールドシミュレータ

Watts Storogatz Simulator を作ってみました。Java Web Start で起動します。

  • ノードの個数(N)は100
  • 初期レギュラーネットワークを作るときの、つながっている隣人の距離(k)は1から5までの中から選ぶ
  • リセットボタンを押すと、リンクが描かれて（実際はノードの影になって見えない）、全ノード間の平均距離を計算する。
  • ノード間のリンクの付替をする確率(p)を入力してランダマイズボタンを押すと、実際にリンクの付替が起こって、全ノード間の平均距離を計算し直す。
リンクの付替をするアルゴリズムは Watts らのやり方とは少し違う（実装上の理由）。ここでは全てのリンクを順に調べて、確率pでリンクをつけかえる。このときリンクの片方のノードは固定して、もう一方のノードを別のノードに付け替える。どちらのノードを固定するか、別のノードをどう選ぶかは、乱数で決める。ランダマイズは何度でも実行できる。リセットボタンをもう一度押すと、レギュラーネットワークに戻る。

距離の計算は孤立ノードが存在すると、距離無限大になってしまうが、リンクの個数の100倍で距離の計算を打ち切っているので、実際はその値になっている。行列計算には Matrix Toolkits for Java (MTJ) を使った。

  • スモールワールド以外のシミュレーションもしたい
  • 全ノード間距離以外の指標（スペクトル、PageRank など）も計算したい
  • ノードの個数が10000位でも動くように効率化
など、気が向けばやるかも。スペクトルの計算は MTJ についているから実はもうできているんだけど、可視化するのが面倒・・・・・。

posted at 14:00 | category: /Math/GraphTheory | 固定リンク(ワッツ＆ストロガッツのスモールワールドシミュレータ)

頂点の間の距離

グラフ理論の復習。 無向重みなしグラフ（隣接行列が対称で、成分が0または1）を考える。 隣接行列 A の (i,j) 成分は i 番目の頂点から j 番目の頂点への辺があるか ないかを表している。このとき、行列 A の n 乗の (i,j) 成分は i 番目の頂点から j 番目の頂点へ n ステップで到達することのできる 場合の数を表している。

これを利用して、A の n 乗の (i,j) 成分がはじめて 0 でない数になる n を求めると、i 番目の頂点から j 番目の頂点への距離となる。 普通距離はこの様にして計算されるが、有限の距離を持つかの判定が この方法でできるわけではないので、適当なところで打ち切る 必要がある。その意味で正確な計算方法ではないが、他のよい方法は 知らない。

posted at 09:00 | category: /Math/GraphTheory | 固定リンク(頂点の間の距離)

Tue, 18 Oct 2005

PageRank とボナチッチの中心性指標

PageRank の計算も WebLink の隣接行列を考えて、 最大固有値の非負固有ベクトルを求めているのだろう。 Google PageRnak の原論文まで読んだわけではない （読まなくちゃね）ので、計算方法がどうなっているのかは知らないが、 Perron-Frobenius の方法をつかえば、すべての固有ベクトルまで求めなくてもよいし、 近似が荒くてよければ収束計算を途中で打ち切ればよいので、パフォーマンスも期待できる。 逆に言えば、ネットワーク分析でボナチッチの中心性指標を計算している、 と説明するよりも、このリンク構造の PageRank を計算している、といった方が 今やわかりやすいだろうな。

少し検索してみると、Perron-Frobenius の方法を改良して計算効率を上げようとか、 別のネットワーク指標を作ろうという研究は山ほど出てくる。 MATLAB NEWS のコラム（かなり古いが）に The World’ s Largest Matrix Computation というのがある。日本語だと Google の秘密 - PageRank 徹底解説 が面白い。

posted at 07:25 | category: /Math/GraphTheory | 固定リンク(PageRank とボナチッチの中心性指標 )

Mon, 17 Oct 2005

Java による数学・物理関係ライブラリ

以前にも紹介した Java Numerics にも挙げられていますが、 JSci という数学関係のライブラリがありました。 wavelet や MathML 用の DOM もあるみたい。

java.net の中にもedu-math というカテゴリーがあるけど、あまりたくさん登録されていない。 上位階層のedu-developer からたどってみる方が面白いものがあるかも。 edu-desktoptools にはちゃんと Project Looking Glass が登録されています。

posted at 07:56 | category: /Java | 固定リンク(Java による数学・物理関係ライブラリ)

Sun, 16 Oct 2005

ボナチッチの中心性指標

ネットワーク分析の分野でボナチッチのの中心性指標という指標が知られている。 無向グラフで辺に重みも多重辺もないとする。つまり隣接行列Aは対称で成分には ０と１しかないとする。

p0をすべての成分が１のベクトルとして、 

pn = A・pn-1 を成分の最大値で割って正規化したもの
として、pnの極限を考えたものがボナチッチの中心性指標だと定義されている。 （「社会を＜モデル＞で見る」より）

数学の立場ではこれはいわゆるペロン・フロベニウスの定理で導かれる非負行列 （この場合は隣接行列）の最大固有値の非負固有ベクトルを求めていることに過ぎない。 要するにこれも隣接行列の固有値を考えるという意味で、グラフのスペクトル理論の 範疇にあるといっていい。

posted at 12:37 | category: /Math/GraphTheory | 固定リンク(ボナチッチの中心性指標 )

Thu, 13 Oct 2005

M-Learning?

VR が Learning システムの中でどのように使われているのかを調べていたら、 Collaborative M-learning using Agents and Virtual Reality というのを発見。M-Learning の M とは mobile の m らしい。 システムとしては、VR のフレームワークである CLEV-R と e-Learning (画面から推察するとたぶんBlackBoard)のエージェントシステムである ABITS を融合してモバイル化しようという試みらしい。VR を　PDA で見せられても という気はするものの、適材適所で使うというのはありでしょうね。

posted at 07:07 | category: /VR/Learning | 固定リンク(M-Learning? )

Wed, 12 Oct 2005

カテゴリーを階層化してみました

Permalink が変わってしまってます。リンク切れしてしまったらごめんなさい。

posted at 07:50 | category: /About | 固定リンク(カテゴリーを階層化してみました)

Mon, 10 Oct 2005

隣接行列

グラフ理論の復習。 線形代数的グラフ理論（竹中 淑子）などを参考に。

グラフの表現のひとつとして、隣接行列を考える。 つまり、頂点が n 個のグラフの場合、n×n行列で、

(i,j)成分 = i番目の頂点からj番目の頂点への辺の個数
とする行列を、隣接行列という。無向グラフの場合は対称行列になる。 有向グラフの場合はそうとは限らない。辺に重みがあるとき、多重辺 （ある始点からある終点までの辺が２つ以上あること）を持たない場合に
(i,j)成分 = i番目の頂点からj番目の頂点への辺の重み。辺がないときは0。
と定義することもある。ここでは重みの値は正であることを仮定する。 （参考： Weighted Graph (mathworld)） 仮定しない場合は、重みが０のときと辺がないときの区別がつけられない、 内積をうまく定義できない、などの弊害が出てしまう（後述）。

このように定義すると、隣接行列からグラフを構成することができる。 グラフから隣接行列を定義するには、頂点の順番の取り方によって 置換行列による相似変換の分だけのあいまいさがある。 とすると、グラフの性質を調べるには隣接行列の置換行列による 相似変換によって変化しない不変量を考えればよい。

隣接行列（またはそこから導かれるラプラシアン行列）の固有値について調べることは、 一般の相似変換によって変化しない不変量を調べていることになるから、 情報は少し落ちている。でも調べやすいので、まずはそこから考えてみる。

posted at 00:35 | category: /Math/GraphTheory | 固定リンク(隣接行列 )

Sun, 09 Oct 2005

グラフ理論のシミュレーターを作る

ネットワーク分析に興味が出てきたので、グラフ理論の復習をしながら、 簡単なシミュレータを作っていこうと思う。 中期的なプランとしては（また放ったらかしにならないようにせねば）

  • グラフの数値実験を簡単にできるようなシミュレーターを作る
  • ワッツのスモールワールドモデルを検証する
  • グラフの構造の指標となるものを探す
  • その指標に対して相転移が起こっているところを探す
  • 相転移をおこすメカニズムを解明する
  • エネルギー関数を導入して、力学系としてグラフ構造の変化をとらえる
  • 知人ネットワーク、所有ネットワーク、知識ネットワークなどへ応用する
まあ、目標は大きく持っておいた方がいいでしょう。

posted at 18:59 | category: /Math/GraphTheory | 固定リンク(グラフ理論のシミュレーターを作る)

3D Visual Data Mining

3D Visual Data Mining というデンマークの大学がやっているプロジェクトはおもしろい。 データマイニングの可視化。

posted at 08:51 | category: /VR | 固定リンク(3D Visual Data Mining )

Sat, 08 Oct 2005

Virtual Universe

3DChat.org フリーの3Dワールドサーバ。3Dチャットもできる。

posted at 00:37 | category: /VR | 固定リンク(Virtual Universe )

Tue, 04 Oct 2005

サッカープレーヤーは40試合以上出ることが才能の証明？

Complex network study of Brazilian soccer players なんて言うのを発見してしまいました。洒落なのか、まじめなのか よくわかりません。スポーツ番組の蘊蓄みたいな内容ですが、 面白いです。題材選択の勝利だなあ。

通算出場試合数の分布をとると、40試合で相転移が起こり、 通算獲得得点数の分布をとると、10点で相転移が起こるそうです。 ブラジルの選手でも40試合未満しか出られず、ゴールも一桁の プレーヤーが大多数で、それ以上のプレーヤーとは層が違う ということが証明されてしまったわけで。

本家 Wikipedia での Complex network の項目にも取り上げられているので、やっぱりまじめなのかな。

posted at 00:02 | category: /physics/Econophysics | 固定リンク(サッカープレーヤーは40試合以上出ることが才能の証明？)

Sat, 01 Oct 2005

ImageJ を使って 3D 表示する(2)

さて、sourceforge の ImageJ Plugiins に行ってみる。そこの IJ Plugins: 3D Toolkit の手順にしたがってインストールする。 具体的には、

  • ij-3D-Toolkit の最新バージョンのバイナリ版 zip を落としてくる。
  • zip ファイルを展開して、3D IO、3D Toolkit、VTK Filters のフォルダを ImageJ の plugin の中にコピーする。
  • ij-plugins-toolkit.jar をクラスパスに通す。
  • vtk.orgからVTKの最新バージョンをダウンロードして、インストールする。
  • vtk.jar をクラスパスに通す。
  • ImageJ を実行。
VTK ファイルの表示はメニューの Plugins から。File からではないので注意。 マウスでグリグリ視点を変える方法はよくわからない。ImageJ じゃ無理？

VTK を直接 Java で扱えばできるのだろう。次にやって見よう。

posted at 19:05 | category: /Java | 固定リンク(ImageJ を使って 3D 表示する(2))

ImageJ を使って 3D 表示する(1)

ImageJ というアメリカ国立衛生研究所(NIH)が作っているソフトウェアがある。 Java ベースの画像解析用のソフトウェアで、plugin やマクロで機能を追加できる。 おそらくMRIなどの医療用の画像を表示したり、画像処理したりするのが 目的で開発されたのだろう。これの 3D 表示用の plugin を使ってみる ことを目標にする。

まずは ImageJ 単体の起動。上に書いた ImageJ のサイトから最新版を ダウンロード。JDK1.5 の環境では、JRE のバンドル版じゃなくて JAR File バージョンで大丈夫だった。zip ファイルを展開して ij.jar と言うファイルができたら、そこで 

$ java -jar ij.jar
とすればよい。これで jpeg や gif ファイルを開いて簡単なフィルタを かけたりすることができる。Java で書かれているが、それほど遅くはない。

posted at 16:34 | category: /Java | 固定リンク(ImageJ を使って 3D 表示する(1))