グラフの隣接行列に対する適用例

個数がZipfの法則に従う人工的なネットワークに対して提案手法を適用 した．ネットワークはKumarら[99]の(α, β)モデルにより構成した．

ここでは，ネットワークのリンク構造を表している隣接行列Aに対し て修正Ojaアルゴリズムを用いて第1，第2，第3主成分と第1，第2，第 3マイナー成分を抽出した．また，隣接行列のサイズは(550×550)となっ ている．

まず，(α, β)モデルによって生成したネットワーク内に存在する各ノー ドのin-degreeおよびout-degreeに対するノードの数の分布を示す．

以下で，

・(a) authority linkの解析

・(b) hub linkの解析

の2つの問題について，本提案手法を適用した結果を示す．

図 26: authrity linkおよびhub linkに対するノードの個数の分布

(a) authorty linkに関する主成分およびマイナー成分抽出の結果を図 27に示す．

10万回のステップ数で求めた解ベクトルを用いてReyleigh 商(6)に より計算した近似固有値はλ₁ = 100.9, λ₂ = 46.42, λ₃ = 41.41, µ₁ = 0.0017, µ₂ = 0.0021, µ₃ = 0.0025 となった．

図27から，

・ 主成分については大きなin-degreeをもつノードに対して主成分固有 ベクトルの大きな値をもつ要素が対応している．これは，Kleinberg の結果とほぼ一致する．

・ マイナー成分については主成分とは逆に小さなin-degree(0を除く) をもつノードに対してマイナー成分固有ベクトルの大きな値をもつ 要素が対応している場合が多い．

という結果が得られた．

図 27: in-degreeとauthority linkの主成分とマイナー成分

(b) hub linkに関する主成分およびマイナー成分抽出の結果を図28に 示す．

このとき，Reylegh商により求めた近似固有値はλ₁ = 100.9, λ₂ = 46.42, λ₃ = 41.41, µ₁ = 1.7×10⁻⁵, µ₂ = 3.3×10⁻⁵, µ₃ = 6.0×10⁻⁶ となっている．

図28から，

・ 主成分についてはauthority linkと同様に大きなout-degreeをもつ ノードに対して主成分固有ベクトルの大きな値をもつ要素が対応し ている．これは，Kleinbergの結果とほぼ一致する．

・ マイナー成分については主成分とは逆に小さなin-degreeをもつノー ドに対してマイナー成分固有ベクトルの大きな値をもつ要素が対応 している場合が多い．

という結果が得られた．

authority linkとhub linkのマイナー成分の関係は過去に調べられてい ないので更に考察が必要である．また，hub linkのマイナー成分につい ては，in-degreeの場合と異なり，out-degreeが0であるノードに対して も大きな値を持つ要素が存在している．hub linkに関するMCAの10万 ステップ終了時の誤差ノルムρ_kとη_kの値はそれぞれ，ρ_k = 2.0×10⁻⁵， η_k = 1.0×10⁻⁶ となっていた．ρ_kの計算には真の固有値の代わりにステッ プ毎にw_n,(n = 1,2,3)を用いてReyleigh商により求めた近似固有値を用 いた．しかしながら，固有値が昇順に求められていないことから，誤差 の大きな結果が得られていると考えられる．この原因は，MCAの対象と なった行列のマイナー成分に対応する固有値がお互いに近いことと，問 題の行列が提案手法の反復計算において，数値誤差が大きくなりやすい 構造をもっているためであると推測される．

図 28: out-degreeとhub linkの主成分とマイナー成分

5 おわりに

本研究では，正負の符号の違いのみで主成分とマイナー成分を抽出で きるとともに，数知的に安定なアルゴリズムを提案した．

従来の手法では，

1. マイナー成分の抽出における数値安定化のために正規直交行列の空 間上の力学系を考えている．

2. 各々の固有ベクトルを抽出するためには，Gram-Schmidtの正規直 交化に対応するようなアルゴリズムの非対称化が必要である．ただ し，上記の手法(W^TW の積による正規直交化の強化)では非対称化 によってW^TW =Iが崩れる．

