(57)【要約】【課題】関連度算出の計算量を抑制する技術を備えた関連度計算の仕組みを提供することを課題とする。【解決手段】関連度計算装置１０は、データ間の関係をノードとエッジの関係で表現するデータモデルであるグラフ構造データにおいて、ノードから隣接ノードに対する伝搬値をノードの関連度とエッジの重みを用いてエッジごとに計算し、該エッジの伝搬値を用いてノードの集合体に対する各ノードの関連度を繰り返し計算する。そして、関連度計算装置１０は、ノードの関連度が計算されるたびに、ノードの関連度またはエッジの伝搬値に基づいて、所定のノードを計算対象のノードから除外する。そして、関連度計算装置１０は、所定のノードが除外された計算対象のノードの関連度を計算する。【選択図】図１
2014146280.tif 000002
【特許請求の範囲】
【請求項１】
データ間の関係をノードとエッジの関係で表現するデータモデルであるグラフ構造データにおいて、ノードから隣接ノードに対する伝搬値をノードの関連度とエッジの重みを用いてエッジごとに計算し、該エッジの伝搬値を用いてノードの集合体に対する各ノードの関連度を繰り返し計算する関連度計算部と、
前記関連度計算部によって前記ノードの関連度が計算されるたびに、前記ノードの関連度または前記エッジの伝搬値に基づいて、所定のノードを計算対象のノードから除外する削除部と、を備え、
前記関連度計算部は、前記所定のノードが除外された前記計算対象のノードの前記関連度を計算することを特徴とする関連度計算装置。
【請求項２】
前記削除部は、前記関連度計算部によって計算されたノードの関連度が所定の第１閾値未満であるか否かを判定し、前記ノードの関連度が前記第１閾値未満であるノードを、前記所定のノードとして、前記計算対象のノードから除外することを特徴とする請求項１に記載の関連度計算装置。
【請求項３】
ノードごとに該ノードにつながれたエッジの重み値が設定され、該重み値が大きい順にエッジを並び替える並び替え部をさらに備え、
前記関連度計算部は、前記並び替え部に並び替えられた順にエッジの伝搬値を計算し、
前記削除部は、前記関連度計算部によって計算されたエッジの伝搬値が所定の第２閾値未満であるか否かを判定し、前記エッジの伝搬値が前記第２閾値未満である場合には、該エッジの重み値よりも小さい重み値のエッジの伝搬値の計算を中止し、該エッジで接続されるノードを、前記所定のノードとして、前記計算対象のノードから除外することを特徴とする請求項１に記載の関連度計算装置。
【請求項４】
前記関連度計算部は、予め設定された繰り返し計算回数に応じて、前記ノードの関連度を繰り返し計算することを特徴とする請求項１〜３のいずれか一つに記載の関連度計算装置。
【請求項５】
データ間の関係をノードとエッジの関係で表現するデータモデルであるグラフ構造データにおいて、ノードから隣接ノードに対する伝搬値をノードの関連度とエッジの重みを用いてエッジごとに計算し、該エッジの伝搬値を用いてノードの集合体に対する各ノードの関連度を繰り返し計算する関連度計算部と、
前記関連度計算部によって前記ノードの関連度が計算されるたびに、前記ノードの関連度または前記エッジの伝搬値に基づいて、所定のノードを計算対象のノードから除外する削除部と、を備え、
前記関連度計算部は、前記所定のノードが除外された前記計算対象のノードの前記関連度を計算することを特徴とする関連度計算システム。
【請求項６】
関連度計算装置で実行される関連度計算方法であって、
データ間の関係をノードとエッジの関係で表現するデータモデルであるグラフ構造データにおいて、ノードから隣接ノードに対する伝搬値をノードの関連度とエッジの重みを用いてエッジごとに計算し、該エッジの伝搬値を用いてノードの集合体に対する各ノードの関連度を繰り返し計算する関連度計算工程と、
前記関連度計算工程によって前記ノードの関連度が計算されるたびに、前記ノードの関連度または前記エッジの伝搬値に基づいて、所定のノードを計算対象のノードから除外する削除工程と、を含み、
前記関連度計算工程は、前記所定のノードが除外された前記計算対象のノードの前記関連度を計算することを特徴とする関連度計算方法。
【請求項７】
データ間の関係をノードとエッジの関係で表現するデータモデルであるグラフ構造データにおいて、ノードから隣接ノードに対する伝搬値をノードの関連度とエッジの重みを用いてエッジごとに計算し、該エッジの伝搬値を用いてノードの集合体に対する各ノードの関連度を繰り返し計算する関連度計算ステップと、
前記関連度計算ステップによって前記ノードの関連度が計算されるたびに、前記ノードの関連度または前記エッジの伝搬値に基づいて、所定のノードを計算対象のノードから除外する削除ステップと、をコンピュータに実行させ、
前記関連度計算ステップは、前記所定のノードが除外された前記計算対象のノードの前記関連度を計算することを特徴とする関連度計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、関連度計算装置、関連度計算システム、関連度計算方法および関連度計算プログラムに関する。
【背景技術】
【０００２】
従来、データ間の関係などをノードとエッジの関係で表現するデータモデルであるグラフ構造データが知られている。例えば、図１４に例示するようなコンピュータとそれらの接続関係が与えられた時に、グラフ構造データを用いることによって、これらコンピュータとそれらの接続関係を、図１５に例示するようなデータモデルで表現することができる。近年、Personalized  Searchへのグラフ理論の適用による高度で高品質な検索処理の実現等により、グラフ理論の利用に関する関心が高まりつつある。このグラフ理論の利用において、ノード間の関連度は重要な属性の一つであり、様々な分野のアプリケーションに適用されており、各種の関連度の計算手法が提案されている。
【０００３】
このような関連度の計算手法として、例えば、Personalized  Page  Rankという計算手法が、ノード間の関連度の計算手法として注目を集めているもののひとつである。Personalized  Page  Rankは、今までグラフ理論でよく用いられてきたノード間の最短距離などと異なり、グラフの構造的な特徴に基づいて関連度が計算できる。
【０００４】
このPersonalized  Page  Rankでは、問い合わせ分布に基づいた各ノードの存在確率からランダムウォークを開始し、隣接するノードにエッジの重みに比例した確率でランダムに移動する。さらにノードに到達するたびに一定の確率で問い合わせ分布に基づいた確率でノードに戻る。この操作を再帰的に繰り返した結果として各ノードにおける定常状態確率が得られるが、Personalized  Page  Rankでは、この得られた定常状態確率を関連度とする手法である。
【０００５】
ここで、図１６を参照して、Personalized  Page  Rankにおいて、関連度を計算するためのアルゴリズムの一例について説明する。図１６の例では、このアルゴリズムにおいてＶとＣｕをそれぞれグラフにおける全てのノードの集合及びノードｕから出ているエッジがつながっている隣接ノードの集合とする。またｓ′を繰り返しにおいて計算される更新後の関連度とし、ｐをノード間で計算される関連度の伝搬値とする。ここで伝搬値とは、ノードの関連度とエッジの重みをかけたものである。
【０００６】
図１６に示すように、はじめに関連度の分布ｓを問い合わせ分布ｄに初期化する（１行目参照）。そして、繰り返し計算のなかで、まず更新後の関連度を０に初期化する（３〜５行目参照）。その後、すべてのノードに対してそれらのノードから出ているエッジが他のノードに伝搬する関連値を計算する（６〜１１行目参照）。そして伝搬された関連度から更新後の関連度を求める（１２，１３行目参照）。その後、所定の繰り返し条件が満たされるまで、グラフ全体を用いた関連度の計算を再帰的に実行する。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】“A  Survey  on  PageRank  Computing”,  Pavel  Berkhin著,  Internet  Mathematics  Vol.2,  2005
【非特許文献２】“Fast  and  Exact  Top-k  Search  for  Random  Walk  with  Restart”,  Yasuhiro  Fujiwara,  Makoto  Nakatsuji,  Makoto  Onizuka,  Masaru  Kitsuregawa著,  PVLDB  Endowment，Vol.5，No.5  2012
【非特許文献３】“ネットワーク分析(Ｒで学ぶデータサイエンス８)”、鈴木努著、金明哲編、共立出版
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上記した従来の技術では、グラフ全体を用いた関連度の計算を繰り返し行っているので、関連度の算出に要する計算量が多いという問題がある。このため、高度で効率的な検索処理の実現等、実用的なアプリケーションで関連度を有効に利用するためには、関連度の算出に要する計算量を削減し、関連度計算を効率的に実現することが課題となる。
【０００９】
そこで、この発明は、上述した従来技術の課題を解決するためになされたものであり、関連度算出の計算量を抑制する技術を備えた関連度計算の仕組みを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述した課題を解決し、目的を達成するために、本発明に係る関連度計算装置は、データ間の関係をノードとエッジの関係で表現するデータモデルであるグラフ構造データにおいて、ノードから隣接ノードに対する伝搬値をノードの関連度とエッジの重みを用いてエッジごとに計算し、該エッジの伝搬値を用いてノードの集合体に対する各ノードの関連度を繰り返し計算する関連度計算部と、前記関連度計算部によって前記ノードの関連度が計算されるたびに、前記ノードの関連度または前記エッジの伝搬値に基づいて、所定のノードを計算対象のノードから除外する削除部と、を備え、前記関連度計算部は、前記所定のノードが除外された前記計算対象のノードの前記関連度を計算することを特徴とする。
【００１１】
また、本発明に係る関連度計算システムは、データ間の関係をノードとエッジの関係で表現するデータモデルであるグラフ構造データにおいて、ノードから隣接ノードに対する伝搬値をノードの関連度とエッジの重みを用いてエッジごとに計算し、該エッジの伝搬値を用いてノードの集合体に対する各ノードの関連度を繰り返し計算する関連度計算部と、前記関連度計算部によって前記ノードの関連度が計算されるたびに、前記ノードの関連度または前記エッジの伝搬値に基づいて、所定のノードを計算対象のノードから除外する削除部と、を備え、前記関連度計算部は、前記所定のノードが除外された前記計算対象のノードの前記関連度を計算することを特徴とする。
【００１２】
また、本発明に係る関連度計算方法は、データ間の関係をノードとエッジの関係で表現するデータモデルであるグラフ構造データにおいて、ノードから隣接ノードに対する伝搬値をノードの関連度とエッジの重みを用いてエッジごとに計算し、該エッジの伝搬値を用いてノードの集合体に対する各ノードの関連度を繰り返し計算する関連度計算工程と、前記関連度計算工程によって前記ノードの関連度が計算されるたびに、前記ノードの関連度または前記エッジの伝搬値に基づいて、所定のノードを計算対象のノードから除外する削除工程と、を含み、前記関連度計算工程は、前記所定のノードが除外された前記計算対象のノードの前記関連度を計算することを特徴とする。
【００１３】
また、本発明に係る関連度計算プログラムは、データ間の関係をノードとエッジの関係で表現するデータモデルであるグラフ構造データにおいて、ノードから隣接ノードに対する伝搬値をノードの関連度とエッジの重みを用いてエッジごとに計算し、該エッジの伝搬値を用いてノードの集合体に対する各ノードの関連度を繰り返し計算する関連度計算ステップと、前記関連度計算ステップによって前記ノードの関連度が計算されるたびに、前記ノードの関連度または前記エッジの伝搬値に基づいて、所定のノードを計算対象のノードから除外する削除ステップと、をコンピュータに実行させ、前記関連度計算ステップは、前記所定のノードが除外された前記計算対象のノードの前記関連度を計算することを特徴とする。
【発明の効果】
【００１４】
実施形態に係る関連度計算装置、関連度計算システム、関連度計算方法および関連度計算プログラムによれば、関連度算出の計算量を抑制する技術を備えた関連度計算の仕組みを提供することができるという効果を奏する。
【図面の簡単な説明】
【００１５】
【図１】図１は、実施例１に係る関連度計算装置の構成を説明するための図である。
【図２】図２は、関連度を計算するためのアルゴリズムの一例を示す図である。
【図３】図３は、ノードとエッジで表現されるグラフと、問い合わせ分布の値の一例を示す図である。
【図４】図４は、ノードとエッジで表現されるグラフと、関連度の値の一例を示す図である。
【図５】図５は、ノードの枝刈りが行われた後のノードとエッジで表現されるグラフと、関連度の値の一例を示す図である。
【図６】図６は、実施例１に係る関連度計算装置による関連度計算処理の流れを示すフローチャートである。
【図７】図７は、実施例１に係る関連度計算装置により関連度の計算を行った場合の結果の一例を示す図である。
【図８】図８は、実施例２に係る関連度計算装置の構成を説明するための図である。
【図９】図９は、重みの降順で並び替えられたエッジの例を示す図である。
【図１０】図１０は、関連度を計算するためのアルゴリズムの一例を示す図である。
【図１１】図１１は、実施例２に係る関連度計算装置による関連度計算処理の流れを示すフローチャートである。
【図１２】図１２は、実施例２に係る関連度計算装置により関連度の計算を行った場合の結果の一例を示す図である。
【図１３】図１３は、関連度計算装置プログラムによる情報処理がコンピュータを用いて具体的に実現されることを示す図である。
【図１４】図１４は、コンピュータの接続関係の一例を示す図である。
【図１５】図１５は、ノードとエッジの関係で表現されたコンピュータの接続関係の一例を示す図である。
【図１６】図１６は、従来の関連度を計算するためのアルゴリズムの一例を示す図である。
【発明を実施するための形態】
【００１６】
以下に添付図面を参照して、この発明に係る関連度計算装置、関連度計算システム、関連度計算方法および関連度計算プログラムの実施例を詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。例えば、以下の説明では、Personalized  Page  Rankを用いて関連度を計算する場合の例を用いて説明するが、これに限定されるものではなく、Personalized  Page  Rank以外の手法（例えば、Page  RankやRandom  walk  with  restart）などを用いて関連度を計算する場合にも本発明を適用することができる。
【実施例１】
【００１７】
以下の実施例では、実施例１に係る関連度計算システムに含まれる関連度計算装置の構成、処理の流れを順に説明し、最後に実施例１による効果を説明する。
【００１８】
［関連度計算装置の構成］
まず、実施例１における関連度計算システムに含まれる関連度計算装置１０について図１を用いて説明する。図１は、実施例１に係る関連度計算装置１０の構成を説明するための図である。図１に示すように、実施例１における関連度計算システムは、関連度計算装置１０およびユーザ端末２０を有する。関連度計算システム１０およびユーザ端末２０は、例えば、インターネット等（図示せず）を介して、接続されている。
【００１９】
この関連度計算装置１０は、通信制御部１１および制御部１２を有し、インターネット等を介してユーザ端末２０と接続される。以下にこれらの各部の処理を説明する。
【００２０】
通信制御部１１は、インターネット等を介して接続されるユーザ端末２０との間でやり取りする各種情報に関する通信を制御する。具体的には、通信制御部１１は、問い合わせ分布ｄと、グラフの隣接行列Ｗと、再開始確率ｃと、繰り返し計算回数Ｔと、枝刈りの閾値θとをユーザ端末２０から受信する。また、通信制御部１１は、計算した関連度分布をユーザ端末２０に対して送信する。
【００２１】
制御部１２は、関連度計算装置１０において実行される各種処理を制御する。具体的には、制御部１２は、図１に示すように、関連度計算部１２ａおよび削除部１２ｂを有する。
【００２２】
関連度計算部１２ａは、データ間の関係をノードとエッジの関係で表現するデータモデルであるグラフ構造データにおいて、ノードから隣接ノードに対する伝搬値をノードの関連度とエッジの重みを用いてエッジごとに計算し、該エッジの伝搬値を用いてノードの集合体に対する各ノードの関連度を繰り返し計算する。また、関連度計算部１２ａは、後述する削除部１２ｂにより所定のノードが除外された計算対象のノードの関連度を計算する。また、関連度計算部１２ａは、予め設定された繰り返し計算回数Ｔに応じて、ノードの関連度を繰り返し計算する。
【００２３】
例えば、関連度計算部１２ａは、図２に例示するアルゴリズムを用いて、各ノードの関連度を計算する。図２は、関連度を計算するためのアルゴリズムの一例を示す図である。図２におけるアルゴリズムにおいてＶとＣｕをそれぞれグラフにおける全てのノードの集合及びノードｕから出ているエッジがつながっている隣接ノードの集合とする。また、ｓ′を繰り返しにおいて計算される更新後の関連度とし、ｐをノード間で計算される関連度の伝搬値とする。また、更新後のあるノードの関連度の値は、そのノードにつながっている隣接ノードからの伝搬値の総和から計算される。Ｖ′を枝刈り後のノードの集合とし、θを枝刈りにおける閾値とする。
【００２４】
図２に示すように、関連度計算部１２ａは、まず関連度の分布ｓを問い合わせ分布ｄに初期化し、ノードの集合Ｖ′をノード全体の集合Ｖに初期化する（１〜２行目参照）。また、関連度計算部１２ａは、計算回数ｔを「１」とする。そして、関連度計算部１２ａは、ノードｕを全てのノードの集合Ｖから選択し、ノードの更新後の関連度ｓ′を０に初期化する（４行目〜６行目参照）。
【００２５】
続いて、関連度計算部１２ａは、繰り返し計算の中で各ノードからの伝搬値ｐは全てのノードの集合Ｖからでなく、伝搬対象を絞り込んだ枝刈り後のノードの集合Ｖ′から計算する（７〜１２行目参照）。具体的には、関連度計算部１２ａは、ノードｕをＶ′から選択し、ノードｖをＣｕから選択する。そして、関連度計算部１２ａは、ノードの関連度ｓとエッジの重みを示すグラフの隣接行列Ｗを乗算して伝搬値ｐを計算、すなわち、p=W[v,u]s[u]を計算し（９行目参照）、計算したｐを用いて、s′[v]=s′[v]+pを計算する（１０行目参照）。この処理をＶ′とＣｕの全てのノードの組において繰り返し計算する。その後、関連度計算部１２ａは、s′=(1-c)s′[v]+cdを計算し（１３行目参照）、関連度分布ｓを更新後の関連度ｓ′とする（１４行目参照）。そして、関連度計算部１２ａは、計算した関連度分布ｓを削除部１２ｂに出力し、削除部１２ｂが有する記憶部（図示せず）に関連度分布ｓを格納させる。
【００２６】
その後、関連度計算部１２ａは、ノード関連度ｓ′が枝刈りの閾値θ以上であるノードのみを含むＶ′が後述する削除部１２ｂにより記憶部（図示せず）が格納され、該Ｖ′を読み出して、上記の関連度計算処理を予め設定された繰り返し計算回数Ｔだけ繰り返し行う。このように、関連度計算部１２ａは、繰り返し計算のなかで関連度が枝刈りの閾値θ以上の関連度の高いノードからの伝搬に対してのみ関連度の伝搬値を計算し、結果高速に関連度の計算を行う。そして、関連度計算部１２ａは、関連度の計算処理を繰り返し計算回数Ｔだけ行うと、計算した関連度分布ｓをユーザ端末２０に出力する。
【００２７】
削除部１２ｂは、関連度計算部１２ａによってノードの関連度が計算されるたびに、ノードの関連度に基づいて、所定のノードを計算対象のノードから除外する。具体的には、削除部１２ｂは、関連度計算部１２ａによって計算されたノードの関連度を記憶部から読みだし、該ノードの関連度が枝刈りの閾値未満であるか否かを判定し、ノードの関連度が枝刈りの閾値未満であるノードを計算対象のノードから除外する。
【００２８】
図２を参照して説明すると、削除部１２ｂは、枝刈り後のノードの集合は、各繰り返し計算の中で更新された関連度から求める（１５〜２０行目参照）。具体的には、削除部１２ｂは、図２に示すように、枝刈り後のノードの集合Ｖ′を０に初期化した後（１５行目参照）、関連度計算部１２ａによって計算された各ノードｕのノード関連度ｓ′が枝刈りの閾値θ以上であるか否かを判定する（１７行目参照）。この結果、削除部１２ｂは、ノード関連度ｓ′が枝刈りの閾値θ以上であるノードのみをＶ′に加え（１８行目参照）、ノード関連度ｓ′が枝刈りの閾値θより低いノードを関連度計算対象のノードから削除する。その後、削除部１２ｂは、枝刈り後のノードの集合Ｖ′を関連度計算部１２ａに出力し、関連度計算部１２ａが有する記憶部（図示せず）にノードの集合Ｖ′を格納させる。
【００２９】
ここで、図３〜図５を用いて、関連度計算装置１０が実行する関連度計算処理の概要を説明する。図３は、ノードとエッジで表現されるグラフと、問い合わせ分布の値の一例を示す図である。図４は、ノードとエッジで表現されるグラフと、関連度の値の一例を示す図である。図５は、ノードの枝刈りが行われた後のノードとエッジで表現されるグラフと、関連度の値の一例を示す図である。
【００３０】
図３〜図５の例では、複数のノードＡ〜Ｈが存在し、ノード間がエッジで結合されている。まず、図３に示すように、問い合わせ分布から決定される存在確率がノードＡ〜Ｃに対して設定されている。また、図３に例示するように、ノードＡの存在確率が「０．５」であり、ノードＢの存在確率が「０．２５」であり、ノードＣの存在確率が「０．２５」である。ここで存在確率とは、ランダムウォークが開始される各ノードの確率である。具体例な例を挙げて説明すると、例えば、ノードＡ〜Ｃは、ユーザがブックマークしているサイトであり、存在確率とは、ユーザが最初にアクセスするであろう各サイトの確率である。
【００３１】
次に、図４に示すように、関連度計算装置１０は、最初の関連度計算では、全てについてのノードＡ〜Ｈの関連度を計算する。図４に例示するように、ノードＡの関連度が「０．２２」、ノードＢの関連度が「０．１８」、ノードＣの関連度が「０．２１」、ノードＤの関連度が「０．１８」、ノードＥの関連度が「０．１１」、ノードＦの関連度が「０．０５」、ノードＧの関連度が「０．０２」、ノードＨの関連度が「０．３３」となっている。ここで関連度とは、問い合わせノードに対して個別化された重要度である。つまり、具体例な例を挙げて説明すると、例えば、ノードＡ〜Ｃが、ユーザがブックマークしているニュースサイトである場合には、ブックマークされていないニュースサイトのノードの関連度が高くなる。
【００３２】
次に、関連度計算装置１０は、関連度を計算した後であって、次の関連度計算処理を行う前に、各関連度が枝刈りの閾値よりも低いか否かを判定する。例えば、枝刈りの閾値が「０．０４」である場合には、図４の例では、ノードＧおよびノードＨの関連度が枝刈りの閾値「０．０４」よりも低い。このため、図５に例示するように、枝刈りの閾値「０．０４」よりも低いノードＧおよびノードＨが計算対象のノードから削除され、次の関連度計算処理が行われる。
【００３３】
このように、繰り返し計算の中で更新後の関連度が閾値θ未満の関連度の小さいノード（図４、５の例では、ノードＧ、Ｈ）を、計算対象のノードから削除（枝刈り）する。その結果、枝刈りされたノードからの伝搬値を計算する必要がなくなるので、伝搬値量の計算量が削減し、結果高速な関連度の計算が可能になる。なお、この手法は「関連度の小さいノードまたはエッジは更新後の関連度の値に大きな影響を与えない」という知見に基づいている。つまり、関連度の小さいノードまたはエッジを除外した場合であっても、更新後の関連度の値に大きな影響を与えないため、計算対象から除外して計算量を抑制することで、関連度計算を効率的に行うことができる。
【００３４】
［関連度計算装置による関連度計算処理］
次に、図６を用いて、関連度計算装置１０による関連度計算処理の流れを説明する。図６は、実施例１に係る関連度計算装置による関連度計算処理の流れを示すフローチャートである。図６に示すように、関連度計算装置１０の関連度計算部１２ａは、関連度計算開始指示をユーザ端末２０から受け付けると（ステップＳ１０１肯定）、まず関連度の分布ｓを問い合わせ分布ｄに初期化し、ノードの集合Ｖ′をノード全体の集合Ｖに初期化する（ステップＳ１０２）。そして、関連度計算部１２ａは、計算回数ｔを「１」とする（ステップＳ１０３）。
【００３５】
続いて、関連度計算部１２ａは、ノードｕを一つずつノードの集合Ｖから選択し（ステップＳ１０４）、ノードｕの更新後の関連度ｓ′［ｕ］を０に初期化する（ステップＳ１０５）。そして、関連度計算部１２ａは、Ｖから全てのノードを選択したか否かを判定し（ステップＳ１０６）、Ｖから全てのノードを選択していない場合には（ステップＳ１０６否定）、ステップＳ１０４に戻る。また、関連度計算部１２ａは、Ｖから全てのノードを選択した場合には（ステップＳ１０６肯定）、ノードｕを一つずつノードの集合Ｖ′から選択し（ステップＳ１０７）、ノードｖを一つずつノードの集合Ｃｕから選択する（ステップＳ１０８）。
【００３６】
そして、関連度計算部１２ａは、p=W[v,u]s[u]を計算し、計算したｐを用いて、s′[v]=s′[v]+pを計算する（ステップＳ１０９）。続いて、関連度計算部１２ａは、関連度計算部１２ａは、Ｃｕから全てのノードを選択したか否かを判定し（ステップＳ１１０）、Ｃｕから全てのノードを選択していない場合には（ステップＳ１１０否定）、ステップＳ１０８に戻る。また、関連度計算部１２ａは、Ｃｕから全てのノードを選択した場合には（ステップＳ１１０肯定）、Ｖ′から全てのノードを選択したか否かを判定し（ステップＳ１１１）、Ｖ′から全てのノードを選択していない場合には（ステップＳ１１１否定）、ステップＳ１０７に戻る。
【００３７】
また、関連度計算部１２ａは、Ｖ′から全てのノードを選択した場合には（ステップＳ１１１肯定）、s′=(1-c)s′[v]+cdを計算し、関連度分布ｓを更新後の関連度ｓ′とする（ステップＳ１１２）。
【００３８】
そして、関連度計算装置１０の削除部１２ｂは、枝刈り後のノードの集合Ｖ′を０に初期化した後（ステップＳ１１３）、ノードｕを一つずつノードの集合Ｖから選択する（ステップＳ１１４）。そして、削除部１２ｂは、関連度計算部１２ａによって計算された各ノードｕのノード関連度ｓ′が枝刈りの閾値θ以上であるか否かを判定する（ステップＳ１１５）。この結果、削除部１２ｂは、ノードｕのノード関連度ｓ′が枝刈りの閾値θ以上である場合には（ステップＳ１１５肯定）、ノードｕを枝刈り後のノードの集合Ｖ′に加え（ステップＳ１１６）、ステップＳ１１７に進む。また、削除部１２ｂは、ノードｕのノード関連度ｓ′が枝刈りの閾値θ未満である場合には（ステップＳ１１５否定）、ノード関連度ｓ′が枝刈りの閾値θより低いノードを関連度計算対象のノードから除外して、ステップＳ１１７に進む。
【００３９】
ステップＳ１１７では、削除部１２ｂは、ノードの集合Ｖから全てのノードを選択したかを判定し、ノードの集合Ｖから全てのノードを選択していない場合には（ステップＳ１１７否定）、ステップＳ１１４に戻る。また、削除部１２ｂがノードの集合Ｖから全てのノードを選択したと判定した場合には（ステップＳ１１７肯定）、関連度計算部１２ａは、計算回数ｔに１を加算し（ステップＳ１１８）、計算回数ｔが繰り返し計算回数Ｔを超えたか否かを判定する（ステップＳ１１９）。
【００４０】
この結果、関連度計算部１２ａは、計算回数ｔが繰り返し計算回数Ｔを超えていないと判定した場合には（ステップＳ１１９否定）、ステップＳ１０４に戻って、関連度計算処理を行う。ここでの関連度計算処理は、関連度の低いノードが除外された計算対象のノードの集合Ｖ′から関連度を計算する。また、関連度計算部１２ａは、計算回数ｔが繰り返し計算回数Ｔを超えたと判定した場合には（ステップＳ１１９肯定）、関連度分布ｓをユーザ端末２０に出力し（ステップＳ１２０）、関連度計算処理を終了する。
【００４１】
［関連度計算装置による関連度計算処理の実験結果］
次に、実施例１に係る関連度計算装置による関連度計算処理の実験結果について、図７を用いて説明する。なお、実験結果については、あくまで一例であり、これにより構成または処理が限定されるものではない。図７は、実施例１に係る関連度計算装置により関連度の計算を行った場合の結果の一例を示す図である。なお、図７に示す「ノード枝刈り」とは、実施例１に係る関連度計算装置による関連度計算処理の実験結果を示し、「オリジナル」とは、従来のアルゴリズムに従って関連度計算した場合の実験結果を示す。
【００４２】
また、この実験においては、ノード数が２６５２１４、エッジ数が４２００４５で実験を行った。また、この実験においてはｃ＝０．１５，Ｔ＝１００とし、ランダムウォークを開始するノードはランダムに１つ設定した。またノードの枝刈りによる手法においては枝刈りの閾値θを１０−３及び１０−７にして実験を行った。
【００４３】
図７から本発明は従来の手法と比較して高速に関連度を計算できることがわかる。図７の例では、従来の計算時間が「１．０１［ｓ］」であるのに対して、本発明の手法では、閾値θが１０−３である場合には、「０．０５［ｓ］」であり、閾値θが１０−７である場合には、「０．４６［ｓ］」である。また、同時に枝刈りの閾値が大きいほうがより高速な関連度の計算が可能であることがわかる。これは閾値が大きい方がより多くのノードを枝刈りできるからである。
【００４４】
また図７から本発明における関連度の誤差が非常に小さい値になることがわかる。図７に示すように、本発明の手法では、閾値θが１０−３である場合には、平均誤差が従来の手法に比べて「３．１５・１０−８」であり、閾値θが１０−７である場合には、「４．８１・１０−１１」である。これは、本発明の手法ではノードを枝刈りするが、なるべく関連度の値に影響がないように閾値が設定されているからである。また図７から本発明は閾値が小さい方がより高い精度で関連度を計算できることがわかる。これは閾値が小さい方がより多くのノードまたはエッジが計算対象となるため、関連度の計算精度が向上するためである。これらの結果から本発明において高速な計算を行いたい場合は閾値を大きくし、高精度な計算を行いたい場合は閾値を小さくすればいいことがわかる。
【００４５】
[実施例１の効果]
上述してきたように、実施例１に係る関連度計算装置１０は、データ間の関係をノードとエッジの関係で表現するデータモデルであるグラフ構造データにおいて、ノードから隣接ノードに対する伝搬値をノードの関連度とエッジの重みを用いてエッジごとに計算し、該エッジの伝搬値を用いてノードの集合体に対する各ノードの関連度を繰り返し計算する。そして、関連度計算装置１０は、ノードの関連度が計算されるたびに、ノードの関連度またはエッジの伝搬値に基づいて、所定のノードを計算対象のノードから除外する。そして、関連度計算装置１０は、所定のノードが除外された計算対象のノードの関連度を計算する。これにより、関連度の低いノードを計算対象のノードから除外していくことが出来る結果、関連度算出の計算量を抑制する技術を備えた関連度計算の仕組みを提供することが可能である。また、閾値を調整することにより関連度計算における計算速度の精度の調整が可能である。
【００４６】
また、実施例１に係る関連度計算装置１０は、計算されたノードの関連度が所定の閾値未満であるか否かを判定し、ノードの関連度が閾値未満であるノードを、計算対象のノードから除外する。このため、関連度の低いノードを計算対象のノードから除外していく枝刈りを実行することができ、枝刈りを実行した後の計算処理では、絞り込んだノードから関連度の計算を実行するので、関連度算出の計算量を抑制することが可能である。
【００４７】
また、実施例１に係る関連度計算装置１０は、予め設定された繰り返し計算回数に応じて、ノードの関連度を繰り返し計算する。このため、関連度計算の繰り返し回数を容易に変更することが可能である。
【実施例２】
【００４８】
ところで、上記の実施例１では、関連度が低いノードを計算対象のノードから除外する場合を説明したが、これに限定されるものではなく、例えば、関連度の低いエッジの計算を中止し、エッジにつながれたノードを計算対象から除外するようにしてもよい。そこで、以下で説明する実施例２では、関連度の低いエッジの計算を中止し、エッジにつながれたノードを計算対象から除外する場合について説明する。
【００４９】
まず、図８を用いて、実施例２に係る関連度計算装置１０Ａの構成について説明する。図８は、実施例２に係る関連度計算装置の構成を説明するための図である。なお、実施例１に係る関連度計算装置１０と同様の構成については、説明を省略する。
【００５０】
図８に示すように、実施例２に係る関連度計算装置１０Ａは、実施例１に係る関連度計算装置１０と比較して、並び替え部１ｃ２をさらに有する。並び替え部１２ｃは、ノードごとに該ノードにつながれたエッジの重み値が設定され、該重み値が大きい順にエッジを並び替える。ここで、図３の例を用いて説明すると、並び替え部１２ｃは、ノードＡについて、ノードＢとつながるエッジ（ここでは、エッジＩＤ「１」のエッジとする）およびノードＣとつながるエッジ（ここでは、エッジＩＤ「２」のエッジとする）の２つのエッジにつながれている。
【００５１】
ここで、図９に例示するように、ノードＡとノードＢを接続するエッジＩＤ１のエッジについて、重み値が「０．６」であり、ノードＡとノードＣを接続するエッジＩＤ２のエッジについて、重み値が「０．４」である場合には、並び替え部１２ｃは、重み値が大きい順として、エッジＩＤ１、エッジＩＤ２の順に並び替える。図９は、重みの降順で並び替えられたエッジの例を示す図である。
【００５２】
また、実施例２に係る関連度計算装置１０Ａの関連度計算部１２ａは、並び替え部１２ｃに並び替えられた順にエッジの伝搬値を計算し、また、各ノードの関連度を計算する。具体的には、関連度計算部１２ａは、図１０に例示するアルゴリズムを用いて、関連度分布を計算する。図１０におけるアルゴリズムにおいてＶとＣｕをそれぞれグラフにおける全てのノードの集合及びノードｕから出ているエッジがつながっている隣接ノードの集合とする。また、ｓ′を繰り返しにおいて計算される更新後の関連度とし、ｐをノード間で計算される関連度の伝搬値とする。また、更新後のあるノードの関連度の値は、そのノードにつながっている隣接ノードからの伝搬値の総和から計算される。Ｖ′を枝刈り後のノードの集合とし、θを枝刈りにおける閾値とする。
【００５３】
図１０に示すように、関連度計算部１２ａは、まず関連度の分布ｓを問い合わせ分布に初期化する（１行目参照）。そして繰り返し計算のなかで効率的な計算の枝刈りを行うために、各ノードに対してそれらのノードから出ているエッジをエッジの重み（グラフの隣接行列の非ゼロ要素の大きさに対応）が大きい順で並び替える（２〜４行目参照）。
【００５４】
そして、関連度計算部１２ａは、繰り返し計算のなかでは各ノードから他の隣接するノードへの伝搬値ｐを計算する（１１行目参照）。
【００５５】
削除部１２ｂは、関連度計算部１２ａによって計算されたエッジの伝搬値が枝刈り閾値未満であるか否かを判定し、エッジの伝搬値が枝刈り閾値未満である場合には、該エッジの重み値よりも小さい重み値のエッジの伝搬値の計算を中止し、該エッジで接続されるノードを、計算対象のノードから除外する。
【００５６】
つまり、各ノードにおいて、エッジの集合を用いて当該ノードに隣接する隣接ノードへの伝搬値を計算する過程で、ある隣接ノードへの伝搬値からその後に計算する他の隣接ノードへの伝搬値が枝刈りの閾値θより小さくなることがわかった段階で当該他の隣接ノードを含む未計算の残りの隣接ノードに対する伝搬値の計算を中止し（計算を枝刈りし）、結果として高速な関連度の計算を行う。
【００５７】
具体的には、削除部１２ｂは、図１０に示すように、計算された伝搬値が枝刈りの閾値θより小さければそのノードからの以下のエッジの重みを有する未計算の残りの隣接ノードに対する伝搬値の計算を枝刈りする（１３〜１５行目参照）。これは、エッジが重みの大きい順に並び替えられているため、その後に計算される予定の残りの隣接ノードへの伝搬値がθより大きく以上になることがないからである。この手法は伝搬値が既定の閾値より小さいエッジで接続されるノードへの伝搬値の計算を効率的に枝刈りできるため、高速な関連度の計算が可能である。
【００５８】
［関連度計算装置による関連度計算処理］
次に、図１１を用いて、関連度計算装置１０Ａによる関連度計算処理の流れを説明する。図１１は、実施例２に係る関連度計算装置による関連度計算処理の流れを示すフローチャートである。図１１に示すように、関連度計算装置１０Ａの並び替え部１２ｃは、関連度計算開始指示をユーザ端末２０から受け付けると（ステップＳ２０１肯定）、まず関連度の分布ｓを問い合わせ分布ｄに初期化する（ステップＳ２０２）。
【００５９】
続いて、並び替え部１２ｃは、ノードｕを一つずつノードの集合Ｖから選択し（ステップＳ２０３）、ノードの集合Ｃｕをエッジの重みの降順でソートする（ステップＳ２０４）。そして、並び替え部１２ｃは、Ｖから全てのノードを選択したか否かを判定し（ステップＳ２０５）、Ｖから全てのノードを選択していない場合には（ステップＳ２０５否定）、ステップＳ２０３に戻る。また、並び替え部１２ｃがＶから全てのノードを選択したと判定した場合には（ステップＳ２０５肯定）、関連度計算部１２ａは、計算回数ｔを「１」とする（ステップＳ２０６）。
【００６０】
続いて、関連度計算部１２ａは、ノードｕを一つずつノードの集合Ｖから選択し（ステップＳ２０７）、ノードｕの更新後の関連度ｓ′［ｕ］を０に初期化する（ステップＳ２０８）。そして、関連度計算部１２ａは、Ｖから全てのノードを選択したか否かを判定し（ステップＳ２０９）、Ｖから全てのノードを選択していない場合には（ステップＳ２０９否定）、ステップＳ２０７に戻る。また、関連度計算部１２ａは、Ｖから全てのノードを選択した場合には（ステップＳ２０９肯定）、ノードｕを一つずつノードの集合Ｖ′から選択し（ステップＳ２１０）、ノードｖを一つずつノードの集合Ｃｕから選択する（ステップＳ２１１）。ここでは、ステップＳ２０３でソートされた順番に、ノードの集合Ｃｕからノードｖを一つずつ選択する。
【００６１】
そして、関連度計算部１２ａは、p=W[v,u]s[u]を計算し、計算したｐを用いて、s′[v]=s′[v]+pを計算する（ステップＳ２１２）。そして、削除部１２ｂは、計算された伝搬値ｐが枝刈りの閾値θ未満であるか否かを判定する（ステップＳ２１３）。この結果、削除部１２ｂが計算された伝搬値ｐが枝刈りの閾値θ未満でない場合には（ステップＳ２１３否定）、関連度計算部１２ａは、Ｃｕから全てのノードを選択したか否かを判定し（ステップＳ２１４）、Ｃｕから全てのノードを選択していない場合には（ステップＳ２１４否定）、ステップＳ２１１に戻る。また、Ｃｕから全てのノードを選択した場合には（ステップＳ２１４肯定）、ステップＳ２１５に進む。また、削除部１２ｂが計算された伝搬値ｐが枝刈りの閾値θ未満である場合には（ステップＳ２１３肯定）、ステップＳ２１５に進む。
【００６２】
ステップＳ２１５では、関連度計算部１２ａは、ノードの集合Ｖから全てのノードを選択したかを判定し、ノードの集合Ｖから全てのノードを選択していない場合には（ステップＳ２１５否定）、ステップＳ２１０に戻る。また、関連度計算部１２ａは、ノードの集合Ｖから全てのノードを選択したと判定した場合には（ステップＳ２１５肯定）、s′=(1-c)s′[v]+cdを計算し、関連度分布ｓを更新後の関連度ｓ′とする（ステップＳ２１６）。
【００６３】
そして、関連度計算部１２ａは、計算回数ｔに１を加算し（ステップＳ２１７）、計算回数ｔが繰り返し計算回数Ｔを超えたか否かを判定する（ステップＳ２１８）。
【００６４】
この結果、関連度計算部１２ａは、計算回数ｔが繰り返し計算回数Ｔを超えていないと判定した場合には（ステップＳ２１８否定）、ステップＳ２０７に戻って、関連度計算処理を行う。また、関連度計算部１２ａは、計算回数ｔが繰り返し計算回数Ｔを超えたと判定した場合には（ステップＳ２１８肯定）、関連度分布ｓをユーザ端末２０に出力し（ステップＳ２１９）、関連度計算処理を終了する。
【００６５】
［関連度計算装置による関連度計算処理の実験結果］
次に、実施例２に係る関連度計算装置による関連度計算処理の実験結果について、図１２を用いて説明する。なお、実験結果については、あくまで一例であり、これにより構成または処理が限定されるものではない。図１２は、実施例２に係る関連度計算装置により関連度の計算を行った場合の結果の一例を示す図である。なお、図１２に示す「エッジ枝刈り」とは、実施例２に係る関連度計算装置による関連度計算処理の実験結果を示し、「オリジナル」とは、従来のアルゴリズムに従って関連度計算した場合の実験結果を示す。
【００６６】
また、この実験においては、ノード数が２６５２１４、エッジ数が４２００４５で実験を行った。また、この実験においてはｃ＝０．１５，Ｔ＝１００とし、ランダムウォークを開始するノードはランダムに１つ設定した。またエッジの枝刈りによる手法においては枝刈りの閾値θを１０−３及び１０−７にして実験を行った。
【００６７】
図１２から本発明は従来の手法と比較して高速に関連度を計算できることがわかる。図１２の例では、従来の計算時間が「１．０１［ｓ］」であるのに対して、本発明の手法では、閾値θが１０−３である場合には、「０．９３［ｓ］」であり、閾値θが１０−７である場合には、「０．９６［ｓ］」である。また、同時に枝刈りの閾値が大きいほうがより高速な関連度の計算が可能であることがわかる。これは閾値が大きい方がより多くのノードまたはエッジを枝刈りできるからである。
【００６８】
また図１２から本発明における関連度の誤差が非常に小さい値になることがわかる。図１２に示すように、本発明の手法では、閾値θが１０−３である場合には、平均誤差が従来の手法に比べて「３．５４・１０−８」であり、閾値θが１０−７である場合には、「３．１７・１０−１０」である。これは、本発明はノードまたはエッジを枝刈りするが、なるべく関連度の値に影響がないように閾値が設定されているからである。また図１２から本発明は閾値が小さい方がより高い精度で関連度を計算できることがわかる。これは閾値が小さい方がより多くのノードまたはエッジが計算対象となるため、関連度の計算精度が向上するためである。これらの結果から本発明において高速な計算を行いたい場合は閾値を大きくし、高精度な計算を行いたい場合は閾値を小さくすればよいことがわかる。
【００６９】
[実施例２の効果]
上述してきたように、実施例２に係る関連度計算装置１０Ａは、ノードごとに該ノードにつながれたエッジの重み値が設定され、該重み値が大きい順にエッジを並び替える。そして、関連度計算装置１０Ａは、並び替えられた順にエッジの伝搬値を計算し、計算されたエッジの伝搬値が閾値未満であるか否かを判定し、エッジの伝搬値が閾値未満である場合には、該エッジの重み値よりも小さい重み値のエッジの伝搬値の計算を中止し、該エッジで接続されるノードを、計算対象のノードから除外する。これにより、関連度の低いエッジを計算対象から除外していくことが出来る結果、関連度算出の計算量を抑制する技術を備えた関連度計算の仕組みを提供することが可能である。また、閾値を調整することにより関連度計算における計算速度の精度の調整が可能である。
【実施例３】
【００７０】
ところで、上記実施例１、２における関連度計算装置は、上述した実施例以外にも、種々の異なる形態にて実施されてよい。そこで、実施例３では、上記の関連度計算システムの他の実施例について説明する。
【００７１】
［繰り返し計算］
上記実施例１、２の関連度計算装置は、繰り返し計算の収束条件として、繰り返し計算回数を予め設定する場合を説明したが、本発明はこれに限定されるものではなく、収束の閾値を予め設定するようにしてもよい。例えば、関連度計算装置は、繰り返し行われる関連度の計算において、今回計算された関連度と前回計算された関連度との差分を計算し、該差分が予め設定された収束の閾値よりも小さい場合には、関連度の計算を終了し、大きい場合には、関連度の計算を繰り返すようにしてもよい。
【００７２】
［システム構成］
また、本実施例において説明した各処理の内、自動的に行われるものとして説明した処理の全部又は一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部又は一部を公知の方法で自動的に行うこともできる。この他、上述文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００７３】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部又は一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的又は物理的に分散・統合して構成することができる。
【００７４】
［プログラム］
図１３は、開示の技術に係る関連度計算プログラムによる情報処理がコンピュータを用いて具体的に実現されることを示す図である。図１３に例示するように、コンピュータ１０００は、例えば、メモリ１０１０と、ＣＰＵ（Central  Processing  Unit）１０２０と、ハードディスクドライブインタフェース１０３０と、ディスクドライブインタフェース１０４０と、シリアルポートインタフェース１０５０と、ビデオアダプタ１０６０と、ネットワークインタフェース１０７０とを有する。コンピュータ１０００の各部はバス１０８０によって接続される。
【００７５】
メモリ１０１０は、図１３に例示するように、ＲＯＭ１０１１及びＲＡＭ１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、図１３に例示するように、ハードディスクドライブ１０３１に接続される。ディスクドライブインタフェース１０４０は、図１３に例示するように、ディスクドライブ１０４１に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブ１０４１に挿入される。シリアルポートインタフェース１０５０は、図１３に例示するように、例えばマウス１０５１、キーボード１０５２に接続される。ビデオアダプタ１０６０は、図１３に例示するように、例えばディスプレイ１０６１に接続される。
【００７６】
ここで、図１３に例示するように、ハードディスクドライブ１０３１は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、開示の技術に係る関連度計算プログラムは、コンピュータによって実行される指令が記述されたプログラムモジュール１０９３として、例えばハードディスクドライブ１０３１に記憶される。具体的には、上記実施例で説明した制御部１２の各部と同様の情報処理を実行する手順各々が記述されたプログラムモジュールが、ハードディスクドライブ１０３１に記憶される。
【００７７】
また、関連度計算プログラムによる情報処理に用いられるデータは、プログラムデータ１０９４として、例えばハードディスクドライブ１０３１に記憶される。そして、ＣＰＵ１０２０が、ハードディスクドライブ１０３１に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出し、各種の手順を実行する。
【００７８】
なお、関連度計算プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０３１に記憶される場合に限られない。例えば、プログラムモジュール１０９３やプログラムデータ１０９４は、着脱可能な記憶媒体に記憶されても良い。この場合、ＣＰＵ１０２０は、ディスクドライブなどの着脱可能な記憶媒体を介してデータを読み出す。また、同様に、関連度計算プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ネットワーク（ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）等）を介して接続された他のコンピュータに記憶されても良い。この場合、ＣＰＵ１０２０は、ネットワークインタフェースを介して他のコンピュータにアクセスすることで各種データを読み出す。
【００７９】
［その他］
なお、本実施例で説明した関連度計算プログラムは、インターネットなどのネットワークを介して配布することができる。また、制御プログラムは、ハードディスク、フレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行することもできる。
【符号の説明】
【００８０】
１０、１０Ａ  関連度計算装置
１１  通信制御部
１２  制御部
１２ａ  関連度計算部
１２ｂ  削除部
１２ｃ  並び替え部
２０  ユーザ端末
１０００  コンピュータ
１０１０  メモリ
１０２０  ＣＰＵ
１０３０  ハードディスクドライブインタフェース
１０４０  ディスクドライブインタフェース
１０５０  シリアルポートインタフェース
１０５１  マウス
１０５２  キーボード
１０６０  ビデオアダプタ
１０６１  ディスプレイ
１０７０  ネットワークインタフェース
１０８０  バス
１０９１  ＯＳ
１０９２  アプリケーションプログラム
１０９３  プログラムモジュール
１０９４  プログラムデータ
【図１】
2014146280.tif 000003
【図２】
2014146280.tif 000004
【図３】
2014146280.tif 000005
【図４】
2014146280.tif 000006
【図５】
2014146280.tif 000007
【図６】
2014146280.tif 000008
【図７】
2014146280.tif 000009
【図８】
2014146280.tif 000010
【図９】
2014146280.tif 000011
【図１０】
2014146280.tif 000012
【図１１】
2014146280.tif 000013
【図１２】
2014146280.tif 000014
【図１３】
2014146280.tif 000015
【図１４】
2014146280.tif 000016
【図１５】
2014146280.tif 000017
【図１６】
2014146280.tif 000018