(57)【要約】【課題】各ノードに関するリンクの総量から、個々のノード間のリンクを推定する。【解決手段】グラフ推定装置100は、複数のノードとノード間のリンクとから構成されるグラフのリンクに所定の物理量を対応付け、各ノードのリンクの物理量の総量から個々のノード間のリンクの物理量を推定する。グラフ推定装置100は、観測された各ノードのリンクの物理量の総量を入力するリンク総量入力手段111と、推定されたグラフの各ノードのリンクの物理量の総量と前記観測された各ノードのリンクの物理量の総量との差が小さいグラフを推定する推定手段112と、推定したグラフにおけるノード間のリンクの物理量を出力する出力手段113とを備える。【選択図】図1
2010117877.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードとノード間のリンクとから構成されるグラフのリンクに所定の物理量を対応付け、各ノードのリンクの物理量の総量から個々のノード間のリンクの物理量を推定するグラフ推定装置であって、
観測された各ノードのリンクの物理量の総量を入力するリンク総量入力手段と、
推定されたグラフの各ノードのリンクの物理量の総量と前記観測された各ノードのリンクの物理量の総量との差が小さいグラフを推定する推定手段と、
前記推定したグラフにおけるノード間のリンクの物理量を出力する出力手段とを備えることを特徴とするグラフ推定装置。
【請求項２】
前記推定手段は、推定されたグラフの各ノードのリンクの物理量の総量と前記観測された各ノードのリンクの物理量の総量との差異に関する評価関数を最小化するための目的関数を含んで構成される最適化問題を作成する最適化問題作成手段と、前記作成された最適化問題の解を求める最適化問題解法手段とを有することを特徴とする請求項１に記載のグラフ推定装置。
【請求項３】
前記推定手段は、推定するグラフの行のノード数をnr、列のノード数をnc、予め設定されたパラメータをmとするとき、推定するグラフをnr×mの行列Aとm×ncの行列Bの積ABとして表現し、推定された行列Aと行列Bとから求めた各ノードのリンクの物理量の総量と前記観測された各ノードのリンクの物理量の総量との差異に関する評価関数を最小化するための目的関数を含んで構成される最適化問題を作成する最適化問題作成手段と、前記作成された最適化問題の解を求める最適化問題解法手段と、前記推定された行列Aと行列Bとから各ノードのリンクの物理量を計算する計算手段とを有することを特徴とする請求項１に記載のグラフ推定装置。
【請求項４】
複数のノードとノード間のリンクとから構成されるグラフのリンクに所定の物理量を対応付け、各ノードのリンクの物理量の総量から個々のノード間のリンクの物理量を推定するグラフ推定装置であって、
観測された各ノードのリンクの物理量の総量を入力するリンク総量入力手段と、
ノード間のリンクの有無を示すトポロジー情報を入力するトポロジー情報入力手段と、
推定されたグラフの各ノードのリンクの物理量の総量と前記観測された各ノードのリンクの物理量の総量との差、および、推定されたグラフのノード間のリンク関係と前記入力されたトポロジー情報との差が小さいグラフを推定する推定手段と、
前記推定したグラフにおけるノード間のリンクの物理量を出力する出力手段とを備えることを特徴とするグラフ推定装置。
【請求項５】
前記推定手段は、推定されたグラフの各ノードのリンクの物理量の総量と前記観測された各ノードのリンクの物理量の総量との差異に関する評価関数を最小化するための目的関数と、前記トポロジー情報でリンクが無いことが示されたノード間のリンクの物理量は0であるとする制約条件とを含んで構成される最適化問題を作成する最適化問題作成手段と、前記作成された最適化問題の解を求める最適化問題解法手段とを有することを特徴とする請求項4に記載のグラフ推定装置。
【請求項６】
前記推定手段は、推定されたグラフの各ノードのリンクの物理量の総量と前記観測された各ノードのリンクの物理量の総量との差異に関する評価関数、および、推定されたグラフのノード間のリンクの物理量のうち、トポロジー情報でリンクが無いことが示されたノード間のリンクの物理量が0でないことに関する罰則に関する評価関数を最小化するための目的関数を含んで構成される最適化問題を作成する最適化問題作成手段と、前記作成された最適化問題の解を求める最適化問題解法手段とを有することを特徴とする請求項4に記載のグラフ推定装置。
【請求項７】
前記推定手段は、推定するグラフの行のノード数をnr、列のノード数をnc、予め設定されたパラメータをmとするとき、推定するグラフをnr×mの行列Aとm×ncの行列Bの積ABとして表現し、推定された行列Aと行列Bとから求めた各ノードのリンクの物理量の総量と前記観測された各ノードのリンクの物理量の総量との差異に関する評価関数、および、推定された行列Aと行列Bとから求めたノード間のリンクの物理量のうち、トポロジー情報でリンクが無いことが示されたノード間のリンクの物理量が0でないことに関する罰則に関する評価関数を最小化するための目的関数を含んで構成される最適化問題を作成する最適化問題作成手段と、前記作成された最適化問題の解を求める最適化問題解法手段と、前記推定された行列Aと行列Bとから各ノードのリンクの物理量を計算する計算手段とを有することを特徴とする請求項4に記載のグラフ推定装置。
【請求項８】
複数のノードとノード間のリンクとから構成されるグラフのリンクに所定の物理量を対応付け、各ノードのリンクの物理量の総量から個々のノード間のリンクの物理量を推定するグラフ推定装置であって、
観測された各ノードのリンクの物理量の総量を入力するリンク総量入力手段と、
観測された一部のノード間のリンクの物理量を入力する部分リンク情報入力手段と、
推定されたグラフの各ノードのリンクの物理量の総量と前記観測された各ノードのリンクの物理量の総量との差、および、推定されたグラフのノード間のリンクの物理量と前記観測された一部のノード間のリンクの物理量との差が小さいグラフを推定する推定手段と、
前記推定したグラフにおけるノード間のリンクの物理量を出力する出力手段とを備えることを特徴とするグラフ推定装置。
【請求項９】
前記推定手段は、推定されたグラフの各ノードのリンクの物理量の総量と前記観測された各ノードのリンクの物理量の総量との差異に関する評価関数を最小化するための目的関数と、推定されたグラフのノード間のリンクのうち物理量が観測されたリンクの物理量は観測値と等しいとする制約条件とを含んで構成される最適化問題を作成する最適化問題作成手段と、前記作成された最適化問題の解を求める最適化問題解法手段とを有することを特徴とする請求項8に記載のグラフ推定装置。
【請求項１０】
前記推定手段は、推定されたグラフの各ノードのリンクの物理量の総量と前記観測された各ノードのリンクの物理量の総量との差異に関する評価関数、および、推定されたグラフのノード間のリンクの物理量が前記観測された物理量と等しくないことに関する罰則に関する評価関数を最小化するための目的関数を含んで構成される最適化問題を作成する最適化問題作成手段と、前記作成された最適化問題の解を求める最適化問題解法手段とを有することを特徴とする請求項8に記載のグラフ推定装置。
【請求項１１】
前記推定手段は、推定するグラフの行のノード数をnr、列のノード数をnc、予め設定されたパラメータをmとするとき、推定するグラフをnr×mの行列Aとm×ncの行列Bの積ABとして表現し、推定された行列Aと行列Bとから求めた各ノードのリンクの物理量の総量と前記観測された各ノードのリンクの物理量の総量との差異に関する評価関数、および、推定された行列Aと行列Bとから求めたノード間のリンクの物理量が前記観測された物理量と等しくないことに関する罰則に関する評価関数を最小化するための目的関数を含んで構成される最適化問題を作成する最適化問題作成手段と、前記作成された最適化問題の解を求める最適化問題解法手段と、前記推定された行列Aと行列Bとからノードのリンクの物理量を計算する計算手段とを有することを特徴とする請求項8に記載のグラフ推定装置。
【請求項１２】
複数のノードをネットワーク機器に、ノード間のリンクをネットワーク機器間を接続する通信路に、各ノードのリンクの物理量をネットワーク機器間の通信量に、それぞれ対応付け、各ネットワーク機器の通信量の総量から個々のネットワーク機器間の通信量を推定する請求項1乃至11の何れか1項に記載のグラフ推定装置。
【請求項１３】
複数のノードとノード間のリンクとから構成されるグラフのリンクに所定の物理量を対応付け、各ノードのリンクの物理量の総量から個々のノード間のリンクの物理量を推定するグラフ推定方法であって、
a)リンク総量入力手段が、観測された各ノードのリンクの物理量の総量を入力するリンク総量入力ステップと、
b)推定手段が、推定されたグラフの各ノードのリンクの物理量の総量と前記観測された各ノードのリンクの物理量の総量との差が小さいグラフを推定する推定ステップと、
c)出力手段が、前記推定したグラフにおけるノード間のリンクの物理量を出力する出力ステップとを含むことを特徴とするグラフ推定方法。
【請求項１４】
複数のノードとノード間のリンクとから構成されるグラフのリンクに所定の物理量を対応付け、各ノードのリンクの物理量の総量から個々のノード間のリンクの物理量を推定するグラフ推定装置を構成するコンピュータを、
観測された各ノードのリンクの物理量の総量を入力するリンク総量入力手段と、
推定されたグラフの各ノードのリンクの物理量の総量と前記観測された各ノードのリンクの物理量の総量との差が小さいグラフを推定する推定手段と、
前記推定したグラフにおけるノード間のリンクの物理量を出力する出力手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はグラフ推定方法及びグラフ推定装置に関し、特に複数のノードとノード間のリンクとから構成されるグラフのリンクに所定の物理量を対応付け、各ノードのリンクの物理量の総量から個々のノード間のリンクの物理量を推定するグラフ推定方法及びグラフ推定装置に関する。
【背景技術】
【０００２】
グラフデータとは、一般にノードおよびノード間のリンク関係からなるデータを指し、無向グラフと有向グラフが存在する。無向グラフにおけるリンクは、2つのノード間の関係性の有無を表し、関係性の方向は考慮しない。一方で、有向グラフにおけるリンクは、2つのノードに対して、リンク元とリンク先という形で、リンクの方向が考慮される。
【０００３】
図16は無向グラフデータの一例を示している。表中で、1は対応するノード間にリンクがあることを表し、0はリンクがないことを表す。無向グラフでは、ノード1からノード2へのリンクとノード2からノード1へのリンクの区別はなく、表はノードのインデックスに対して対称となり、行の数(n)と列の数(n)は等しい。この例ではリンクは1または0の2値をとるが、リンクの強さを表す実数値としてもよい。
【０００４】
図17は有向グラフデータの一例を示している。有向グラフでは行と列が同じノードを表す必要はなく、図17は例えば行ノード1から列ノード2へのリンクの強さが0.5であることを表している。これに付随し、行の数(nr)と列の数(nc)も等しい必要はない。
【０００５】
グラフデータの具体的な例を挙げると、Webページのハイパーリンクを分析する場合、ノードは各Webページであり、リンクはWebページ間のハイパーリンクの有無とすることが考えられるし、SNSネットワークの分析をする場合には、ノードは各ユーザーであり、リンクはユーザー間の友人登録の有無とすることが考えられるし、LANの解析をする場合には、ノードは各ネットワーク機器であり、リンクはネットワーク機器間のトラフィック量などとすることが考えられる。また、有向グラフでは、行ノードと列ノードは同じものである必要はなく、例えば行ノードが顧客、列ノードが商品、リンクが顧客と商品の購買状況を表すといった場合がある。
【０００６】
グラフデータに対する分析技術として、部分的なリンク情報から、全体のリンク情報を推定する技術が研究されている。これは例えば、ノードを顧客および商品とし、リンクを顧客が対応する商品を買ったかどうかを表すグラフを考えると、部分的な購買情報から、まだ買っていない顧客がその商品を買うかどうかを推定し、買いそうであれば推薦するシステムなどに利用可能である。代表的な技術としては、協調フィルタリング、協調ランキングが挙げられ、様々な手法が提案されている（例えば特許文献1、非特許文献1参照）。
【０００７】
他方、通信ネットワークの設計に数理計画問題を適用した技術の一例が特許文献2に記載されている。この特許文献2に記載される技術は、複数のノードからなり且つ他のネットワークに接続される対象ネットワークにおいて、他のネットワークからデータが入ってくる入口ノードから流入するデータのトラフィック量および他のネットワークにデータが出て行く出口ノードから流出するデータのトラフィック量を与えて、その範囲内で任意に通信可能とする多地点間通信サービスのための通信ネットワークを設計する技術であり、多地点間通信サービスを求めるための数理計画問題を設定する設定手段と、設定された数理計画問題を解いて多地点間通信サービスのためのパスを得る最適化手段とを備えている。
【０００８】
【特許文献１】特開2007-323315号公報
【特許文献２】特開2002-57676号公報
【非特許文献１】COFIRANK-Maximum Margin Matrix Factorization for Collaborative Ranking, Advances in Neural Information Processing 20, 1593-1600, 2008.
【発明の開示】
【発明が解決しようとする課題】
【０００９】
特許文献1および非特許文献1に記載された技術は、部分的に観測された一部のリンクから、未観測の残りのリンクを推定する。したがって、個々のノード間のリンクが部分的に観測されていることが前提となり、しかもある程度多数のリンクが観測されている必要がある。このため、部分的であっても個々のリンクの観測が難しい対象については適用できないという課題がある。
【００１０】
他方、特許文献2に記載された技術は、一部のノードのリンク総量さえ与えれば個々のノード間のリンクを推定することができる。しかし、ノードとノードのつながりであるトポロジーが既知である必要があるため、トポロジーが不明な対象については適用できないという課題がある。
【００１１】
本発明の目的は、各ノードに関するリンクの総量が観測できる場合に、それを利用して、個々のノード間のリンクを推定することのできるグラフ推定方法及びグラフ推定装置を提供することにある。
【課題を解決するための手段】
【００１２】
本発明のグラフ推定方法は、複数のノードとノード間のリンクとから構成されるグラフのリンクに所定の物理量を対応付け、各ノードのリンクの物理量の総量から個々のノード間のリンクの物理量を推定するグラフ推定方法であって、a)リンク総量入力手段が、観測された各ノードのリンクの物理量の総量を入力するリンク総量入力ステップと、b)推定手段が、推定されたグラフの各ノードのリンクの物理量の総量と前記観測された各ノードのリンクの物理量の総量との差が小さいグラフを推定する推定ステップと、c)出力手段が、前記推定したグラフにおけるノード間のリンクの物理量を出力する出力ステップとを含む。
【００１３】
本発明のグラフ推定装置は、複数のノードとノード間のリンクとから構成されるグラフのリンクに所定の物理量を対応付け、各ノードのリンクの物理量の総量から個々のノード間のリンクの物理量を推定するグラフ推定装置であって、観測された各ノードのリンクの物理量の総量を入力するリンク総量入力手段と、推定されたグラフの各ノードのリンクの物理量の総量と前記観測された各ノードのリンクの物理量の総量との差が小さいグラフを推定する推定手段と、前記推定したグラフにおけるノード間のリンクの物理量を出力する出力手段とを備える。
【発明の効果】
【００１４】
本発明によれば、各ノードに関するリンクの総量が観測できる場合に、それを利用して、個々のノード間のリンクを推定することができる。
【発明を実施するための最良の形態】
【００１５】
［第1の実施の形態］
図1を参照すると、本発明の第1の実施の形態に関わるグラフ推定装置100は、データ処理装置110と、記憶装置120と、リンク総量検出装置130と、出力装置140とを備えている。このグラフ推定装置100は、複数のノードとノード間のリンクとから構成されるグラフのリンクに所定の物理量を対応付け、各ノードのリンクの物理量の総量から個々のノード間のリンクの物理量を推定する。
【００１６】
本実施の形態では、複数のノードをサーバ装置の如きネットワーク機器に、ノード間のリンクをネットワーク機器間を接続する通信路に、各ノードのリンクの物理量をネットワーク機器間の通信量に、それぞれ対応付けることにより、各ネットワーク機器の通信量の総量から個々のネットワーク機器間の通信量を推定する。
【００１７】
リンク総量検出装置130は、各ノード毎のリンク総量を観測し、リンク総量データ150としてデータ処理装置110に入力する装置である。リンク総量データ150は、図2に示されるように、行ノード毎の列ノードに対するリンクの総量データ151と、列ノード毎の行ノードに対するリンクの総量データ152とから構成される。これは、ネットワーク機器間の通信量のグラフを考えた場合に、行ノードに対するリンク総量は、或るネットワーク機器から出力された通信の総量を表し、列ノードに対するリンク総量は、或るネットワーク機器へ入力された通信の総量を表す。個々のネットワーク機器間の通信を漏れなく全て観測することは、技術的あるいはコスト的に難しい場合があるが、個々のネットワーク機器における通信の総量を観測することは比較的容易である。
【００１８】
データ処理装置110は、リンク総量検出装置130から入力したリンク総量データ150に基づいて個々のノード間のリンクを推定し、推定結果160を出力装置140へ出力する装置である。このデータ処理装置110は、リンク総量入力手段111と、推定手段112と、出力手段113とを備えている。
【００１９】
リンク総量入力手段111は、リンク総量検出装置130からリンク総量データ150を入力し、記憶装置120に記憶する手段である。
【００２０】
推定手段112は、推定されたグラフの各ノードのリンク総量とリンク総量データ150との差が小さいグラフを推定する手段である。この推定手段112は、最適化問題作成手段1121と最適化問題解法手段1122とを備えている。
【００２１】
最適化問題作成手段1121は、推定されたグラフの各ノードのリンク総量とリンク総量データ150との差異に関する評価関数を最小化するための目的関数を含んで構成される最適化問題170を作成する手段である。作成された最適化問題170は、記憶装置120に記憶される。
【００２２】
最適化問題解法手段1122は、最適化問題170の解171を求める手段である。本実施の形態では、この解171で、推定グラフの各ノード間のリンクが与えられる。求められた解171は記憶装置120に記憶される。
【００２３】
出力手段113は、解171によって与えられる推定グラフの各ノード間のリンクを含む推定結果160を出力装置140に出力する手段である。推定結果160は、例えば図3に示すような表形式で、ノードおよびその間のリンクの情報が示される。
【００２４】
出力装置140は、推定結果160を出力する液晶ディスプレイ装置、プリンタ装置、ファイル装置あるいはデータ送信装置などである。
【００２５】
記憶装置120は、リンク総量データ150、最適化問題170および解171を記憶する半導体メモリ、磁気ディスク装置などの記憶装置である。
【００２６】
次に本実施の形態の動作を説明する。
【００２７】
図4を参照すると、本実施の形態に関わるグラフ推定装置100は、まずリンク総量入力手段111により、リンク総量検出装置130で観測されたリンク総量データ150を入力して記憶装置120に記憶する（S100）。
【００２８】
次に、推定手段112の最適化問題作成手段1121により、記憶装置120からリンク総量データ150を読み込み、推定されたグラフの各ノードのリンク総量とリンク総量データ150との差異に関する評価関数を最小化するための目的関数を含んだ最適化問題170を作成し、記憶装置120に記憶する（S101）。
【００２９】
次に、推定手段112の最適化問題解法手段1122により、記憶装置120から最適化問題170を読み込み、予め設定された解法アルゴリズムに従って最適化問題170を解き、その解171を記憶装置120に記憶する（S102）。
【００３０】
最後に、出力手段113により、記憶装置120から解171を読み込み、推定結果160を例えば図3に示すような表形式で、出力装置140に出力する（S103）。
【００３１】
次に、推定手段112に関して具体的な例を挙げて説明する。
【００３２】
以降では、グラフはGと表記し、（行）ノードiから（列）ノードjへのリンクをgijと表記する。ここで、一般にはgij≧0である。また、行ノードiに対するリンク総量をriと表記し、列ノードjのリンク総量をcjとする。また、ベクトルrおよびベクトルcは、r=(r1,r2,…,rnr)およびc=(c1,c2,…,cnc)とする。
【００３３】
推定手段112の最適化問題作成手段1121は、式1に示されるように、G,r,cに関する評価関数J1に対してGを最適化する最適化問題、つまり、推定されたグラフの各ノードのリンク総量と観測された各ノードのリンク総量との差異に関する評価関数を最小化するための最適化問題を作成する。ただし、G*は、最適化されたGとする。
［式1］
G*＝arg minG J1(G,r,c)
【００３４】
ここで、J1には、2乗誤差損失、ヒンジ損失、KL-ダイバージェンスなど、公知の任意の損失関数（評価関数）を使用することができる。J1を例えば、推定されたグラフとリンク総量の間の2乗誤差損失を表す評価関数とした場合には、最適化問題を構成する目的関数は、式2で示される。
［式2］
2010117877.tif 000003
【００３５】
また一般に、リンクが正の場合には、次式に示されるような制約条件が成り立つ。
［式3］
gij≧0
【００３６】
最適化問題解法手段1122は、式2の目的関数および式3の制約条件で構成される制約付き最適化問題を解くことにより、最適化されたG*、つまり最適なgijを求める。最適化問題作成手段1121が作成する最適化問題170は、組合せ最適化問題に属する。組合せ最適化問題の解法については、目的関数値の良さを示す局所的評価に基づいて可能解を直接構成していく「欲張り法」、解をランダムに何個か選び、発見された可能解の中で目的関数値が最小のものを選ぶ「ランダム法」、何らかの方法で得られた近似最適解に対して、その近傍、つまり少し変更を加えることで得られる他の解を調べ、改善されていればそれに置き換えていく反復改善法など、各種の解法アルゴリズムが知られている。最適化問題解法手段1122は、それらのうちの任意の解法アルゴリズムを使用して最適化問題170を解法する。
【００３７】
ここで、推定すべき変数gijはnr×nc個あり、観測された値はrとcのnr＋nc個なので、一般に式1または式2の最適化問題は縮退しており、解が複数存在する。このため、最適化問題解法手段1122は、そのうちの1つ以上を最適化されたG*あるいはその候補として出力する。
【００３８】
なお、推定の際にノイズに対して推定をロバストにするために、推定誤差だけでなく、正則化などを評価の中に入れることも可能である。また、前記の最適化問題に、事前に設定すべきパラメータがある場合には、リンク総量データ150と一緒に入力することが可能であるし、事前に記憶装置120に記憶しておくことも可能である。
【００３９】
次に本実施の形態の効果を説明する。
【００４０】
本実施の形態によれば、各ノードに関するリンク総量を利用して、個々のノード間のリンクを推定することができる。具体的には、個々のノードを構成するネットワーク機器の入力および出力の通信量の総量から、個々のネットワーク機器間の通信量を推定することができる。これにより、特定のネットワーク機器間の通信量の異常な増加や、トラフィック量の予測など、ネットワークに対する分析が可能となる。
【００４１】
［第2の実施の形態］
図5を参照すると、本発明の第2の実施の形態に関わるグラフ推定装置200は、第1の実施の形態に関わるグラフ推定装置100と比較して、推定手段112に代えて推定手段114を備えている点で相違する。
【００４２】
第1の実施の形態における推定手段112がグラフGを直接推定していたのに対して、本実施の形態における推定手段114は、グラフGが低ランク構造を持つように制限して間接的に推定する点で相違する。この推定手段114は、最適化問題作成手段1141と、最適化問題解法手段1142と、計算手段1143とを備えている。
【００４３】
最適化問題作成手段1141は、推定するグラフの行のノード数をnr、列のノード数をnc、予め設定されたパラメータをmとするとき、推定するグラフをnr×mの行列Aとm×ncの行列Bの積ABとして表現し、式4に示されるように、A,B,r,cに関する評価関数J2に対してA,Bを最適化する最適化問題、つまり、推定された行列Aと行列Bとから求めたグラフGの各ノードのリンク総量と観測された各ノードのリンク総量との差異に関する評価関数J2を最小化するための目的関数を含んだ最適化問題を作成する手段である。ただし、A*,B*は最適化されたA,Bとする。
［式4］
{A*,B*}＝arg minA,B J2(A,B,r,c)
【００４４】
ここで、J2には、2乗誤差損失、ヒンジ損失、KL-ダイバージェンスなど、公知の任意の損失関数（評価関数）を使用することができる。J2を例えば、推定された行列Aと行列Bとから求めたグラフの各ノードのリンク総量と観測されたリンク総量の間の2乗誤差損失を表す評価関数とした場合には、最適化問題を構成する目的関数は、式5で示される。ただし、Aのi番目の行ベクトルをAi、Bのj番目の列ベクトルをBjとする。また、行ベクトルAiのj番目の要素をAij、列ベクトルBjのi番目の要素をBjiとする。
［式5］
2010117877.tif 000004
【００４５】
また一般に、リンクが正の場合には、式3に示したようにgij≧0が成り立つので、次式に示されるような制約条件が成り立つ。
［式6］
Aij≧0,Bij≧0
【００４６】
最適化問題解法手段1142は、最適化問題解法手段1122と同様の解法アルゴリズムを使用して、式5の目的関数および式6の制約条件で構成される制約付き組合せ最適化問題を解くことにより、最適化されたA*,B*、つまり最適なAij,Akj,Bjk,Bjiを求める手段である。
【００４７】
計算手段1143は、推定された行列Aと行列BとからグラフGの各ノードのリンクを計算する手段である。
【００４８】
次に本実施の形態の動作を説明する。
【００４９】
図6を参照すると、本実施の形態に関わるグラフ推定装置200は、まずリンク総量入力手段111により、リンク総量検出装置130で観測されたリンク総量データ150を入力して記憶装置120に記憶する（S200）。
【００５０】
次に、推定手段114の最適化問題作成手段1141により、記憶装置120からリンク総量データ150を読み込み、前述した式5の目的関数および式6の制約条件で構成される最適化問題173を作成し、記憶装置120に記憶する（S201）。
【００５１】
次に、推定手段114の最適化問題解法手段1142により、記憶装置120から最適化問題173を読み込み、予め設定された解法アルゴリズムに従って最適化問題173を解き、その解174を記憶装置120に記憶する（S202）。解174には、最適化されたA*,B*のAij,Akj,Bjk,Bjiの値が含まれている。
【００５２】
次に、計算手段1143は、記憶装置120から解174を読み込み、例えば次式7により、最適化されたA*,B*から、最適なグラフG*のリンクgikを計算し、その計算結果175を記憶装置120に記憶する（S203）。
［式7］
gik＝Ai1B1k＋Ai2B2k＋…＋AimBmk      （1≦i≦nr、1≦k≦nc）
【００５３】
最後に、出力手段113により、記憶装置120から計算結果175を読み込み、推定結果160を例えば図3に示すような表形式で、出力装置140に出力する（S204）。
【００５４】
なお、推定の際にノイズに対して推定をロバストにするために、推定誤差だけでなく、正則化などを評価の中に入れることも可能である。また、前記の最適化問題に、事前に設定すべきパラメータがある場合には、リンク総量データ150と一緒に入力することが可能であるし、事前に記憶装置120に記憶しておくことも可能である。
【００５５】
次に本実施の形態の効果を説明する。
【００５６】
本実施の形態によれば、各ノードに関するリンク総量を利用して、個々のノード間のリンクを推定することができる。具体的には、本実施の形態によれば、個々のノードを構成するネットワーク機器の入力および出力の通信量の総量から、個々のネットワーク機器間の通信量を推定することができる。
【００５７】
また本実施の形態によれば、グラフGが低ランク構造を持つように制限して間接的に推定するため、有効な変数の数を低く抑えることが可能となる。すなわち、推定するグラフGの行のノード数をnr、列のノード数をnc、予め設定されたパラメータをmとするとき、Gをnr×mの行列Aとm×ncの行列Bの積ABとして表現した場合、G=ABを満たすGのランクはm以下となる。
【００５８】
［第3の実施の形態］
図7を参照すると、本発明の第3の実施の形態に関わるグラフ推定装置300は、第1の実施の形態に関わるグラフ推定装置100と比較して、トポロジー情報入力装置131およびトポロジー情報入力手段116を新たに備えている点、推定手段112の代わりに推定手段115を備えている点で相違する。
【００５９】
トポロジー情報入力装置131は、推定を行うグラフGのトポロジー情報153をデータ処理装置110に入力する装置であり、キーボード、ファイル装置あるいはデータ受信装置などで構成される。
【００６０】
トポロジー情報153は、グラフGのノード間にリンクがあるか無いかという情報を意味する。このトポロジー情報153は、リンクの有るノード間には値1、リンクの無いノード間には値0を設定した例えば図8に示されるような表形式で入力することが可能である。これは、ネットワーク機器間の通信量のグラフを考えた場合に、或るネットワーク機器が別の或るネットワーク機器へデータを送信する可能性があるか否か、或るネットワーク機器が別の或るネットワーク機器からデータを受信する可能性があるか否かを示していることになる。
【００６１】
データ処理装置110のトポロジー情報入力手段116は、トポロジー情報入力装置131からトポロジー情報153を入力し、記憶装置120に記憶する手段である。
【００６２】
推定手段115は、推定されたグラフの各ノードのリンク総量と観測された各ノードのリンク総量150との差、および、推定されたグラフのノード間のリンク関係と入力されたトポロジー情報153との差が小さいグラフを推定する手段である。この推定手段115は、最適化問題作成手段1151と最適化問題解法手段1152とを備えている。
【００６３】
最適化問題作成手段1151は、推定されたグラフの各ノードのリンク総量とリンク総量データ150との差、および、推定されたグラフのノード間のリンク関係と入力されたトポロジー情報153との差が小さいグラフを推定するための最適化問題176を作成する手段である。作成された最適化問題176は、記憶装置120に記憶される。
【００６４】
最適化問題解法手段1152は、最適化問題176の解177を求める手段である。本実施の形態では、この解177で、推定グラフの各ノード間のリンクが与えられる。求められた解177は記憶装置120に記憶される。
【００６５】
次に本実施の形態の動作を説明する。
【００６６】
図9を参照すると、本実施の形態に関わるグラフ推定装置300は、まずリンク総量入力手段111により、リンク総量検出装置130で観測されたリンク総量データ150を入力して記憶装置120に記憶する（S300）。
【００６７】
次に、トポロジー情報入力手段116により、トポロジー情報入力装置131からトポロジー情報153を入力して記憶装置120に記憶する（S301）。なお、ステップS301の処理はステップS300の前に実行しても良い。
【００６８】
次に、推定手段115の最適化問題作成手段1151により、記憶装置120からリンク総量データ150およびトポロジー情報153を読み込み、推定されたグラフの各ノードのリンク総量とリンク総量データ150との差、および、推定されたグラフのノード間のリンク関係とトポロジー情報153との差が小さいグラフを推定するための最適化問題176を作成し、記憶装置120に記憶する（S302）。
【００６９】
次に、推定手段115の最適化問題解法手段1152により、記憶装置120から最適化問題176を読み込み、予め設定された解法アルゴリズムに従って最適化問題176を解き、その解177を記憶装置120に記憶する（S303）。
【００７０】
最後に、出力手段113により、記憶装置120から解177を読み込み、推定結果160を例えば図3に示すような表形式で、出力装置140に出力する（S304）。
【００７１】
次に、推定手段115に関して具体的な例を挙げて説明する。
【００７２】
今、ノードiとノードjの間にリンクがある場合には(i,j)∈Iとし、無い場合には(i,j)∈Zとする。ここで、I,Zは、リンクの有無に関するノードインデックス組の集合であり、トポロジー情報153により一意に決まる。推定手段115の最適化問題作成手段1151は、式8に示されるように、G,r,c,I,Zに関する評価関数J3に対してGを最適化する最適化問題、つまり、推定されたグラフの各ノードのリンク総量と観測された各ノードのリンク総量との差および推定されたグラフのノード間のリンク関係とトポロジー情報153との差に関する評価関数を最小化するための最適化問題を作成する。
［式8］
G*＝arg minG J3(G,r,c,I,Z)
【００７３】
式8に示す最適化問題の具体例を以下に示す。
【００７４】
（1）例1
この例1では、推定されたグラフの各ノードのリンク総量と観測されたリンク総量150との差異に関する評価関数を最小化するための目的関数と、トポロジー情報153でリンクが無いことが示されたノード間のリンクは0であるとする制約条件とを用いて、最適化問題を作成する。このときの評価関数には、2乗誤差損失、ヒンジ損失、KL-ダイバージェンスなど、公知の任意の損失関数（評価関数）を使用することができる。評価関数を例えば、推定されたグラフとリンク総量の間の2乗誤差損失を表す評価関数とした場合には、最適化問題を構成する目的関数は、式9で示される。
［式9］
2010117877.tif 000005
【００７５】
また、トポロジー情報153でリンクが無いことが示されたノード間のリンクは0であるとする制約条件は、次式10で与えられる。
［式10］
g*ij＝0    if  (i,j)∈Z
【００７６】
なお、一般に、リンクが正の場合には、前述した式3に示されるgij≧0の制約条件も成り立つ。
【００７７】
（2）例2
この例2では、推定されたグラフの各ノードのリンク総量と観測されたリンク総量150との差異に関する第1の評価関数、および、推定されたグラフのノード間のリンクのうち、トポロジー情報153でリンクが無いことが示されたノード間のリンクが0でないことに関する罰則に関する第2の評価関数を最小化するための目的関数を用いて、最適化問題を作成する。このときの第1の評価関数には、2乗誤差損失、ヒンジ損失、KL-ダイバージェンスなど、公知の任意の損失関数（評価関数）を使用することができる。また、第2の評価関数には、L1ノルムやL2ノルムなど、罰則を表す任意の損失関数（評価関数）を使用することができる。第1の評価関数を例えば、推定されたグラフとリンク総量の間の2乗誤差損失を表す評価関数とした場合には、最適化問題を構成する目的関数は、式11で示される。
［式11］
2010117877.tif 000006
【００７８】
ただし、式11中のf(gij)は引数に対する罰則を表す第2の評価関数であり、例えばL1ノルムの場合はf(gij)＝|gij|であり、L2ノルムの場合はf(gij)＝gij2である。
【００７９】
なお、一般に、リンクが正の場合には、前述した式3に示されるgij≧0の制約条件が成り立つ。
【００８０】
例1によってG*を推定した場合、推定誤差は全て(i,j)∈Iに対応するリンクに関する誤差となる。これに対して例2では、誤差を全リンクへ分散させることができる。
【００８１】
最適化問題解法手段1152は、式9の目的関数および式3および式10の制約条件で構成される制約付き最適化問題、あるいは式11の目的関数および式3の制約条件で構成される制約付き最適化問題を適当な解法アルゴリズムを使用して解くことにより、最適化されたG*、つまり最適なgijを求める。
【００８２】
なお、推定の際にノイズに対して推定をロバストにするために、推定誤差だけでなく、正則化などを評価の中に入れることも可能である。また、前記の最適化問題に、事前に設定すべきパラメータがある場合には、リンク総量データ150と一緒に入力することが可能であるし、事前に記憶装置120に記憶しておくことも可能である。
【００８３】
次に本実施の形態の効果を説明する。
【００８４】
本実施の形態によれば、各ノードに関するリンク総量およびトポロジー情報を利用して、個々のノード間のリンクを推定することができる。具体的には、本実施の形態によれば、個々のノードを構成するネットワーク機器の入力および出力の通信量の総量およびネットワーク機器間の通信の可能性の有無から、個々のネットワーク機器間の通信量を推定することができる。
【００８５】
また本実施の形態によれば、トポロジー情報を用いたことにより、第1の実施の形態に比べて推定精度を高めることができる。その理由は、トポロジー情報が分かっている場合には、リンクが無いノード組が事前にわかるため、推定すべきパラメータの数を減らすことが可能になるためである。
【００８６】
［第4の実施の形態］
図10を参照すると、本発明の第4の実施の形態に関わるグラフ推定装置400は、第3の実施の形態に関わるグラフ推定装置300と比較して、推定手段115に代えて推定手段117を備えている点で相違する。
【００８７】
第3の実施の形態における推定手段115がグラフGを直接推定していたのに対して、本実施の形態における推定手段117は、グラフGが低ランク構造を持つように制限して間接的に推定する点で相違する。この推定手段117は、最適化問題作成手段1171と、最適化問題解法手段1172と、計算手段1173とを備えている。
【００８８】
最適化問題作成手段1171は、推定するグラフの行のノード数をnr、列のノード数をnc、予め設定されたパラメータをmとするとき、推定するグラフをnr×mの行列Aとm×ncの行列Bの積ABとして表現し、式12に示されるように、A,B,r,c,I,Zに関する評価関数J4に対してA,Bを最適化する最適化問題、つまり、推定された行列Aと行列Bとから求めたグラフGの各ノードのリンク総量と観測された各ノードのリンク総量との差異、および、推定されたグラフのノード間のリンク関係とトポロジー情報153との差異に関する評価関数J4を最小化するための目的関数を含んだ最適化問題を作成する手段である。
［式12］
{A*,B*}＝arg minA,B J4(A,B,r,c,I,Z)
【００８９】
式12で示される最適化問題の具体例を以下に示す。
【００９０】
この例では、推定されたグラフの各ノードのリンク総量と観測されたリンク総量150との差異に関する第1の評価関数、および、推定されたグラフのノード間のリンクのうち、トポロジー情報153でリンクが無いことが示されたノード間のリンクが0でないことに関する罰則に関する第2の評価関数を最小化するための目的関数を用いて、最適化問題を作成する。このときの第1の評価関数には、2乗誤差損失、ヒンジ損失、KL-ダイバージェンスなど、公知の任意の損失関数（評価関数）を使用することができる。また、第2の評価関数には、L1ノルムやL2ノルムなど、罰則を表す任意の損失関数（評価関数）を使用することができる。第1の評価関数を例えば、推定されたグラフとリンク総量の間の2乗誤差損失を表す評価関数とした場合には、最適化問題を構成する目的関数は、式13で示される。
［式13］
2010117877.tif 000007
【００９１】
ただし、式13中のf(ricj)は引数に対する罰則を表す第2の評価関数であり、例えばL1ノルムやL2ノルムなどである。
【００９２】
なお、一般に、リンクが正の場合には、前述した式6に示したAij≧0,Bij≧0という制約条件が成り立つ。
【００９３】
上記の例は、第2の実施の形態における例2に相当し、誤差を全リンクへ分散させることができる。なお、G=ABとした場合には、Gの各成分はAとBによって記述され、独立とならないため、(i,j)∈Zに対応するリンクを全て0とすることはできない。このため、第2の実施の形態における例1のような実現例は本実施の形態では採用できない。
【００９４】
最適化問題解法手段1172は、式13の目的関数および式6の制約条件で構成される制約付き最適化問題を適当な解法アルゴリズムを使用して解くことにより、最適化されたA*,B*、つまり最適なAij,Akj,Bjk,Bjiを求める手段である。
【００９５】
計算手段1173は、推定された行列Aと行列BとからグラフGの各ノードのリンクを計算する手段である。
【００９６】
次に本実施の形態の動作を説明する。
【００９７】
図11を参照すると、本実施の形態に関わるグラフ推定装置400は、まずリンク総量入力手段111により、リンク総量検出装置130で観測されたリンク総量データ150を入力して記憶装置120に記憶する（S400）。
【００９８】
次に、トポロジー情報入力手段116により、トポロジー情報入力装置131からトポロジー情報153を入力して記憶装置120に記憶する（S401）。なお、ステップS401の処理はステップS400の前に実行しても良い。
【００９９】
次に、推定手段117の最適化問題作成手段1171により、記憶装置120からリンク総量データ150およびトポロジー情報153を読み込み、前述した式13の目的関数および式6の制約条件で構成される最適化問題178を作成し、記憶装置120に記憶する（S402）。
【０１００】
次に、推定手段117の最適化問題解法手段1172により、記憶装置120から最適化問題178を読み込み、予め設定された解法アルゴリズムに従って最適化問題178を解き、その解179を記憶装置120に記憶する（S403）。解179には、最適化されたA*,B*のAij,Akj,Bjk,Bjiの値が含まれている。
【０１０１】
次に、計算手段1173は、記憶装置120から解179を読み込み、例えば前述した式7により、最適化されたA*,B*から、最適なグラフG*のリンクgikを計算し、その計算結果180を記憶装置120に記憶する（S404）。
【０１０２】
最後に、出力手段113により、記憶装置120から計算結果180を読み込み、推定結果160を例えば図3に示すような表形式で、出力装置140に出力する（S405）。
【０１０３】
なお、推定の際にノイズに対して推定をロバストにするために、推定誤差だけでなく、正則化などを評価の中に入れることも可能である。また、前記の最適化問題に、事前に設定すべきパラメータがある場合には、リンク総量データ150と一緒に入力することが可能であるし、事前に記憶装置120に記憶しておくことも可能である。
【０１０４】
次に本実施の形態の効果を説明する。
【０１０５】
本実施の形態によれば、各ノードに関するリンク総量およびトポロジー情報を利用して、個々のノード間のリンクを推定することができる。具体的には、本実施の形態によれば、個々のノードを構成するネットワーク機器の入力および出力の通信量の総量およびネットワーク機器間の通信の可能性の有無から、個々のネットワーク機器間の通信量を推定することができる。
【０１０６】
また本実施の形態によれば、トポロジー情報を用いたことにより、第3の実施の形態に比べて推定精度を高めることができる。その理由は、トポロジー情報が分かっている場合には、リンクが無いノード組が事前にわかるため、推定すべきパラメータの数を減らすことが可能になるためである。
【０１０７】
また本実施の形態によれば、グラフGが低ランク構造を持つように制限して間接的に推定するため、有効な変数の数を低く抑えることが可能となる。
【０１０８】
［第5の実施の形態］
図12を参照すると、本発明の第5の実施の形態に関わるグラフ推定装置500は、第1の実施の形態に関わるグラフ推定装置100と比較して、部分リンク情報入力装置132および部分リンク情報入力手段119を新たに備えている点、推定手段112の代わりに推定手段118を備えている点で相違する。
【０１０９】
部分リンク情報入力装置132は、部分リンク情報154をデータ処理装置110に入力する装置であり、キーボード、ファイル装置あるいはデータ受信装置などで構成される。
【０１１０】
部分リンク情報154は、部分的に観測されたリンクを指す。ノードiとノードjのリンクが観測されている場合には、(i,j)∈Oとする。Oは、観測されたリンクに対応するノードインデックス組の集合を表す。また、観測されたリンクをoi,jと表記する。ネットワーク機器間の通信量のグラフを考えた場合に、或るネットワーク機器が別の或るネットワーク機器へ実際に送信したデータ量が観測されている場合や、或るネットワーク機器が別の或るネットワーク機器から実際に受信したデータ量が観測されている場合には、部分リンク情報154でそれらのリンクを入力することになる。
【０１１１】
データ処理装置110の部分リンク情報入力手段119は、部分リンク情報入力装置132から部分リンク情報154を入力し、記憶装置120に記憶する手段である。
【０１１２】
推定手段118は、推定されたグラフの各ノードのリンク総量と観測された各ノードのリンク総量150との差、および、推定されたグラフのノード間のリンクと入力された部分リンク情報154との差が小さいグラフを推定する手段である。この推定手段118は、最適化問題作成手段1181と最適化問題解法手段1182とを備えている。
【０１１３】
最適化問題作成手段1181は、推定されたグラフの各ノードのリンク総量とリンク総量データ150との差、および、推定されたグラフのノード間のリンクと部分トポロジー情報154との差が小さいグラフを推定するための最適化問題181を作成する手段である。作成された最適化問題181は、記憶装置120に記憶される。
【０１１４】
最適化問題解法手段1182は、最適化問題181の解182を求める手段である。本実施の形態では、この解182で、推定グラフの各ノード間のリンクが与えられる。求められた解182は記憶装置120に記憶される。
【０１１５】
次に本実施の形態の動作を説明する。
【０１１６】
図13を参照すると、本実施の形態に関わるグラフ推定装置500は、まずリンク総量入力手段111により、リンク総量検出装置130で観測されたリンク総量データ150を入力して記憶装置120に記憶する（S500）。
【０１１７】
次に、部分リンク情報入力手段119により、部分リンク情報入力装置132から部分リンク情報154を入力して記憶装置120に記憶する（S501）。なお、ステップS501の処理はステップS500の前に実行しても良い。
【０１１８】
次に、推定手段118の最適化問題作成手段1181により、記憶装置120からリンク総量データ150および部分リンク情報154を読み込み、推定されたグラフの各ノードのリンク総量とリンク総量データ150との差、および、推定されたグラフのノード間のリンクと部分リンク情報154との差が小さいグラフを推定するための最適化問題181を作成し、記憶装置120に記憶する（S502）。
【０１１９】
次に、推定手段118の最適化問題解法手段1182により、記憶装置120から最適化問題181を読み込み、予め設定された解法アルゴリズムに従って最適化問題181を解き、その解182を記憶装置120に記憶する（S503）。
【０１２０】
最後に、出力手段113により、記憶装置120から解182を読み込み、推定結果160を例えば図3に示すような表形式で、出力装置140に出力する（S504）。
【０１２１】
次に、推定手段118に関して具体的な例を挙げて説明する。
【０１２２】
今、ノードiとノードjのリンクが観測されている場合には(i,j)∈Oとし、その観測されたリンクをoijとする。また観測されていない場合には(i,j)∈Uとする。ここで、O,Uは、観測されているリンク、観測されていないリンクに関するノードインデックス組の集合であり、部分リンク情報154により一意に決まる。推定手段118の最適化問題作成手段1181は、式14に示されるように、G,r,c,Oに関する評価関数J5に対してGを最適化する最適化問題、つまり、推定されたグラフの各ノードのリンク総量と観測されたリンク総量データ150との差および推定されたグラフのノードのリンクと部分リンク情報154との差に関する評価関数を最小化するための最適化問題を作成する。
［式14］
G*＝arg minG J5(G,r,c,O)
【０１２３】
式14に示す最適化問題の実現例を以下に示す。
【０１２４】
（1）例1
この例1では、推定されたグラフの各ノードのリンク総量と観測されたリンク総量150との差異に関する評価関数を最小化するための目的関数と、部分リンク情報154によってリンクが観測されているリンクの値は観測値と等しいとする制約条件とを用いて、最適化問題を作成する。このときの評価関数には、2乗誤差損失、ヒンジ損失、KL-ダイバージェンスなど、公知の任意の損失関数（評価関数）を使用することができる。評価関数を例えば、推定されたグラフとリンク総量の間の2乗誤差損失を表す評価関数とした場合には、最適化問題を構成する目的関数は、式15で示される。
［式15］
2010117877.tif 000008
【０１２５】
また、部分リンク情報154によってリンクが観測されているリンクの値は観測値と等しいとする制約条件は、次式16で与えられる。
［式16］
g*ij＝oi,j    if  (i,j)∈O
【０１２６】
なお、一般に、リンクが正の場合には、前述した式3に示されるgij≧0の制約条件も成り立つ。
【０１２７】
（2）例2
この例2では、推定されたグラフの各ノードのリンク総量と観測されたリンク総量150との差異に関する第1の評価関数、および、推定されたグラフのノード間のリンクのうち、部分リンク情報154によってリンクが観測されているリンクの値が観測値と等しくないことに関する罰則に関する第2の評価関数を最小化するための目的関数を用いて、最適化問題を作成する。このときの第1および第2の評価関数には、2乗誤差損失、ヒンジ損失、KL-ダイバージェンスなど、公知の任意の損失関数（評価関数）を使用することができる。第1の評価関数を例えば、推定されたグラフとリンク総量の間の2乗誤差損失を表す評価関数、第2の評価関数を、(i,j)∈Oに対応するリンクの推定値と観測されたoijとの2乗誤差損失を表す評価関数とした場合には、最適化問題を構成する目的関数は、式17で示される。
［式17］
2010117877.tif 000009
【０１２８】
なお、一般に、リンクが正の場合には、前述した式3に示されるgij≧0の制約条件が成り立つ。
【０１２９】
例1によってG*を推定した場合、推定誤差は未観測のリンクに関する誤差となる。これに対して例2では、誤差を全リンクへ分散させることができる。
【０１３０】
最適化問題解法手段1182は、式15の目的関数および式3および式16の制約条件で構成される制約付き最適化問題、あるいは式17の目的関数および式3の制約条件で構成される制約付き最適化問題を適当な解法アルゴリズムを使用して解くことにより、最適化されたG*、つまり最適なgijを求める。
【０１３１】
なお、推定の際にノイズに対して推定をロバストにするために、推定誤差だけでなく、正則化などを評価の中に入れることも可能である。また、前記の最適化問題に、事前に設定すべきパラメータがある場合には、リンク総量データ150と一緒に入力することが可能であるし、事前に記憶装置120に記憶しておくことも可能である。
【０１３２】
次に本実施の形態の効果を説明する。
【０１３３】
本実施の形態によれば、各ノードに関するリンク総量および部分リンク情報を利用して、個々のノード間のリンクを推定することができる。具体的には、本実施の形態によれば、個々のノードを構成するネットワーク機器の入力および出力の通信量の総量および一部のネットワーク機器間の通信量から、残りの全てのネットワーク機器間の通信量を推定することができる。
【０１３４】
また本実施の形態によれば、部分リンク情報を用いたことにより、第1の実施の形態に比べて推定精度を高めることができる。その理由は、部分リンク情報が存在する場合には、推定すべきパラメータの数を減らすことが可能になるためである。
【０１３５】
［第6の実施の形態］
図14を参照すると、本発明の第6の実施の形態に関わるグラフ推定装置600は、第5の実施の形態に関わるグラフ推定装置500と比較して、推定手段118に代えて推定手段11Aを備えている点で相違する。
【０１３６】
第5の実施の形態における推定手段118がグラフGを直接推定していたのに対して、本実施の形態における推定手段11Aは、グラフGが低ランク構造を持つように制限して間接的に推定する点で相違する。この推定手段11Aは、最適化問題作成手段11A1と、最適化問題解法手段11A2と、計算手段11A3とを備えている。
【０１３７】
最適化問題作成手段11A1は、推定するグラフの行のノード数をnr、列のノード数をnc、予め設定されたパラメータをmとするとき、推定するグラフをnr×mの行列Aとm×ncの行列Bの積ABとして表現し、式18に示されるように、A,B,r,c,Oに関する評価関数J6に対してA,Bを最適化する最適化問題、つまり、推定された行列Aと行列Bとから求めたグラフGの各ノードのリンク総量と観測された各ノードのリンク総量との差異、および、推定されたグラフのノードのリンクと部分リンク情報154（(i,j)∈O）との差異に関する評価関数J6を最小化するための目的関数を含んだ最適化問題を作成する手段である。
［式18］
{A*,B*}＝arg minA,B J4(A,B,r,c,O)
【０１３８】
式18で示される最適化問題の具体例を以下に示す。
【０１３９】
この例では、推定されたグラフの各ノードのリンク総量と観測されたリンク総量150との差異に関する第1の評価関数、および、推定されたグラフのノードのリンクが部分リンク情報154と等しくないことに関する罰則に関する第2の評価関数を最小化するための目的関数を用いて、最適化問題を作成する。このときの第1および第2の評価関数には、2乗誤差損失、ヒンジ損失、KL-ダイバージェンスなど、公知の任意の損失関数（評価関数）を使用することができる。第1の評価関数を例えば、推定されたグラフとリンク総量の間の2乗誤差損失を表す評価関数、第2の評価関数を、(i,j)∈Oに対応するリンクの推定値と観測されたoijとの2乗誤差損失を表す評価関数とした場合には、最適化問題を構成する目的関数は、式19で示される。
［式19］
2010117877.tif 000010
【０１４０】
なお、一般に、リンクが正の場合には、前述した式6に示したAij≧0,Bij≧0という制約条件が成り立つ。
【０１４１】
上記の実現例は、第2の実施の形態における例2に相当し、誤差を全リンクへ分散させることができる。なお、G=ABとした場合には、Gの各成分はAとBによって記述され、独立とならないため、第2の実施の形態における例1のような実現例は本実施の形態では採用できない。
【０１４２】
最適化問題解法手段11A2は、式19の目的関数および式6の制約条件で構成される制約付き最適化問題を適当な解法アルゴリズムを使用して解くことにより、最適化されたA*,B*、つまり最適なAij,Akj,Bjk,Bjiを求める手段である。
【０１４３】
計算手段11A3は、推定された行列Aと行列BとからグラフGの各ノードのリンクを計算する手段である。
【０１４４】
次に本実施の形態の動作を説明する。
【０１４５】
図15を参照すると、本実施の形態に関わるグラフ推定装置500は、まずリンク総量入力手段111により、リンク総量検出装置130で観測されたリンク総量データ150を入力して記憶装置120に記憶する（S600）。
【０１４６】
次に、部分リンク情報入力手段119により、部分リンク情報入力装置132から部分リンク情報154を入力して記憶装置120に記憶する（S601）。なお、ステップS601の処理はステップS600の前に実行しても良い。
【０１４７】
次に、推定手段11Aの最適化問題作成手段11A1により、記憶装置120からリンク総量データ150および部分リンク情報154を読み込み、前述した式19の目的関数および式6の制約条件で構成される最適化問題183を作成し、記憶装置120に記憶する（S602）。
【０１４８】
次に、推定手段11Aの最適化問題解法手段11A2により、記憶装置120から最適化問題183を読み込み、予め設定された解法アルゴリズムに従って最適化問題183を解き、その解184を記憶装置120に記憶する（S603）。解184には、最適化されたA*,B*のAij,Akj,Bjk,Bjiの値が含まれている。
【０１４９】
次に、計算手段11A3は、記憶装置120から解184を読み込み、例えば前記式7により、最適化されたA*,B*から、最適なグラフG*のリンクgikを計算し、その計算結果185を記憶装置120に記憶する（S604）。
【０１５０】
最後に、出力手段113により、記憶装置120から計算結果185を読み込み、推定結果160を例えば図3に示すような表形式で、出力装置140に出力する（S605）。
【０１５１】
なお、推定の際にノイズに対して推定をロバストにするために、推定誤差だけでなく、正則化などを評価の中に入れることも可能である。また、前記の最適化問題に、事前に設定すべきパラメータがある場合には、リンク総量データ150と一緒に入力することが可能であるし、事前に記憶装置120に記憶しておくことも可能である。
【０１５２】
次に本実施の形態の効果を説明する。
【０１５３】
本実施の形態によれば、各ノードに関するリンク総量および部分リンク情報を利用して、個々のノード間のリンクを推定することができる。具体的には、本実施の形態によれば、個々のノードを構成するネットワーク機器の入力および出力の通信量の総量および部分的に観測されたネットワーク機器間の通信量から、残りの全てのネットワーク機器間の通信量を推定することができる。
【０１５４】
また本実施の形態によれば、部分リンク情報を用いたことにより、第1の実施の形態に比べて推定精度を高めることができる。その理由は、部分リンク情報が存在する場合には、推定すべきパラメータの数を減らすことが可能になるためである。
【０１５５】
また本実施の形態によれば、グラフGが低ランク構造を持つように制限して間接的に推定するため、有効な変数の数を低く抑えることが可能となる。
【０１５６】
［その他の実施の形態］
以上、本発明の実施の形態について説明したが、本発明は以上の実施の形態にのみ限定されず、以下に述べるような各種の付加変更が可能である。
【０１５７】
第3の実施の形態と第5の実施の形態とを組み合わせることにより、或いは第4の実施の形態と第6の実施の形態とを組み合わせることにより、リンク総量データ150、トポロジー情報153および部分リンク情報154を用いて、残りの全てのノードのリンクを推定する実施の形態も考えられる。この実施の形態では、推定手段は、推定されたグラフの各ノードのリンク総量とリンク総量データ150との差、推定されたグラフのノード間のリンク関係とトポロジー情報153との差、および、推定されたグラフのノード間のリンクと部分リンク情報154との差が小さいグラフを推定する。
【０１５８】
以上の各実施の形態では、ネットワーク機器の通信量の総量から個々のネットワーク機器間の通信量を推定する技術に本発明を適用したが、本発明はそれだけに限定されず、その他各種の応用が可能である。
【０１５９】
例えば、Webページのハイパーリンクの分析への応用例として、ノードを各Webページに、リンクをWebページ間のハイパーリンクの有無に対応付け、各Webページの他からの非参照総数および他への参照総数から、個々のWebページ間の参照数を推定することが考えられる。
【０１６０】
また、SNSネットワークの分析への応用例として、ノードを各ユーザーに、リンクをユーザー間の友人登録の有無に対応付け、各ユーザーの他ユーザーへの友人登録総数と他ユーザーからの友人登録総数とから、個々のユーザー間の友人関係の有無を推定することが考えられる。
【０１６１】
また、購買状況の分析への応用例として、行ノードを顧客、列ノードを商品、リンクを顧客と商品の購買状況にそれぞれ対応付け、顧客毎の商品購入総数と、商品毎の販売総数とから、各顧客毎にどの商品をどれだけ購入したかを推定することが考えられる。
【０１６２】
また、金融分野への応用例として、複数の行ノードを資金の貸し手（例えば金融機関）、複数の列ノードを資金の借り手（例えば企業）、行ノードから列ノードへのリンクの物理量を貸し出し金額、列ノードから行ノードへのリンクを借り受け金額に、それぞれ対応付けることにより、各貸し手毎の総貸し出し金額、各借り手毎の総借り受け金額から、個々の貸し手と借り手との間の資金の貸し借り金額を推定する技術への応用が考えられる。
【０１６３】
また、本発明のグラフ推定装置は、その有する機能をハードウェア的に実現することは勿論、コンピュータとプログラムとで実現することができる。プログラムは、磁気ディスクや半導体メモリ等のコンピュータ可読記録媒体に記録されて提供され、コンピュータの立ち上げ時などにコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータを前述した各実施の形態におけるリンク総量入力手段、トポロジー情報入力手段、部分リンク情報入力手段、推定手段、出力手段として機能させる。
【図面の簡単な説明】
【０１６４】
【図１】本発明の第1の実施の形態のブロック図である。
【図２】リンク総量データの一例を示す図である。
【図３】推定結果の一例を示す図である。
【図４】本発明の第1の実施の形態の処理例を示すフローチャートである。
【図５】本発明の第2の実施の形態のブロック図である。
【図６】本発明の第2の実施の形態の処理例を示すフローチャートである。
【図７】本発明の第3の実施の形態のブロック図である。
【図８】トポロジー情報の一例を示す図である。
【図９】本発明の第3の実施の形態の処理例を示すフローチャートである。
【図１０】本発明の第4の実施の形態のブロック図である。
【図１１】本発明の第4の実施の形態の処理例を示すフローチャートである。
【図１２】本発明の第5の実施の形態のブロック図である。
【図１３】本発明の第5の実施の形態の処理例を示すフローチャートである。
【図１４】本発明の第6の実施の形態のブロック図である。
【図１５】本発明の第6の実施の形態の処理例を示すフローチャートである。
【図１６】無向グラフデータの一例を示す図である。
【図１７】有向グラフデータの一例を示す図である。
【符号の説明】
【０１６５】
100、200、300、400、500、600…グラフ推定装置
110…データ処理装置
111…リンク総量入力手段
112、114、115、117、118、11A…推定手段
113…出力手段
116…トポロジー情報入力手段
119…部分リンク情報入力手段
120…記憶装置
130…リンク総量検出装置
131…トポロジー情報入力装置
132…部分リンク情報入力装置
140…出力装置
150…リンク総量データ
151…行ノード毎のリンク総量データ
152…列ノード毎のリンク総量データ
153…トポロジー情報
154…部分リンク情報
160…推定結果
170、173、176、178、181、183…最適化問題
171、174、177、179、182、184…解
175、180、185…計算結果
1121、1141、1151、1171、1181、11A1…最適化問題作成手段
1122、1142、1152、1172、1182、11A2…最適化問題解法手段
1143、1173、11A3…計算手段
【図１】
2010117877.tif 000011
【図２】
2010117877.tif 000012
【図３】
2010117877.tif 000013
【図４】
2010117877.tif 000014
【図５】
2010117877.tif 000015
【図６】
2010117877.tif 000016
【図７】
2010117877.tif 000017
【図８】
2010117877.tif 000018
【図９】
2010117877.tif 000019
【図１０】
2010117877.tif 000020
【図１１】
2010117877.tif 000021
【図１２】
2010117877.tif 000022
【図１３】
2010117877.tif 000023
【図１４】
2010117877.tif 000024
【図１５】
2010117877.tif 000025
【図１６】
2010117877.tif 000026
【図１７】
2010117877.tif 000027