という相反する条件が必要であったが，本研究で提案したアルゴリズ

ムはGram-Schmidtの直交化法に対応する非対称化と，数値安定化のた

めのペナルティ項を組み合わせることで上の問題を回避している．

また，既存の主成分およびマイナー成分を抽出するアルゴリズムでは 利用可能なパラメータの範囲を系統的に調べられてないので，平衡点近 傍での漸近解析と数値実験により利用可能なパラメータの範囲を調べた．

漸近解析ではマイナー成分の抽出においてはペナルティ項に与えるゲ インγが少なくとも，抽出されるマイナー成分に対応する固有値よりも 大きくないと解がマイナー成分固有ベクトルに収束しないという結果が 得られた．

数値実験では，行列Dが定理の条件を満たしていたとしても，パラメー タθ_n,(n= 1, ..., N)の比により利用可能なパラメータの範囲が変化し，θ_n の比が大きい場合には，その範囲が狭くなった．これは漸近解析の結果 が大域的には十分条件になっていないことを示すものである．

さらに，より現実的な規模の適用例としてネットワークのリンク構造 解析に対して，提案したアルゴリズムを用いた．

得られた主成分は接続リンク数が多いノードに対して大きな値をもつ 要素が対応しており，Kleinbergとほぼ一致した結果が得られた．

一方，マイナー成分は接続リンク数が少ないノードに対して，大きな 値をもつ要素が対応しているという傾向が見られた．しかしながら，各 マイナー成分とリンク構造の関係については明確なものではなく，更に 考察が必要である．

A 定理 1 の証明

【定理１】

K 個の主成分である固有ベクトルを列ベクトルとした行列 V˜ = [v₁v₂...v_K],||v_i||² = 1, i= 1, ..., K と，それぞれに対応する固有値

λ₁, λ₂, ..., λ_K, λ₁ > λ₂ > ... > λ_N ≥λ_N+1≥...≥λ_K ≥ 0,(K > N) をもつ対角行列

Λ =˜ diag(λ₁, λ₂, ..., λ_K) で表される正定値対称行列

C = ˜VΛ ˜˜V^T ∈R^K×K と対角行列

D=diag(θ₁, ..., θ_N)∈ R^N×N で定義された

dZ

dt ≡CZ−ZD⁻¹Z^TCZD+γZ(I−Z^TZ) (39) の解

Z ∈R^K×N は，

V = [v₁v₂...v_N] で与えられ，

0< θ₁ < θ₂ < ... < θ_N (40) かつ

γ >0 (41)

【証明】

V = [v₁...v_N] に対応する固有値からなる対角行列

Λ = diag(λ₁, ..., λ_N) を考える．そのとき，V は直交行列になるので，

CV = VΛ (42)

V^TCV = Λ (43)

となる．

ここで，式(39)の右辺に，この定数行列V を代入すると，

(右辺) = CV −V D⁻¹(V^TCV)D

= VΛ−V D⁻¹ΛD

= VΛ−VΛD⁻¹D

= VΛ−VΛ

= 0 (44)

次に，Z¯ の漸近安定性を証明するために，平衡点Z¯ からの微小な摂動 E(t) = [e₁(t)...e_n(t)]を考える．

Z(t) = Z¯+E(t)

= V +E(t)

を式(39)に代入すると，E(t)に対して次の式を得る．

dE

dt = dZ

dt|_Z=V+E

= C(V +E)

−(V +E)D⁻¹(V +E)^TC(V +E)D +γ(V +E)[I−(V +E)^T(V +E)]

= [CV +CE

−V D⁻¹V^TCVD−V D⁻¹V^TCED

−V D⁻¹E^TCVD−ED⁻¹V^TCVD]

−γ[V^TV E−V E^TV] +O||E||²

ここで，O(||E||²)はEの要素の2次以上の項を示している．||E||²が十 分に小さいと仮定すると，式(42) と式(43)を用いて次の式が得られる．

dE

dt = CV +CE

−V D⁻¹V^TCVD−V D⁻¹V^TCED

