犀角(Diceros Horn)

Pagerank Central Laplacian ボタンでそれぞれグラフから決まる行列の最大固有値の固有ベクトル（の絶対値）を頂点の半径に比例させて表示させます。 Pagerank は「グラフの推移確率行列*0.9 + すべての行成分が 1/頂点数の定数行列 * 0.1」の行列について固有値を計算しています。本来は有向グラフについて計算すべきですが、無向グラフについても双方向に推移できる対称的な有向グラフとして計算しています。 Central はボナチッチの中心性指標すなわち隣接行列の最大固有値の固有ベクトルを求めるものです。ボタンを押し続けると、2番目に大きい固有値の固有ベクトル、 3番目に大きい固有値の固有ベクトル、の順に徐々に小さな固有値に付随する固有ベクトルの成分を可視化します。Degree ボタンで戻ります。今どのモードなのかを示すために、頂点の色とボタンの文字の色を一致させています。 Degree（次数＝デフォルト）以外では Update ボタンで更新しても自動的には計算しません。毎回ボタンを押しなおしてください。押したときに、右上の通常次数分布が表示されるグラフは固有値の分布になります。

モデルの説明

Barabasi Albert Simulator: Barabasi Albert のスケールフリーモデル
Watts Beta Model: Watts Storogatz のスモールワールドモデル
Erdos Renyi Model: JUNG に付属のモデル
Eppstein Power Law Model: JUNG に付属のモデル
Kleinberg SmallWorld Model: JUNG に付属のモデル
Apriori Power Law Model: ベキ則に従う次数分布を与えて、そこからグラフを作る
Unlink Smaller Degree: 頂点数ははじめから固定し、初期状態はWSのレギュラーグラフ。 1ステップごとに、乱数でリンクをひとつ選択して、端点のうち次数の小さい方のノードを別のノードに付け替える。ただし、次数が１の時は付け替えない。付け替えるノードは、自分自身及びすでにリンクのあるノードは除いて、ノードの次数に比例した確率で選ぶものとする。（優先的選択）
Clusterize Simulator: ランダムグラフからはじめて、次数分布を変えずにクラスタ係数が局所的に大きくなるように辺を付け替える。
ScaleFreeInit Clusterize: 上と同じだが、初期状態を Barabasi Albert のスケールフリーネットワークからはじめる。
Link More Common Neighbor: ランダムグラフからはじめて、リンクを共通の近傍がより大きくなるようなノードに付け替えていく。

履歴

2006/6/14: Pagerank とボナチッチの中心性指標を可視化する機能を追加
2006/6/12: モデルをいろいろ追加
2006/5/21: Watts Storogatz モデルにバグを発見したので直す
2006/5/6: グラフ可視化アルゴリズム SpringLayout 以外に KKLayout を追加。切り替えられるようにした。SpringLayout のパラメータも変更可能。JNLP 版ではセキュリティの関係で動かないが、Pajek 形式のファイルを出力する機能、グラフ画面を Jpeg で出力する機能（バグ残っているけど）を追加
2006/3/5: いくつかの不具合を修正。設計の若干の見直し。オリジナルルール Node Concentrate モデルの見直し。ベキ則が現れるようになった。ベキ則が現れることの条件として、Barabasi Albert モデルからノードが新たに加わることが条件のように書いてある本も多いが、そうとは限らないことの反例になるかな。
2006/1/6: いろいろなシミュレーションを統合
2006/1/1: 対数目盛表示を追加
2005/12/31: クラスタ係数の計算を追加
2005/12/24: オリジナルルールを追加
2005/11/30: JUNG を使って作り直す
2005/11/5: BAモデルのプロトタイプ作成
2005/11/3: クラスター度の計算を追加
2005/10/30: 隣接行列の固有値を計算する（現在この機能は削除中）
2005/10/23: WSモデルのプロトタイプ作成

リンクする場合は http://www.tokunagakenichi.net/Program/ScaleFree/index.html にどうぞ。

2007/06/11追記

1年ほど触っていませんでしたが、中部地方の学生さんからネットオークションの研究の参考にしたいと、コメントをいただきました。どのように発展するのか楽しみにしています。

posted at 23:37 | category: /Program/ScaleFree | 固定リンク(スケールフリーネットワークシミュレータ)

Mon, 16 Oct 2006

多角形の三角形分割（その２）

平面上の凸ｎ角形と言う制限をなくして考えてみる。つまり、三角形分割したときの面の張り方がメビウスの輪みたいになっていることを許すことにするとどうなるか。ｎ＝５の場合は、平面の場合以外に、

[0,2,3]
[1,3,4]
[2,4,0]
[3,0,1]
[4,1,2]

の５つの三角形で分割する方法がある。普通の平面上だと当然自己交差が起こってしまうけれども、ここではそれは考えないことにする。

力技でｎが小さいときに数えてみる

n角形	3	4	5	6	7	8
n-2個の三角形による分割	1	2	5	14	42	132
n個の三角形による分割	0	0	1	14	141	1056
n+2個の三角形による分割	0	0	0	2	210	4968
n+4個の三角形による分割	0	0	0	0	49	10184
n+6個の三角形による分割	0	0	0	0	0	7012
n+8個の三角形による分割	0	0	0	0	0	272
三角形による分割合計	1	2	6	30	442	23624

まだ規則性が見えていません。

posted at 00:59 | category: /Math/Discrete | 固定リンク(多角形の三角形分割（その２）)

Tue, 10 Oct 2006

Rで3D表示

