R でグラフ理論
の編集
http://www.okadajp.org/RWiki/?R+%E3%81%A7%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96
[
トップ
] [
編集
|
差分
|
バックアップ
|
添付
|
リロード
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
]
-- 雛形とするページ --
(no template pages)
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では、2つのノードを直接結ぶ辺を複数持つ、多重グラフがうまく表現できないのが難点です。~ 右の図では、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}; - ↑ご返答ありがとうございます。CRANからパッケージを直接ダウンロードしてインストールしたところ、2.5.1でも動作しました。 -- &new{2008-10-02 (木) 14:30:40}; #comment()
タイムスタンプを変更しない
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では、2つのノードを直接結ぶ辺を複数持つ、多重グラフがうまく表現できないのが難点です。~ 右の図では、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}; - ↑ご返答ありがとうございます。CRANからパッケージを直接ダウンロードしてインストールしたところ、2.5.1でも動作しました。 -- &new{2008-10-02 (木) 14:30:40}; #comment()
テキスト整形のルールを表示する
添付ファイル:
shortest.jpg
2615件
[
詳細
]
shortest.R
1139件
[
詳細
]