−V D⁻¹E^TCVD−ED⁻¹V^TCVD

−γE−γVE^TV

= VΛ +CE−V D⁻¹ΛD−V D⁻¹ΛV^TED

−V D⁻¹E^TVΛD−ED⁻¹ΛD

−γE−γVE^TV

= VΛ +CE−VΛ−V D⁻¹ΛV^TED−V D⁻¹E^TVΛD−EΛ

−γE−γVE^TV

= (C−γI)E−EΛ−V D⁻¹ΛV^TED

−V D⁻¹E^TVΛD−γVE^TV (45) Eのn番目の列ベクトルe_nに対して、式(45)は

de_n

dt = [C−(γ+λ_n)I]e_n−

_N

m=1

θ_n

θ_mλ_mv_mv^T_m

e_n

−

_N

m=1

λ_n

θ_mθ_n−γv_me^T_m

v_n (46)

となる．

(46)の両辺に，左から固有ベクトルv_r, r = 1, ..., Kを掛け，以下の三 つの場合に分けて議論する．

(i)まず，r > N とする．このとき，実対称行列Cの固有ベクトルv_rの 正規直交性により次のようになる．

d

dt(v_r^Te_n) = v^T_r[C−(λ_n+γ)I]e_n−v^T_r

_N

m=1

θ_n

θ_mλ_mv_mv_m^T

e_n

−v_r^T

_N

m=1

θ_n

θ_mλ_n−γv_me^T_m

v_n (47)

= λ_r−λ_n−γv_r^Te_n (48)

したがって，v_r^Te_n は λ_r−λ_n−γ <0 のとき漸近的に0に近づく．

(ii)つぎに，r =n, r, n≤N とすると，

d

dt(v_n^Te_n) = v_n^T[C−(λ_n+γ)I]e_n−v_n^T

_N

m=1

θ_n

θ_mλ_mv_mv_m^T

e_n

−v_n^T

_N

m=1

θ_n

θ_mλ_n−γv_me^T_m

v_n

= λ_n−λ_n−γ(v_n^Te_n)−λ_n(v_n^Te_n)−

λ_nθ_n θ_n −γ

(e^T_nv_n)

= −(λ_n+λ_n)(v_n^Te_n)

= −2λ_n(v^T_ne_n) (49)

λ_n >0より，この式は漸近的に0に近づく．

(iii)最後に，r =n,(r, n≤N)とする．一般性を失うこと無く，r < n と仮定することができる．式(47)より，次の式を得る．

d

dt(v_r^Te_n) = v^T_r[C−(λ_n+γ)I]e_n−v^T_r

_N

m=1

θ_n

θ_mλ_mv_mv_m^T

e_n

−v_r^T

_N

m=1

θ_n

θ_mλ_n−γv_me^T_m

v_n

=

1− θ_n θ_r

λ_r−λ_n−γ

(v_r^Te_n)

−θ_n

θ_rλ_n−γ(v_n^Te_r) (50) また，上式のrとnを置換すると，次のようになる．

d

dt(v_n^Te_r) =1− θ_r θ_n

λ_n−λ_r−γ

(v_n^Te_r)−θ_r

θ_nλ_r−γ(v_r^Te_n) (51) 更に，式(50)より，

(v_n^Te_r) = −θ_n

θ_rλ_n−γ⁻¹

×

d

dt(v^T_re_n)−1− θ_n θ_r

λ_r−λ_n−γ(v_r^Te_n)

(52)

この結論も式(16)とは独立である．そして，すべてのθn が等しい，または正値を とる場合においても成り立つ．

式(52)を式(51)の右辺に代入すると，

d

dt(v^T_ne_r) = −θ_n

θ_rλ_n−γ

₋₁

1− θ_r θ_n

λ_n−λ_r−γ

×

d

dt(v_r^Te_n)−1−θ_n θ_r

λ_r−λ_n−γ(v_r^Te_n)

−θ_r

θ_nλ_r−γ(v_r^Te_n) (53) となる．

(v^T_re_n)のみに関する方程式を得るために，式(50)を時間tで微分して，

d²