R はデータ解析処理ソフトだけれども、OpenGL の機能をいくつか使うことができるので、簡易 3D 表示ソフトとしても使えるのです。ポリゴン表示の練習として、三葉結び目のザイフェルト曲面をポリゴンで表示させてみました。位相的にはメビウスの輪と同じなので、表裏がないため片面だけ表示するとおかしくなるから、両面とも赤色にしてあります。

作るのに使ったR のスクリプト。

> install.packages("rgl")
> library(rgl)

してから使おう。

posted at 02:19 | category: /R | 固定リンク(Rで3D表示)

Sun, 06 Aug 2006

多角形の三角形分割

凸ｎ角形を三角形に分割する方法が何通りあるかを考えてみた。ｎ＝４の時は、対角線の引き方だから２通り。ｎ＝５の時は、頂点を順に0,1,2,3,4とすると、

[0,2][0,3]
[1,3][1,4]
[2,4][2,0]
[3,0][3,1]
[4,1][4,2]

の辺を追加する５通り。ｎ＝６の時は１４通りである。

一般にはｎ角形（ｎ≧３）の時

Π_{k=2}^{n-1} (4k-6)/k

通りになる。小さいところを計算すると

n=3のとき1
n=4のとき1*(6/3)=2
n=5のとき1*(6/3)*(10/4)=5
n=6のとき1*(6/3)*(10/4)*(14/5)=14
n=7のとき1*(6/3)*(10/4)*(14/5)*(18/6)=42

のようになる。

上の式の (4k-6)/k の部分は

4k-6 = 2(2k-3) = 2*(k角形の三角形分割が与えられた時の辺と対角線の本数)
k = k角形の頂点の回転による同一視

をあらわす。すなわち、n角形の三角形分割と、三角形分割を与える頂点の順序つきの組が与えられた時に、(n+1)角形の三角形分割が与えられることをいう。さらにそれが、頂点の番号付けに対して対称であることを言えばよい。

頂点の組[p,q]が辺の場合は、1点rを外部に追加して[p,r,q]を新たな三角形として、(n+1)角形の三角形分割を得る。ここで、[p,q]が順方向なら頂点の番号は r = q として、新たな q は r+1 とする。逆方向なら r = q+1 として、新たな p = r+1 とする。
頂点の組[p,q]が対角線の場合は、[p,q,r=q+1] を新たな三角形として追加する。p>q の場合は p もひとつ増やす。

n=4 の時の例として計算してみると、[0,1,2][0,2,3] を4角形の三角形分割として、

[0,1]を追加した場合[0,1,2][0,2,3][0,3,4]という5角形の三角形分割を得る
[1,0]を追加した場合[0,1,2][0,2,3][0,3,4]という5角形の三角形分割を得る
[1,2]を追加した場合[0,1,3][1,2,3][0,3,4]という5角形の三角形分割を得る
[2,1]を追加した場合[0,1,3][1,2,3][0,3,4]という5角形の三角形分割を得る
[2,3]を追加した場合[0,1,2][0,2,4][2,3,4]という5角形の三角形分割を得る
[3,2]を追加した場合[0,1,2][0,2,4][2,3,4]という5角形の三角形分割を得る
[3,0]を追加した場合[0,1,4][1,2,3][1,3,4]という5角形の三角形分割を得る
[0,3]を追加した場合[0,1,2][0,2,3][0,3,4]という5角形の三角形分割を得る
[0,2]を追加した場合[0,1,2][0,2,3][0,3,4]という5角形の三角形分割を得る
[2,0]を追加した場合[0,1,3][1,2,3][0,3,4]という5角形の三角形分割を得る

が得られ、[0,1,3][1,2,3]からも同様に得られて、頂点の回転対象性から、同じ三角形分割が 4つずつ得られるので、２＊１０／４＝５通りの三角形分割が得られる。

追加情報

The On-Line Encyclopedia of Integer Sequences によると、この数列は Catalan numbers として知られているみたいです。

posted at 23:37 | category: /Math/Discrete | 固定リンク(多角形の三角形分割 )

Mon, 03 Jul 2006

経済時系列データのグラフィカルモデリング

2006年上半期

Pajek NET 形式ファイル

posted at 01:25 | category: /economics | 固定リンク(経済時系列データのグラフィカルモデリング )

Sun, 18 Jun 2006

複雑ネットワークの生成過程のシミュレーション分析

PDF化した発表原稿 2006年6月,関東社会学会

posted at 01:24 | category: /research | 固定リンク(複雑ネットワークの生成過程のシミュレーション分析 )

Wed, 14 Jun 2006

PageRank

JUNG に PageRank を計算するクラスがついている。それによると、推移確率行列と定数行列（すべての成分が定数＝1/頂点数）を内分した行列の最大固有値の固有ベクトルを求めているみたい。すべての成分が定数の行列というのは、マルコフ過程の推移確率行列だと思うと、すべての頂点に同確率で移りうるということだから、辺をたどらずに別の頂点にジャンプする場合を考慮したものといえる。

(1-alpha)*推移確率行列+alpha*定数行列という形で、 alpha の値は0.1から0.2までぐらいが適当。

こうすると、

ボナチッチの中心性指標＝隣接行列の最大固有値の固有ベクトル
PageRank＝推移確率行列（を少し摂動したもの）の最大固有値の固有ベクトル

となり区別がわかりやすい。

posted at 20:34 | category: /ComplexNetwork | 固定リンク(PageRank )

Sun, 11 Jun 2006

ネットワークのサンプルデータが落ちているところ

UCINET IV DatasetsUCINET IV Datasets

posted at 21:19 | category: /ComplexNetwork | 固定リンク(ネットワークのサンプルデータが落ちているところ )

Next 10 entries