【論考】グループ分けページランク

以下の内容は、転載を禁じます。

【導入】

ページランクとそれに類するアルゴリズムは一般に、ランク付けすべき対象(本論考では、ノードと呼ぶ)は同質な集団である。(例えば、ページランクの場合はウェブページ、EigenTrustではブロックチェーンに参加しているノード)

 

本論考では、ノードが本質的に違うようないくつかの集団に分けられるが、お互いに関係があって相対的な評価が可能である場合に、グループ分けしてランクを評価したい、あるいは、何らかの属性を持っているノードをクラスタリングし、グループ分けして異なるグループに属するノード間の相対的な評価を何らかの方法で定義した場合に、クラスタリングにより分けられたグループのそれぞれのノードの中でのみランクを評価したい場合などを考える。

例えば、店舗網があり、複数のアルバイトがいて、それぞれのアルバイトはいくつか複数の店舗で働いた経験をもっているような場合を考えると、店舗網同士、アルバイト同士での相対的評価値は存在しないが、各店舗と各アルバイトでの相対的評価値は何らかの方法であらかじめ計算しておけるような状況が考えられる。

また、会社などの組織中で、取締役、エンジニア、営業などの本質的に異なるグループがあり、取締役同士で直接評価値を出したくはないが、エンジニア、営業などからどれぐらい評価値があるのかを考えたうえで取締役同士の評価をしたい場合なども考えられる。

さらに、ある文章があり、それぞれの文ごとに区切り、これを一グループとして、それぞれの文中の単語のそれぞれにスコアを与えたい場合なども考えられるだろう。

 

以下、このような状況を数学的に抽象化、一般化、定式化して議論を行う。

 

【数学的議論】

 

グループの集合\(\textbf{G}=\{G_1,G_2,…,G_n\}\)

ノードの集合\(\textbf{n}=\{n_1,n_2,…,n_N \}(\forall n \in \textbf{n},\exists ! G \in \textbf{G},n \in G)\)

とし、ノード\(i\)から\(j\)への相対評価を\(r_{ij}\)と書く。

全てのグループの数\(n(=|\textbf{G}|)\)を長さとする任意の巡回置換\(\sigma\)を考え、全てのグループ\(G_i\)に関して、それに属する全てのノードからあるグループ\(G_{\sigma (i)}\)に属する全てのノードのみへの\(|G_i||G_{\sigma(i)}|\)通りの正の相対評価値\(\forall n \in G_i,m \in G_{\sigma(i)}\)に対して\(r_{nm}\)があらかじめ何らかの方法で計算されている場合を考える。

\(\forall i \in \{1,2,…,n\},\forall n \in G_i,m \in G_{\sigma(i)},\exists r_{nm} \in \mathbb{R}_{>0},\)

\(if \ n \in G_i,m \not\in G_ {\sigma(i)},r_{nm}=0\)

逆に、巡回置換でない場合、以下の議論を追えばわかるように、相対評価を行列で表現したものは既約でないため、べき乗法による収束は保証されない。

巡回置換である場合には、以下に示すように数学的、アルゴリズム的に面白い。さらに以下で示すように、複数の巡回置換を考えて行列に足しこむことで理論は一般化できるから、本論考ではこの場合のみに絞って考えていく。

 

ここで、以下のようにそれぞれのノードを評価する方法を考える。

 まず、相対評価を表す行列\(r_{ij}\)を行列で表したもの)\(A\)は、行、列の入れ替え(つまり、\(\sigma(i)=i+1\)になるようにグループ番号を変更し、行列の各行、列に早いグループ番号に属するノードから詰めていく。)によって以下の形の行列に変形できる。

\(A=\begin{pmatrix}0 & A_1 & 0 & \cdots &0\\ 0 & 0 & A_2 & 0 &0\\ \vdots & \vdots & \vdots  &  \ddots &\\ A_n & 0 & 0 & 0 &0\end{pmatrix}\)

\(A_i\)は、グループ\(i\)の属するノードからグループ\(i+1\)に属するノードへの評価を表した行列である。

 \(A^2\)は、

\(A^2=\begin{pmatrix}0 & 0 & A_1 A_2 & \cdots &0\\ 0 & 0 & 0 & \cdots &0\\ \vdots & \vdots & \vdots  &  \ddots &\\ 0 & A_n A_1 & 0 & 0 &0\end{pmatrix}\)

となる。

これを繰り返す(n-1回の掛け算を行う)と、以下の式になることは容易に想像できよう。

\(A^n=\begin{pmatrix}A_1 A_2 … A_n & 0 & 0 & \cdots &0\\ 0 & A_2 A_3 … A_1 & 0 & \cdots &0 \\ \vdots & \vdots & \vdots  &  \ddots \\ 0 & 0 & 0 & 0 &A_n A_1 … A_n-1\end{pmatrix}\)

つまり対角線上に、それぞれのグループの要素数ごとの大きさの正方行列があるような行列が作れる。

それぞれの正方行列はまた、\(i\)のグループから\(i+1,i+2,…,N,1,…,i-1\)のグループの相対評価を考慮した上での、それぞれのグループ内での相対評価値を求めたものとして解釈できる。

それぞれの正方行列は一般に、全ての成分が正であるから、既約かつ非周期的である。よって、それぞれの正方行列でべき乗法を実行すれば、それぞれのグループ内での絶対的評価を計算することもできる。

つまり、対角線上のそれぞれの対角行列\(P_i=A_i A_{i+1}\cdots A_{i-1}\)と\(P_i\)の、最大固有値以外の固有値に属する固有ベクトルを除く、次元\(|G_i|\)の任意のベクトル\(x\)に対して、

\(\displaystyle \lim _{n \rightarrow \infty} (P_i)^n x/|(P_i)^n x|\)

を考えると、\(n \rightarrow \infty\)での収束が保証され、収束先のベクトルは、ページランクと同じようにそれぞれのノード固有の評価値として解釈できる。

(これは、\((A^n)^m\)を計算し、再度対角線上の正方行列を取り出すことと同じである。それぞれのグループの中でのみランク付けしたい場合、Aそのものの掛け算を計算する必要はないから、計算コストは削減できることに気付いてほしい。)

さらに、長さ\(n\)の巡回置換を複数考え、これを”道”のようなものと捉えることもできる。

道を複数考え、つまり大きさ\(n\)の巡回置換を複数考え、その巡回置換に対応するようなグループ間の評価値を行列\(A\)に足しこんだとしても、道に交わり(合流する部分、つまり2つの巡回置換\(\sigma_1,\sigma_2\)において、\(\sigma_1(i)=\sigma_2(i)\)となるような\(i\)が存在するとき)がない場合、行列の和の積は積の和に直せるから、計算コストを削減しつつ、有用な道をたくさん考えたうえで\(A\)に足しこむことも可能である。

交わりのある場合でも、繰り返しループの中でその交わりを考慮しなければならないとき以外で行列の和の積は積の和の形で書けるから、計算量は大幅に削減できる。