dt²(v_r^Te_n) =

1− θ_n θ_r

λ_r−λ_n−γ

d

dt(v_r^Te_n)−θ_n

θ_rλ_n−γ

d

dt(v_n^Te_r)(54) を得る．上式の右辺に，式(53)を代入すると，次式を得る．

d²

dt²(v^T_re_n) = 1− θ_n θ_r

λ_r−λ_n−γd

dt(v_r^Te_n) +1− θ_r θ_n

λ_n−λ_r−γd

dt(v_r^Te_n)

−1− θ_n θ_r

λ_r−λ_n−γ1− θ_r θ_n

λ_n−λ_r−γ

−θ_n

θ_rλ_n−γθ_r

θ_nλ_r−γ(v_r^Te_n) (55) ここで，

β ≡ θ_n

θ_r, .≡ λ_n λ_r とすると，式(55)は

d²

dt²(v^T_re_n) = (1−β)λ_r−.λ_r−γd

dt(v_r^Te_n) +(1−β⁻¹).λ_r−λ_r−γd

dt(v_r^Te_n)

−(1−β)λ_r−.λ_r−γ(1−β⁻¹).λ_r−λ_r−γ

−(β.λ_r−γ)(β⁻¹λ_r−γ)(v_r^Te_n)

= (1−β)λ_r−.λ_r−γ+{(1−β⁻¹).−1}λ_r−γd

dt(v_r^Te_n)

−(1−β)λ_r−.λ_r−γ(1−β⁻¹).λ_r −λ_r−γ

−(β.λ_r−γ)(β⁻¹λ_r−γ)(v_r^Te_n)

= −(β+β⁻¹.)λ_r+ 2γ d

dt(v_r^Te_n)

−(β⁻¹−1).²−(β−3 +β⁻¹).+ (β−1)

−1 2

T

となる．これは定数係数２階線形微分方程式である．この解は二つの特 性根が負の実部をもつ場合，またその場合に限り0に収束する．上式の 特性方程式の解をsとして求める．

s = (2β)⁻¹[−2βγ−λ_rβ²−λ_n

±{4β²γ²−4(β³λ_n+βλ_r)γ +λ²_rβ⁴+ 4λ_r(λ_n−λ_r)β³ +(4λ²_r−6λ_rλ_n+ 4λ²_n)β²

+4λ_n(λ_r−λ_n)β+λ²_n}⁻¹²] (56) となる．よって，式(55)が0に収束するためには，

s₁ = (2β)⁻¹[−2βγ−λ_rβ²−λ_n

+{4β²γ²−4(β³λ_n+βλ_r)γ +λ²_rβ⁴+ 4λ_r(λ_n−λ_r)β³ +(4λ²_r−6λ_rλ_n+ 4λ²_n)β² +4λ_n(λ_r −λ_n)β+λ²_n}⁻¹²]

< 0 (57)

が条件となる．上の不等式をγについてMapleを用いて解くと，

γ > (.−1)(β−1)(β+.)

(.+ 1)(β²+ 1) λ_r ≡I (58) となる．ここで，

λ₁ > λ₂ > ... > λ_N ≥λ_N+1 =...=λ_K = 0, 0< θ₁< θ₂ < ... < θ_N

であることから，

0< . <1のときβ >1，また. >1のとき0< β <1 (59) なので，

(.−1)(β−1)<0

となる．また，(β²+ 1)>0であり，

β+.

.+ 1 = β+.+ 1−1 .+ 1

= β−1 .+ 1 + 1

> 0

となる．ゆえにI <0となるので，γ >0であれば式(58)を満足する．

【証明終】

B 定理 2 の証明

【定理２】

k 個のマイナー成分である固有ベクトルを列ベクトルとした行列 V˜ = [v₁v₂...v_K],||v_i||² = 1, i= 1, ..., K

とその固有値

µ₁, µ₂, ..., µ_K,0< µ₁ < µ₂ < ... < µ_N ≤µ_N+1 ≤...≤ µ_K(K > N) をもつ対角行列

M˜ =diag(µ₁, µ₂, ..., µ_K) で表される正定値対称行列

