(57)【要約】【課題】  消費活動に関係する様々な主体の信頼値、及び、主体間の関係を定義し、これらに基づいて主体の信頼値を求めることは、消費者にとって非常に重要である。消費活動に関係する様々な主体の数が膨大である場合においても、ユーザによって特定される主体の信頼値を効率的に求めることが必要である。【解決手段】  本願明では、膨大の数の主体を含む信頼ネットワークグラフを分割することにより、所定のノードを含む副信頼ネットワークグラフの信頼値を効率的に求める方法・装置を開示する。【選択図】  図５
2007299138.tif 000002
【特許請求の範囲】
【請求項１】
以下の手段を有する、一つ以上の副信頼ネットワークグラフを含む信頼ネットワークグラフにおいて、第一の副信頼ネットワークグラフに含まれる第一のノードの信頼値を求める装置。
前記第一の副信頼ネットワークグラフのノードから前記第一の副信頼ネットワークグラフのノードへ向う矢で指定されるノードに基づいて生成される第一の変換遷移行列（ｎ行ｎ列）と、
前記第一の副信頼ネットワークグラフのノードから前記第一の副信頼ネットワークグラフ外のノードへ向う矢で指定されるノードに基づいて生成される第二の変換遷移行列（ｎ行１列）と、
前記第一の副信頼ネットワークグラフ外のノードから前記第一の副信頼ネットワークグラフのノードへ向う矢で指定されるノードに基づいて生成される第三の変換遷移行列（１行ｎ列）と、
前記第一の副信頼ネットワークグラフ外のノードから前記第一の副信頼ネットワークグラフ外のノードへ向う矢で指定されるノードに基づいて生成される第四の変換遷移行列（１行１列）とから、
第五の変換遷移行列Ｒ（（ｎ＋１）行（ｎ＋１）列）を生成し、ｘ＝ＲＴｘの変換遷移行列の固有ベクトルｘを求めることにより、前記第一の副信頼ネットワークグラフのノードの信頼値を求める手段。但しＴは転置を表す。
【請求項２】
前記第三の変換遷移行列（１行ｎ列）は、前記第一の副信頼ネットワークグラフ外のノードから前記第一の副信頼ネットワークグラフのノードへ向う矢で指定されるノードに重み係数を乗じて求める請求項１に記載の装置。
【請求項３】
前記重み係数は、以下の（ａ）から（ｃ）のいずれかで定義される重み係数を含む請求項２に記載の装置。
（ａ）各ノードに同等の重みを与える重み係数。
（ｂ）既に求められているネットワークグラフ全体の各ノードの信頼値に基づいて求められる重み係数。
（ｃ）前記副信頼ネットワークグラフ毎に求められている各ノードの信頼値に基づいて求められる重み係数。
【請求項４】
さらに、以下の（ａ）から（ｃ）の手段を有する、請求項１から３のいずれかに記載の装置。
（ａ）信頼値を求めるべき前記第一のノードの指定を受け入れる手段。
（ｂ）前記信頼ネットワークグラフを複数の副信頼ネットワークグラフに分割する手段。
（ｃ）前記第一のノードを含む第一の副信頼ネットワークグラフを特定する手段。
【請求項５】
以下のステップを含み、コンピュータを用いて、一つ以上の副信頼ネットワークグラフを含む信頼ネットワークグラフにおいて、第一の副信頼ネットワークグラフに含まれる第一のノードの信頼値を求める方法。
前記第一の副信頼ネットワークグラフのノードから前記第一の副信頼ネットワークグラフのノードへ向う矢で指定されるノードに基づいて生成される第一の変換遷移行列（ｎ行ｎ列）と、
前記第一の副信頼ネットワークグラフのノードから前記第一の副信頼ネットワークグラフ外のノードへ向う矢で指定されるノードに基づいて生成される第二の変換遷移行列（ｎ行１列）と、
前記第一の副信頼ネットワークグラフ外のノードから前記第一の副信頼ネットワークグラフのノードへ向う矢で指定されるノードに基づいて生成される第三の変換遷移行列（１行ｎ列）と、
前記第一の副信頼ネットワークグラフ外のノードから前記第一の副信頼ネットワークグラフ外のノードへ向う矢で指定されるノードに基づいて生成される第四の変換遷移行列（１行１列）とから、
第五の変換遷移行列Ｒ（（ｎ＋１）行（ｎ＋１）列）を生成し、ｘ＝ＲＴｘの変換遷移行列の固有ベクトルｘを求めることにより、前記第一の副信頼ネットワークグラフのノードの信頼値を求めるステップ。但しＴは転置を表す。
【請求項６】
コンピュータを制御して、以下の手段として動作させ、一つ以上の副信頼ネットワークグラフを含む信頼ネットワークグラフにおいて、第一の副信頼ネットワークグラフに含まれる第一のノードの信頼値を求めるプログラム。
前記第一の副信頼ネットワークグラフのノードから前記第一の副信頼ネットワークグラフのノードへ向う矢で指定されるノードに基づいて生成される第一の変換遷移行列（ｎ行ｎ列）と、
前記第一の副信頼ネットワークグラフのノードから前記第一の副信頼ネットワークグラフ外のノードへ向う矢で指定されるノードに基づいて生成される第二の変換遷移行列（ｎ行１列）と、
前記第一の副信頼ネットワークグラフ外のノードから前記第一の副信頼ネットワークグラフのノードへ向う矢で指定されるノードに基づいて生成される第三の変換遷移行列（１行ｎ列）と、
前記第一の副信頼ネットワークグラフ外のノードから前記第一の副信頼ネットワークグラフ外のノードへ向う矢で指定されるノードに基づいて生成される第四の変換遷移行列（１行１列）とから、
第五の変換遷移行列Ｒ（（ｎ＋１）行（ｎ＋１）列）を生成し、ｘ＝ＲＴｘの変換遷移行列の固有ベクトルｘを求めることにより、前記第一の副信頼ネットワークグラフのノードの信頼値を求める手段。但しＴは転置を表す。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、日常生活における消費活動において関与している様々な要素の信頼度及び要素間の信頼度を定義し、それらの要素及び要素間の信頼値に基づく各要素の信頼値の算出方法及び装置等に関し、特に要素の数が膨大である場合に、所望の要素の信頼値の効率的な算出方法及び装置等に関する。
【背景技術】
【０００２】
われわれの日常の消費活動においては、消費者、広告媒体、商店、製造者、専門家(評論家)など様々な「要素」が関係している。これらの「要素」を本願出願では消費活動での「主体」と呼ぶ。これらの主体は主体同士間で様々な関係を有しており、これらの主体間の関係を示す様々な情報を消費者は入手できる。例えば商品Ａが製造者Ｂによって製造され商店Ｃで販売される。その時製造者Ｂがインターネットを使用し商品Ａを宣伝し、さらに商店Ｃは地域新聞の折り込み広告を利用して商品Ａ及び商店Ｃの宣伝をする。
【０００３】
さらに、評論家Ｄがその商品Ａについて評価を行い雑誌Ｅに掲載することはよく行われる。他の商品に対しても同様の消費活動が行われ、その結果として様々は情報が氾濫することが現実に起こっている。消費者の立場からすると、このような環境の中で、信頼の置ける製造者・商店・専門家などを見極める判断が困難な場合がある。
【０００４】
このような問題を解決するために、信頼出来る製造者・商店・専門家などについての指標あるいは情報の提供が切望されている。図１参照。
さらに、消費活動での「主体」に関する信頼値の情報だけでなく、これらの情報に個人の嗜好情報を考慮した情報が得られるとさらに有益となる。個人の有する嗜好情報を利用した自己の嗜好に合致し、さらに、最も信頼の置ける消費活動における主体に関する情報の提供が望まれている。
これらの問題を解決するために、本願発明者は、特開2005-135071（「商品購入における信頼値の算出方法及び装置」）を開示した。本願発明において、主体（要素）の数が膨大である場合に、所望の主体の信頼値を効率的に算出する方法及び装置等を開示する。
【特許文献１】宮内 興治. 商品購入における信頼値の算出方法及び装置.特開2005-135071
【非特許文献１】Lawrence Page; Sergey Brin; Rajeev Motwani; Terry Winograd. "The PageRank Citation Ranking: Bringing Order to the Web." Technical ReportStanford University, 1998.
【非特許文献２】Steve Chien; Cynthia Dwork; Ravi Kumar; D. Sivakumar. "Towards exploiting link evolution."
【非特許文献３】S. van Dongen. "A cluster algorithm for graphs." Technical Report INS-R0010CWI (Dutch National Research Institute for Mathematics and Computer Science), 2000.
【非特許文献４】S. van Dongen. "A stochastic uncoupling process for graphs." Technical Report INS-R0011CWI (Dutch National Research Institute for Mathematics and Computer Science), 2000.
【非特許文献５】S. van Dongen. "Performance criteria for graph clustering and Markov cluster experiments." Technical Report INS-R0012CWI (Dutch National Research Institute for Mathematics and Computer Science), 2000.
【非特許文献６】Sepandar D. Kamvar; Taher H. Haveliwala; Christopher D. Manning; Gene H. Golub. "Exploiting the Block Structure of the Web for Computing PageRank." Stanford Technical ReportStanford University, 2003.
【非特許文献７】Kazutami Kato; Hiroshi Matsuo. "The Discovery Method of Multiple Web Communities with Markov Cluster Algorithm." Natural Language Processing Technical Report 166 IPSJ, 2005.
【非特許文献８】Amy N. Langville; Carl D. Meyer. "Updating PageRank using the Group Inverse and Stochastic Complementation." Techreport CRSC-TR02-32North Carolina State University, 2002.
【非特許文献９】Amy N. Langville; Carl D. Meyer. "Deeper Inside PageRank", 2004.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
消費活動に関係する様々な主体の信頼値、及び、主体間の関係を定義し、これらに基づいて主体の信頼値を求めることは、消費者にとって非常に重要である。
本発明の目的は、消費活動に関係する様々な主体の数が膨大である場合において、ユーザによって特定される主体の信頼値を効率的に求めることである。主体の数が膨大である場合において、各主体の信頼値を求めるには、従来技術による繰り返し法で行列計算を行なった場合大きなメモリ量と計算量が必要となる。
本願発明では、本発明では、膨大の数の主体を含む信頼ネットワークグラフを図２（ａ）及び（ｂ）に示すように、「分割」することにより、互いに共通のノードを持たない複数の副信頼ネットワークグラフに分け、その内で特定された主体を含む副信頼ネットワークグラフの信頼値を求めることにより、効率的に信頼値を計算する方法・装置を開示する。
【課題を解決するための手段】
【０００６】
[請求項１]
請求項１では、一つ以上の副信頼ネットワークグラフを含む信頼ネットワークグラフにおいて、第一の副信頼ネットワークグラフに含まれる第一のノードの信頼値を求める装置について記載している。
前記第一の副信頼ネットワークグラフのノードから前記第一の副信頼ネットワークグラフのノードへ向う矢で指定されるノードに基づいて生成される第一の変換遷移行列（ｎ行ｎ列）と、
前記第一の副信頼ネットワークグラフのノードから前記第一の副信頼ネットワークグラフ外のノードへ向う矢で指定されるノードに基づいて生成される第二の変換遷移行列（ｎ行１列）と、
前記第一の副信頼ネットワークグラフ外のノードから前記第一の副信頼ネットワークグラフのノードへ向う矢で指定されるノードに基づいて生成される第三の変換遷移行列（１行ｎ列）と、
前記第一の副信頼ネットワークグラフ外のノードから前記第一の副信頼ネットワークグラフ外のノードへ向う矢で指定されるノードに基づいて生成される第四の変換遷移行列（１行１列）とから、
第五の変換遷移行列Ｒ（（ｎ＋１）行（ｎ＋１）列）を生成し、ｘ＝ＲＴｘの変換遷移行列の固有ベクトルｘを求めることにより、前記第一の副信頼ネットワークグラフのノードの信頼値を求める手段。但しＴは転置を表す。
[請求項２]
請求項２では、請求項１の第三の変換遷移行列（１行ｎ列）において、前記第一の副信頼ネットワークグラフ外のノードから前記第一の副信頼ネットワークグラフのノードへ向う矢で指定されるノードに重み係数を乗じることを記載している。
[請求項３]
請求項３では、請求項２の重み係数を算出する３つの例について記載している。
[請求項４]
請求項４では、信頼ネットワークグラフを複数の副信頼ネットワークグラフに分割する手段、及び、第一の副信頼ネットワークグラフを特定する手段について記載している。
[請求項５]
請求項５では、請求項１に対応する方法について記載している。
[請求項６]
請求項６では、請求項１に対応するプログラムについて記載している。
【発明の効果】
【０００７】
本願発明により一般性を失うことなく、特定された副信頼ネットワークグラフの各ノードの信頼値を巨大な信頼ネットワークグラフ全体の信頼値を求めるのではなく、信頼値を必要とする主体を含む副信頼ネットワークグラフともう一つのノードだけで信頼値を計算できる。従ってより少ないメモリーでかつ効率よく計算することが出来る。
【発明を実施するための最良の形態】
【０００８】
１．装置のブロック図
図３は、本願発明を実施する装置を示している。筐体１００の中には、記憶部１１０、メインメモリー１２０、出力部１３０、中央制御部（ＣＰＵ）１４０、操作部１５０、入力部１６０が含まれている。使用者が操作部１５０から必要な情報を入力する。中央制御部１４０は記憶部１１０に記憶されている信頼ネットワークグラフの情報に基づいて、入力部１６０から入力される所望のノードを含む変換信頼ネットワークグラフの信頼値を求め、出力部１３０に結果を出力する。
【０００９】
２．本願発明のブロック図
図４は、本願発明のブロック図を示している。２１０は所望のノード情報、または、信頼ネットワークグラフなどの入力部、２２０は信頼ネットワークグラフの格納部、２３０は信頼ネットワークグラフの分割部、２４０はスーパーノード生成部、２５０は変換遷移行列生成部、２６０は信値計算部、２７０は信頼値出力部を示す。
【００１０】
３．ネットワークの分割
図２（ａ）及び（ｂ）を用いて、信頼ネットワークグラフの分割について説明する。図２（ａ）には、複数の副信頼ネットワークグラフからなる信頼ネットワークグラフを示す。ここでは各ノードを結ぶ矢が示されているが矢の方向は省略されている。ここでは５つの副信頼ネットワークグラフが示されている。図２（ｂ）には、信頼ネットワークグラフを５つの副信頼ネットワークグラフ（ａからｅ）に分割した例を示す。
ネットワークの分割方法については次のような状況を想定している。
【００１１】
（１）複数の信頼ネットワークグラフをまとめて一つの大きな信頼ネットワークグラフを作った場合
複数の信頼ネットワークグラフの各々が副信頼ネットワークグラフとなる。副信頼ネットワークグラフ間には共通のノードが無く、これらを合成して大きな信頼ネットワークグラフを構築した後で、異なる副信頼ネットワークグラフに属するノード間に矢が設定された場合である。
【００１２】
（２）一つの信頼ネットワークグラフを分割した場合
分割した結果として得られるそれぞれのクラスタが副信頼ネットワークグラフとなる。分割の方法は、例えばお互いのクラスタ間にまたがる矢の重みができるだけ小さくなるようクラスタ化するものとする。
分割アルゴリズムの一つとして、非特許文献３、４、５に記載のMCL (Markov Clustering Algorithm)が知られている。また、このMCLアルゴリズムをネットワークグラフへの分割に応用した例として非特許文献７が報告されている。
なお、一旦分割した複数の副信頼ネットワークグラフを格納装置に格納しておくと、以後ノードの構成とノードの信頼値とノード間の信頼値の変更が無い限り、再度分割する必要がない。
【００１３】
４．信頼ネットワークグラフ
以下の様に信頼ネットワークグラフＧを定義する。信頼ネットワークグラフＧがｇ個のノードを含んでおり、信頼ネットワークグラフＧが共通のノードを持たないＮ個の副信頼ネットワークグラフＧ１, Ｇ２, ・・・,ＧＮ に分割されていてそれぞれg１,g２,・・・,gＮ個のノードを含んでいるものとする。ただし、
g ＝ g１＋g２＋・・・＋gＮ
また、
｛ノード n(１) 〜 n(ｇ1) ｝はＧ１に属し、
｛ノード n(ｇ1＋１) 〜 n(ｇ1＋ｇ２) ｝はＧ２に属し、
・ ・ ・
｛ノード n(ｇ1＋・・・＋ｇN-1＋１) 〜 n(ｇ1＋・・・＋ｇＮ) ｝はＧＮにそれぞれ属しているとする。
【００１４】
５．各ノードの信頼値の計算
特許文献１に記載されているように、信頼ネットワークグラフではノードｇi がｇj を信頼するときｇi からｇjへ矢が描かれる。この矢の重み（または複数の矢が二つのノードを結んでいるときはそれらの矢の重みの総和）をpi,j と表す。矢の重みは同時にノード間の信頼情報を表現している。これを第i 行第j 列の要素とする遷移行列を考えＰと置き、各ノードの信頼値をベクトルｘＴ＝（ｘ(１),・・・,ｘ(ｇ)）で表すと遷移行列Ｐとｘとの関係は数式（１）で表すことが出来る。ここで、Ｔは行列の転置を表す。
（１）    ｘ＝ＰＴｘ
各ノードの信頼値はＰＴの固有値１に対する固有ベクトルｘを求めることによって求められる。即ちｘの各成分であるｘ(ｊ)，ｊ＝１〜ｇを求めることによって求められる。ここで、ただし、すべての行i に対して
１  ＝  Σｊ(pi,j)（ｊ＝１〜ｇ）
とする。
【００１５】
６．遷移行列の変換
信頼値の計算が必要なノードを含む副信頼ネットワークグラフ（Ｇ１）以外の副信頼ネットワークグラフ（Ｇ２,Ｇ３,・・・,ＧＮ）に含まれるノードをスーパーノードΩで代表させる。そこで行列Ｐを数式（２）のように定義する。
【００１６】
【数１】
2007299138.tif 000003
【００１７】
ここで、各小行列Ｐijは次の信頼情報を有する。
Ｐ11はＧ1内のノードからＧ1内のノードの信頼情報
Ｐ1ΩはＧ1内のノードからＧ1以外のノードの信頼情報
ＰΩ1はＧ1以外のノードからＧ1内のノードの信頼情報
ＰΩΩはＧ1以外のノードからＧ1以外のノードの信頼情報
を有し、ＰはスーパーノードΩの導入により次のように変換される。ここで、ＰはＲに、またＰijはＲijに変換される。
【００１８】
（ａ）Ｐ11の変換
Ｇ1 内のノードからＧ1内のノードへの信頼情報を表現する部分であり、Ωの導入でも変化しない。
従って、Ｐ11＝Ｒ11
【００１９】
（ｂ）Ｐ1Ωの変換
Ｇ1内のノードからΩへの信頼情報を表現する部分である。Ｇ1内の一つのノードからＧ1以外のノードへの信頼情報を加算すると、スーパーノードΩへの信頼情報ｒi,Ωが数式（３）のように表現できる。
（３）    ｒi,Ω= Σｊ(pi,j) (j=(g1+1)〜ｇ),（i = 1,・・・, g1）
行列Ｐ1Ωが修正されてＲ1Ωになるとすると、数式（４）のように表現できる。
（４）    Ｒ1Ω= Ｐ1Ω・e
また、eは適当な次元数を持つ、全ての要素が１である列ベクトルである。
【００２０】
（ｃ）ＰΩ1の変換
Ｇ1以外のすべてのノードからＧ1内の一つのノードへの信頼情報を表す部分である。Ｇ1以外のすべてのノードからＧ1内の一つのノードへの信頼情報を重みをつけて加算すると、Ω からＧ1内の一つのノードへの信頼情報ｒΩ,jが表現できる。ノードｎ(ｇ1＋１),・・・,ｎ(ｇ)に対する重みをそれぞれｓ(ｇ1＋１),・・・, ｓ(ｇ)とすると、数式（５）のように表現できる。
（５）    ｒΩ,j = Σi(ｓipi,j) (i=g1+1 〜 ｇ),（j = 1,・・・, g1）
重みをベクトルst = (ｓ(g1+1),・・・, ｓ(ｇ))で表現して、行列ＰΩ1が修正されてＲΩ1になるとすると、数式（６）のように表現できる。
（６）    ＲΩ1= st ＰΩ1
なお、重みベクトルの求め方は７．重みベクトルで述べる。
【００２１】
（ｄ）ＰΩΩの変換
スーパーノードΩ からスーパーノードΩ への信頼情報を表現する部分であるが、Ｒの各行の要素の和が１になるようにするために、数式（７）のように表現できる。
（７）    ｒΩ,Ω = 1−ΣｊｒΩ,ｊ  （ j＝1〜ｇ１）
上の説明で用いた重みベクトルs を使って行列で表現すると、数式（８）のように表現できる。
（８）    ＲΩΩ= 1 - st ＰΩ1・e
となる。以上をまとめると、数式（９）のように表すことが出来る。
【００２２】
【数２】
2007299138.tif 000004
【００２３】
以上のようにg行g列の遷移行列Ｐを(ｇ１＋１)行(ｇ１＋１)列の遷移行列Ｒに変換する。各ノードの信頼値をベクトルｘＴ＝（ｘ(１),・・・,ｘ(ｇ１＋１))で表すと、変換遷移行列Ｒとｘとの関係は数式（１０）で表すことが出来る。
（１０）    ｘ＝ＲＴｘ
各ノードの信頼値はＲＴの固有値１に対する固有ベクトルｘを求めることによって求められる。即ちｘの各成分であるｘ(ｊ),ｊ＝１〜(ｇ１＋１)を求めることによって求められる。
これは、Ｐ11 に属するノードの信頼値を求めるために、g行g列の行列の固有値を求めることなく、(ｇ１＋１)行(ｇ１＋１)列の行列の固有値を求めることにより副信頼ネットワーク、Ｇ1内の各ノードの信頼値を求めることが出来ることを意味する。
【００２４】
７．重みベクトル
重みベクトルst = (ｓ(g1+1),・・・,ｓ(g))を求める方法について説明する。
ここでは三通りの方法を開示する。
【００２５】
（ａ）各ノードに同等の重みを与える場合
ｇΩ＝ｇ２＋・・・＋ｇＮ
と置いたとき、sを数式（１１）のように定義する。
（１１）    ｓ＝ｅ／ｇΩ
【００２６】
（ｂ）全体の信頼値を既に求めた後で一部のデータを更新したときに、所望のノードの信頼値を求める場合
各ノードの信頼値をｖ(ｉ)   (ｉ= 1,・・・,ｇ)とする。
但し、Σｉｖ(ｉ)＝１  （ｉ＝１〜ｇ）。
ベクトルｖΩｔ＝（ｖ（ｇ１＋１）,・・・,ｖ(ｇ)）を導入すれば、sは数式（１２）のように定義出来る。
（１２）    ｓ＝ｖΩ／(ｖΩｔｅ)
【００２７】
（ｃ）副信頼ネットワークグラフ毎の信頼値が既に求められているときに、所望のノードの信頼値を求める場合
各副信頼ネットワークグラフＧｉに属するノードの信頼値を表すベクトルをＶ(ｉ)とする。ただし、Ｖ(i)ｔ・ｅ＝１  （ｉ＝１〜Ｎ）とする。ｖΩｔ＝（Ｖ(２)ｔ,・・・,Ｖ(Ｎ)ｔ）とすると、ｓは数式（１３）のように定義出来る。但し、Ｖ(２)＝(ｖ(ｇ1＋１)，・・・,ｖ(ｇ1＋ｇ２))，Ｖ(３)＝(ｖ(ｇ1＋ｇ２＋１)，・・・,ｖ(ｇ1＋ｇ２＋ｇ３))，・・・，Ｖ(Ｎ)＝(ｖ(ｇ1＋，・・・，＋ｇＮ−１＋１)，・・・,ｖ(ｇ))
（１３）    ｓ＝ｖΩ／（Ｎ−１）
【００２８】
８．アルゴリズム
【００２９】
図５に本願発明に従い膨大の数の「ノード」を含む信頼ネットワークグラフにおいて、所望のノードを含む副信頼ネットワークグラフの信頼値を求める計算方法のアルゴリズムを示す。
（ａ）データ入力
（ｂ）信頼ネットワークグラフの分割
（ｃ）所望の副信頼ネットワークグラフの特定
（ｄ）変換遷移行列の生成
（ｅ）信頼値の計算・出力
【００３０】
以下に本アルゴリズムの詳細について説明する。
（ａ）データ入力
ここで入力するデータとしては、信頼ネットワークグラフに関するデータを入力する場合、及び、信頼値を求めたい所望のノードを入力する場合とがある。
信頼ネットワークグラフに関するデータが既に記憶装置に格納されている場合には新たにデータを入力する必要はない。
【００３１】
（ｂ）信頼ネットワークグラフの分割
信頼ネットワークグラフを複数の副信頼ネットワークグラフに分割する。
分割する方法については、前述の非特許文献３、４、５に記載のMCL (Markov Clustering Algorithm)が等が知られている。なお、予め分割した副信頼ネットワークグラフを入力している場合には分割する必要は無い。
【００３２】
（ｃ）副信頼ネットワークグラフの特定
信頼値を求めたいノードが属している副信頼ネットワークグラフを特定する。
【００３３】
（ｄ）変換遷移行列の生成
変換行列Ｒを構成する各行列を生成する。前述の説明に従いＲを構成する各行列Ｒ11，Ｒ1Ω，ＲΩ1，ＲΩΩを求める。
具体的には、
（ｄ-１）所望のノードを含む副信頼ネットワークグラフから当該副信頼ネットワークグラフのノードへ向う矢で指定されるノードに基づいて生成されるｎ行ｎ列のＲ11と、
（ｄ-２）所望のノードを含む副信頼ネットワークグラフのノードからその副信頼ネットワーク外のノードへ向う矢で指定されるノードに基づいて生成されるｎ行１列のＲ1Ωと、
（ｄ-３）所望のノードを含む副信頼ネットワークグラフ外のノードから当該副信頼ネットワークグラフのノードへ向う矢で指定されるノードに基づいて生成される１行ｎ列のＲΩ1と、
（ｄ-４）所望のノードを含む副信頼ネットワークグラフ外のノードから当該副信頼ネットワーク外のノードへ向う矢で指定されるノードに基づいて生成される１行１列のＲΩΩとを生成し、
（ｄ-５）これらの行列により、(ｎ＋１)行(ｎ＋１)列の遷移行列Ｒを生成する。
【００３４】
（ｅ）信頼値の計算・出力
変換遷移行列Ｒから所望の副信頼ネットワークグラフＧ1の各ノードの信頼値を求める。求める方法は、ｘ＝ＲＴｘに従い、各ノードの信頼値はＲＴの固有値１に対する固有ベクトルｘを求めることによって求められる。
【００３５】
９．情報転送量について
今、各副信頼ネットワークグラフ 毎にプロセッサが与えられているとする。実際に信頼値を式ｘ＝Ｒｔｘによって計算するためにはＲｔ,ｘに関する値を持たねばならず、そのためには別の副信頼ネットワークグラフを管理するプロセッサにその情報を送ってもらわねばならない。
副信頼ネットワークグラフ,ＧｉのノードからＧｊのノードへの信頼情報がｇｉ行ｇｊ列の小行列Ｑｉｊで表現されているとする。αi＝ｇ１+・・・+ｇi-1とするとき、Ｑｉｊは数式（１４）で表すことが出来る。
【００３６】
【数３】
2007299138.tif 000005
【００３７】
この小行列を用いると、もとの遷移行列は数式（１５）のように表現できる。
【００３８】
【数４】
2007299138.tif 000006
【００３９】
従来の計算方法では各ノードからの信頼情報として行列Ｐの(ｇ１＋１)行からｇ行までの要素、すなわち、Ｑ２１,・・・,Ｑ２Ｎ,Ｑ３１,・・・,Ｑ３Ｎ,ＱＮ１,・・・,ＱＮＮの各要素が必要となる。従がって、(ｇ２＋・・・＋ｇＮ)×ｇ＝Ｏ(ｇ２)の量の情報転送が発生する。一方、本発明では、Ｒを構成する各小行列はそれぞれのプロセッサで計算しその結果を転送する。Ｒの要素で他のプロセッサからＱ１１への通信が必要なのは、ｒΩ,ｊ (ｊ＝ 1,・・・,ｇ１)の部分である。なお、ｒｊ,Ω(ｊ＝ 1,・・・,ｇ１)については、Ｑ１１内部で計算できるので、転送情報量としては考慮する必要はない。今、第ｊ列の要素について考える。
【００４０】
Ｕｊ(Ｉ)＝  Σｉ(ｓｉｐi,ｊ)（ｉ＝αＩ＋１〜αＩ＋ｇＩ）とおくと、
ｒΩ,ｊ ＝  Σｉ(ｓｉｐi,ｊ)（ｉ＝ｇ１＋１〜ｇ）
＝  Σｉ(ｓｉｐi,ｊ)（ｉ＝(ｇ１＋１) 〜 (g１＋ｇ２)）
＋  Σｉ(ｓｉｐi,ｊ)（ｉ＝(g１＋ｇ２＋１) 〜 (g１＋ｇ２＋ｇ３)）
＋・・・
＋  Σｉ(ｓｉｐi,ｊ)（ｉ＝(ｇ１＋ｇ２＋・・・＋ｇＮ−１＋１) 〜                                             (ｇ１＋ｇ２＋・・・＋ｇＮ)）
【００４１】
ここで、αi＝ｇ１+・・・+ｇi-1であるので、
α２＝ｇ１
α３＝ｇ１＋ｇ２＝α２＋ｇ２
α４＝ｇ１＋ｇ２＋ｇ３＝α３＋ｇ３
・・・
αＮ＝ｇ１＋ｇ２＋・・・＋ｇ（Ｎ−１）＝α（Ｎ−１）＋ｇ（Ｎ−１）
となる。従って、
ｇ１＋１＝α２＋１
ｇ１＋ｇ２＝α２＋ｇ２
・・・
ｇ１＋ｇ２＋ｇ３＋・・・＋ｇ（Ｎ−１）＝α（Ｎ−１）＋ｇ（Ｎ−１）＝αＮ
ｇ１＋ｇ２＋ｇ３＋・・・＋ｇ（Ｎ−１）＋１＝αＮ＋１
ｇ１＋ｇ２＋ｇ３＋・・・＋ｇ（Ｎ−１）＋ｇＮ＝αＮ＋ｇＮ＝ｇ
となり、
【００４２】
ｒΩ,ｊ ＝  Σｉ(ｓｉｐi,ｊ)（ｉ＝α２＋１〜α２＋ｇ２）
＋・・・
＋Σｉ(ｓｉｐi,ｊ)（ｉ＝αＮ＋１〜αＮ＋ｇＮ）
＝  Ｕj(２)＋・・・＋Ｕj(Ｎ)
【００４３】
定義式よりＵj(I)は副信頼ネットワークグラフ、ＧＩ内で計算できることが明らかであるから、第ｊ列の要素を求めるには、副信頼ネットワークグラフ、Ｎ１以外から一つの値、Ｕj(I)を受け取る必要があることが分かる。他の列ｊ＝1,・・・,ｇ１についても同様であるから、合計で、(Ｎ−１）×ｇ１＝Ｏ(Ｎ×ｇ１)の量の情報転送が発生する。副信頼ネットワークグラフの数Ｎはノードの数ｇよりもはるかに小さい(Ｎ＜＜ｇ）と仮定できるので、本発明によって情報転送量はＯ(ｇ２)からＯ(Ｎ×ｇ１) (＜＜Ｏ(ｇ２)）へと大幅に減少することになる。
【００４４】
１０．計算量について
信頼値の計算量を求める上で最も支配的なのは、信頼情報を格納した行列ＰまたはＲとベクトルｘの積の部分である。ノード数の大きなグラフの場合、PageRank は通常、繰り返し法(power method) によってこれを求める( 非特許文献９,5.1 節 "The Power of Method" 参照) が、本発明でも繰り返し法が適用できる。
普通の計算方法では、繰り返し一回当たりｇ×ｇ＝Ｏ(ｇ２) 回の実数の乗算が必要である。本発明では遷移行列が小さくなり、(ｇ１＋１)２ ＝ Ｏ(ｇ１２)回の実数の乗算で計算できる。従がって、実数の乗算の回数はＯ(ｇ２)からＯ(ｇ１２)へと減少することになるが、繰り返し法によって何度も行列とベクトルの積の計算をする場合や、大きな信頼ネットワークグラフ を扱う場合に相当するｇ１＜＜ ｇの条件下では、大幅な改善が期待できるといえる。
【図面の簡単な説明】
【００４５】
【図１】信頼ネットワークグラフの概念図を示す図である。
【図２ａ】分割前の副信頼ネットワークグラフを示す図である。
【図２ｂ】分割後の副信頼ネットワークグラフを示す図である。
【図３】本発明を実施する装置である。
【図４】本発明の好適実施例に関するブロック図である。
【図５】本発明の好適実施例に関するフローチャートである。
【符号の説明】
【００４６】
１００：筐体
１１０：記憶部
１２０：メインメモリー
１３０：出力部
１４０：中央制御部（ＣＰＵ）
１５０：操作部
１６０：入力部
【図１】
2007299138.tif 000007
【図２ａ】
2007299138.tif 000008
【図２ｂ】
2007299138.tif 000009
【図３】
2007299138.tif 000010
【図４】
2007299138.tif 000011
【図５】
2007299138.tif 000012