(57)【要約】      （修正有）【課題】有向グラフの各点の特徴値を、分散計算環境下で、隣接行列Ｇに重み行列Ｃを再帰的に作用させて求める際、各コンピュータ間の通信量を低減し、高速に処理するグラフデータ演算方法を提供する。【解決手段】グラフデータ演算方法は、重み行列を、複数のバーテックスの一つから出ている第１のエッジの終点のバーテックスである宛先バーテックスに関する第１の情報と、複数のバーテックスの一つに入ってくる第２のエッジの出発点である複数のバーテックスの一つである参照元バーテックスと第２のエッジに付与されている重みと第２のエッジの出発点である複数のバーテックスの一つ付与された特徴値とに関する第２の情報に分解することと、第１の情報に第２の計算機ノードが担当する第２のバーテックスが含まれている場合、第１の計算機ノードが、更新された第１のバーテックスに付与された特徴値を第２の計算機ノードに送ること、を含む。【選択図】図８
2015106374.tif 000002
【特許請求の範囲】
【請求項１】
複数のバーテックスの各々に付与される特徴値を要素とするベクトルである特徴値ベクトルを、バーテックス間を結ぶエッジの向きと前記エッジに付与される重みに関する情報を含む重み行列を用いて、少なくとも第１の計算機ノードおよび第２の計算機ノードを含む複数の計算機ノードによって逐次的に計算するグラフデータ演算方法であって、
前記重み行列を、前記複数のバーテックスの一つから出ている第１のエッジの終点のバーテックスである宛先バーテックスに関する第１の情報と、前記複数のバーテックスの一つに入ってくる第２のエッジの出発点である前記複数のバーテックスの一つである参照元バーテックスと前記第２のエッジに付与されている重みと前記第２のエッジの出発点である前記複数のバーテックスの一つ付与された前記特徴値に関する第２の情報に分解することと、
前記第１の計算機ノードにおいて、第１のバーテックスに付与された前記特徴値を更新するために、前記第２の情報を参照して演算を行い、更新された第１のバーテックスに付与された特徴値を求めることと、
前記第１の情報に前記第２の計算機ノードが担当する第２のバーテックスが含まれている場合、前記第１の計算機ノードが、前記更新された第１のバーテックスに付与された前記特徴値を前記第２の計算機ノードに送ること、
を含むグラフデータ演算方法。
【請求項２】
前記重み行列を分解することは、第１の計算機ノードにおいて、前記第１の計算機ノードを出発点とする第３のエッジの終点のバーテックスである宛先バーテックスに関する第３の情報と、前記第１の計算機ノードをに入ってくる第４のエッジの出発点である前記複数のバーテックスの一つである参照元バーテックスと前記第２のエッジに付与されている重みと前記第２のエッジの出発点である前記複数のバーテックスの一つ付与された前記特徴値に関する第４の情報に分解する、請求項１に記載のグラフデータ演算方法。
【請求項３】
さらに、
前記複数のバーテックスの一つを担当する前記複数の計算機ノードの一つを、前記複数のバーテックスと前記複数の計算機ノードの対応を示す表を参照して特定すること、
を含む請求項１または２に記載のグラフデータ演算方法。
【請求項４】
さらに、
前記複数のバーテックスの一つを担当する前記複数の計算機ノードの一つを、前記複数のバーテックスの識別子から計算して得られる数を用いて特定すること、
を含む請求項１または２に記載のグラフデータ演算方法。
【請求項５】
複数のバーテックスの各々に付与される特徴値を要素とするベクトルである特徴値ベクトルを、バーテックス間を結ぶエッジの向きと前記エッジに付与される重みに関する情報を含む重み行列を用いて、少なくとも第１の計算機ノードおよび第２の計算機ノードを含む複数の計算機ノードによって逐次的に計算するグラフデータ演算システムであって、
前記重み行列を、前記複数のバーテックスの一つから出ている第１のエッジの終点のバーテックスである宛先バーテックスに関する第１の情報と、前記複数のバーテックスの一つに入ってくる第２のエッジの出発点である前記複数のバーテックスの一つである参照元バーテックスと前記第２のエッジに付与されている重みと前記第２のエッジの出発点である前記複数のバーテックスの一つ付与された前記特徴値に関する第２の情報に分解する変換配備機構と、
前記第１の計算機ノードにおいて、前記第１のバーテックスに付与された前記特徴値を更新するために、前記第２の情報を参照して演算を行い、更新された第１のバーテックスに付与された特徴値を求める演算機構と、
前記第１の情報に前記第２の計算機ノードが含まれている場合、前記第１の計算機ノードが、前記更新された第１のバーテックスに付与された前記特徴値を前記第２の計算機ノードに送る伝播機構、を含むグラフデータ演算システム。
【請求項６】
複数のバーテックスの各々に付与される特徴値を要素とするベクトルである特徴値ベクトルを、バーテックス間を結ぶエッジの向きと前記エッジに付与される重みに関する情報を含む重み行列を用いて、少なくとも第１の計算機ノードおよび第２の計算機ノードを含む複数の計算機ノードによって逐次的に計算するグラフデータ演算プログラムであって、
前記重み行列を、前記複数のバーテックスの一つから出ている第１のエッジの終点のバーテックスである宛先バーテックスに関する第１の情報と、前記複数のバーテックスの一つに入ってくる第２のエッジの出発点である前記複数のバーテックスの一つである参照元バーテックスと前記第２のエッジに付与されている重みと前記第２のエッジの出発点である前記複数のバーテックスの一つ付与された前記特徴値に関する第２の情報に分解させ、
前記第１の計算機ノードにおいて、第１のバーテックスに付与された前記特徴値を更新するために、前記第２の情報を参照して演算を行い、更新された第１のバーテックスに付与された特徴値を求めさせ、
前記第１の情報に前記第２の計算機ノードが担当する第２のバーテックスが含まれている場合、前記第１の計算機ノードが、前記更新された第１のバーテックスに付与された前記特徴値を前記第２の計算機ノードに送らせ、
処理をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフデータ演算方法、システムおよびプログラムに関するものである。
【背景技術】
【０００２】
有向グラフで表されるデータ構造において、各バーテックスにおける特徴値の計算を分散コンピューティング環境で行なうシステムが知られている。そのようなシステムとして、例えば、ＷＥＢページのリンク関係を有向辺で表し、各ページのランク付けの値を各点の特徴値として表した有向グラフにおいて、各ページのランク付けの値を分散コンピューティング環境で求めるものが知られている。
【０００３】
たとえば、Ｎ点からなるグラフの構造は、各バーテックスに付与された値を要素とするＮ×Ｎ行列の隣接行列Ｇで表すことができる。各バーテックスには特徴値が付与されている。特徴値は、隣接するバーテックスとの間を結ぶエッジに付与された特徴値や隣接点に付与された特徴値と関連する。各エッジは重みを持っており、これらを各バーテックスの特徴値を計算するための行列Ｃ（以下、重み行列と呼ぶことがある）として表す。たとえば、バーテックスＡとバーテックスＢを結ぶエッジには向きが付いていても良い。このようなエッジを有向辺と呼ぶことがある。有向辺では、たとえば、バーテックスＡからバーテックスＢに向かうときの重みと、バーテックスＢからバーテックスＡに向かうときの重みが異なり得る。
【０００４】
各バーテックスの特徴値の算出法としてべき乗法が用いられることがある。これは、初期値となるベクトルＶ０に対して重み行列Ｃを作用させてベクトルＶ１を求め、さらにベクトルＶ１に対して行列Ｃを作用させてＶ２を求める形で計算を行ない、ベクトルＶｎとベクトルＶｎ−１とがほぼ同じ値となるまで再帰的に重み行列Ｃを作用させる。このように、各バーテックスの特徴値は、重み行列Ｃを用いて求めることができる。
【０００５】
このような計算を複数のコンピュータを用いる分散計算機環境で算出することが行われている。たとえば、随時構造が変化する可能性がある、有向辺と点からなる有向グラフ構造に対して各バーテックスの特徴値をＨａｄｏｏｐ等の分散計算機環境で算出する処理を取り扱うことが行われている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Ｕ．Ｋａｎｇ、Ｈ．Ｔｏｎｇ、Ｊ．Ｓｕｎ、Ｃ−Ｙ．Ｌｉｎ、Ｃ．Ｆａｌｏｕｔｓｏｓ“ＧＢＡＳＥ：Ａ  Ｓｃａｌａｂｌｅ  Ｇｅｎｅｒａｌ  Ｇｒａｐｈ  Ｍａｎａｇｅｍｅｎｔ  Ｓｙｓｔｅｍ”、Ｋｎｏｗｌｅｄｇｅ  Ｄｉｓｃｏｖｅｒｙ  ａｎｄ  Ｄａｔａ  Ｍｉｎｉｎｇ  ＫＤＤ−２０１１、ｐｐ．１０９１−１０９９  （２０１１）
【発明の概要】
【発明が解決しようとする課題】
【０００７】
有向グラフの各バーテックスの特徴値を、分散計算環境下で、隣接行列Ｇに重み行列Ｃを再帰的に作用させて求める際、ベクトルＶｎを求めるために用いるベクトルＶｎ−１のデータとして、対応する列の全ての値が必要である。つまり、各コンピュータの処理対象としてベクトルＶの特定の行を当てはめるだけでは処理ができない。したがって、各コンピュータは計算後の値を他のコンピュータに知らせる必要がある。このため、分散計算機環境での各コンピュータ間の通信量が膨大となってしまうという問題がある。
【０００８】
よって、一つの側面として、本発明は、有向グラフの各点の特徴値を、分散計算環境下で、隣接行列Ｇに重み行列Ｃを再帰的に作用させて求める際、各コンピュータ間の通信量の低減を図ったグラフデータ演算方法、システムおよびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
複数のバーテックスの各々に付与される特徴値を要素とするベクトルである特徴値ベクトルを、バーテックス間を結ぶエッジの向きと前記エッジに付与される重みに関する情報を含む重み行列を用いて、少なくとも第１の計算機ノードおよび第２の計算機ノードを含む複数の計算機ノードによって計算するグラフデータ演算方法が提供される。グラフデータ演算方法は、重み行列を、複数のバーテックスの一つから出ている第１のエッジの終点のバーテックスである宛先バーテックスに関する第１の情報と、複数のバーテックスの一つに入ってくる第２のエッジの出発点である複数のバーテックスの一つである参照元バーテックスと第２のエッジに付与されている重みと第２のエッジの出発点である複数のバーテックスの一つ付与された特徴値とに関する第２の情報に分解することと、前記第１の情報に前記第２の計算機ノードが担当する第２のバーテックスが含まれている場合、前記第１の計算機ノードが、前記更新された第１のバーテックスに付与された前記特徴値を前記第２の計算機ノードに送ること、を含むことを特徴とする。
【発明の効果】
【００１０】
有向グラフの各点の特徴値を、分散計算環境下で、隣接行列Ｇに重み行列Ｃを再帰的に作用させて求める際、各コンピュータ間の通信量を低減することができる。
【図面の簡単な説明】
【００１１】
【図１】有向グラフの例を示す図である。
【図２Ａ】各バーテックスに特徴値（Ｐ）と各エッジに辺重み（ｒ）が付与された有向グラフの例を示す図である。
【図２Ｂ】図２Ａに示された有向グラフの各エッジに付与された辺重みの例を示す図である。
【図２Ｃ】図２Ａに示された有向グラフの各バーテックスに付与された特徴値の例を示す図である。
【図３】実施形態のグラフデータ演算システムの概略を示す図である
【図４】実施形態のグラフデータ演算システムの構成の例を示す図である。
【図５】実施形態のグラフデータ演算システムの構成の例を示す図である。
【図６】実施形態のグラフデータ演算システムの構成の例を示す図である。
【図７】実施形態のグラフデータ演算システムの構成の例を示す図である。
【図８】実施形態のグラフデータ演算システムの変換配備機構を説明するための図である。
【図９】実施形態のグラフデータ演算システムの各計算機ノードにおけるデータの例を示す図である。
【図１０】実施形態のグラフデータ演算システムの各計算機ノードにおけるデータの例を示す図である。
【図１１】実施形態のグラフデータ演算システムの各計算機ノードにおけるデータの例を示す図である。
【図１２】実施形態のグラフデータ演算システムの各計算機ノードの構成の例を示す図である。
【図１３】実施形態のグラフデータ演算方法の処理の流れの例を示す図である。
【図１４】変換配備処理の流れの例を示す図である。
【図１５】ノードの特定処理の流れの例を示す図である。
【図１６】ノードの特定処理の流れの別の例を示す図である。
【図１７】ノード処理の流れの例を示す図である。
【図１８】計算処理の流れの例を示す図である。
【図１９】伝播処理の流れの例を示す図である。
【図２０】協調フィルタリングを説明するための図である。
【図２１】ユーザの評価値の決め方を説明するための図である。
【図２２】行列Ｙ、Ｒをグラフに変換して処理する仕方を説明するための図である。
【図２３】行列Ｙ、Ｒをグラフに変換して処理する仕方を説明するための図である。
【図２４】Ｘ、θの初期値の例を示す図である。
【図２５】変換配備処理後の各節点のＬｓｒｃの値の例を示す図である。
【図２６】変換配備処理後の各節点のＬｄｓｔの値の例を示す図である。
【発明を実施するための形態】
【００１２】
以下、図面を参照して、実施形態について説明する。以下で説明する実施形態は、有向グラフ構造に対して各バーテックスに付与された特徴値を分散計算機環境で算出する処理を取り扱うグラフデータ演算方法、システムおよびプログラムに関する。特に分散計算機環境での計算機間通信量を低く抑えながら実行するグラフデータ演算方法、システムおよびプログラムに関する。
【００１３】
まず、本明細書中で用いる用語の定義について簡単に説明する。
＜定義＞
図１は、有向グラフの例を示す図である。
【００１４】
有向グラフＧは、図１では数字を丸で囲まれているバーテックス（単に点とも呼ぶ）と、バーテックス間を結ぶ向き付きのエッジ（単に辺とも呼ぶ）を含んでいる。バーテックスに記載された数字は、バーテックスを指定する識別子（ＩＤ）であり得る。例えば、識別子“ｉ”（ｉは正整数とする）を有するバーテックスを単に、バーテックスｉと呼ぶことがある。
【００１５】
図１に示されている有向グラフＧは、３つのバーテックス１、２、３と３つのエッジａ、ｂ、ｃを含んでいる。図１に示されている有向グラフＧに含まれるバーテックスの集合をＶ＝｛１，２，３｝と表すことがある。また、図１に示されている有向グラフＧに含まれるエッジの集合をＥ＝｛ａ，ｂ，ｃ｝と表すことがある。バーテックスｉからバーテックスｊに向かうエッジｘをｘ＝ｉ→ｊと表すことがある。図１に示されている有向グラフＧのエッジの集合Ｅは、Ｅ＝｛ａ，ｂ，ｃ｝＝｛１→２、１→３、３→１｝を表される。
【００１６】
一般にＮ個のバーテックスとＭ個のエッジを含むグラフ構造は、隣接行列Ｐと接続行列Ｑを用いて表すことができる。
【００１７】
一般にＮ個のバーテックスとＭ個のエッジを含むグラフ構造の隣接行列Ｐは、Ｎ×Ｎ行列である。隣接行列Ｐは、
【数１】
2015106374.tif 000003
として、バーテックスｊからバーテックスｉにエッジが存在するならばａｉｊ＝１、そうでなければａｉｊ＝０である行列として定義する。
【００１８】
図１に示されているグラフＧの隣接行列Ｐは、
【数２】
2015106374.tif 000004
となる。
【００１９】
一般にＮ個のバーテックスとＭ個のエッジを含むグラフ構造の接続行列Ｑは、Ｎ×Ｍ行列である。接続行列Ｑは、
【数３】
2015106374.tif 000005
として、エッジｘがバーテックスｉから出るときｋｉｘ＝１、エッジｘがバーテックスｉへ入るときｋｉｘ＝−１である行列として定義する。エッジｘがバーテックスｉから出るとき、バーテックスｉを出力点と呼ぶことがある。エッジｘがバーテックスｉへ入るとき、バーテックスｉを入力点と呼ぶことがある。
【００２０】
図１に示されているグラフＧの接続行列Ｑは、
【数４】
2015106374.tif 000006
となる。
【００２１】
図２Ａは、各バーテックスに特徴値（Ｐ）と各エッジに辺重み（ｒ）が付与された有向グラフの例を示す図、図２Ｂは、図２Ａに示された有向グラフの各エッジに付与された辺重みの例を示す図、そして、図２Ｃは、図２Ａに示された有向グラフの各バーテックスに付与された特徴値の例を示す図である。
【００２２】
各バーテックスに付与される特徴値は、一般に隣接するバーテックスとの間を結ぶエッジに付与された特徴値や、隣接するバーテックスと特徴値と所定の関係を有することがある。この関係は、Ｎ個のバーテックスを含むグラフの場合、Ｎ×Ｎ行列で表される。
【００２３】
図２Ａに示されている例では、たとえば、図２Ｂに示されているようにバーテックス１に付与される特徴値は０．１４であり、これを“Ｐ［１］＝０．１４”と表す。同様に、バーテックス２、３についても、Ｐ［２］＝０．１１、Ｐ［３］＝０．１１である。
【００２４】
また、図２Ａに示されている例では、たとえば、図２Ｃに示されているようにエッジａ＝１→２に付与される辺重みは１／２であり、これを“ｒ（ａ）＝ａ２１＝１／２”と表す。同様に、エッジｂ、ｃについても、ｒ（ｂ）＝ａ３１＝１／２，ｒ（ｃ）＝ａ１３＝１である。
【００２５】
図２Ａ〜２Ｃに示されている例では、バーテックスはウェブページを表し、特徴値はそのウェブページのページランク（登録商標）であり得る。ページランクは、そのウェブページの重要度を示す指数である。ページランクは、「多くの良質なページからリンクされているページは、やはり良質なページである」 という再帰的な関係に基づいている。勿論、特徴値はページランクに限定されず、実施形態は、有向グラフ表示が有効なあらゆる例に適用可能である。
【００２６】
図２Ａ〜２Ｃに示されているグラフを用いて特徴値の算出に用いる関係式について説明する。
【００２７】
各バーテックスｖ∈Ｖに対して、バーテックスｖを出力点とするエッジｅ１、ｅ２、…、があったとして、それぞれのエッジの入力点をｗ１、ｗ２、…、とする。このとき、バーテックスｖの特徴値Ｐ［ｖ］は、
【数５】
2015106374.tif 000007
として求められ得る。上式で、｜Ｖ｜はバーテックスの総数、ｄは定数で、たとえば、ｄ＝０．８５である。
【００２８】
また、Ｐ[１］、Ｐ[２］、…、Ｐ[｜Ｖ｜］をまとめてベクトルＰで表すこととする。さらに、接続行列Ｑの各要素に、辺重みを掛け合わせて定義される重み行列Ｃを導入する。例えば、図２Ａ〜２Ｃに示されている例では、重み行列Ｃを、
【数６】
2015106374.tif 000008
とする。すると、ベクトルＰは、
【数７】
2015106374.tif 000009
と書くことができる。ここで、ｂは要素が定数であるベクトル、ｄは定数のスカラーである。図２Ａ〜２Ｃに示されている例では、定数ベクトルｂは、
【数８】
2015106374.tif 000010
と書くことが出来る。
【００２９】
特徴値Ｐ[１］、Ｐ[２］、…、Ｐ[｜Ｖ｜］（またはベクトルＰ）を算出する方法の一つとして、冪乗法が知られている。
【００３０】
以下では、冪乗法を用いて特徴値を算出する例を示すが、算出方法は冪乗法に限定されない。分散環境下で特徴値Ｐ[１］、Ｐ[２］、…、Ｐ[｜Ｖ｜］（またはベクトルＰ）が計算できる方法であれば、任意の方法を用いることが出来る。
【００３１】
冪乗法では、まず、特徴値Ｐ[１］、Ｐ[２］、…、Ｐ[｜Ｖ｜］（またはベクトルＰ）の初期値を設定する。たとえば、図２Ａ〜２Ｃに示されている例では、
【数９】
2015106374.tif 000011
と設定しても良い。
【００３２】
冪乗法では、まず、第１ステップで、
【数１０】
2015106374.tif 000012
を計算する。同様にＰ２、Ｐ３、…と計算し、第ｍステップでは、
【数１１】
2015106374.tif 000013
によってＰｍを求める。そして、上記の処理を、ベクトルＰｍ−１とベクトルＰｍの差が所定の条件を満たすほどに小さくなるまで繰り返す。ベクトルＰｍ−１とベクトルＰｍの差としては、要素ごとに比べたとき、差が最も大きいものをベクトルＰｍ−１とベクトルＰｍの差としても良いし、ベクトルＰｍ−１とベクトルＰｍの各要素の差の２乗の和をベクトルＰｍ−１とベクトルＰｍの差としても良い。
【００３３】
たとえば、重み行列Ｃが
【数１２】
2015106374.tif 000014
であり、ｂＴ＝（０．０５，０．０５，０．０５）（Ｔは転置を表す）、ｄ＝０．８５として、初期値Ｐ０が、
【数１３】
2015106374.tif 000015
の場合、ＰＴ１＝（０．０５，０．４８，０．４８）、ＰＴ２＝（０．４５，０．０７，０．０７）であり、ＰＴ１７＝（０．１４，０．１１，０．１１）、ＰＴ１８＝（０．１４，０．１１，０．１１）となり収束したとみなされる。
【００３４】
上記のように、演算を多数回行なって特徴値を算出する処理を複数個の計算機（計算ノード）で行うことを考える。たとえば、Ｎ個のバーテックスの特徴値を表すＮ要素のベクトルがｍ個に分割され、ｍ個の計算機で実行されるような場合が考えられる。
【００３５】
以下「バーテックス」はグラフの節点を表し，「ノード」は計算機を表すものとする。また、ノードを計算機ノードと呼ぶことがある。
【００３６】
＜＜比較例＞＞
分割した特徴値ベクトルの各部分を各計算機ノードで実行し、結果を他のノードに転送する方法では、次のような処理を行う。
【００３７】
以下では、Ｘ［ｉ；ｊ］を、行列Ｘの第ｉ行目から第ｊ行目までを表すこととする。Ｘがベクトルの場合、Ｘ［ｉ；ｊ］は、第ｉ要素から第ｊ要素を表す。
【００３８】
たとえば、まず、計算機ノード１では、
【数１４】
2015106374.tif 000016
を計算する。そして、得られたＰ１［１；１］を他の計算機ノードに送る。
【００３９】
同時に、計算機ノード２では、
【数１５】
2015106374.tif 000017
を計算する。そして、得られたＰ１［２；３］を他の計算機ノードに送る。
【００４０】
このように、有向グラフで表されるデータ構造において、各バーテックスにおける特徴値の計算を分散コンピューティング環境で行なう場合、密に結合するバーテックス同士を同一の計算機ノードに担当させ、計算機ノード間の転送を減らすなどの工夫がされ得る。
【００４１】
しかしながら、上記のようなアルゴリズムでは、有向グラフで表されるデータ構造において、各バーテックスにおける特徴値の計算を分散コンピューティング環境で行なうとき、計算のたびに計算結果を他の全ての計算機ノードに転送する。これは、各計算機ノードが、自身が担当するバーテックスがとのバーテックスと隣接しているかに関して、不完全な情報しか持たないためである。
【００４２】
また、密に結合する部分グラフを探す計算はＮＰ困難問題として知られており、計算コストが高い。
【００４３】
＜グラフデータ演算システム＞
以下で説明するグラフデータ演算システムでは、重み行列Ｃに相当する情報を、接続行列Ｑに相当する情報に変換し、エッジに付与される重みを付加したデータ構造を用い、接続行列Ｑの形式のデータに対する演算アルゴリズムを用いて、各計算機ノードに送るデータを必要最低限に抑えることができる。
【００４４】
このような構成を採用することによって、各計算機ノードには、計算に値が必要となる値のみを伝播することができる。このため、システム全体で必要とするメモリ量は従来の方法と同程度に抑えたまま、必要最低限の計算機ノード間通信のみを行う演算を実現できる。後述の、変換配備機構により、グラフ構造の密結合部分を探すことなく通信量削減可能なデータ分散配置を行うことができ、時間コストを削減することができる。またその際、変換配備機構により一般的でよく知られた行列形式の算出方法表記をそのまま流用して演算を行えるため、従来法と同じ作業量で準備して演算を行うことができるといった効果を得ることができる。
【００４５】
本実施形態では、特徴値Ｐ［１］、Ｐ［２］、…、Ｐ［｜Ｖ｜］（またはベクトルＰ）の計算に上述の冪乗法を用いるが、特徴値Ｐ［１］、Ｐ［２］、…、Ｐ［｜Ｖ｜］（またはベクトルＰ）を計算する別の方法を用いても、計算機ノード間通信を最小限にすることができる。
【００４６】
図３は、実施形態のグラフデータ演算システム１０の概略を示す図である。
グラフデータ演算システム１０は、変換配備機構１００、計算機ノード（演算用ノード）３００、３５０、３６０を含んでいる。
【００４７】
変換配備機構１００は、計算機ノード（演算用ノード）３００、３５０、３６０とは異なる計算機であり得る。
【００４８】
変換配備機構１００には、算出方法を表すデータ１０２が入力される。算出方法を表すデータ１０２には、重み行列Ｃ、バーテックスの総数｜Ｖ｜、定数ｄが含まれる。
【００４９】
図８は、実施形態のグラフデータ演算システム１０の変換配備機構１００を説明するための図である。
【００５０】
グラフデータ演算システム１０の変換配備機構１００は、入力された算出方法を表すデータ１０２に含まれる重み行列Ｃから宛先の集合である宛先集合２０２と参照元とパラメタの対の集合である参照元パラメタ集合２０４を出力する。宛先集合２０２と参照元パラメタ集合２０４は、各計算機ノードに対して定義され、各計算機ノードが必要とする最小限のデータである。
【００５１】
たとえば、重み行列Ｃが、
【数１６】
2015106374.tif 000018
で表される図１、２に示されている有向グラフでは、バーテックス１からはバーテックス２、３に向かうエッジが存在し、バーテックス３からはバーテックス１に向かうエッジが存在する。バーテックス２が出力点となるエッジは存在しない。よって、図８に示されているように、宛先集合２０２は、バーテックス１を出力点とする集合Ｌｄｓｔ（１）＝｛２、３｝、バーテックス２を出力点とする集合Ｌｄｓｔ（２）＝｛｝、バーテックス３を出力点とする集合Ｌｄｓｔ（３）＝｛１｝から構成される。
【００５２】
すなわち、宛先集合２０２は、Ｌｄｓｔ（ｉ）＝｛バーテックスｉを出力点とするエッジの終点のバーテックス｝である。
【００５３】
ここでバーテックス１は計算機ノード１が計算を担当し、バーテックス２は計算機ノード２が計算を担当し、バーテックス３は計算機ノード３が計算を担当するものとする。バーテックスｉ（ｉ＝１、２、３）に付与される特徴値をＰ［ｉ］とする。図８に示されている段階では、Ｐ［１］＝１、Ｐ［２］＝Ｐ［３］＝０であるとする。
【００５４】
また、バーテックス１に入ってくるエッジは、図２Ａに示されているように計算機ノード３からのものが存在する。そのエッジに付与される重みはｒ（ａ）＝１である。このように、図８に示されているように、参照元パラメタ集合２０４は、バーテックス１を入力点とする参照元とパラメタ（エッジに付与される重みと参照元バーテックスの特徴値Ｐ［３］）の集合Ｌｓｒｃ（１）＝｛（３，（ａ１３，Ｐ［３］））｝＝｛（３，（１，０））｝、バーテックス２を入力点とする参照元とパラメタ（エッジに付与される重み）の集合Ｌｓｒｃ（２）＝｛（１，（ａ２１，Ｐ［１］））｝＝｛（１，（１／２，０））｝、バーテックス３を入力点とする参照元とパラメタ（エッジに付与される重み）の集合Ｌｓｒｃ（３）＝｛（１，（ａ３１，Ｐ［１］））｝＝｛（１，（１／２，０）｝から構成される。
【００５５】
すなわち、参照元パラメタ集合２０４は、Ｌｓｒｃ（ｉ）＝｛（参照元のバーテックス、（エッジに付与される重みｒ（ａ）、参照元のバーテックスの特徴値Ｐ［ｊ］））｝である。
【００５６】
図３に示されているように、変換配備機構１００で生成された宛先集合２０２と参照元パラメタ集合２０４は、各計算機ノード３００、３５０、３６０に送られる。
【００５７】
たとえば、計算機ノード３００では、宛先集合２０２と参照元パラメタ集合２０４はそれぞれ、宛先集合データベース（ＤＢ）３０４と参照元パラメタデータベース（ＤＢ）３０６に格納される。
【００５８】
図９は、実施形態のグラフデータ演算システム１０の各計算機ノードにおけるデータの例を示す図である。
【００５９】
図９ではエッジごとに、重み行列Ｃから先集合２０２と参照元パラメタ集合２０４に変換する。
【００６０】
たとえば、バーテックス１からバーテックス２に向かうエッジａ２１の重みは１／２である。そこで、変換配備機構１００は、バーテックス１担当の演算用ノードの記憶領域の宛先集合データベース（ＤＢ）３０４の集合Ｌｄｓｔ（１）に２を追加する。また、変換配備機構１００は、バーテックス１担当の演算用ノードの記憶領域の参照元パラメタデータベース（ＤＢ）３０６の集合Ｌｓｒｃ（２）に（１，（１／２，１））を追加する。
【００６１】
バーテックス１からバーテックス３に向かうエッジａ３１の重みは１／２である。そこで、変換配備機構１００は、バーテックス１担当の演算用ノードの記憶領域の宛先集合データベース（ＤＢ）３０４の集合Ｌｄｓｔ（１）に３を追加する。また、変換配備機構１００は、バーテックス３担当の演算用ノードの記憶領域の参照元パラメタデータベース（ＤＢ）３０６の集合Ｌｓｒｃ（３）に（１，（１／２，１））を追加する。
【００６２】
バーテックス３からバーテックス１に向かうエッジａ１３の重みは１である。そこで、変換配備機構１００は、バーテックス１担当の演算用ノードの記憶領域の参照元パラメタデータベース（ＤＢ）３０６の集合Ｌｓｒｃ（１）に（３，（１，０））を追加する。また、変換配備機構１００は、バーテックス３担当の演算用ノードの記憶領域の宛先集合データベース（ＤＢ）３０４の集合Ｌｄｓｔ（３）に１を追加する。
【００６３】
したがって、図１０に示されているように、バーテックス１担当の演算用ノードの記憶領域の宛先集合データベース（ＤＢ）３０４にＬｄｓｔ（１）＝｛２，３｝が、参照元パラメタデータベース（ＤＢ）３０６にはＬｓｒｃ（１）＝｛（３，（１，０））｝が格納される。バーテックス２担当の演算用ノードの記憶領域の宛先集合データベース（ＤＢ）３０４にＬｄｓｔ（２）＝｛｝が、参照元パラメタデータベース（ＤＢ）３０６にはＬｓｒｃ（２）＝｛（１，（１／２，１））｝が格納される。バーテックス３担当の演算用ノードの記憶領域の宛先集合データベース（ＤＢ）３０４にＬｄｓｔ（３）＝｛１｝が、参照元パラメタデータベース（ＤＢ）３０６にはＬｓｒｃ（３）＝｛（１，（１／２，１））｝が格納される。
【００６４】
算出方法を現すデータ１０２に含まれるバーテックスの総数｜Ｖ｜、定数ｄは、固定値パラメタデータベース（ＤＢ）に格納される。
【００６５】
各計算機ノードには、別の計算機ノードで計算された結果も入力される。図３では更新情報３２０は、計算機ノード（演算用ノード）３５０で計算された結果で計算機ノード（演算用ノード）３００に入力されるものである。更新情報３２２は、計算機ノード（演算用ノード）３００で計算された結果で計算機ノード（演算用ノード）３６０に入力されるものである。
【００６６】
計算機ノード３００では、受信機構３１６が計算機ノード３５０から更新情報３２０を受ける。受信機構３１６が受けた更新情報３２０に関するデータは、他バーテックス演算前情報データベース（ＤＢ）３１０に格納される。
【００６７】
自バーテックス演算前情報データベース（ＤＢ）３１２は、計算機ノード３００で直前に計算された特徴値Ｐ［１］、Ｐ［２］、…、Ｐ［｜Ｖ｜］（またはベクトルＰ）の値が格納されている。
【００６８】
演算機構３０２は、参照元パラメタデータベース（ＤＢ）３０６に格納されているデータ、他バーテックス演算前情報データベース（ＤＢ）３１０に格納されているデータ、および自バーテックス演算前情報データベース（ＤＢ）３１２に格納されているデータを用いて、特徴値Ｐ［１］、Ｐ［２］、…、Ｐ［｜Ｖ｜］（またはベクトルＰ）の値を更新する。たとえば、演算機構３０２は、直前の計算の結果である特徴値Ｐ［１］、Ｐ［２］、…、Ｐ［｜Ｖ｜］（またはベクトルＰ）の値をＰ０とすると、
【数１７】
2015106374.tif 000019
によって新たな特徴値Ｐを計算することができる。定数ベクトルｂ、定数ｄは、参照元パラメタデータベース（ＤＢ）３０６に格納されているデータである。
【００６９】
直前の計算結果である特徴値Ｐ［１］、Ｐ［２］、…、Ｐ［｜Ｖ｜］（またはベクトルＰ）の値をＰ０とし、新たな特徴値をＰとする。
【００７０】
Ｘ［ｉ］で、ベクトルＸのｉ番目の値を示すものとする。
たとえば、演算機構３０２において、バーテックス１の特徴値Ｐ［１］は、
【数１８】
2015106374.tif 000020
で計算される。このとき、「Ｐ０［３］」の“３”は、Ｌｓｒｃ（１）＝｛（３，（１，０））｝中の“３”であり、「Ｐ０［３］×１」の“１”は、Ｌｓｒｃ（１）＝｛（３、（１、０））｝中の“１”である。演算機構３０２は、このような処理をＬｓｒｃ（ｉ）＝｛（ｊ，ｒ）｝が要素を持つ全てのタプル（ｊ，ｒ）について実行する。ここで、ｒ＝（エッジに付与される重みａｊｉ、参照元のバーテックスの特徴値Ｐ［ｊ］）である。
【００７１】
例えば、バーテックス３を担当する計算機ノードのデータ構造の変化を図１１を参照して説明する。
【００７２】
図１１は、実施形態のグラフデータ演算システムの各計算機ノードにおけるデータの例を示す図である。
【００７３】
まず、１回目の計算の実施直前では、バーテックス３を担当する計算機ノードには、宛先の集合は Ｌｄｓｔ（３）＝｛１｝、参照元パラメタ集合Ｌｓｒｃ（３）＝｛ （１，（１／２，１）） ｝、担当するバーテックスの前回演算後の特徴値Ｐ０［３］＝０、演算で必要となる点の前回演算後のＬｓｒｃ（３）内に格納した特徴値｛Ｐ［１］＝１｝が格納されている。
【００７４】
１回目の計算では、Ｐ［３］＝ｂ［３］＋ｄ×Ｐ０［１］×ａｊｉ＝０．０５＋０．８５×１×（１／２）＝０．４７５が計算される。よって、１回目の計算の実施後では、担当するバーテックスの今回演算後の特徴値Ｐ［３］＝０．４７５となる。
【００７５】
１回目の伝播実施後、担当する点の前回演算後の特徴値はＰ［３］＝０．４７５であり、演算で必要となる点の前回演算後のＬｓｒｃ（３）内に格納した特徴値は｛Ｐ［１］＝０．０５｝となる。演算結果は各バーテックスを担当する演算用ノードの他バーテックス演算前情報データベース（ＤＢ）３１０、または自バーテックス演算前情報データベース（ＤＢ）３１２に分散して格納、保持される。
【００７６】
これを繰り返すと、２回目の計算の実施後では、担当するバーテックスの今回演算後の特徴値Ｐ［３］＝０．０７１となる。
【００７７】
図３に戻って、演算機構３０２で計算された新たな特徴値Ｐは、自バーテックス演算後情報データベース（ＤＢ）３１４に格納される。
【００７８】
伝播機構３１８では、演算機構３０２で計算された新たな特徴値Ｐを必要な計算機ノードに伝播する。
【００７９】
伝播機構３１８は、演算機構３０２で新たに特徴値が計算されたバーテックスｊの特徴値Ｐ［ｊ］が、前の計算結果である特徴値Ｐｏと異なるときのみ、処理を行う。
【００８０】
たとえば伝播機構３１８は、演算機構３０２で新たに特徴値が計算されたバーテックスｊが自分自身が担当するバーテックスではなく、自身の参照元パラメタデータベース（ＤＢ）３０６に格納されている集合Ｌｓｒｃ（ｉ）の要素（ｊ，ｒ）に含まれる場合、バーテックスｊ担当の計算機ノードに更新情報として特徴値Ｐ［ｊ］を送る。そして伝播機構３１８は、バーテックスｊ担当の計算機ノードの他バーテックス演算前情報データベース（ＤＢ）３１０に格納されているバーテックスｊの特徴値をＰ［ｊ］に変更させる。
【００８１】
たとえば伝播機構３１８は、演算機構３０２で新たに特徴値が計算されたバーテックスｊは自分自身が担当するバーテックスではなく、自身の宛先集合データベース（ＤＢ）３０４に格納されているＬｄｓｔ（ｉ）に含まれるならば、バーテックスｊ担当の計算機ノードに更新情報として特徴値Ｐ［ｊ］を送る。そして伝播機構３１８は、バーテックスｊ担当の計算機ノードに自身の他バーテックス演算前情報データベース（ＤＢ）３１０に格納されているバーテックスｊの特徴値をＰ［ｊ］に変更させる。
【００８２】
また伝播機構３１８は、演算機構３０２で新たに特徴値が計算されたバーテックスｊの特徴値Ｐ［ｊ］について、自身がバーテックスｊ担当の計算機ノードであり、この値がＰｏ［ｊ］とは異なるならば、自身の自バーテックス演算前データベース３１２に格納されている値をＰ［ｊ］に更新する。
【００８３】
演算機構３０２と受信機構３１６と伝播機構３１８は組み合わされて、演算・伝播・受信機構３３０を構成する。
【００８４】
図３に示されているように、計算機ノード３００の伝播機構３１８から送られた新たな特徴値は、更新情報３２２として、適切な計算機ノード３００に送られる。
【００８５】
このように、複数のバーテックスの各々に付与される特徴値Ｐ［１］、…、Ｐ［ｎ］を要素とするベクトルである特徴値ベクトルＰを、バーテックス間を結ぶエッジの向きと前記エッジに付与される重みに関する情報を含む重み行列Ｃを用いて、少なくとも第１の計算機ノード３００および第２の計算機ノード３５０、３６０を含む複数の計算機ノードによって逐次的に計算するグラフデータ演算システムは、変換配備機１００、演算機構３０２、伝播機構３１８を含む。
【００８６】
変換配備機１００は、重み行列Ｃを、複数のバーテックスの一つから出ている第１のエッジの終点のバーテックスである宛先バーテックスに関する第１の情報「宛先の集合Ｌｄｓｔ」と、複数のバーテックスの一つに入ってくる第２のエッジの出発点である複数のバーテックスの一つである参照元バーテックスと第２のエッジに付与されている重みと第２のエッジの出発点である複数のバーテックスの一つに付与された特徴値Ｐ［ｉ］（ｉはバーテックスを指定する）とに関する第２の情報「参照元とパラメタの対の集合Ｌｓｒｃ」に分解する。
【００８７】
演算機構３０２は、第１の計算機ノードにおいて、第１のバーテックスに付与された特徴値を更新するために、第２の情報「参照元とパラメタの対の集合Ｌｓｒｃ」を参照して演算を行い、更新された第１のバーテックスに付与された特徴値を求める。
【００８８】
伝播機構３１８は、第１の情報「宛先の集合Ｌｄｓｔ」に第２の計算機ノードが担当する第２のバーテックスが含まれている場合、第１の計算機ノードは、前記更新された第１のバーテックスに付与された前記特徴値を第２の計算機ノードに送る。
【００８９】
実施形態のグラフデータ演算システムでは、上記のようなアルゴリズムでは、有向グラフで表されるデータ構造において、各バーテックスにおける特徴値の計算を分散コンピューティング環境で行なうとき、計算のたびに計算結果を、その計算結果を必要とする計算機ノードにのみ転送する。
【００９０】
このように各コンピュータに割り当てられた計算に必要な値のみをコンピュータ間に伝播させることによって、有向グラフの各点の特徴値を、分散計算環境下で、隣接行列Ｇに重み行列Ｃを再帰的に作用させて求める際、各コンピュータ間の通信量を低減し、高速に処理することができる。
【００９１】
図４は実施形態のグラフデータ演算システム１１の構成の例を示す図である。
グラフデータ演算システム１１では、１台の変換配備用ノード１２０に変換配備機構１００が含まれている。
【００９２】
変換配備用ノード１２０には、有向グラフ構造データストア（配信サーバとも呼ばれる）１１０から、有向グラフの構造に関する情報が入力される。たとえば有向グラフの構造に関する情報には、隣接行列Ｐ、接続行列Ｑなどが含まれ得る。
【００９３】
また、グラフの各バーテックスを担当する演算用ノード（計算機ノード）の割り当てを演算用ノードディレクトリサーバ１３０で管理する。演算用ノードディレクトリサーバ１３０は、グラフの各バーテックスと、バーテックスを担当する演算用ノード（計算機ノード）の対応に関する情報を含むバーテックス・ノード対応表１３２を含む。
【００９４】
演算用ノードディレクトリサーバ１３０は、ノードのＩＤとＩＰアドレスの対応表１４２を含むＤＮＳサーバ１４０を必要に応じて参照する。
【００９５】
演算用ノード３００、３５０、３６０のそれぞれは、演算・伝播・受信機構３３０を含む。演算用ノード３００、３５０、３６０のそれぞれは、演算用ノードディレクトリサーバ１３０を参照して、受信、計算、伝播を繰り返す。
【００９６】
図５は、実施形態のシステム１２の構成の例を示す図である。
グラフデータ演算システム１２では、１台の変換配備用ノード１２２に変換配備機構１００とバーテックスＩＤ・ノードＩＤ変換機構１２４が含まれている。
【００９７】
また、演算用ノード３００、３５０、３６０のそれぞれは、演算・伝播・受信機構３３０とバーテックスＩＤ・ノードＩＤ変換機構３４０を含む。
【００９８】
バーテックスＩＤ・ノードＩＤ変換機構１２４、３４０は、グラフの各バーテックスを担当する演算用ノードの割り当ての際、バーテックスＩＤからノードＩＤへの変換を行う。
【００９９】
グラフデータ演算システム１２では、図４に示されているグラフデータ演算システム１１の演算用ノードディレクトリサーバ１３０、ＤＮＳサーバ１４０は存在せず、その代わり、各計算機ノードはバーテックスＩＤ・ノードＩＤ変換機構１２４、３４０を含んでいる。
【０１００】
図６は、実施形態のグラフデータ演算システム１３の構成の例を示す図である。
グラフデータ演算システム１３では、複数の計算機ノード６００、６０２、６０４で変換配備を担当する。演算用ノードと１対１で対応する変換配備ノードに変換配備処理が割り振られている。
【０１０１】
また、変換配備を複数の計算機ノード６００、６０２、６０４に振り分けるために、振り分け用ノード１２６が複数の計算機ノード６００、６０２、６０４に接続されている。
【０１０２】
振り分け用ノード１２６は、エッジの両端のバーテックスの担当演算ノードと直結する変換配備ノード２箇所に処理を振る。
【０１０３】
たとえば、変換配備用ノード６０２は、演算用ノード７０２と１対１に対応する。変換配備用ノード６０２は、変換配備機構１００を含み、演算用ノード７０２は演算・伝播・受信機構３３０を含む。変換配備用ノード６０２の変換配備機構１００は、１つのエッジの変換につきＬｓｒｃ、Ｌｄｓｔいずれか一方の要素追加を指示する。
【０１０４】
演算用ノード７００、７０２、７０４のそれぞれは、対になる変換配備用ノードと一体に構成しても良い。
【０１０５】
図７は、実施形態のグラフデータ演算システム１４の構成の例を示す図である。
グラフデータ演算システム１４では、複数の計算機ノード６０６、６０８、６１０で変換配備を担当する。演算用ノードと多対多で接続する変換配備ノードに変換配備処理が割り振られる。
【０１０６】
グラフデータ演算システム１４の振り分け用ノード１２６は、ラウンドロビンで処理を分配する。グラフデータ演算システム１４は、図６に示されているグラフデータ演算システム１３で演算用ノードと変換配備ノードが１対１で対応していたものを、多対多に変更したものである。変換配備用ノード６０６、６０８、６１０の変換配備機構１００は、１つのエッジの変換につきＬｓｒｃ、Ｌｄｓｔを担当する各１ノード(計２ノード)に要素追加を指示する。
【０１０７】
図１５はグラフデータ演算システムを構成する計算機、たとえば、変換配備用ノード、演算用ノード、演算用ノードディレクトリサーバ、ＤＮＳサーバ、配信用サーバ等の構成の例を示す図である。
【０１０８】
このコンピュータ８００は、Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ（ＣＰＵ）８０２、Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ（ＲＯＭ）８０４、及びＲａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＲＡＭ）８０６を備えている。コンピュータ８００は、さらに、ハードディスク装置８０８、入力装置８１０、表示装置８１２、インタフェース装置８１４、及び記録媒体駆動装置８１６を備えている。なお、これらの構成要素はバスライン８１８を介して接続されており、ＣＰＵ８０２の管理の下で各種のデータを相互に授受することができる。
【０１０９】
Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ（ＣＰＵ）８０２は、このコンピュータ８００全体の動作を制御する演算処理装置であり、コンピュータ８００の制御処理部として機能する。
【０１１０】
Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ（ＲＯＭ）８０４は、所定の基本制御プログラムが予め記録されている読み出し専用半導体メモリである。ＣＰＵ８０２は、この基本制御プログラムをコンピュータ８００の起動時に読み出して実行することにより、このコンピュータ８００の各構成要素の動作制御が可能になる。
【０１１１】
Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＲＡＭ）８０６は、ＣＰＵ８０２が各種の制御プログラムを実行する際に、必要に応じて作業用記憶領域として使用する、随時書き込み読み出し可能な半導体メモリである。
【０１１２】
ハードディスク装置８０８は、ＣＰＵ８０２によって実行される各種の制御プログラムや各種のデータを記憶しておく記憶装置である。ＣＰＵ８０２は、ハードディスク装置８０８に記憶されている所定の制御プログラムを読み出して実行することにより、後述する各種の制御処理を行えるようになる。
【０１１３】
入力装置８１０は、例えばマウス装置やキーボード装置であり、情報処理装置のユーザにより操作されると、その操作内容に対応付けられている各種情報の入力を取得し、取得した入力情報をＣＰＵ８０２に送付する。
【０１１４】
表示装置８１２は例えば液晶ディスプレイであり、ＣＰＵ８０２から送付される表示データに応じて各種のテキストや画像を表示する。
【０１１５】
インタフェース装置８１４は、このコンピュータ８００に接続される各種機器との間での各種情報の授受の管理を行う。
【０１１６】
記録媒体駆動装置８１６は、可搬型記録媒体８１８に記録されている各種の制御プログラムやデータの読み出しを行う装置である。ＣＰＵ８０２は、可搬型記録媒体１１８に記録されている所定の制御プログラムを、記録媒体駆動装置８１６を介して読み出して実行することによって、後述する各種の制御処理を行うようにすることもできる。なお、可搬型記録媒体１１８としては、例えばＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）規格のコネクタが備えられているフラッシュメモリ、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＤＶＤ−ＲＯＭ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）などがある。
【０１１７】
このようなコンピュータ８００を用いて情報処理装置を構成するには、例えば、上述の各処理部における処理をＣＰＵ８０２に行わせるための制御プログラムを作成する。作成された制御プログラムはハードディスク装置８０８若しくは可搬型記録媒体８２０に予め格納しておく。そして、ＣＰＵ８０２に所定の指示を与えてこの制御プログラムを読み出させて実行させる。こうすることで、情報処理装置が備えている機能がＣＰＵ８０２により提供される。
【０１１８】
＜グラフデータ演算処理＞
図１３〜２０を参照して、グラフデータ演算処理について説明する。
【０１１９】
処理を開始すると、Ｓ１００で変換配備機構１００は、変換配備処理を行う。
変換配備処置を図１４を参照して説明する。
【０１２０】
Ｓ２００で変換配備機構１００は、ダミー変数ｉ、ｊをリセットする。たとえば、ｉ＝ｊ＝０とする。
【０１２１】
Ｓ２０２で変換配備機構１００は、ダミー変数ｉ、ｊを更新する。たとえば、ダミー変数ｉ、ｊのいずれかの値を１増やしても良い。ダミー変数ｉ、ｊは、バーテックスの数を｜Ｖ｜として、共に｜Ｖ｜以下の整数である。
【０１２２】
Ｓ２０４で変換配備機構１００は、重み行列Ｃのｉ行ｊ列の要素をｒ＝ａｉｊで表したときの、ａｉｊは非ゼロであるか否かを判定する。もしこの判定の結果が“Ｙｅｓ”、すなわちａｉｊは非ゼロである場合には、処理はＳ２０６に進む。もしこの判定の結果が“Ｎｏ”、すなわちａｉｊは非ゼロではない場合には、処理はＳ２０２に戻る。
【０１２３】
Ｓ２０６で変換配備機構１００は、本計算機ノードはバーテックスｊの変換を担当しているか否かを判断する。もしこの判定の結果が“Ｙｅｓ”、すなわち本計算機ノードはバーテックスｊの変換を担当している場合には、処理はＳ２０８に進む。もしこの判定の結果が“Ｎｏ”、すなわち本計算機ノードはバーテックスｊの変換を担当していない場合には、処理はＳ２１２に進む。
【０１２４】
Ｓ２０８で変換配備機構１００は、バーテックスｊの計算を担当する計算機ノードｎｊの特定処理を行う。
【０１２５】
計算機ノードｎｊの特定処理について、図１５、１６を参照して説明する。
図１５はノードの特定処理の流れの例を示す図であり、図１６はノードの特定処理の流れの別の例を示す図である。
【０１２６】
図１５に示されているように、処理が開始されるとＳ３００で変換配備機構１００は、演算用ノードディレクトリに問い合わせるなどして、バーテックスの識別子（ＩＤ）と担当するノードの識別子（ＩＤ）の対応表から、バーテックスｉを担当するノードの識別子（ＩＤ）とさらに対応するノードのＩＰアドレスを取得する。
【０１２７】
図１６に示されているノードの特定処理の流れの別の例では、Ｓ４００で変換配備機構１００は、（（「バーテックスの識別子（ＩＤ）」−１）  ｍｏｄ  ｍ）＋１を計算する。
【０１２８】
次のＳ４０２で変換配備機構１００は、計算結果をノードの識別子（ＩＤ）とし、同時にＤＮＳサーバ等に問い合わせてノードＩＤとＩＰアドレスの対応表からノードのＩＰアドレスを取得する。
【０１２９】
図１４に戻って、Ｓ２０８の次のＳ２１０で変換配備機構１００は、計算機ノードｎｊに対し集合Ｌｄｓｔ（ｊ）に（ｉ，ｒ）を追加するよう指示をする。ｒ＝ａｉｊ、Ｐ［ｉ］、 タプル（ａｉｊ，Ｐ［ｉ］）、空タプルのいずれかである。計算機ノードｎｊはこれを実施する。処理が終了するとＳ２１２に進む。
【０１３０】
Ｓ２１２で変換配備機構１００は、本計算機ノードはバーテックスｉの変換を担当しているか否かを判断する。もしこの判定の結果が“Ｙｅｓ”、すなわち本計算機ノードはバーテックスｉの変換を担当している場合には、処理はＳ２１４に進む。もしこの判定の結果が“Ｎｏ”、すなわち本計算機ノードはバーテックスｉの変換を担当していない場合には、処理はＳ２１８に進む。
【０１３１】
Ｓ２１４で変換配備機構１００は、バーテックスｉの計算を担当する計算機ノードｎｉの特定処理を行う。計算機ノードｎｉの特定処理については、図１５、１６に示されている。
【０１３２】
Ｓ２１６で変換配備機構１００は、計算機ノードｎｉに対し集合Ｌｓｒｃ（ｉ）に（ｊ，ｒ）を追加するよう指示をする。ここで、ｒ＝ａｉｊ、Ｐ［ｉ］、 タプル（ａｉｊ，Ｐ［ｉ］）、空タプルのいずれかである。計算機ノードｎｉはこれを実施する。処理が終了するとＳ２１８に進む。
【０１３３】
Ｓ２１８で変換配備機構１００は、ダミー変数ｉ、ｊのとりうる値の組合せ全てについて計算したか否かを判定する。もしこの判定の結果が“Ｙｅｓ”、すなわちダミー変数ｉ、ｊのとりうる値の組合せ全てについて計算した場合には、処理を終了する。もしこの判定の結果が“Ｎｏ”、すなわちダミー変数ｉ、ｊのとりうる値の組合せのいずれかについて計算していない場合には、処理はＳ２０２に戻る。ダミー変数ｉ、ｊは、バーテックスの数を｜Ｖ｜として、共に｜Ｖ｜以下の整数である。
【０１３４】
図１３に戻って、Ｓ１００の次のＳ１０２で変換配備機構１００は、各計算機ノードに演算で必要な固定値パラメタを配備する。図３に示されているシステム１０では、算出方法を表すデータ１０２を、たとえば、計算機ノード３００の固定値パラメタＤＢ３０８に送る。
【０１３５】
Ｓ１０２の次のＳ１０４で計算ノードの演算機構、たとえば計算機ノード３００の演算機構３０２は、各計算機ノードに割り当てられた計算を行う計算処理と、計算結果の伝播を行う伝播処理を含むノード処理を実行する。
【０１３６】
図１７は、ノード処理の流れの例を示す図である。
図１７に示されているように、処理が開始されるとＳ５００で演算機構３０２は計算処理を行う。
【０１３７】
計算処理について、図１８を参照して説明する。
図１８は計算処理の流れの例を示す図である。
【０１３８】
処理が開始されるとＳ６００で演算機構３０２は、ダミー変数ｉをリセットする。たとえば、ｉ＝１とする。ダミー変数ｉは、バーテックスの数を｜Ｖ｜として、｜Ｖ｜以下の整数である。
【０１３９】
次のＳ６０２で演算機構３０２は、ダミー変数ｉを更新する。たとえば、ダミー変数ｉの値を１増やしても良い。
【０１４０】
次のＳ６０４で演算機構３０２は、バーテックスｉの特徴値Ｐ［ｉ］に、定数ｂ［ｉ］を代入する。
【０１４１】
次のＳ６０６で演算機構３０２は、ｊをリセットする。ｊは、Ｌｓｒｃ（ｉ）が要素として持つタプル（ｊ、ｒ）に含まれるｊの値である。本ステップの処理を終了すると、処理はＳ６０８に進む。
【０１４２】
Ｓ６０８で演算機構３０２は、Ｌｓｒｃ（ｉ）が要素として持つタプル（ｊ，ｒ）のｊの更新を行う。本ステップの処理を終了すると、処理はＳ６１０に進む。
【０１４３】
Ｓ６１０で演算機構３０２は、
【数１９】
2015106374.tif 000021
を計算し、Ｐ［ｉ］を更新する。本ステップの処理を終了すると、処理はＳ６１２に進む。
【０１４４】
Ｓ６１２で演算機構３０２は、Ｌｓｒｃ（ｉ）が要素として持つタプル（ｊ，ｒ）の全てのｊについて処理をしたかを判定する。もしこの判定の結果が“Ｙｅｓ”、すなわち全てのｊについて処理をした場合には、Ｓ６１４に進む。もしこの判定の結果が“Ｎｏ”、すなわち全てのｊについて処理をしていない場合には、処理はＳ６０８に戻る。
【０１４５】
Ｓ６１４で演算機構３０２は、全てのｉについて処理をしたかを判定する。もしこの判定の結果が“Ｙｅｓ”、すなわち全てのｉについて処理をした場合には、処理を終了する。もしこの判定の結果が“Ｎｏ”、すなわち全てのｉについて処理をしていない場合には、処理はＳ６０２に戻る。
【０１４６】
図１７に戻って、Ｓ５００の計算処理が終了すると、Ｓ５０２で伝播機構３１８は、伝播処理を行う。
【０１４７】
伝播処理について図１９を参照して説明する。
図１９は、伝播処理の流れの例を示す図である。
【０１４８】
処理が開始されると、Ｓ７００で伝播機構３１８は、ダミー変数ｊをリセットする。たとえば、ｊ＝０とする。ダミー変数ｊはバーテックスの数を｜Ｖ｜として、｜Ｖ｜以下の整数である。
【０１４９】
次のＳ７０２で伝播機構３１８は、ダミー変数ｊを更新する。たとえば、ダミー変数ｊの値を１増やしても良い。
【０１５０】
Ｓ７０４で伝播機構３１８は、バーテックスｊにおいて、Ｐ［ｊ］≠Ｐｏ［ｊ］かどうかを判定する。もしこの判定の結果が“Ｙｅｓ”、すなわちＰ［ｊ］≠Ｐｏ［ｊ］の場合には、処理はＳ７０６に進む。もしこの判定の結果が“Ｎｏ”、すなわちＰ［ｊ］≠Ｐｏ［ｊ］ではない場合には、処理はＳ７０２に戻る。
【０１５１】
Ｓ７０６で伝播機構３１８は、直前の計算結果であるＰｏ［ｊ］をＰ［ｊ］＝ｖｎｅｗに更新する。本ステップの処理を終了すると、処理はＳ７０８に進む。
【０１５２】
Ｓ７０８で伝播機構３１８は、Ｌｓｒｃの要素（ｊ，ｒ）のｒにバーテックス特徴値Ｐ［ｊ］が含まれるか否かを判定する。もしこの判定の結果が“Ｙｅｓ”、すなわちＬｓｒｃの要素（ｊ，ｒ）のｒにバーテックス特徴値Ｐ［ｊ］が含まれる場合には、処理はＳ７１０に進む。もしこの判定の結果が“Ｎｏ”、すなわちＬｓｒｃの要素（ｊ，ｒ）のｒにバーテックス特徴値Ｐ［ｊ］が含まれない場合には、処理はＳ７２４に進む。
【０１５３】
Ｓ７１０で伝播機構３１８は、ダミー変数ｉをリセットする。
次のＳ７１２で伝播機構３１８は、Ｌｄｓｔ（ｊ）が要素として持つタプル（ｉ、（ａｉｊ，Ｐ［ｊ］）） のｉを更新する。たとえば、ｉの値を１つ増やす。
【０１５４】
次のＳ７１４で伝播機構３１８は、バーテックスｉの計算を担当する計算機ノードｎｉの特定処理を行う。計算機ノードｎｉの特定処理については、図１５、１６に示されているので、ここでは繰り返さない。本ステップの処理を終了すると、処理はＳ７１６に進む。
【０１５５】
Ｓ７１６で伝播機構３１８は、計算機ノードｎｉは自ノードかどうかを判定する。もしこの判定の結果が“Ｙｅｓ”、すなわち計算機ノードｎｉは自ノードである場合には、処理はＳ７１８に進む。もしこの判定の結果が“Ｎｏ”、すなわち計算機ノードｎｉは自ノードではない場合には、処理はＳ７２０に進む。
【０１５６】
Ｓ７１８で伝播機構３１８は、Ｌｓｒｃ（ｉ）の要素（ｊ，ｒ）のｒに含まれるバーテックス特徴値Ｐ［ｊ］、たとえば、自バーテックス演算前情報ＤＢに格納されている値をｖｎｅｗに更新する。本ステップの処理を終了すると、処理はＳ７２２に進む。
【０１５７】
Ｓ７２０で伝播機構３１８は、計算機ノードｎｉに更新情報としてｊの値とｖｎｅｗを送る。そして、計算機ノードｎｉは、Ｌｓｒｃ（ｉ）の要素（ｊ，ｒ）のｒに含まれるバーテックス特徴値Ｐ［ｊ］、たとえば計算機ノードｎｉの他バーテックス演算前情報ＤＢに格納されている値をｖｎｅｗに更新する。本ステップの処理を終了すると、処理はＳ７２２に進む。
【０１５８】
Ｓ７２２で伝播機構３１８は、全てのｉについて処理をしたか否かを判定する。この判定の結果が“Ｙｅｓ”、すなわち全てのｉについて処理をした場合には、処理はＳ７２４に進む。もしこの判定の結果が“Ｎｏ”、すなわち全てのｉについて処理をしていない場合には、処理はＳ７１２に進む。
【０１５９】
Ｓ７２４で伝播機構３１８は、Ｓ７０８〜Ｓ７２２における「Ｌｓｒｃ」と「Ｌｄｓｔ」を入れ替えた処理を行う。本ステップの処理を終了すると、処理はＳ７２６に進む。
【０１６０】
Ｓ７２６で伝播機構３１８は、全てのｊについて処理をしたか否かを判定する。この判定の結果が“Ｙｅｓ”、すなわち全てのｊについて処理をした場合には、処理を終了する。もしこの判定の結果が“Ｎｏ”、すなわち全てのｊについて処理をしていない場合には、処理はＳ７０２に戻る。
【０１６１】
上記のような処理を行うことで、重み行列Ｃに相当する情報を、接続行列Ｑに相当する情報に変換し、エッジの属性値を付加したデータ構造を用い、接続行列Ｑの形式のデータに対する演算アルゴリズムを用いて、各計算機ノードに送るデータを必要最低限に抑えることができる。
【０１６２】
＜実施例＞
図２０〜２６を参照して、上述の実施形態を協調フィルタリングに適用した例を説明する。
【０１６３】
図２０は、協調フィルタリングを説明するための図である。
協調フィルタリングとは、多くのユーザの嗜好情報を蓄積し、あるユーザと嗜好の類似した他のユーザの情報を用いて自動的に推論を行う方法である。
【０１６４】
図２０に示されているように、ユーザｕ１〜ｕ４のそれぞれが、物品ｍ１〜ｍ５を、たとえば５段階で評価するものとする。評価の値は高いほどユーザはその物品を高く評価しているものとする。もちろん、逆でも良い。
【０１６５】
図２０では、ユーザｕ１は物品ｍ１〜ｍ５の全てについて既に評価をしている。ユーザｕ２は物品ｍ１について既に評価をしている。ユーザｕ３は物品ｍ５について既に評価をしている。ユーザｕ４は物品ｍ３について既に評価をしている。未評価の部分の評価値を推定する。ユーザの数を｜ｕ｜、評価の対象となる物品の数を｜ｍ｜とする。
【０１６６】
図２１は、評価値行列Ｙ、評価済行列Ｒを示す図である。
図２１に示されているように評価値行列と呼ばれる行列Ｙは、｜ｍ｜行｜ｕ｜列の行列である。第ｉ行ｊ列の行列要素は、物品ｍｉのユーザｕｊによる評価の値である。
【０１６７】
また、評価済行列Ｒの第ｉ行ｊ列の行列要素は、物品ｍｉがユーザｕｊによって既に評価されていれば「１」、さもなければ「０」である。
【０１６８】
ユーザの評価値を算出する１手法として、評価値行列Ｙを２つの行列、すなわち特徴値行列Ｘと、ユーザパラメタ値行列Θの積で算出するモデルを採用することができる。すなわち、ｆを正整数として、特徴値行列Ｘを｜ｍ｜行ｆ列の行列、ユーザパラメタ値行列Θを｜ｕ｜行ｆ列の行列とすると、
【数２０】
2015106374.tif 000022
で定義される行列Ｙ’と実際の評価値行列Ｙの差が小さくなる特徴値行列Ｘとユーザパラメタ値行列Θを探索し、未評価の部分を推定する。
【０１６９】
特徴値行列Ｘとユーザパラメタ値行列Θの探索には、たとえば、勾配降下法を用いることができる。
【０１７０】
この場合、評価関数Ｊ（Ｘ，Θ）を、特徴値行列Ｘを（ｘ（ｋ，ｉ））、ユーザパラメタ値行列Θを（θ（ｋ，ｊ））として、
【数２１】
2015106374.tif 000023
で定義する。
【０１７１】
勾配降下法では、特徴値行列Ｘとユーザパラメタ値行列Θの各要素の偏微分値を使って、評価関数値のより小さな値を探す。
【数２２】
2015106374.tif 000024
ｘ（ｉ，ｋ）とθ（ｊ，ｋ）の全てを同時に更新する処理を１回と数えて、ｍ回目の評価関数Ｊ（Ｘ，Θ）の計算結果と、ｍ＋１回目の評価関数Ｊ（Ｘ，Θ）の計算結果の差が十分に小さくなるまで処理を複数回繰り返す。
上のｘ（ｉ，ｋ）とθ（ｊ，ｋ）の更新に、上記実施形態を適用することができる。
【０１７２】
図２２、２３は、行列Ｙ、Ｒをグラフに変換して処理する仕方を説明するための図である。
【０１７３】
図２２に示されているように、各行、各列をバーテックスに対応づける。評価済み行列Ｒの第ｉ行ｊ列の行列要素が１である場合、評価値行列Ｙの要素値をエッジの特徴値に対応させる。ここでエッジは、列が元になったバーテックスから，行が元になったバーテックスへの有向辺として定義する。たとえば、図２２に示されている例では評価値行列Ｙの要素値ｙ（ｉ，ｊ）は、ユーザｕｊから物品ｍｉへの有向辺となる。
【０１７４】
図２３に示されているように、行列Ｘ、Θをバーテックスの特徴値に変換する。たとえば、Ｘの各行ベクトルｘ（ｉ，＊）をバーテックスｍｉの特徴値にする。Θの各行ベクトルθ（ｊ，＊） を節点ｕｊの特徴値にする。
【０１７５】
例えばバーテックスｍ３の特徴値ｘ（３，＊）は、（ｘ（３，１），ｘ（３，２），ｘ（３，３））となる。例えばバーテックスｕ１の特徴値θ（１，＊）は、（θ（１，１）、θ（１，２）、θ（１，３））となる（ｆ＝３の場合）。
【０１７６】
特徴値行列Ｘ、ユーザパラメタ値行列Θのランダムな初期値を図２４に示されているように設定し，勾配下降法で特徴値行列Ｘとユーザパラメタ値行列Θの各要素の更新を行う。
実際に、上記実施形態を適用して計算する。
【０１７７】
図２５は、変換配備処理後の各バーテックスのＬｓｒｃの値の例を示す図であり、図２６は、変換配備処理後の各節点のＬｄｓｔの値の例を示す図である。
【０１７８】
また、図１４に示されている変換配備処理において、Ｓ２１０における集合Ｌｄｓｔは、Ｌｄｓｔ（ｊ，（ａｉｊ，Ｐ［ｉ］））に、Ｓ２１６における集合Ｌｓｒｃは、Ｌｓｒｃ（ｉ，（ａｉｊ，Ｐ［ｊ］））とする。さらに、図１８に示されている計算処理において、Ｓ６１０で演算機構３０２は、
【数２３】
2015106374.tif 000025
の計算を行う。またＳ６０４で演算機構３０２は何も行わない。
【０１７９】
たとえば、ｍ３の特徴値を算出する際は、ｋ＝｛１，２，３｝として、
【数２４】
2015106374.tif 000026
を計算する。この算出に必要な値のうち、ｘ（３，＊）はバーテックスｍ３の特徴値として自身の計算機ノードにローカルに存在するが、θ（１，＊）、θ（４，＊）、ｙ（３，１）、ｙ（３，４）は、Ｌｓｒｃ（ｍ３）の中に存在する。よって、算出はバーテックスｍ３を担当する計算機ノードにローカルに存在する値のみを用いて行える。
【０１８０】
ｘ（３，＊）＝（ｘ（３，１）、ｘ（３，２）、ｘ（３，３））＝（１．３，−０．３，−１．１）、θ（１，＊）＝（θ（１，１），θ（１，２），θ（１，３））＝（−０．４，−１．２，０．８）を得ることができる。
【０１８１】
以上の実施形態に関し、さらに以下の付記を開示する。
（付記１）
複数のバーテックスの各々に付与される特徴値を要素とするベクトルである特徴値ベクトルを、バーテックス間を結ぶエッジの向きと前記エッジに付与される重みに関する情報を含む重み行列を用いて、少なくとも第１の計算機ノードおよび第２の計算機ノードを含む複数の計算機ノードによって逐次的に計算するグラフデータ演算方法であって、
前記重み行列を、前記複数のバーテックスの一つから出ている第１のエッジの終点のバーテックスである宛先バーテックスに関する第１の情報と、前記複数のバーテックスの一つに入ってくる第２のエッジの出発点である前記複数のバーテックスの一つである参照元バーテックスと前記第２のエッジに付与されている重みと前記第２のエッジの出発点である前記複数のバーテックスの一つ付与された前記特徴値に関する第２の情報に分解することと、
前記第１の計算機ノードが、第１のバーテックスに付与された前記特徴値を更新するために、前記第２の情報を参照して演算を行い、更新された第１のバーテックスに付与された特徴値を求めることと、
前記第１の情報に前記第２の計算機ノードが担当する第２のバーテックスが含まれている場合、前記第１の計算機ノードが、前記更新された第１のバーテックスに付与された前記特徴値を前記第２の計算機ノードに送ること、
を含むグラフデータ演算方法。
（付記２）
前記重み行列を分解することは、第１の計算機ノードにおいて、前記第１の計算機ノードを出発点とする第３のエッジの終点のバーテックスである宛先バーテックスに関する第３の情報と、前記第１の計算機ノードをに入ってくる第４のエッジの出発点である前記複数のバーテックスの一つである参照元バーテックスと前記第２のエッジに付与されている重みと前記第２のエッジの出発点である前記複数のバーテックスの一つ付与された前記特徴値に関する第４の情報に分解する、付記１に記載のグラフデータ演算方法。
（付記３）
さらに、
前記複数のバーテックスの一つを担当する前記複数の計算機ノードの一つを、前記複数のバーテックスと前記複数の計算機ノードの対応を示す表を参照して特定すること、
を含む付記１または２に記載のグラフデータ演算方法。
（付記４）
さらに、
前記複数のバーテックスの一つを担当する前記複数の計算機ノードの一つを、前記複数のバーテックスの識別子から計算して得られる数を用いて特定すること、
を含む付記１または２に記載のグラフデータ演算方法。
（付記５）
複数のバーテックスの各々に付与される特徴値を要素とするベクトルである特徴値ベクトルを、バーテックス間を結ぶエッジの向きと前記エッジに付与される重みに関する情報を含む重み行列を用いて、少なくとも第１の計算機ノードおよび第２の計算機ノードを含む複数の計算機ノードによって逐次的に計算するグラフデータ演算システムであって、
前記重み行列を、前記複数のバーテックスの一つから出ている第１のエッジの終点のバーテックスである宛先バーテックスに関する第１の情報と、前記複数のバーテックスの一つに入ってくる第２のエッジの出発点である前記複数のバーテックスの一つである参照元バーテックスと前記第２のエッジに付与されている重みと前記第２のエッジの出発点である前記複数のバーテックスの一つ付与された前記特徴値に関する第２の情報に分解する変換配備機構と、
前記第１の計算機ノードにおいて、前記第１のバーテックスに付与された前記特徴値を更新するために、前記第２の情報を参照して演算を行い、更新された第１のバーテックスに付与された特徴値を求める演算機構と、
前記第１の情報に前記第２の計算機ノードが担当する第２のバーテックスが含まれている場合、前記第１の計算機ノードが、前記更新された第１のバーテックスに付与された前記特徴値を前記第２の計算機ノードに送る伝播機構、を含むグラフデータ演算システム。
（付記６）
前記変換配備機構は、第１の計算機ノードにおいて、前記第１の計算機ノードを出発点とする第３のエッジの終点のバーテックスである宛先バーテックスに関する第３の情報と、前記第１の計算機ノードに入ってくる第４のエッジの出発点である前記複数のバーテックスの一つである参照元バーテックスと前記第２のエッジに付与されている重みと前記第２のエッジの出発点である前記複数のバーテックスの一つ付与された前記特徴値に関する第４の情報に分解する、付記５に記載のグラフデータ演算システム。
（付記７）
さらに、
前記複数のバーテックスの一つを担当する前記複数の計算機ノードの一つを、前記複数のバーテックスと前記複数の計算機ノードの対応を示す表を参照して特定する演算用ノードディレクトリサーバ、
を含む付記５または６に記載のグラフデータ演算システム。
（付記８）
さらに、
前記複数のバーテックスの一つを担当する前記複数の計算機ノードの一つを、前記複数のバーテックスの識別子から計算して得られる数を用いて特定するＤＮＳサーバ、
を含む付記１または２に記載のグラフデータ演算システム。
（付記９）
複数のバーテックスの各々に付与される特徴値を要素とするベクトルである特徴値ベクトルを、バーテックス間を結ぶエッジの向きと前記エッジに付与される重みに関する情報を含む重み行列を用いて、少なくとも第１の計算機ノードおよび第２の計算機ノードを含む複数の計算機ノードによって逐次的に計算するグラフデータ演算プログラムであって、
前記重み行列を、前記複数のバーテックスの一つから出ている第１のエッジの終点のバーテックスである宛先バーテックスに関する第１の情報と、前記複数のバーテックスの一つに入ってくる第２のエッジの出発点である前記複数のバーテックスの一つである参照元バーテックスと前記第２のエッジに付与されている重みと前記第２のエッジの出発点である前記複数のバーテックスの一つ付与された前記特徴値に関する第２の情報に分解させ、
前記第１の計算機ノードにおいて、前記第１のバーテックスに付与された前記特徴値を更新するために、前記第２の情報を参照して演算を行い、更新された第１のバーテックスに付与された特徴値を求めさせ、
前記第１の情報に前記第２の計算機ノードが担当する第２のバーテックスが含まれている場合、前記第１の計算機ノードが、前記更新された第１のバーテックスに付与された前記特徴値を前記第２の計算機ノードに送らせ、
処理をコンピュータに実行させることを特徴とするプログラム。
（付記１０）
前記重み行列を分解させることは、第１の計算機ノードに、前記第１の計算機ノードを出発点とする第３のエッジの終点のバーテックスである宛先バーテックスに関する第３の情報と、前記第１の計算機ノードをに入ってくる第４のエッジの出発点である前記複数のバーテックスの一つである参照元バーテックスと前記第２のエッジに付与されている重みと前記第２のエッジの出発点である前記複数のバーテックスの一つ付与された前記特徴値に関する第４の情報に分解させる処理をコンピュータに実行させることを特徴とする、付記９に記載のグラフデータ演算プログラム。
（付記１１）
さらに、
前記複数のバーテックスの一つを担当する前記複数の計算機ノードの一つを、前記複数のバーテックスと前記複数の計算機ノードの対応を示す表を参照して特定させる、
処理をコンピュータに実行させることを特徴とする、付記９または１０に記載のグラフデータ演算プログラム。
（付記１２）
さらに、
前記複数のバーテックスの一つを担当する前記複数の計算機ノードの一つを、前記複数のバーテックスの識別子から計算して得られる数を用いて特定させる、
処理をコンピュータに実行させることを特徴とする、付記９または１０に記載のグラフデータ演算プログラム。
【符号の説明】
【０１８２】
１００  変換配備機構
３００、３５０、３６０  計算機ノード（演算用ノード）
３０２  演算機構  
３１６  受信機構
３１８  伝播機構
【図１】
2015106374.tif 000027
【図２Ａ】
2015106374.tif 000028
【図２Ｂ】
2015106374.tif 000029
【図２Ｃ】
2015106374.tif 000030
【図３】
2015106374.tif 000031
【図４】
2015106374.tif 000032
【図５】
2015106374.tif 000033
【図６】
2015106374.tif 000034
【図７】
2015106374.tif 000035
【図８】
2015106374.tif 000036
【図９】
2015106374.tif 000037
【図１０】
2015106374.tif 000038
【図１１】
2015106374.tif 000039
【図１２】
2015106374.tif 000040
【図１３】
2015106374.tif 000041
【図１４】
2015106374.tif 000042
【図１５】
2015106374.tif 000043
【図１６】
2015106374.tif 000044
【図１７】
2015106374.tif 000045
【図１８】
2015106374.tif 000046
【図１９】
2015106374.tif 000047
【図２０】
2015106374.tif 000048
【図２１】
2015106374.tif 000049
【図２２】
2015106374.tif 000050
【図２３】
2015106374.tif 000051
【図２４】
2015106374.tif 000052
【図２５】
2015106374.tif 000053
【図２６】
2015106374.tif 000054