グラフ・スペクトル解析と代数的確率論のための雑多なメモ

  • グラフを考える
    • 無向グラフと有向グラフがある。有向グラフの中にはとくにDirected Acyclic Graph(DAG)と呼ばれるものがあり半順序・ポセットと関係がある
    • グラフのノード集合は量子力学では、量子の取りうる「場所のようなもの」を表しており、ノード集合に連結情報を持たせたグラフの隣接行列は「物理量」を表しているとされる。行列には変換するものという見方もあり、「物理量は作用素」であるとの見方もされる。あるときにこの物理量を観察すると、状態に応じて「期待値」が観察される。物理量とその状態とから「期待値」が得られるという関係は、代数的確率論としてまとめられている。そのとき、グラフ~物理量~作用素は確率変数であると見られる
    • ここで用いたのは隣接行列である。正方行列である
    • DAG・ポセットの方では、グラフの接続行列というものを使う。ノード数xエッジ数の非正方行列である
    • 半順序関係のTrue/Falseで正方行列の値の1/0を決める
    • ポセットのノード集合には離散的確率質量分布の情報幾何的座標(\theta,\eta座標)を付与することができる
    • \theta,\eta座標が付与されたポセットは『ある確率的現象』とその『特定の確率質量分布』とを表している
  • グラフを用いた確率的現象と分布との小まとめ
    • グラフ自体は「確率的現象~確率変数」を表している
    • グラフのノード数の長さのベクトルはその「確率的現象~確率変数」の特定の状態を表している
    • 確率変数の特定の状態を「確率質量・密度(関数)」と呼ぶことにすれば、量子力学・物理量の方では、「状態を表すベクトル」と1対1対応する行列が存在することが知られており、それを「密度行列」と呼ぶ
    • DAG・ポセットの方では、各ノードに確率質量を乗せることもできるし、それをポセットの半順序情報に基づいて表現しなおすと\theta,\eta座標が各ノードに与えられる
  • グラフの代数
    • 隣接行列は隣接代数を有し、それは*-代数であるという
    • 接続行列は接続代数を有し、それはHopf代数であるという
    • Hopf代数の中に*-代数は含まれる模様
    • 接続行列が作る代数は、行列が作る代数なので、そう言う意味では(おそらく)*-代数
    • Hopf代数って言うのは、代数の中でも、興味深い色々な特徴を有する代数構造で、(少なくとも)Posetが作る接続代数と言うのは、Incidence Hopf algebras"と言うものを構成するらしい(こちら)。これも多分有用なPDF
  • グラフのゼータ関数
    • グラフのゼータ関数と言えば、伊原のゼータ関数。これは「サイクル」の長さ別の列挙総数の母関数
    • グラフの隣接行列のk-乗の(i,j)成分はノードi からjへのk歩の歩き方の場合の数になるので、伊原のゼータ関数は、iからiへの歩き方の場合の数という意味では、隣接行列のk=0,1,.....-乗のトレース(対角成分の和)と関係しているとも(多分)言える
    • 他方、接続行列・接続代数にもゼータ関数があって、これはまさにポセットで\theta,\eta座標を扱うときに登場する関数。ゼータ関数積分的な仕事をする。メビウス関数はその逆で微分的な仕事をする
    • ただし、接続代数のゼータ関数が、「リーマンのゼータ関数素数の積」と繋がることの理解は、ちょっと難航しそうな感じ。なぜなら、このWiki記事の記載にある通り、接続代数のゼータ関数は「普通と違って」いて、Dirichlet seriesにまで戻らないとゼータ関数との共通性が見えない、と言うことらしいから("Zeta function of an incidence algebra, a function that maps every interval of a poset to the constant value 1. Despite not resembling a holomorphic function, the special case for the poset of integer divisibility (割り切れること) is related as a formal Dirichlet series to the Riemann zeta function." Wikiより引用)
    • 他方、隣接行列や、エッジ行列を用いた「グラフの伊原ゼータ関数」の方は、サイクルをPrimesとする母関数である、と言う意味合いでの解釈が可能であり、リーマンのゼータ関数が、全自然数について、素数を用いて理解するための母関数である、と言う側面の対応が取りやすい
    • このPDFはこの辺りを理解するために必要そうだ
  • 確率変数の期待値とモーメント
    • モーメント列はある意味で確率変数をよく特定する
    • 確率変数の1次モーメントは平均値であり、いわゆる確率変数の期待値
    • 隣接行列が属する*-代数的確率変数では、状態\Psiに対して\langle \Psi, A^m \Psi \rangle = \int_{-\infty}^{+\infty} x^m \mu (dx)がm次モーメントを表す
    • 量子物理学的には、これが「観察されるモーメントの期待値」。それがスカラー値を持つということは、グラフのノードが「空間の座標」や「エネルギーの強さ」などの何かしらの「値」を持つものと想定していて、その値の平均やバラツキとしてのモーメントを観測する、という文脈(らしい)
    • グラフノードに一様な分布があるとき、隣接行列の0乗に関する1次モーメント(平均)は1(ノード数を標準化したもの)になるようだ。隣接行列の1乗に関する1次モーメントはノードの次数の平均値になるだろう(グラフを二次元多様体と考え、ノードが多様体上に均一に分布していると考えれば、面積のようなものになるだろうか)
    • 他方、ポセットの接続代数の方にも期待値というものがある。\eta座標はそのノードに相当する期待値である。また指数型分布族表現(対数確率分布を線形分解した表現)の言葉では、線形要素(取りうる状態を並べたものに重みを与えたベクトル)に対応する期待値が\eta座標である
  • 特定のノードを基準にすること
    • グラフは全体で一つの情報を表していて、特に1つのノードが特別ということはない、というのが原則である
    • ただし、ある一つのノード\rhoを取り上げると、そこからのグラフ距離というものが定まる
    • 隣接行列・隣接代数では、ある基準ノード\rhoからのグラフ距離によって階層的に排他的部分集合に分解して論を進めることがある
    • これを利用すると、隣接行列を次の3つに分解することができる
      • ノードx,yの間にエッジがあるとき、隣接行列Aの(x,y)成分は1。今、\rhoからx,yへの距離\partial(\rho,x),\partial(\rho,y)は、前者が1大きいか、後者が1大きいか、同じかの3通りになる
      • これを用いてA=A^+ + A^- + A^oと分けるというのがその分解方法である
    • 他方、ポセットにも基準ノード\rhoを定められることがある。例えば、ある1ノードが存在し、ポセット上の全てのノードに到達できるようなポセットや、その逆に、ポセット上の全てのノードからある1ノードに到達できるとしたとき、そのノードを基準ノード\rhoにすることで、ポセットの隣接行列の分解が可能になる
  • グラフから作る正方行列と伊原のゼータ関数
    • 基本は隣接行列
    • エッジの隣り合わせ関係を表す行列(Edge matrix (エッジ本数x2)行、(エッジ本数x2)列の行列)
    • グラフから全域木を取り出し、残ったエッジで作る正方行列も伊原のゼータ関数には使える

