R でグラフ理論の編集

COLOR(red){SIZE(25){R でグラフ理論}}

#contents
----

*[[CRAN Task View: gRaphical Models in R:http://cran.at.r-project.org/web/views/gR.html]] [#e3b1db3c]
-グラフの表現、操作および表示
//-(Representation, manipulation and display of graphs)
-- graph [vignette: y; demo: n] グラフデータ構造を取り扱うパッケージ.
-- RBGL [vignette: y; demo: n] C++ グラフライブラリインターフェース (graph パッケージの graph オブジェクトベース).
-- gRain [vignette: y; demo: y] graph の代替インターフェース. graph と RBGL を使い、追加のグラフ操作を実装.
-- dynamicGraph [vignette: n; demo: y] グラフを使った表示と対話のための高度なグラフィカルユーザインターフェースを提供する(Tcl/Tk ベース).
//-- dynamicGraph [vignette: n; demo: y] Provides an advanced graphical user interface for display and interaction with graphs (based on Tcl/Tk).
-- mathgraph [vignette: n; demo: n] グラフのマトリックス表現の実装及び作図に関するものを提供.
-- diagram [vignette: n; demo: y] 単純なグラフ（ネットワーク）の可視化、流れ図の作図のための関数
//-- diagram [vignette: n; demo: y] Functions for visualising simple graphs (networks), plotting flow diagrams
-- giRaph [vignette: n; demo: y] グラフ表現と操作のためのクラスと関数を与える
//-- giRaph [vignette: n; demo: y] Supply classes and methods to represent and manipulate graphs
-- igraph [vignette: n; demo: n] シンプルなグラフ、ネットワーク解析用ルーチン.
--dagR: R functions for directed acyclic graphs
-古典的モデル　−　汎用パッケージ
//-Classical models - General purpose packages）
-- gRbase [vignette: y; demo: y] いくつかの他のパッケージ（これらには mimR とgRainが入る）が用いているメタデータのセットアップ。gRbase はモデルとあてはめエンジンの実装方法を示す。これは階層対数モデルで解説している。
//Sets up a meta data representation which is used by several other packages (among these are mimR and gRain). gRbase suggests a way to implement models and fitting engines - illustrated by hierarchical log-linear models.
-- mimR [vignette: n; demo: n] General package for model selection in contingency tabels, graphical Gaussian models and mixed interaction models. The package provides an interface to the MIM program and only runs on Windows.
-- CoCo [vignette: n; demo: y] An advanced suite of functions for contingency tabels, graphical Gaussian models and mixed interaction models.
-- ggm [vignette: n; demo: n] グラフィカルガウシアンモデルの当てはめ
//Fitting graphical Gaussian models.

-雑多な事柄：モデルの探索、特化したモデルタイプ等
//-(Miscellaneous: Model search, specialized types of models etc.)
-- SIN [vignette: n; demo: n] ガウスグラフィカルマルコフモデルでの SIN モデルの選択.
//-- SIN [vignette: n; demo: n] SIN model selection in Gaussian graphical Markov models.
-- pcalg [vignette: y; demo: n] DAG のスケルトンと等価の推定
//-- pcalg [vignette: y; demo: n] Estimating the skeleton and equivalence class of a DAG
-- qp [vignette: n; demo: n] q-order partial correlation graph search algorithm. A robust procedure for structure learning of undirected Gaussian graphical Markov models from "small n, large p" data.
-- gRc [vignette: n; demo: n] エッジとバーテクッスの対象性をもちいたグラフィカルガウスモデルの推定(色つきグラフィカルガウスモデル).
//-- gRc [vignette: n; demo: n] Inference in graphical Gaussian models with edge and vertex symmetries (Graphical Gaussian models with colours).
-- rggm [vignette: n; demo: n] ガウスグラフィカルモデルの頑健化手法.
//-- rggm [vignette: n; demo: n] Robustified methods for Gaussian Graphical Models.
-- GeneNet [vignette: n; demo: n] Modeling and Inferring Gene Networks. GeneNet is a package for analyzing gene expression (time series) data with focus on the inference of gene networks.

-ベイズネットワーク/確率的エキスパートシステム
//-(Bayesian Networks/Probabilistic expert systems )
-- gRain [vignette: y; demo: n] グラフィカルモデル（ベイジアンネットワーク）の伝播（メッセージ受け渡し）の実装
//Implements propagation (message passing) in graphical models (Bayesian networks).
-- deal [vignette: n; demo: n] 混合（離散」および連続）変数のベイズネットワーク学習
//Learning Bayesian networks with mixed (discrete and continuous) variables.

-BUGS モデル
-- R2WinBUGS [vignette: y; demo: n] R / S-PLUS より WinBUGS と OpenBUGS を実行
-- rbugs [vignette: n; demo: n]  と OpenBugs のフュージョン
-- BRugs [vignette: n; demo: n] Provides an R interface on Windows machines to OpenBUGS. It works only under Windows and used to be available from CRAN, now it is located at the CRANextras repository.
-- boa [vignette: n; demo: n] MCMC のためのベイズ出力分析 (BOA).
//-- boa [vignette: n; demo: n] Bayesian Output Analysis Program (BOA) for MCMC.
-- coda [vignette: n; demo: n] MCMC　の出力分析及び診断.
//-- coda [vignette: n; demo: n] Output analysis and diagnostics for MCMC.
-- bayesmix [vignette: n; demo: n] JAGS を使ったベイズ混合モデル
//-- bayesmix [vignette: n; demo: n] Bayesian Mixture Models with JAGS
//-- bayesmix [vignette: n; demo: n] JAGS をもちいたベイズ混合モデル
-- bnlearn [vignette: n; demo: n] ベイズネットワーク構造学習
//-- bnlearn [vignette: n; demo: n] Bayesian network structure learning
-- G1DBN [vignette: n; demo: n] 動的ベイズネットワーク推定実行パッケージ.
//-- G1DBN [vignette: n; demo: n] A package performing Dynamic Bayesian Network inference.
-- ergm [vignette: n; demo: n] ネットワークのための指数族モデルのあてはめ、シミュレートおよび診断
//Fit, Simulate and Diagnose Exponential-Family Models for Networks

-classGraph: S4 クラス階層のグラフの構築
//Construct Graphs of S4 Class Hierarchies

-degreenet: Models for Skewed Count Distributions Relevant to Networks

-brainwaver: Basic wavelet analysis of multivariate time series with a visualisation and parametrisation using graph theory

*パッケージ [#c492103e]
-igraph [#y9deba80]
　大規模なグラフに対応。最短経路探索はあるがパスのみで距離には対応していない。

- [[P.グリッツマン, R.ブランデンベルグ 著, 石田基広 訳(2007): 最短経路の本 レナのふしぎな数学の旅, シュプリンガー・ジャパン, 東京:http://www.springer.jp/japan/math/j10011.html]]、のなかにある例題を解いてみました。~
igraphを使ってグラフを描画し、ダイクストラのアルゴリズムをつかって、sからzまでの最短経路を求める。
 library(igraph)
 #エッジリストの作成
 d <- data.frame(matrix(c( "s","a", "s","b", "a","b", "a","c", "a","d", "b","a", "b","c", "b","d", 
                           "c","d", "c","e", "c","f", "d","a", "d","b", "d","f", "e","d", "e","z",
                           "f","e", "f","z"),nc=2,byrow=TRUE),stringsAsFactors=FALSE)
 colnames(d) <- c("from","to")
 #ノードリストの作成
 vers <- data.frame(c("s","a","b","c","d","e","f","z"),stringsAsFactors=FALSE)
 #グラフの作成
 g <- graph.data.frame(d,directed=TRUE,vertices=vers)
 #ウエイトの指定
 E(g)$weight <- c(3,5,1,10,11,3,2,3,2,7,12,15,7,2,11,2,3,2)
 #ノードの座標の指定
 vs <- c(1,2); va <- c(3,3); vb <- c(3,1); vc <- c(5,3); vd <- c(5,1); ve <- c(7,3); vf <- c(7,1); vz <- c(9,2)
 lay <- rbind(vs,va,vb,vc,vd,ve,vf,vz)
 #プロット
 par(mfrow=c(1,2),oma=c(0,0,0,0))
 plot(g,layout=lay,vertex.label=V(g)$name,edge.label=E(g)$weight)
 #最短経路の計算
 spv <- shortest.paths(g, v=0,mode="out")
 sp <- get.shortest.paths(g,from=0,to=7)
 V(g)$color <- "lightblue" 
 V(g)$color[(unlist(sp)+1)] <- "red" 
 E(g)$width <- 1
 E(g,path=unlist(sp))$width <- 3
 plot(g,layout=lay,vertex.label=spv,edge.label=E(g)$weight)
#ref(shortest.jpg)
左の図が与えられたグラフです。いま求めたいのは、sからzへの最短経路です。辺の上にある正の数は重みを表し、実際には所要時間に相当します。igraphでは、２つのノードを直接結ぶ辺を複数持つ、多重グラフがうまく表現できないのが難点です。~
右の図では、get.shortest.paths()で求めた最短経路を示す辺を太くし、通過するノードを赤く塗っています。~
また、ノード上の数字は、shortest.paths()で求めた、sからの最短距離を表します。

-graph@BioConductor

-RGraphViz@BioConductor
　可視化パッケージ

-network: Classes for Relational Data

*応用例 [#n4dfd337]
-[[統計的にテキスト解析(6)〜語のネットワーク分析〜:http://mjin.doshisha.ac.jp/R/200808_61.pdf]] 共起ネットワーク

*参考 [#ude51543]
-[[R で社会ネットワーク分析]]

*参考書 [#x844b066]
-[[ネットワーク分析 - Rで学ぶデータサイエンス :http://www.kyoritsu-pub.co.jp/series/arudemanabu.html]], 鈴木　努　著、共立出版、2009?

*コメント欄 [#u45c20ba]

- igraphパッケージで最短経路を示すグラフを描いてみました。 -- ザブ &new{2008-09-27 (土) 09:38:12};
- 素晴らしい．とても参考になります． graph.data.frame関数にvertices引数が追加されているとは知りませんでした． -- [[ishida]] &new{2008-09-27 (土) 12:13:42};
- ありがとうございます。そうなんです、vertices引数を指定しなくともエラーにはなりませんが、ノード名の自然な順番(s,a,b,...,f,z)が崩れて、後で面倒な事になります。 -- [[ザブ]] &new{2008-09-27 (土) 12:42:45};
- R2.5.1 Win32 版で、"g <- graph.data.frame(d,directed=TRUE,vertices=vers) "で、" 以下にエラーgraph.data.frame(d, directed = TRUE, vertices = vers) :           使われていない引数 (vertices = list(c..s....a....b....c....d....e....f....z.. = c("s", "a", "b", "c", "d", "e", "f", "z"))) "とエラーが出て処理が終わってしまいます。 --  &new{2008-10-01 (水) 15:08:51};
- 私も最初同じエラーに遭遇しました．vertices引数は最近サポートされたようです．igraph，またRを最新版にupdateして試してみてください． -- [[ishida]] &new{2008-10-02 (木) 07:51:50};
- ↑ご返答ありがとうございます。CRAＮからパッケージを直接ダウンロードしてインストールしたところ、2.5.1でも動作しました。 --  &new{2008-10-02 (木) 14:30:40};

#comment()

タイムスタンプを変更しない