Pajekの色使い一覧

たまに使うと忘れてしまうので。。。







←人気blogランキングに参加しております

Exploratory Social Network Analysis with Pajekの翻訳計画！？

webサーフィンしていたら、社会ネットワーク分析で著名な安田雪氏のブログを見つけました。ブログ自体は8月に開始されているので、3ヶ月も私は気づかないでいたわけで、すでにご存知の方も多数いるとは思いますが、、、 (^^;

中でも、個人的にとりわけ興味深かったのは 10/31の記事。
「pajekによる探索的ネットワーク分析」の翻訳プロジェクトという言葉が！これって、 Exploratory Social Network Analysis with Pajekのことなんでしょうか。


だとしたら、この本の翻訳に安田氏は適任だと思います。期待して待ちましょう。


←人気blogランキングに参加しております

Pajek の日本語Howto

しばらくPajekのオフィシャルを見ていなかった(半年以上)ので、日本語のHowtoが出来てて、しかもそれはGBRCという団体の出版した『赤門マネジメント・レビュー』 Vol.4, No.5の中の記事だということを知りました。この記事自体の存在は以前から知っていましたが、無料で閲覧できないと自分で勝手に思い込んでいましたので、二度びっくりしてしまいました。
http://vlado.fmf.uni-lj.si/pub/networks/pajek/howto/jp/pajek-AMR4-6-2.pdf

そういえば先日、ある知人がPajekでデータ処理することを「パヤくる」と申しておりました。Pajek (パエックorパヤック)と読む人が多いからでしょうか。

関連サイト
Pajek Program for Large Network Analysis
http://vlado.fmf.uni-lj.si/pub/networks/pajek/

グローバルビジネスリサーチセンター(GBRC)
http://www.gbrc.jp/GBRC.files/top.asp

ネットワーク分析プログラムPajek 1.03

去る1月16日にネットワーク分析プログラムpajekがバージョンアップしたようです。昨今ネットワーク分析が注目されておりますので、興味のある方は是非使用してみてくださいませ。ただしWindowsのみ。


関連記事

Networks / Pajek Program forLarge Network Analysis
http://vlado.fmf.uni-lj.si/pub/networks/pajek/

それゆけBioinformatics: pajek
http://bioinfo-goto.seesaa.net/category/67276.html
(以前に、Pajekのごく初歩的な扱いを解説しました)

それゆけBioinformatics: graphviz
http://bioinfo-goto.seesaa.net/category/67259.html
(Pajekのような分析機能は無いですが、ネットワーク図を描くのによく利用されております)

Pajek入門 −巨大ネットワーク分析用フリーソフトウェア−

Pajek official site
Developed by Vladimir Batagelj and Andrej Mrvar at the University of Ljubljana, Slovenia.

1. Pajek概要

Pajekは、フリーのWindows (32 bit)用の巨大なネットワーク分析プログラムである。

Yeast two-hybrid (Y2H)法によるタンパク質−タンパク質相互作用ネットワークのような大量データ(多数のタンパク質がある)をネットワーク分析する際に、行列表示に基づく標準的なネットワーク分析ツールで効率的に扱うことは非常に困難である。大量なネットワークデータに対してPajekが出来ること・目指すゴールは以下の通りである。

(1) 巨大なネットワークを小さなネットワークへと分離・抽出する
(2) ユーザにネットワークの強力な視覚化ツールを提供
(3) 巨大なネットワークの効果的な分析アルゴリズム選択を実装すること

Pajekは、様々な学術雑誌の論文でも使われている (今後も増えるはず)。
[掲載例]
・Réka Albert, Hawoong Jeong, and Albert-László Barabási: Attack and error tolerance in complex networks. 　Nature, 406 (July 2000), 378-382. (PDF)
・Steven H. Strogatz: Exploring complex networks
・Yuen Ho, ... : Systematic identification of protein ...
・Jeffrey C. Johnson, ...: Network Role Analysis in the Study of Food Webs: An Application of Regular Role Coloration
・Douglas White, Vladimir Batagelj and Andrej Mrvar. Analyzing Large Kinship and Marriage Networks. Social Science Computer Review 17 (1999), 245-274
・Linton C. Freeman: Visualizing Social Networks
・Andrej Mrvar, Vladimir Batagelj: Drawing genealogies; XVIII Sunbelt, Sitges, May 1998 (PDF)
・Patrick Doreian, Vladimir Batagelj, Anuška Ferligoj: Symmetric-Acyclic Decompositions of Networks (PDF)


2. Pajek入門

ここでは、ネットワーク分析ツールPajekの使い方の説明をして、実際にPajekを動かしてみる。

2.1. ファイルのフォーマット

Pajekで扱うファイルは基本的にプレインテキスト形式である。かなり厳密に、そのフォーマットに従わねばならない。Pajekは正確に書いてないファイルをロード出来ないからだ。そのファイルフォーマットは以下の通りである。

*Vertices <number of vertices>
1 “label1”
2 “label2”
…

*Edges
<vertex1> <vertex2>
<vertex3> <vertex4>
…


1行目には、*Verticesの後ろにスペースを空けて、頂点の数を記す。
以下、番号つけされた頂点を記述する (数字の後にスペースを空けてラベルも書く)。
*Edgesの次の行からは、ある頂点pとある頂点qを結ぶエッジのパターンをp -> qの順でスペースを空けて記述する。



Pajek ネットワークファイル (拡張子*.net)の例 [ファイル名　testdata.net]

*Vertices 5
1 "YAL005C"
2 "YAR002W"
3 "YLR310C"
4 "YPL240C"
5 "YAL021C"

*Edges
1 2
1 3
1 4
3 4
4 5

なお、ファイル中ではスペースのみを使用し、タブを使ってはならない。


2.2. ネットワークの書き方

(1) 上記のデータファイルをエディタを使って(Wordでもメモ帳でも良い)、testdata.netというファイル名でテキスト保存する。
(2) Pajekを起動してから、メニューのFile -> Network -> Readを選ぶ。そして、testdata.netを開いてPajekにロードする。




(3) メニューDraw -> Draw (Ctrl + G)とすると、ネットワーク図が描ける。ラベルを表示するには、メニューのOptions -> Mark Vertices Using -> Labels (Ctrl + L)とする。逆にラベルを無効にするには、Options -> Mark Vertices Using -> No Labels (Ctrl + D)とする。



(4) ネットワークのレイアウトは、頂点をマウスでクリック＆ドラッグすると調整できる。



(5) ビットマップ形式で、ネットワーク図を保存するには、メニューのExport -> Bitmapとたどって、出力先のフォルダと出力ファイル名を指定すればよい。(詳細は、2.3節)



(6) メインウインドウのメニューNet -> Partitions -> Degree -> Allとすると、各のノードの連結性がカウントできる (この場合、無向グラフなので、あるノードへの入次数と出次数の両方の合計)。




メニューのFile -> Partition -> Edit でその詳細が別ウインドウで表示される。さらに詳細な情報は、Info -> Partitionでレポートウインドウに表示される。



(7) メニューのNetを使って、Net -> Paths between 2 vetices -> Diameterでネットワークの直径がわかる。

(8) クラスタ係数(CC)は、Net -> Vector -> Clustering Coefficients -> CC1で求められる。これは各ノードのCCを算出する。なお、CC2 は標準化したクラスタ係数である。CCの統計情報は、Info -> Vectorで表示する。


2.3. 画像ファイルへの保存

Pajekで描いたネットワーク図を、画像ファイルとして保存するには、DrawウインドウのメニューExportからBMP (bitmap)、EPS (Encapsulated Postscript)、SVG (Scalable Vector Graphics)などの形式を選ぶ。その際、保存されるネットワーク図の幅や高さは、ウインドウのサイズと同じになる。EPSやSVGを利用する際、画素のプロパティはExport -> Optionsで行える。

BMP形式は、ファイルサイズが非常に大きいので、適当なグラフィックソフトを使って画像圧縮して別の保存形式に変換する。オススメなのはPNG (Portable Network Graphics)である。PNGは特にWWWでの利用に焦点を置いており、可逆方式でデータを圧縮し、圧縮効率はGIFより高く、より美しくインターレース表示できるようになっている。Word文書にもそのまま貼り付けられる。


3. Rによる統計処理

Pajek から統計ソフトRへ送られたネットワーク行列とベクトルの解析例を示す。ベクトル v1, v2, v3 とネットワーク (行列) n1, n2, n3がPajekからRに送られたとする。Rでは、これらベクトルや行列の演算は非常に簡単なコマンドで行える。以下、行頭の”>”はRのプロンプトを表す。

3.1. ベクトル演算

ベクトルの加減乗除など

> v1+v2
> vsum <- v1+v2
> v1sq <- v1^2
> a <- sqrt(v1*v2)
...


3.2. 基本的な統計処理

var：分散, cov：共分散, cor：相関

> sum(v1)
> length(v1)
> mean(v1)
> summary(v1)
> var(v1)
> cov(v1,v2)
> cor(v1,v2)


3.3. グラフィクス

ベクトルのプロットやヒストグラム表示

> plot(v1)
> plot(v1,v2)
> boxplot(v1,v2)
> hist(v1)

ヒストグラムの階級幅はbreaksの値を変えればよい(詳しくは、R入門などを参照)。

> hist(v1,br=0:10)

や

> hist(v1, br=-1:10)

などとする。


3.4. グラフ出力

pdf フォーマット

> pdf("c:/temp/test.pdf")
> hist(v1)
> dev.off()

ps フォーマット

> postscript("c:/temp/test.ps")
> hist(v1)
> dev.off()

Windows meta フォーマット

> win.metafile("c:/temp/test.wmf")
> hist(v1)
> dev.off()


3.5. 二変量・多変量解析

クロス集計 (cross-tabulation)

> table(v1,v2)

カイ二乗検定 (chi-square test)

> tabl <- table(v1,v2)
> summary(tabl)

t-検定 (t-test)

> t.test(v1,v2)

等分散性の検定 (F-test)

> var.test(v1, v2)


3.6. 回帰

線形モデリング

> linm <- lm(v1 ~ v2)
> summary(linm)

変数が増えた場合

> linm <- lm(v1 ~ v2 + v3)
> summary(linm)

非線形回帰

> nlm <- lm(v1 ~ v2 + v3^2)
> summary(linm)


3.7. 行列演算

行列の転置 (Transpose network)

> t(n1)

固有値および固有ベクトル (eigenvalues/eigenvectors)

> eigen(n1)

Hub と authority

> hubs <- eigen(n1 %*% t(n1)) $ vec[,1]
> auth <- eigen(t(n1) %*% n1) $ vec[,1]



Appendix 1. Pajekのデータ構造

Pajekが用いる6つのデータ構造

network メインのオブジェクト (nodeとedge)
permutation nodeの交換・再配列
vector ノードの値
cluster ノードの部分集合
partition 各ノードに対して、属しているノードをクラスタリングして分ける
hierarchy クラスタとノードを階層的に並べる

Pajekはこの6つのデータ構造間の異なる移り変わりをサポートしている種々の変換を基礎に置いている。



Appendix 2. Pajekのアルゴリズム実装

実装されているアルゴリズム例

・partitions: 次数 (degree)、深さ (depth)、コア (core)、p-クリーク (p-cliques)、中心性 (centers)
・binary operations: union, intersection, difference;
・components: strong, weak, biconnected, symmetric [1];
・decompositions: symmetric-acyclic;
・paths: 最短距離 (shortest path)、2頂点間のすべての経路 [11]
・flows: 2頂点間の最大フロー [14]
・citation weights: Paths Count Method and SPLC Method [2];
・neighbourhood: k-隣接点 (k-neighbours)
・CPM (Critical Path Method);
・extracting subnetwork;
・shrinking clusters in network (generalized blockmodeling) [4]
・reordering: topological ordering, Richards’s numbering, depth/breadth first search;
・reduction: 階層 (hierarchy)、細分割 (subdivision)、次数 (degree)
・simplifications and transformations: ループの削除、多重線、エッジに対する弧を変形する


References
[1] AHO, A. V., HOPCROFT, J. E., ULLMAN, J. D. (1976): The Design and Analysis of ComputerAlgorithms. Addison-Wesley, Reading, MA.
[2] BATAGELJ, V. (1994): An Efficient Algorithm for Citation Networks Analysis. Presented at EASST’94, Budapest, Hungary, August 28-31, 1994.
[3] DATTA, B. N. (1995): Numerical Linear Algebra and Applications. Brooks&Cole Publishing Company, Pacific Grove.
[4] DOREIAN, P., BATAGELJ, V., FERLIGOJ, A. (1994): Partitioning Networks Based on Generalized Concepts of Equivalence. Journal of Mathematical Sociology, 19, 1, 1-27.
[5] GOLUB, G. H., van LOAN, C. F. (1996): Matrix Computations. The John Hopkins University Press, Baltimore.
[6] FRUCHTERMAN, T. M. J., REINGOLD, E. M. (1991): Graph Drawing by Force-Directed Placement. Software, Practice and Experience, 21, 1129-1164.
[7] HUMMON, N. P., DOREIAN, P. (1989): Connectivity in a Citation Network: The Development of DNA Theory. Social Networks, 11, 39-63.
[8] HUMMON, N. P., DOREIAN, P. (1990): Computational Methods for Social Network Analysis. Social Networks, 12, 273-288.
[9] HUMMON, N. P., DOREIAN, P., FREEMAN, L. C. (1990): Analyzing the Structure of the Centrality-Productivity Literature Created Between 1948 and 1979. Knowledge: Creation, Diffusion, Utilization, Vol. 11, June, No. 4, 459-480.
[10] KAMADA, T., KAWAI, S. (1989): An Algorithm for Drawing General Undirected Graphs. Information Processing Letters, 31, 7-15.
[11] KNUTH, D. E. (1993): The Stanford GraphBase. Stanford University, ACM Press, New York.
[12] PETERSON, J. L., (1981): Petri Net Theory and Modeling of Systems. Prentice-Hall, Inc., Englewood Cliffs, N.J.
[13] ROGERS, E. M., KINCAID, D. L. (1981): Communication Networks, Toward a New Paradigm for Research. The Free Press, New York.
[14] TARJAN, R. E. (1983): Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics Philadelphia, Pennsylvania.
[15] WATSON, A. H., MCCABE, T. J. (1996): Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric. Computer Systems Laboratory, National Institute of Standards and Technology Special Publication 500-235, Gaithersburg, MD 20899-0001.
[16] WHITE, D. R., JORION, P. (1992): Representing and Analyzing Kinship: A New Approach. Current Athropology 33, 454-462.
[17] WHITE, D. R., JORION, P. (1996): Kinship Networks and Discrete Structure Theory: Applications and Implications. Social Networks 18, 267-314.
[18] Erd¨os Number Project:
http://www.oakland.edu/%7Egrossman/erdoshp.html
[19] GEDCOM Standard:
http://www.gendex.com/gedcom55/55gcint.htm
[20] Graph Drawing Competition 1996, Graph B:
http://portal.research.bell-labs.com/orgs/ssr/people/north/contest.html
[21] p-graphs:
http://eclectic.ss.uci.edu/%7Edrwhite/pgraph/p-graphs.html
[22] Plug-in Chime:
http://www.mdli.com/download/chimedown.html
[23] Plug-in Cosmo Player:
http://cosmosoftware.com/
[24] KNUTH, D. E.: Dictionary. Stanford University, Computer Science Department:
ftp://labrea.stanford.edu/pub/dict/
[25] Program GSView:
ftp://ftp.cs.wisc.edu/pub/ghost/rjl/
[26] Program Mage:
http://www.prosci.org/Kinemage/MageSoftware.html
[27] Program MODEL2:
http://vlado.fmf.uni-lj.si/pub/networks/stran/default.htm
[28] Program RasMol (RASter MOLecules):
http://klaatu.oit.umass.edu/microbio/rasmol/getras.htm
[29] SMITH, M. A. (1996): NetScan, Department of Sociology, UCLA:
http://www.sscnet.ucla.edu/soc/csoc/netscan/netscan.htm
[30] Theoretical Computer Science Genealogy:
http://sigact.acm.org/genealogy/
[31] Transportation Networks, National Transportation Atlas Database, Bureau of Transportation Statistics:
http://www.bts.gov/gis/ntatlas/networks.html
[32] American Presidents GEDCOM file:
ftp://www.dcs.hull.ac.uk/public/genealogy/