グラフ

クリークを探せ

クリークとは、グラフの一部(部分グラフ)であって、その部分グラフのすべてのノード間にエッジがあるようなもの これの探索には、1970年台に出たBron-Kerboschアルゴリズムというものが、現在も使われている。 Wikipedia 原論文 Bron-Kerboschアルゴリズムの…

Cytoscape

発現解析に限定せず、グラフ可視化に転用しやすいとよいのだが・・・ すくなくともオープンソースで、Javaで、ネットワーク〜グラフで、可視化 こちら Javaソースをダウンロードして、解凍、その後、eclipseで適当な名称で、Javaプロジェクトを新規作成。プ…

ただのメモ

kd木 BSP木とバイナリ空間分割

グラフレイアウト

数多くの要素について、要素をノードで、要素間の関係をエッジで表したものをグラフという。 グラフはこの定義からもわかるように、図示することが本質ではない。 本質ではないけれども、図示することで、「全体が持つ情報を的確に捕らえる」ことの手助けが…

VGJ

VGJもやはりよい。 VGJのサイトはこちら ダウンロードして、 1. コマンドプロンプトへ行って、 2. hogehoge\graph_drawing に入って、 3. java EDU.auburn.VGJ.VGJたとえば、Windowsで "C:\download\VGJ\graph_drawing"に置いてあるとすれば、以下のような2…

Graphviz

