グラフ

木グラフの流量計算

木グラフがあって、そこに確率質量分布があるとする 木グラフは不変で、別の確率質量分布に変化したとする どのエッジをどれだけのフローがあったかを計算するには、エッジ数xエッジ数(ノード数ー1の二乗)の正方行列を用いた連立方程式の解で出す library(…

2次元空間にベルヌーイ事象の確率関数が広がっているとする その2次元空間で事象を観察すると、値0/1を持つ点が散在したデータが得られる その点の2次元空間におけるドロネー図を描き、そのドロネー図グラフにおける点間距離を定める そうすることで、各…

異次元接続

こちらでポイントクラウドデータをグラフ化して、そこに交通量ベクトルを計測する話を書いた ポイントクラウドの次元を局所推定する、みたいなトピックの一環 方法がうまく行っているのかを確かめるために、異なる次元に移り変わるような分布とそこからの標…

文書を管理する

ルール 文書を管理することにする 多くはSweave経由のてふ文書、ときおり、それ以外の文書 文書間の連携に意味を持たせたい 以下をUTF-8で保存して dot -Kdot -Tpng mybookFlow.txt -o mybookFlow.png とコマンドでpngファイル作成 digraph docs{ graph[char…

DOT language一通り

基本のき 最後の行の末尾も改行しておこう! 空のグラフ(無向グラフはgraph、有向グラフはdigraph、自身へのエッジを許さないのであればそれぞれstrict graph, strict digraph グラフに名前はつけることを自分の中でのルーチンにしておこう graph{}graph hog…

リンクでバインドした文書セット

文書をグラフ状にバインドし、それをグラフ視覚化ツールで視覚化しsvgに保存しつつ、ノード(エッジからも可能)から文書へハイパーリンクを張る、という実験を昨日まで、あれやこれややっている。 こんなsvgができます(PDFファイルへのリンク)。 掲載図はただ…

連携のある文書群を提示する

こちらまでで、いろいろごちゃごちゃやってきた 調べ物を進めると、確かに、ネットワーク研究とかが進んで、ツールは増えているけれど、Graphvizはそれらの基礎に(いまだに)使われているし、いろんなことをカスタマイズするために、良いツールであることがわ…

連携のある文書群を提示する

こちらで文書間連携情報つきで複数文書を提示する話をしている 文書はPDFがよさそうで、たくさんのPDFをウェブ上で見せるには、evernoteの共有機能も悪くないかも(こちら)と思っているところ あとは、ビジュアルな表示 Gephiのノードラベルにhyperlinkを埋め…

ぱらぱらめくる『ゲーデル・エッシャー・バッハ』

Godel, Escher, Bach: An Eternal Golden Braid作者: Douglas R. Hofstadter出版社/メーカー: Basic Books発売日: 1999/02/04メディア: ペーパーバック購入: 4人 クリック: 20回この商品を含むブログ (7件) を見る よくわからない内容をわからないままに学習…

点の雲の主軸

高次元データのヒストグラムとか平滑化とかをやっている 意味合いとしては、高次元空間にたなびく雲のその「形の本体」が知りたい、というところに(今のテーマは)ある こんな風にしてみよう 最小全域木を描く その上ですべての点ペアの最短パスを決める 最…

ぱらぱらめくる『Interaction Combinators』

PDF この「ぱらぱら」のモチベーションは、「情報が入ってきて、決断する」というプロセスを整理するための道具として便利そうな印象があるから 決断を「回路」的に考える 計算機(チューリングマシンやcellular automataやrewrite systemsとかそういったもの…

n次元平面性グラフ

以前ZDDでのアルゴリズムの効率性を考えるときに「平面性グラフ」であることが登場した そのときに、より高次元の「平面性グラフ」の意味合いについてもちょっと考えた(こちら) n次元で「平面性なグラフ」:n次元でならば、交わることなく「きちんと描けるグ…

分割表

2x2の分割表を考える 2群の標本数が等しい分割表を考える 1群の標本数を1,2,..,i,.,nと増やす このとき、取りうるすべての分割表のパターン数は1群の標本数がiのとき、 1つ目の群が(0,i),(1,i-1),...,(i,0)となってi+1通り、もうひとつの群も同様にi+…

トーラスとは

トーラスはWikiで見れば曖昧さ回避ページ(こちら)があるように、色々な書き方がある 幾何・位相幾何・代数幾何での使い方は1つながりでまとめたい トーラスはドーナツのように「穴が一つ〜種数が1」の閉曲面 特にドーナツは『2-トーラス』 ここで言う『2-…

n次元平面性グラフ?

こちらで平面性グラフでのフロンティア構成ノード数の上限の話とか、それがSimPath/ZDDアルゴリズムとどういう関係にあるかについて触れた 一般化するのは悪くないので、フロンティアの一般化… 平面性グラフは2次元空間にエッジの交叉を作らないで埋め込む…

平面的なグラフ

ZDDとSimPathをやってみた(こちら) ZDDは「平面的なグラフ」で特に効果があるそうだ これは、いかにもそんな印象もあるけれど、その背景って…? 『平面分離定理』 頂点数nの平面(に描ける)グラフは、3つの頂点集合に分けることができて、その分け方ではフロ…

べたべたになぞってみる

ZDDは組み合わせの圧縮表現 Simpathはグラフの経路全網羅のためのZDD構築のアルゴリズム(こちら) アルゴリズムの説明をしてもらったけれど、どうやるのだか分らなかったのでRで、べたべたに書いてみることにする グラフがある を定める とエッジに順序を定め…

自分のイントロ ぱらぱらめくる『論理学をつくる』

論理学をつくる作者: 戸田山和久出版社/メーカー: 名古屋大学出版会発売日: 2000/10/10メディア: 単行本購入: 27人 クリック: 330回この商品を含むブログ (108件) を見る これを『ぱらぱらめくる』ことへのイントロ こちらやこちらで知識をグラフ・ハイパー…

知識の仕組み

"Listは再帰性を特徴とするデータ構造"という話からの「脱線」話題 知識を考える。こちらのように 切り口がいろいろあるのだが、この記事ではこんな風に考えてみることにする 知識はこれ以上小さくできないという「要素」が個あるものとする 個の要素の亜集…

目次:ぱらぱらめくる『Introduction to Graph and Hypergraph Theory』

目次 I Graphs II Hypergraphs I Graphs 1. Basic Definitions and Concepts 2. Trees and Bipartite Graphs 3. Chordal Graphs 4. Planar Graphs 5. Graph Coloring 6. Traversals and Flows II Hypergraphs 7. Basic Hypergraph Concepts 8. Hypertrees an…

II ハイパーグラフ:ぱらぱらめくる『Introduction to Graph and Hypergraph Theory』

Chap 7 ハイパーグラフの基礎概念 基礎の基礎 Vertices Hyperedges (Vertidesセット) 隣接は、同様のものの間の関係(Vertices間、Hyperedges間) Hyperedgesの隣接 VeritexとHyperedgeとの関係「Incident」 次数:ノードの次数、エッジの次数 Incidence とDua…

I グラフ:ぱらぱらめくる『Introduction to Graph and Hypergraph Theory』

グラフに関しては、ごく普通の記載

ぱらぱらめくる『Introduction to Graph and Hypergraph Theory』

Introduction to Graph and Hypergraph Theory作者: Vitaly I Voloshin出版社/メーカー: Nova Science Publishers発売日: 2009/05/13メディア: ハードカバー クリック: 3回この商品を含むブログを見る こちらでハイパーグラフについてかじったハイパーグラフ…

複体の場合の数

n個の要素があって、そのすべてが1つ以上の単体に属するものとして、何通りの複体が存在するかを考えてみる のときはの1通り のときはの2通り のときは,,,,の9通り のときは、114通りらしい のときは、『とても多い』らしい 何かうまい計算方法はないのだ…

ただのメモ

グラフGの上にサブグラフsを置く。サブグラフ上の走査とグラフ全体の走査との効率に値を与えるための仕組みは? グラフにおけるトポロジカル・インデックスの計算が漸化式化することと、グラフで表現した複体・部分集合に定める演算とに共通項がある? 演算…

メモ

############ ############ # のたくり雲作成 ここから ############ ############ # サンプル数 Ns <- 200 # マーカー数 Nm <- 50 # サンプルのパターン数(群数) Ns.pt <- Ns # マーカーのパターン数(群数) Nm.pt <- 5 # サンプル・マーカーの存在位置を多…

『グラフとは』、今さら

グラフは、 ノードの集合とエッジの集合の組である エッジはノードのペアで定まる 少し、言い換える グラフは、 ノードの集合とエッジの集合の組である ノードはグラフを構成する単位である ノードの数は非負の整数 エッジはノードのペアに定まる 1ノードの…

Rgraphviz

Graphvizはグラフ視覚化ソフト(こちら) RgraphvizはRでGraphvizを使うパッケージ(こちら) Graphvizのインストールはこちらを参考に ダウンロード先から"graphviz-2.28.0.msi 16-May-2011 14:48 58M"をダウンロード インストール用のファイルがとれるので、そ…

入れ子立方格子

昨日の記事で連結した複体を作ることとその隣接行列を作ることをやった 複体は、単体が連結・オーバーラップしたものだった 今日は、立方格子が同様に連結・オーバーラップしたものとしての「立方格子の入れ子構造(複体的)」というのを考えてみる 関連する話…

複体のグラフ表示

複体というのがある 単体の集合だ お絵かきしてみる 単体の隣接行列は、対角成分を0としそれ以外の成分はすべて1であるような行列である 複体は単体同士がより小さな単体を共有した形になっている したがって、次のようにランダムに作ることができる ノー…