C = ˜VM˜V˜^T ∈R^K×K と対角行列

D=diag(θ₁, ..., θ_N)∈ R^N×N で定義された

dZ

dt ≡ −CZ +ZD⁻¹Z^TCZD+γZ(I−Z^TZ) (60) の解

Z ∈R^K×N は，

V = [v₁v₂...v_N] で与えられ，

0< θ₁ < θ₂ < ... < θ_N (61) かつ

γ > µ_N (62)

の場合に，漸近的に安定である．

【証明】

V = [v₁...v_N] に対応する固有値からなる対角行列

M = diag(µ₁, ..., µ_N) を考える．そのとき，V は直交行列になるので，

CV = V M (63)

V^TCV = M (64)

となる．

ここで，式(60)の右辺に，この定数行列V を代入すると，

(右辺) = −CV +V D⁻¹(V^TCV)D

= −V M +V D⁻¹M D

= −V M +V M D⁻¹D

= −V M +V M

= 0 (65)

次に，Z¯ の漸近安定性を証明するために，平衡点Z¯ からの微小な摂動 E(t) = [e₁(t)...e_n(t)]を考える．

Z(t) = Z¯+E(t)

= V +E(t)

を式(60)に代入すると，E(t)に対して次の式を得る．

dE

dt = dZ

dt |_Z=V+E

= −C(V +E)

+(V +E)D⁻¹(V +E)^TC(V +E)D +γ(V +E)[I−(V +E)^T(V +E)]

= [−CV −CE

+V D⁻¹V^TCVD+V D⁻¹V^TCED

+V D⁻¹E^TCVD+ED⁻¹V^TCVD]

− ^T − ^T || ||²

ここで，O(||E||²)はEの要素の2次以上の項を示している．||E||²が十 分に小さいと仮定すると，式(63) と式(64)を用いて次の式が得られる．

dE

dt = −CV −CE

+V D⁻¹V^TCVD+V D⁻¹V^TCED

+V D⁻¹E^TCVD+ED⁻¹V^TCVD

−γE−γVE^TV

= −V M −CE+V D⁻¹M D +V D⁻¹M V^TED +V D⁻¹E^TV M D+ED⁻¹M D

−γE−γVE^TV

= −V M −CE−V M +V D⁻¹M V^TED+V D⁻¹E^TV M D +EM

−γE−γVE^TV

= −(C+γI)E+EM +V D⁻¹M V^TED

+V D⁻¹E^TV M D−γVE^TV (66) Eのn番目の列ベクトルe_nに対して、式(66)は

de_n

dt = −[C+ (γ−µ_n)I]e_n+

_N

m=1

θ_n

θ_mµ_mv_mv_m^T

e_n

+

_N

m=1

µ_n

θ_mθ_n−γv_me^T_m

v_n (67)

となる．

(67)の両辺に，左から固有ベクトルv_r, r = 1, ..., Kを掛け，以下の三 つの場合に分けて議論する．

(i)まず，r > N とする．このとき，実対称行列Cの固有ベクトルv_rの 正規直交性により次のようになる．

d

dt(v_r^Te_n) = −v_r^T[C+ (γ−µ_n)I]e_n+v_r^T

_N

m=1

θ_n

θ_mµ_mv_mv_m^T

e_n

+v_r^T

_N

m=1

θ_n

θ_mµ_n−γv_me^T_m

v_n (68)

= −µ_r−µ_n+γv_r^Te_n (69) したがって，µ_n < µ_r, γ >0によりµ_r−µ_n−γ <0となり、v^T_re_nは漸近 的に0に近づく．

この結果は条件(16)に依らず，そしてθnがすべて等しい場合においても正しい．

(ii)つぎに，r =n,(r, n≤N) とすると，

d

dt(v_n^Te_n) = −v_n^T[C+ (γ−µ_n)I]e_n+v_n^T

_N

m=1

θ_n

θ_mµ_mv_mv_m^T

e_n

+v_n^T

_N

m=1

θ_n

θ_mµ_n−γv_me^T_m