書式情報を入れてみる graph sample { N0 [color=red]; N1 [color=red]; N2 [color=red]; N3 [color=red]; N4 [color=red]; N5 [color=red]; N6 [color=red]; N7 [color=red]; N8 [color=red]; N9 [color=blue]; N10 [color=blue]; N11 [color=blue]; N12 [c…

Graphviz

ホームページはこちら Windowsで使うには、ダウンロードサイトから、Windows用の自己解凍形式のファイルを入手して、自己解凍に任すだけ。 デフォルトでは(WindowsXP)、"C:\Program Files\Graphviz2.20"にインストールされて、サンプルファイルが"C:\Program…

最短距離

距離"-1"はエッジなしに相当 public class WarshallFloyd { public static int[][][] WFshortestDist(int[][] a){ int n=a.length; int[][] dist=StatUtilsX.MiscUtilX.DeepCopyInt2(a); int[][] pred=new int[n][n]; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(dist[i][j]>0){ pred[i][j]=j; }else{</n;i++){>…

グラフの距離

グラフの点の間の最短距離は ある点から、グラフ上のそれへの距離はDijkstraがある すべての点ペアについてのそれはWarshall-Floydがある jakarta commons-graph があるらしいが、in dormant... 最短ではなくて平均距離は・・・全パスを網羅して、均す・・・…

Smart Game Format

囲碁・オセロなどの対戦ゲームでは、交互に「イベント」があり、それによって、「状態」が変化する。この過程を履歴として残したものが、棋譜である。これをアプリケーションで用いるときのフォーマットのひとつがSGFである。 「木」構造をとっているという…

グラフィカルモデリング

多変量解析の1手法にグラフを基にしたグラフィカルモデリングがある。 確率変数を頂点とするグラフ 確率変数同士は、独立であるか、条件付独立であるかによって、グラフ上での、つながり方が定められる 確率変数同士の関係を辺で表す グラフの辺には、無向…

Semi-graphoid

convex rank test について昨日の記事で書いたが、このconvex rank test は、次のような概念を用いる。 とりうるすべての順列は、Sn-fanと呼ばれる扇(fan)構造になぞらえることができ、その考え方の枠組みの中で、convex rank test とは、このSn-fanの一部の…

後で見るメモ

シリーズ概説リンク シリーズトップページリンク

熱伝導方程式と差分法

PCクラスタについては、過去にもいくつか記事を書いた。こちらやこちら。 グラフは、複雑な関係にある事象を比較的単純に表す便法である。 グラフは簡単に言うと、ノードとエッジで表せる状態である。これにある色づけをするとすると、ノードに局所状態をエ…

集合のグラフ表現

べき集合 k個の要素を持つ集合のべき集合はある。 べき集合の要素(それぞれが部分集合)が半順序の性質を持ち、その中でも特別の性質を持つ束であることは、この記事(順序集合と束)とこの記事(部分集合の束のグラフ表現)で書いた。 部分集合の関係がグラフに…

支配集合

グラフG=(V,E)がある。今、Vの部分集合Wを考える。Vの要素のすべてがWの要素であるか、もしくは、Wの要素のどれかひとつに隣接しているとき、WをGの支配集合と言う。 グラフGの頂点の数をnとする。n個の頂点の次数(接続する辺の数)の最小数(Gの最低次数)をp …

助走(駆け足で読むために) Bayesisn Graphical Models for Discret

伴走資料はこちら イントロダクション 離散的データ 観測現象は、カテゴリカルに記録される。たとえば現象を観測すると、複数のカテゴリがあって、そのいずれかである。 ベイズ を観測したらだった。そのあとに影響されるを観測したらだった。そのあとに影響…

Markov blanket

サイクルを持たない有向グラフを考える。向きを持つ辺の出る側の点を親、入る側の点を子と呼ぶことにする。このようなグラフにはモラルグラフなるものが定められる。 モラルグラフでは、同一の点の親同士の間に辺を与え、すべての辺の向きを取り除いたもので…

Bayesian Graphical Models for Genomewide Association studies

論文はAJHG 79 100-112, 2006 (こちら) Bayesian Graphical Modelがわかっていないと、Methodsの途中から式が不明になるので、とりあえず、モデル自体の調べ物を・・・ サイト(英語) 文献 書籍 Graphical Models: Methods for Data Analysis and Mining 作者…

アルゴリズムグラフの耳分解 2.3 連結性 (グラフ) 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム

グラフがある。それは、次のようにできているとみなせるとする。 1つの閉路がある。これをG0とする。その閉路と1点のみを共有する閉路か、その閉路と2点のみをい共有するパスがある。このG0+閉路またはパスをG1とする。このG1|G0(G1からG0をのぞいた部分…

2.3 連結性 (グラフ) 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム

グラフの実装表現 接続行列表現 行に点、列に辺をとり、点が辺の端点なら1(始点なら1、終点なら−1)、そうでなければ、0 必要領域:O(点の数x辺の数) 隣接行列表現 行と列に点をとり、点のペア間に辺があれば1、なければ0。向きを考慮するときは辺があ…

2.2 木、閉路、カット (グラフ) 駆け足で読む B.コルテ/J.フィーゲンの 組合せと最適化-理論とアルゴリズム

グラフにおける閉路とカット 閉路はぐるっと一巡するタイプのグラフ 定義としては、点と辺を交互にたどってもとの点に戻ってくるような点と辺の集合である。ただし、このとき点と辺はそれぞれ1度ずつしか使用しないし、1度は使用するものとする。 カットは…

完全グラフの行列表現

完全グラフは,各頂点がすべてのほかの頂点に隣接する。完全グラフには自己ループはない。したがって、その行列表現は、主対角線成分が0で、それ以外の成分が1である 参考(Mathematica 日本語サイト)

公開パスウェイをグラフとして取り込みなおす

KEGGはこちら 分子パスウェイが公開されている ヒトのT細胞受容体のパスウェイの図はこちら(データベースリンクト) テキストで情報を使うなら、こちらから該当ファイルを取得 グラフ関連公開アプリケーション(こちらとこちら)に使わせていただいているVGJに…

ほんのメモ

分子間結合力を応用した、ノード配置の最適化に関する記事(こちら) フックの法則(すべてのものはバネであり、位置で微分したものが力を与えるとき、その力がどんな形式であっても、極小付近ではフックの法則が成り立つ)についてはこちら さらに数式的解説は…

グラフの問題は難問が多い

グラフの問題には、アルゴリズム上の難問が多く知られている。アルゴリズム上の難問は計算量などによって定義・分類されるが、そのための基礎知識のために『アルゴリズムと計算量』(臨時別冊 数理科学 SGCライブラリ43)谷 聖一 サイエンス社おすすめ度★★★☆☆…

ネットワーク流

ネットワーク流のグラフでのモデル化には、いくつかの要素を付加する必要がある。ソース(湧出点)とシンク(吸収点)と呼ばれる特殊な2点である(ソースとシンクがそれぞれ1つずつの場合もあれば、これらが複数の場合もある)。また、グラフは重み付き有向グラ…

強連結成分

連結な有向グラフで、有向閉路が存在するとき、ノード同士の関係には、相互に到達可能な関係と、片方のノードから到達可能ながらその逆は到達不能であるような関係の2種類が存在する。相互に到達可能なノードの組を強連結成分とすると、連結な有向グラフは…

連結

連結 グラフを連結成分に分けるには、グラフ探索法により、連結・非連結の判定が必要で、網羅探索をする必要がある。工夫の余地は、連結情報の表現方法であろう。例としては以下のようなものが考えられる 単純に連結成分ごとに保管する方法 ノードに値を与え…

『Algorithms in C アルゴリズム 第3巻 グラフ・数理・トピックス』近代科学社 R.セジウィック 著 野下浩平・星守・佐藤創・田口東 共訳 おすすめ度★★★★☆、ただし、新版が出ている模様。 3分冊の1冊 アルゴリズムC〈第3巻〉グラフ・数理・トピックス 作者…