グラフ

ランダム正則グラフを作る

ランダム正則グラフの隣接行列の作成方法がWikipediaにある(こちら) 次数rの正則グラフが、頂点数nだとする 今、個のアイテムをn個のバケツにr個ずつ入れる N個のアイテムを2個ずつのペアにする このようにすると、頂点数Nのr正則グラフができるが、このr正…

離散小部屋 拡散モデル グラフ・行列・隣接行列

ぱらぱらめくる『Random Walks on Disordered Media and their scaling limits』

Random Walks on Disordered Media and their Scaling Limits: École d'Été de Probabilités de Saint-Flour XL - 2010 (Lecture Notes in Mathematics)作者: Takashi Kumagai出版社/メーカー: Springer発売日: 2014/02/04メディア: ペーパーバックこの商品…

ぱらぱらめくる『Maps, Hypermaps and Related Topics』

PDF Preface Chapter 1 Maps and hypermaps Preface "Regular maps and hypermaps are cellular decompositions of closed surfaces exibiting the highest possible number of symmetries." Chapter 1 Maps and hypermaps グラフの定義を扱いやすくする 通…

グラフのモーメント

こんなペイパーがある グラフのモーメントと言うのを定義している 各ノードになる値が与えられているときに これをモーメントと呼ぶと言う 他にも定義があり、別の呼び名がある mean distance (平均距離) 。これはを全ノードで1に統一してモーメントを計算…

グラフスペクトル:隣接行列・ラプラシアン・Normal行列

グラフが持つ3つの正方行列(隣接行列・ラプラシアン・Normal行列)の固有値分解・スペクトル解析に関する短い文書をRで確かめる作業をしてみた

円周グラフの固有値スペクトル

円周をグラフで模す その隣接行列の固有値スペクトルはになる??? 固有ベクトルは、「調和関数?」のようなもの

行列の冪がばか大きくなる…

行列をべき乗した時の要素の大小を相対的に検討したい 単純にべき乗するとものすごく大きい数になって「計算できません」と言われてしまうことがあるので 固有値分解して、固有値を対数計算することにする 固有値の対数化をしてもまだ、ダメなので、固有値を…

隣接代数

こちらで代数的確率論・量子確率論のことを書いた その中に出てくる隣接代数というものを整理する 隣接行列とは、いわゆるグラフの行列のことで、エッジで結ばれたノードに対応する要素が1でそれ以外が0であるような行列のこと グラフは有限かも無限かもし…

ぱらぱらめくる『Geodesic Methods in Computer Vision and Graphics』

Geodesic Methods in Computer Vision and Graphics(amazon リンク) 著者PDF 目次 1 Theoretical Foundations of Geodesic Methods 2 Numerical Foundations of Geodesic Methods 3 Geodesic Segmentation 4 Geodesic Sampling 5 Geodesic Analysis of Shape…

グラフのゼータ関数 多様体上のゼータ関数 測地線 軌道

伊原のゼータ関数は測地線的なものの分布を扱っていると考えられるという でも、伊原のゼータ関数の説明を読むと、グラフのサイクルの話になっていて、必ずしも、測地線的なグラフパスだけではないように見える 多様体版のゼータ関数(Selbergのゼータ関数)の…

平面グラフを球面に貼り付ける

平面グラフは球面と同相 平面グラフのグラフ距離を球面の測地距離に合わせる(合わない残差は潔く捨てる)、という作戦で貼り付けてみる

グラフのボロノイ図

ボロノイ図は、空間をタイリングする。空間に「支配点」がおかれているときに、空間を最近接支配点の支配領域とする これをグラフに適用してみる

グラフのスペクトル解析

グラフのスペクトル解析をゼロからやってみるためのいくつかの資料 読みもの スライド newGRAPH(お手軽アプリ)

グラフのゼータ関数、ポセットのメビウス関数

メビウス関数についてこちらにメモした メビウス関数には(恒等関数である)ゼータ関数が対応するらしい そしてposetについて組みあわせべき集合の情報幾何をすると、メビウス関数とそれに対応するゼータ関数が登場して説明される 一方、このposetのゼータ関数…

ぱらぱらめくる『Zeta Functions of Graphs』

Zeta Functions of Graphs: A Stroll through the Garden (Cambridge Studies in Advanced Mathematics)作者: Audrey Terras出版社/メーカー: Cambridge University Press発売日: 2010/11/18メディア: ハードカバー クリック: 1回この商品を含むブログ (1件)…

