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

こちらで格子グラフについて少しいじっている 格子上の疎なグラフについて興味がある 探し物をしていて、Expander graphとかCaley graphとかが引っ掛かる Expander graphの論文 Expander graphの論文２ Expander graphに関する大部のpdf ケーリーグラフと置…

多次元立方格子上の点の占拠状態を把握したい 点の座標からペアワイズの距離行列を作ることは容易 距離行列と格子をグラフとみなした場合の隣接行列との関係を確認しよう １辺の長さが１の場合で考える # 距離行列M、隣接行列E M <- E <- list() # 次元０＝…

こちらでGraphletsの話を聞いた こちらの論文に図がある Graphlets(Wikiの記事)は、グラフの次数(ノードに連結しているエッジの本数)の一般化したものに関する定量化 ネットワーク奇跡のためのオープンソースプロジェクトCytospace Cytospaceの中のグラフレ…

昨日の続き ノード数が同数の格子グラフを作るには、格子の次元と１辺の長さとを次のように定めることで可能 # L_s^{k_s} = (\prod_{i}^{n_i} u_i^{\prod_j^{n_j}k_j})^{k_s} # n_i = 1,u_1 = 2にして、n_j = 2にしk_1 =2, k_2 = 3,4,5などと振る # その上で…

グラフの固有値というのがあるそうだ 隣接行列と、それから(も計算できる)グラフのラプラシアン行列に定まるもので、第１固有値より第２のそれの方が意味があるとか PDFへのリンク１ Wikiのグラフの固有値 Rのパッケージigraphの中の固有値(とそれに基づくce…

こちらで、知識をグラフ理論的に扱うために、グラフを階層化してみている まず、ノードのリストが与えられる 個々のノードをシングル・ノードのサブグラフと考える 知識は、(シングル・ノードの)サブグラフを複数取り出してそのサブグラフにペアワイズな関係…

グラフ・ネットワークがあって、そのサブグラフが２つあるとする ２つのサブグラフの間の関係を定量したい こちらで書いたことが目標だ まずは論文を探そう 生態学領域での手法の概説 生態学では、ある種の群・群落が大きさと広がりをもって、空間に点在して…

グラフは多次元データ それを２次元に描くためにノードの位置を定める必要がある 定め方が「グラフレイアウト」 Rのigraphパッケージでは、いくつかのレイアウト関数があって、２次元座標を返してくれるのだが… その座標を「適切に」画面に配置するためのル…

こちらで、木グラフ上の点の点間距離からMDSをすることを書いた 木であるということを利用してMDSするとどうなるだろうか 木であるということは、ノードからのエッジの生え方に偏りを与える理由がないということ 偏りがないということは、平等に生やすのがよ…

空間にグラフがあるとする 空間に点があるとする 点からグラフへの最短距離を描く こちらで作った、「凸包」への垂線の足を利用する ループを回しているのでちょっと重いかも 垂線の足がどの辺に乗っているかで色分けすると、空間が塗り分けて見えやすそう #…

松の木は枝振りを楽しめる。 そういうのとは違うけれども、伸び放題になった松の枝をおろすと、かさばる切落としがたくさんできる かさばるままだと、とにかく邪魔だ。ゴミ袋にも収まらない かさを減らすために、分枝部を切り刻んでみた 切り刻みながら、考…

こちらの続き グラフにはノードとエッジがある 今、連結されたノードについて考える エッジは２つのノードの関係を表していると見る エッジで直接つながっていない２ノードについて、２通りの見方をすることができる 直接につながっていない→関係がない 直接…

library(igraph) # 全域木にplusE本のエッジを加えたグラフを作る N<-5 plusE<-3 s<-sample(1:(N-1),plusE) pluses<-rep(0,N) pluses[s]<-1 M<-matrix(0,N,N) for(i in 1:(N-2)){ num<-1 if(pluses[i]==1){ num<-2 } M[i,sample((i+1):N,num)]<-1 } M[N-1,N]…

鎖状のグラフとは、枝分かれのない木グラフのこと ノードは１次元座標で表すこともできて、隣接するノードの位置座標の差をノード間距離と言う このようなノード数Nのグラフがあったとき、それぞれのノードの値を表す長さNのベクトルVを考える Vの値がノード…

木のグラフがある ノードに値が与えられている 木の上で、この値が順序よく並んでいるのかを評価したい そのために、次のようにする ノードの並びのうち、値が昇順(降順でもよい)になっている鎖状のセグメントに分割する そのセグメントを１つのノードとみた…

木はグラフ 全域木は、すべてのノードが連結な木グラフ ノード数Nに対してエッジ数はN-1 すべてのノードは少なくても１個の隣接ノードを持つ 辺の取り方を考える 木グラフをだんだんに大きくしていく 初めはノードなし ノード数１個の木グラフを作る N個のノ…

木を作ってから距離行列を作る すべての辺の長さを１で考えれば、ペアの距離のうち、木の辺の数のペアの距離が１ 残りののペアの長さを2,3,...で分配するわけだが、その分配の仕方は、木の構造(枝分かれの様子)と関係する情報になる ペア間距離はigraphパッ…

最小全域木を考えている ある空間に均等に散らばることができる点の集合があるときに、その点の集合の存在具合の方よりを表す一つの方法が最小全域木 空間(必ずしも連続でなくてもよい(はず))に広がる「不均一分布」を点集合がサンプルとして代表している そ…

木(グラフ)があって、そのノードに値があるとする グラフは２次元にプロットできる ノードが持つ値を第３軸に与えて３次元プロットしてみよう library(rgl) library(vegan) Ns<-50 # サンプル数 Nm<-40 # 項目数(マーカー数) # 適当にデータ上列を作ろう X<-…

今、M次元格子上にN個の点を取る M次元格子は(0,1,2)としてみる これらの点はその遠近関係(以下のソースではマンハッタン距離にしてある)により、最小全域木を取ることができる 今、このN個の点にある値を付与しよう この値は相対的なものであるとすると、定…

昨日の記事で、多様体学習に触れた 多様体学習は、非線形に次元を下げる話と言い換えることができるが、それに関連する用語を挙げよう Isomap 点間距離を局所について測り、グラフ上の最短距離を局所において定める。その上で、すべての点間のグラフ上最短距…

トーラスの一部(少し曲がった円筒)の３次最小全域木を作ってみた 処理はすごく重い：重くて使えない 多様体推定がどんな具合なのかはだいたいわかったので、いい方法がないか、探してみることにする たとえばこちら Isomapとは→こちら RでIsomap→veganパッケ…

空間に多様体がある 多様体をあっちこっち観察すると、多様体の存在する点が観測される その複数の点の位置データから、多様体が空間上で何次元なのかを知るにはどうしたらよいのだろう？ 「多次元最小全域木」を作ってやると、多様体の次元までは、「多次元…

昨日まで高次元最小全域木とかいうものを考えていた 減次元完全グラフの連結によって、すべてのノードを覆うような作り方をもって、そのように呼ぶことにしていた そのような高次元最小全域木では、k次元最小全域木からk+1次元最小全域木に上げるにあたって…

ソースは、非常に重いのだが… SimplexVolume<-function(x,Factorial=FALSE){ n<-length(x[,1]) #d<-t(x[2:n,])-x[1,] d<-apply(x,2,FUN="diff") if(Factorial){ ret<-log(abs(det(d))) - lfactorial(n-1) }else{ ret<-log(abs(det(d))) } return(ret) } Simp…

頂点数の完全グラフでは、すべての頂点ペア間に辺がある 辺の数はである 今、頂点数の完全グラフが２つあるとする この２つの完全グラフは個の頂点が共通であるとする その共通な個の頂点は完全グラフになっている 今、このような重なりのある２つの完全グラ…

とはいえ、一応、メモ １次元最小全域木では、頂点数に対して、辺の数は(木だから) これは、このように考える 点があって、辺がない状態から、辺を１つ増やすと、点が２つ結ばれる それに連結するように辺を１つ増やすと、連結な点の数が１つ増える したがっ…

最小全域木の多次元化についてこちらにメモした 多次元化する別の方法について考えてみる 最小全域木をもう一度見直す 最小全域木作成のアルゴリズムを確認する すべての点が「辺」でつながるように持っていく 「辺」は１次元的なもの (作りうる)すべての「…

最小全域木 N個のノードがある すべてのノードが連結であるようなグラフのうち、エッジの数が最少なとき、その数はN-1 ここで、エッジの重さ(長さ)の和が最小であるようなエッジの取り方があり、そのようなエッジのセットでノードを連結したとき、それを最小…