v_n

= −(µ_n−µ_n+γ) +λ_n+λ_n−γ(v_n^Te_n)

= 2(µ_n−γ)(v^T_ne_n) (70)

よって，仮定によりµ_n−γ <0なので，この式は漸近的に0に近づく．

(iii)最後に，r=nとする．一般性を失うこと無く，r < nと仮定する ことができる．式(68)より，次の式を得る．

d

dt(v_r^Te_n) = −v_r^T[C+ (γ−µ_n)I]e_n+v_r^T

_N

m=1

θ_n

θ_mµ_mv_mv_m^T

e_n

+v_r^T

_N

m=1

θ_n

θ_mµ_n−γv_me^T_m

v_n

= θ_n

θ_r −1µ_r+µ_n−γ

(v_r^Te_n) +θ_n

θ_rµ_n−γ(v^T_ne_r) (71) また，上式のrとnを置換すると，次のようになる．

d

dt(v_n^Te_r) =θ_r

θ_n −1µ_n+µ_r−γ

(v_n^Te_r)−θ_r

θ_nµ_r−γ(v^T_re_n) (72) 更に，式(71)より，

(v^T_ne_r) =θ_n

θ_rµ_n−γ⁻¹

d

dt(v_r^Te_n)−θ_n

θ_r −1µ_r+µ_n−γ(v^T_re_n)

(73) 式(73)を式(72)の右辺に代入すると，

d

dt(v_n^Te_r) = θ_n

θ_rµ_n−γ⁻¹θ_r

θ_n −1µ_n+µ_r−γ

×

d

dt(v_r^Te_n)−θ_n

θ_r −1µ_r+µ_n−γ(v_r^Te_n)

+θ_r

θ_nµ_r−γ(v_r^Te_n) (74)

この結論も式(16)とは独立である．そして，すべてのθn が等しい，または正値を

となる．

(v^T_re_n)のみに関する方程式を得るために，式(71)を時間tで微分して，

d²

dt²(v^T_re_n) = θ_n

θ_r −1µ_r+µ_n−γ

d

dt(v^T_re_n) +θ_n

θ_rµ_n−γ d

dt(v_n^Te_r) (75) を得る．上式の右辺に，式(74)を代入すると，次式を得る．

d²

dt²(v_r^Te_n) = θ_n

θ_r −1µ_r+µ_n−γ+θ_r

θ_n −1µ_n+µ_r−γd

dt(v_r^Te_n)

−θ_n

θ_r −1µ_r+µ_n−γθ_r

θ_n −1µ_n+µ_r−γ

−θ_n

θ_rµ_n−γθ_r

θ_nµ_r−γ(v_r^Te_n) (76) ここで，

β ≡ θ_n

θ_r, .≡ µ_n µ_r とすると，式(76)は

d²

dt²(v^T_re_n) = (β−1)µ_r +.µ_r−γ+ (β⁻¹−1).µ_r+µ_r−γd

dt(v^T_re_n)

−(β−1)µ_r+.µ_r−γ(β⁻¹−1).µ_r+µ_r−γ

−(β.µ_r−γ)(β⁻¹µ_r −γ)(v_r^Te_n)

=

(β+β⁻¹.)λ_r−2γ

d

dt(v^T_re_n)

−(β⁻¹−1).²−(β−2 +β⁻¹).−1

µ²_r

+(β−β⁻¹).+β⁻¹−βµγ(v_r^Te_n) (77) となる．これは定数係数２階線形微分方程式である．この解は二つの特 性根が負の実部をもつ場合，またその場合に限り0に収束する．上式の 特性方程式の解をsとして求める．

s = (2β)⁻¹[−2βγ+ (β²+ 1)µ_r

±{4β²γ²−4(β³.+β)µ_rγ +µ²_r(β⁴+ 4(.−1)β³+

(4−6.+ 4.²)β²+ 4.(1−.)β+.²)}⁻¹²] (78)

ドキュメント内 JAIST Repository: 主成分およびマイナー成分抽出に対する正規直交化ペナルティ法 (ページ 58-79)