グラフのゼータ関数 その後

資料 グラフのvertex zeta 関数はノード数xノード数の行列を使って以下のように表せる ただし、uは複素数、mとnはグラフGのエッジ数とノード数、はMの行列式で、Iはノード数xノード数の単位行列、AはGの隣接行列、DはGのノードの次数を対角成分とする対角…

斉次グラフ

次数3の斉次グラフ() 2頂点間に1本のエッジしか引かないものとする。エッジの2頂点は異なるものとする のノードを三角形と見立てれば、三角メッシュに相当する 四面体は頂点数4の完全グラフであって、である 正八面体は頂点数6のである 頂点数 n のは…

Four-dimensional graph-manifolds with fundamental groups quasi-isometric to fundamental groups of orthogonal graph-manifolds

グラフのペアワイズ最短距離と最短経路

グラフのペアワイズ最短距離が出したいことがある 密グラフならWarshall-Floyd、疎グラフならJonhsonが効率的という(参考) RのigraphパッケージもRGBLパッケージも最短距離は計算してくれるのだが、Warshall-Floydの行列が欲しい(どうしてほしくなるかはここ…

Weighted graph and its Laplacian

リンク

Rmdファイル『私のためのBrownian map構成法』

--- title: "ブラウニアンマップの構成" author: "ryamada" date: "2017年8月26日" output: html_document: toc: true toc_depth: 6 number_section: true --- ```{r setup, include=FALSE} library(rgl) library(knitr) knitr::opts_chunk$set(echo = TRUE)…

CRT上の酔歩ラベル付けとそれが表すメトリック〜ブラウニアンマップ『私のためのBrownian map構成法』

ブラウニアンラベルでは、上に値を貼り付ける ブラウン散歩での時刻0での点に対応するの点では、このラベルは0 ( そして、ラベル値Zは酔歩でランダムに決めるが、「どれくらい離れているときに、どれくらい遠くまで歩いているか」という意味合いで酔歩を決め…

ブラウン散歩はCRT『私のためのBrownian map構成法』

ブラウン散歩は、0から出発して0に戻る酔歩であって、正の値のみをとっているもの 特に、の時間範囲に限定したものがNormalized Brownian Excursion(標準ブラウン散歩) 今、時刻s,tにおける位置をのように書くことにしとする という値を、時刻sと時刻tとの「…

酔歩の掛け合わせとしてのContinuous Random tree とブラウニアンマップ『私のためのBrownian map構成法』

ブラウン散歩を木とみなすことで出来るのがCRT(Continuum Random Tree) そのCRTの上に酔歩を乗せて、それによって、木の各所に値をラベル付けすることで、「ラベル付けされたCRT」が出来上がる この「ラベル付けされたCRT」の点集合に点間距離が定義づけでき…

p-angulation n faces平面グラフとそのグラフ距離『私のためのBrownian map構成法』

Uniqueness and universality of the Brownian map(資料1) Random Geometry on the Sphere(資料2) The Brownian map is the scaling limit of uniform random plane quadrangulations(資料3) 平面グラフは、球面上の連結グラフであるので、平面グラフはorien…

トポロジー修復

こちらに3次元オブジェクトの画像データのトポロジー状態を変換する話があり、そのアプリも置いてある。Topomender この論文を眺めて、アルゴリズムを確認する 簡単のために 3D ボクセルデータであるとして、すべてのボクセルが0/1の値を持つものとする 0 …

ハーフエッジ データ構造

ポリゴンメッシュなどを扱うときに使われるデータ構造にハーフエッジデータ構造というものがある(こちら) グラフ構造だが、その特性に合わせて、エッジ中心に構成する すべてのエッジは二つの面に帰属することに注意する 構造 エッジがn/2本あるとき、これを…

木をサイクルに見立てる

木のグラフのルートノードから出発して、常に木を右手み見るようにして木の外周を巡れば、必ずルートノードに戻ってくるし、すべてのノードでエッジのたどり方が時計回りになっている。軌跡総距離は、全エッジの長さの和の2倍である これを木の時計まわりの…

三角メッシュの球面埋め込み 続き

昨日の記事で平面グラフの頂点座標の定め方をやった そこに連立方程式が出てきたが、それは、境界条件を外周頂点座標によって定めた上でのグラフ・ラプラシアン方程式を解く作業であると言える(離散ラプラス・オペレータ,関連論文)