NCDawareRank

ノードがネットワーク内でどれほど突出しているかを定義する方法にはいくつかあります。PageRankはその一つです。

NCDawareRankはエルゴード的マルコフ連鎖の定常確率分布が計算される9,11という点ではPageRankに似ていますが、スケールの大きいグラフ(情報の流れを表す)のレベル間近似度行列(inter-level proximity matrix)MMを追加で導入する点に違いがあります。 この行列は、同グループ内に所属するノードはお互いにリンクを張り合っておりより密なクラスタを作っているという事実をモデル化したものです。 これにより、NCDawareRankは計算がPageRankより早く収束するようになります。 さらに、同レベルに属するノードのランクに制限がかかるためスコアの操作に対して堅牢になります。

行列式の場合、NCDawareRankは以下のようにして計算されます。

π^=Oηπ+Mμπ+E(1ημ)π, \hat{\pi} = O\eta\pi + M\mu\pi + E(1 - \eta - \mu)\pi,

ただし

  • OOはアウトリンク行列
  • MMはレベル間近似度行列
  • EEはテレポーテーション行列
  • π\piはNCDawareRank
  • η\etaはアウトリンク行列の寄与率
  • μ\muは近接アカウント(proximal account)の寄与率

を表します。

MMμ\muが加えられたことを除けば、この定義はPageRankと同様です。 NEMの場合、η\etaは0.7、μ\muは0.1です。以下ではそれぞれの変数がいかにして計算されるかを説明します。

WWを収穫に参加できる全アカウントの集合とします。uWu \in Wに対し、GuG_uを、uuへ送信した値よりもuuから受け取った値の方が多いアカウントの集合とします。 WWの部分集合で、お互いにほぼ完全に分離可能(Nearly completely decomposable, NCD)なものをA1,A2,...,AN{A_1, A_2, ..., A_N}と定義します。ただし、任意のuWu \in Wにたいして、uAKu \in A_KとなるKKがただ一つだけ存在します。 したがって、uuの近接アカウントの集合χu\chi_uは以下のように定義されます。

χuw(uGu)A(w) \chi_u \triangleq \bigcup_{w \in (u \cup G_u)} A_{(w)}

そしてNuN_uχu\chi_uに含まれるNCDブロックの数とします。

訳注: わかりにくいですが、PageRankにおいてリンクを貼ることを「投票」と 考えると、これは特定のアカウントではなく、そのアカウントの属するグループ 全体へと投票を「分散させる」ための手続きだと思ってください。χu\chi_uは 投票を受ける「政党」みたいなものです。

OOの定義は7.2: アウトリンク行列で述べたとおりです。収束を保証するために、Oη+Mμ+E(1ημ)O\eta + M\mu + E(1 - \eta - \mu)は既約で列ベクトルが確率分布としての条件を満たす(column-stochastic)行列でなくてはなりません。 この条件は、宙ぶらりんの(dongling)アカウント(外向きの辺が存在しないアカウント)に、0より大きい確率でテレポートするように、全アカウントに対する外向きの辺を持たせることで満たされます。

レベル間近似度行列MMは、トランザクションのグラフをクラスタリング(詳細は7.2説: トランザクショングラフのクラスタリングで述べます)し、各NCDブロックANA_Nを定義し、MMv,uv,u要素である近接アカウントの近似度を以下のように定義することで求められます。

Mv,u{1NvA(v)(vχu)0(otherwise) M_{v,u} \triangleq \left\{ \begin{array}{ll} \frac{1}{N_v|A_{(v)}|} & (v \in \chi_u) \\ 0 & (otherwise) \end{array} \right.

テレポーテーション行列EEは以下で定義されます

EevT E \triangleq ev^T

ただしvTv^Tはテレポーテーション確率のベクトルで、eeは全要素が1のベクトルです。

実用上は、NCDawareRankは以下のようにべき乗法によって求められます。

NCDawareRankr(i)=(1ημ)1G+ηk=1soikNCDawareRankr1(k)+μk=1smikNCDawareRankr1(k) \begin{aligned} NCDawareRank^r(i) = (1-\eta-\mu)\frac{1}{|G|} \\ + \eta\sum_{k=1}^{s}o_{ik}NCDawareRank^{r-1}(k) \\ + \mu\sum_{k=1}^sm_{ik}NCDawareRank^{r-1}(k) \end{aligned}

ただしokio_{ki}OOkkii列目の要素を、mkim_{ki}MMにおけるkkii列目の要素を指します。 このアルゴリズムは、イテレーション時のNCDawareRankの差分が所与のε\varepsilonよりも小さくなった際、つまり以下が真になった際に収束します。

(iGNCDawareRankr(i)NCDawareRankr1(i))<ε \bigg(\sum_{i \in G}|NCDawareRank^r(i) - NCDawareRank^{r-1}(i)|\bigg) < \varepsilon

アウトリンク行列とレベル間近似度行列に加え、テレポーテーションが起こることで、アカウント間の遷移確率行列が、確率分布としての条件を満たし既約で原始的(primitive)であることが保証されますので、上記のアルゴリズムの収束も保証されます。 PageRankの数学的理論についての詳細は^9を参照してください。

^10で述べられているように、スパースな行列であるMMRRAAという2つの行列に分解することで、計算量を減らしてNCDawareRankをより高速に求めることができます。AA

A[eA1000eA2000eAN] A \triangleq \left[ \begin{array}{cccc} e_{|A_1|} & 0 & \cdots & 0 \\ 0 & e_{|A_2|} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & e_{|A_N|} \end{array} \right]

のように定義されます。ここでeAke_{A_k}は要素数Ak|A_k|で、全ての要素が1であるベクトルです。

c=(1A11A2...1AN) c = (\frac{1}{|A_1|} \frac{1}{|A_2|} ... \frac{1}{|A_N|})

R[c1R1c2R2...cNRN] R \triangleq \bigg[c_1R_{1*}^{'} c_2R_{2*}^{'} ... c_NR_{N*}^{'} \bigg]

ただしRiR_{i*}^{'}は、以下のように定義される行列RR^{'}ii番目の行です。

Rij{1Nu(Aiχu)0(otherwise) R_{ij} \triangleq \left\{ \begin{array}{ll} \frac{1}{N_u} & (A_i \in \chi_u) \\ 0 & (otherwise) \end{array} \right.

NEMの実装ではMMAARRに分解しています。これが以下に時間、空間計算量を削減するかについては^10で詳細な議論が行われています。

results matching ""

    No results matching ""