スペクトル
メモ的なソースコード
グラフが持つ３つの正方行列（隣接行列・ラプラシアン・Normal行列)の固有値分解・スペクトル解析に関する短い文書をRで確かめる作業をしてみた
円周をグラフで模す その隣接行列の固有値スペクトルはになる？？？ 固有ベクトルは、「調和関数？」のようなもの
こちらで代数的確率論・量子確率論のことを書いた その中に出てくる隣接代数というものを整理する 隣接行列とは、いわゆるグラフの行列のことで、エッジで結ばれたノードに対応する要素が１でそれ以外が０であるような行列のこと グラフは有限かも無限かもし…
グラフのスペクトル解析をゼロからやってみるためのいくつかの資料 読みもの スライド newGRAPH(お手軽アプリ)
隣接行列Aのm乗の(i,j)要素の値は、i,j間のグラフ距離 3.1 Eigenvalues n完全グラフの隣接行列の固有値は、1がn-1重で-1が1個。p,q-完全2部グラフのそれはとp+q-2重の0 Full-cycle permutation matrix of order nの場合、隣接行列の固有値は、 n頂点を結ぶパ…
10.1 Majorization ベクトルの要素の和が等しいような２つのベクトルがあって、その累積和ベクトルの要素のすべてについて、後者のそれが前者のそれ以上であるとき、前者は後者でMajorzationされているという そのMajorizationでできる行列がある 10.2 Thres…
Distance を考えるとき、最短経路のみが問題になるが、非最短経路との相対的な関係で最短経路とその距離とを考えることも有用。そのような距離がResistance distance Laplacianの章で出てきた行列H(g-inverse of L)を使うと となる 三角不等式も成り立つ ネ…
2.1 ランク 有向グラフGのn個のノードと、m個のエッジ。nxm行列で、エッジの始点と終点とを1,-1で表したもの、それがIncidence matrix Q(G) Q(G)の列和はゼロ、行ベクトルは線形非独立 連結グラフのランクはn-1、k個の連結グラフの集合ならランクはn-k k個の…
木のDistance matrixの場合、 木でないグラフのDistance matrixの場合は、サイクルとそうでない部分(木)に分けて行く 木のDistance matrixのLaplacian、固有値を考えることで有用な性質がある
Laplacian matrixの最小固有値は0。二番目に小さい固有値をalgebraic connectivityと言う。非連結グラフのalgebraic connectivityは0。完全グラフのそれはn 7.1 Preliminary results 7.2 Classification of trees(Types I and II) 7.3 Monotocinicty propert…
グラフはノードとエッジでできており、それにIDを振ると色々な行列が出来る 行列は正方行列と非正方行列とがある 非正方行列の代表はIncidence matrix(ノードとエッジの関係を表した行列) 正方行列はノードｘノードの行列があり、いろいろある グラフの特徴…
全ノードの次数が等しいグラフがRegular 6.1 Perron-Frobenius theory 成分が正である実正方行列には唯一つの最大実固有値が存在し、それに対応する固有ベクトルの各成分は厳密に正である、という主張。グラフのノードの重みづけ(ページランク)計算などに用…
Incidence matrix Qのnull spaceをcycle subspace、Q^Tのnull space を cut subspaceと呼ぶ edgeのセットをうまく取り出して足し合わせると、キャンセルアウトするのがcycleなので、incidence matrixのcolumnsの線形和でゼロベクトルができれば、その線形和…
1.1 Matrices 行列、転置、対角行列 Trace and determinent ベクトル空間とランク Minorsは行の一部と列の一部とを取り出した部分行列。と書くと、行の部分集合S、列の部分集合TでのMinor。はSとTの補集合によるMinor。は１行、１列を除いたMinor 特に、行と…
エッジが無いノードペアは0、エッジありのペアは-1、対角成分はノードの次数であるような行列がLaplacian matrix L=D-A (ただし、Dは対角行列で対角成分がノードの次数、Aはadjacency matrix) L=Q Q^T (ただしQはincidence matrix)でもある Lは対称で半正定…
Graphs and Matrices (Universitext)作者: Ravindra B. Bapat出版社/メーカー: Springer発売日: 2014/10/02メディア: ペーパーバックこの商品を含むブログを見る 目次 1 Preliminaries 2 Incidence Matrix 3 Adjacency Matrix 4 Laplacian Matrix 5 Cycles a…
