R でグラフ理論


CRAN Task View: gRaphical Models in R

  • グラフの表現、操作および表示
    • 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 ベース).
    • mathgraph [vignette: n; demo: n] グラフのマトリックス表現の実装及び作図に関するものを提供.
    • diagram [vignette: n; demo: y] 単純なグラフ(ネットワーク)の可視化、流れ図の作図のための関数
    • giRaph [vignette: n; demo: y] グラフ表現と操作のためのクラスと関数を与える
    • igraph [vignette: n; demo: n] シンプルなグラフ、ネットワーク解析用ルーチン.
    • dagR: R functions for directed acyclic graphs
  • 古典的モデル − 汎用パッケージ
    • gRbase [vignette: y; demo: y] いくつかの他のパッケージ(これらには mimR とgRainが入る)が用いているメタデータのセットアップ。gRbase はモデルとあてはめエンジンの実装方法を示す。これは階層対数モデルで解説している。
    • 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] グラフィカルガウシアンモデルの当てはめ
  • 雑多な事柄:モデルの探索、特化したモデルタイプ等
    • SIN [vignette: n; demo: n] ガウスグラフィカルマルコフモデルでの SIN モデルの選択.
    • pcalg [vignette: y; demo: n] 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] エッジとバーテクッスの対象性をもちいたグラフィカルガウスモデルの推定(色つきグラフィカルガウスモデル).
    • rggm [vignette: n; demo: n] ガウスグラフィカルモデルの頑健化手法.
    • 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.
  • ベイズネットワーク/確率的エキスパートシステム
    • gRain [vignette: y; demo: n] グラフィカルモデル(ベイジアンネットワーク)の伝播(メッセージ受け渡し)の実装
    • deal [vignette: n; demo: n] 混合(離散」および連続)変数のベイズネットワーク学習
  • 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).
    • coda [vignette: n; demo: n] MCMC の出力分析及び診断.
    • bayesmix [vignette: n; demo: n] JAGS を使ったベイズ混合モデル
    • bnlearn [vignette: n; demo: n] ベイズネットワーク構造学習
    • G1DBN [vignette: n; demo: n] 動的ベイズネットワーク推定実行パッケージ.
    • ergm [vignette: n; demo: n] ネットワークのための指数族モデルのあてはめ、シミュレートおよび診断
  • classGraph: S4 クラス階層のグラフの構築
  • 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

パッケージ

  • igraph [#y9deba80]  大規模なグラフに対応。最短経路探索はあるがパスのみで距離には対応していない。
  • P.グリッツマン, R.ブランデンベルグ 著, 石田基広 訳(2007): 最短経路の本 レナのふしぎな数学の旅, シュプリンガー・ジャパン, 東京、のなかにある例題を解いてみました。
    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)
    shortest.jpg
    左の図が与えられたグラフです。いま求めたいのは、sからzへの最短経路です。辺の上にある正の数は重みを表し、実際には所要時間に相当します。igraphでは、2つのノードを直接結ぶ辺を複数持つ、多重グラフがうまく表現できないのが難点です。
    右の図では、get.shortest.paths()で求めた最短経路を示す辺を太くし、通過するノードを赤く塗っています。
    また、ノード上の数字は、shortest.paths()で求めた、sからの最短距離を表します。
  • network: Classes for Relational Data

応用例

参考

  • R で社会ネットワーク分析?

参考書

コメント欄

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


添付ファイル: fileshortest.R 790件 [詳細] fileshortest.jpg 1805件 [詳細]

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Google
WWW を検索 OKADAJP.ORG を検索
Last-modified: 2015-03-01 (日) 01:15:59 (1544d)