-グラフから作る非正方行列

    • ノードxエッジの非正方行列〜接続行列。これからゼータ関数が作れる
    • ノードとエッジの関係で行列を作るのがOKならば、グラフを単体的複体的に捉え、m次元単体とn次元単体との包含関係行列を考えることができて、。これは接続行列を含む
  • そのほか
    • 隣接代数的に考えるとき、3ノード間のグラフ距離関係を考えることがある。ノードx,y,zがあったときに、k =\partial{x,y},i = \partial{x,z},j = \partial{y,z}となっているとする。x,y の取り方によらずこのようなノードzの数がp^k_{ij}と一定であるようなグラフをDistance-regularグラフと呼ぶ。単純な素粒子を確率変数と見たときのグラフはこのような性質をもつらしい。逆に言うと隣接代数として見たときに単純な確率変数はdistance-regularだと言うことらしい
    • Regularグラフと言うものも、ある。全てのノードの字数が等しいグラフのことで、これも隣接代数とその代数的確率論の展開がやりやすい(漸近的特性が定まりやすい)
  • 独立
    • 代数的確率論では、確率変数にいくつかの異なる「独立」の概念がある。これは期待値がある意味で変数ごとに分離して計算できると言うことを意味し、古典的な確率変数の古典的な独立の概念も、代数的確率論の枠組みで再定義できる
    • 独立な確率変数は、複雑な確率現象を分解して理解する部品となる可能性の高いものであり、重要(なはず)