(57)【要約】【課題】直径の上限が定数となるようなふるまいをするグラフデータを解析し、真のグラフ構造を推定することができる。【解決手段】グラフ構造推定装置１０は、グラフデータの隣接行列及び自然数を入力する入力部１２、隣接行列及び自然数に基づいて、グラフの頂点及び頂点に割り当てるテーブルに関する第１のパラメータ、テーブルの人気度に関する第２のパラメータ、及び頂点に割り当てるテーブルの分割を表現した行列を表す第３のパラメータを含むパラメータ群の初期値を生成する初期パラメータ生成部１４、隣接行列、自然数、及びパラメータ群に基づいてグラフの確率的生成モデルを乱択法を用いて生成すると共に、パラメータ群を更新することにより隣接行列を更新するパラメータ更新部１６、パラメータ群の更新を終了するか否かを判定する終了判定部１８、パラメータ群の更新を終了すると判定された場合に、更新された隣接行列を出力する出力部２０を含む。【選択図】図１
2018077584.tif 000002
【特許請求の範囲】
【請求項１】
観測されるグラフデータの隣接行列及び前記グラフデータで表されるグラフ上の距離の上限を表す自然数を入力する入力部と、
前記グラフデータの隣接行列及び前記自然数に基づいて、前記グラフの頂点及び前記頂点に割り当てるテーブルに関する第１のパラメータ、前記テーブルの人気度に関する第２のパラメータ、及び、前記グラフデータと前記第１のパラメータと前記第２のパラメータとに基づく確率的生成モデルを用いて生成したサンプルグラフから得られた、前記頂点に割り当てるテーブルの分割を表現した行列を表す第３のパラメータ、を含むパラメータ群の初期値を生成する初期パラメータ生成部と、
前記グラフデータの隣接行列、前記自然数、及び前記パラメータ群に基づいて、前記グラフデータの隣接行列に対する、前記第３のパラメータに対応する前記グラフの頂点の各々についての完全二部木から得られる隣接行列が尤もらしくなるように、前記確率的生成モデルを用いて生成されたグラフに基づいて前記パラメータ群を更新するパラメータ更新部と、
前記パラメータ群の更新を終了するか否かを判定する終了判定部と、
前記終了判定部により前記パラメータ群の更新を終了すると判定された場合に、前記パラメータ更新部により更新された前記第３のパラメータに対応する前記グラフの頂点の各々についての前記完全二部木から得られる隣接行列を出力する出力部と、
を含むグラフ構造推定装置。
【請求項２】
前記パラメータ更新部は、前記確率的生成モデルとして、前記グラフ上の距離の上限が前記自然数以下となるように前記グラフを生成する確率的生成モデルを用いて前記パラメータ群を更新する
請求項１記載のグラフ構造推定装置。
【請求項３】
前記パラメータ更新部は、前記確率的生成モデルを用いて前記グラフを生成する際に、前記第１のパラメータとして前記頂点の共変量及び前記テーブルの共変量を用いた基準を用いて、前記パラメータ群を更新する
請求項２記載のグラフ構造推定装置。
【請求項４】
入力部、初期パラメータ生成部、パラメータ更新部、終了判定部、及び出力部を含むグラフ構造推定装置におけるグラフ構造推定方法であって、
前記入力部が、観測されるグラフデータの隣接行列及び前記グラフデータで表されるグラフ上の距離の上限を表す自然数を入力するステップと、
前記初期パラメータ生成部が、前記グラフデータの隣接行列及び前記自然数に基づいて、前記グラフの頂点及び前記頂点に割り当てるテーブルに関する第１のパラメータ、前記テーブルの人気度に関する第２のパラメータ、及び、前記グラフデータと前記第１のパラメータと前記第２のパラメータとに基づく確率的生成モデルを用いて生成したサンプルグラフから得られた、前記頂点に割り当てるテーブルの分割を表現した行列を表す第３のパラメータ、を含むパラメータ群の初期値を生成するステップと、
前記パラメータ更新部が、前記グラフデータの隣接行列、前記自然数、及び前記パラメータ群に基づいて、前記グラフデータの隣接行列に対する、前記第３のパラメータに対応する前記グラフの頂点の各々についての完全二部木から得られる隣接行列が尤もらしくなるように、前記確率的生成モデルを用いて生成されたグラフに基づいて前記パラメータ群を更新するステップと、
前記終了判定部が、前記パラメータ群の更新を終了するか否かを判定するステップと、
前記出力部が、前記終了判定部により前記パラメータ群の更新を終了すると判定された場合に、前記パラメータ更新部により更新された前記第３のパラメータに対応する前記グラフの頂点の各々についての前記完全二部木から得られる隣接行列を出力するステップと、
を含むグラフ構造推定方法。
【請求項５】
前記パラメータ更新部が前記パラメータ群を更新するステップは、前記確率的生成モデルとして、前記グラフ上の距離の上限が前記自然数以下となるように前記グラフを生成する確率的生成モデルを用いて前記パラメータ群を更新する
請求項４記載のグラフ構造推定方法。
【請求項６】
前記パラメータ更新部が前記パラメータ群を更新するステップは、前記確率的生成モデルを用いて前記グラフを生成する際に、前記第１のパラメータとして前記頂点の共変量及び前記テーブルの共変量を用いた基準を用いて、前記パラメータ群を更新する
請求項５記載のグラフ構造推定方法。
【請求項７】
コンピュータを、請求項１〜３の何れか１項に記載のグラフ構造推定装置の各部として機能させるためのグラフ構造推定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフ構造推定装置、グラフ構造推定方法、及びグラフ構造推定プログラムに係り、特に、グラフデータを解析するグラフ構造推定装置、グラフ構造推定方法、及びグラフ構造推定プログラムである。
【背景技術】
【０００２】
グラフデータ（例えば、映画俳優の共演関係を表すネットワークのデータ、機械同士をつなぐ無線ネットワークのデータ等）を解析する技術として、非特許文献１には、グラフＧの頂点数Ｎに対して、「直径ｄが小さい」という性質（スモールワールド性と呼ばれる）を表現した確率モデルが開示されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Watts. D. J and Strogatz. S. H. Collective dynamics of ‘small-world' networks. Nature, 393:440-442, 1998.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記確率モデルでは、平均パス長(２頂点間の最短パスの平均長) がおよそｌｏｇＮのオーダになる、という問題がある。
【０００５】
本発明は、観測されるグラフデータを入力として、入力から推定される真のグラフ構造を出力する際に、上記従来技術が抱えていた以下の問題を解決することを目的とする。
【０００６】
例えば、機械同士をつなぐ無線ネットワークの構造は、一定の半径を持つ球上でのunit disk graph（下記参考文献１参照）によりモデル化することができる。
【０００７】
（参考文献１）  Clark. B. N., Colbourn. C. J., and Johnson. D. S. Unit disk graphs. Discrete Mathematics, 86:165-177, 1990.
【０００８】
つまり、或る頂点（機械）ｕは、その頂点ｕから一定の距離Ｌ以内にある頂点ｖとはつながり（辺を結ぶ）、それよりも遠いところにある頂点ｗとはつながらない（辺を結ばない）ものとみなすことができる。
【０００９】
ところで、地球を半径Ｒの球とみなすと、頂点（機械）が置かれる土地は地球の面積によって限られている。このことを考慮した上で、上記のようなunit disk graphによる無線ネットワークのモデル化を考えると、頂点数（機械の数）Ｎ→∞の極限をとっても、その直径（ある機械ｕから、直接つながっている機械を辿って別の機械ｖまでたどり着くために必要な、最小の辺の数の最大値。直感的には、グラフ上で最も離れている機械同士の距離のようなもの）は定数に漸近する。つまり、機械が無限個ある状況においては、最も離れた機械同士であってもある定数個の機械を辿ればつながることができるのである。このような直径のふるまいは、従来のグラフモデルでは説明できない。
【００１０】
実際に上記の無線ネットワークなどのグラフデータを解析する際には、頂点数（地球上に存在する機械の数）が非常に多いため、一部をサンプルした結果がデータセットとして提供されることが考えられる。また、そのようにして作られたデータセットから、計算量削減のために更に一部をサンプルして解析するという状況が考えられる。
【００１１】
従来のモデルでは、サンプル前後のグラフで直径の上限が保存されないため、例えば上記のような有限土地上の無線ネットワークのデータを少数のサンプルから解析しようとすると、直径という観点で不正確な推定結果が出力されてしまう。逆に言えば、直径の観点でできるだけ正しくグラフデータを解析したいと思った場合、できる限り多くの頂点を含むデータを用いる必要があり、これには高い計算コストがかかってしまう。
【００１２】
本発明の目的は、直径の上限が定数となるようなふるまいをするグラフデータを解析し、真のグラフ構造を推定することができるグラフ構造推定装置、グラフ構造推定方法、及びグラフ構造推定プログラムを得ることである。
【課題を解決するための手段】
【００１３】
上記目的を達成するために、本発明のグラフ構造推定装置は、観測されるグラフデータの隣接行列及び前記グラフデータで表されるグラフ上の距離の上限を表す自然数を入力する入力部と、前記グラフデータの隣接行列及び前記自然数に基づいて、前記グラフの頂点及び前記頂点に割り当てるテーブルに関する第１のパラメータ、前記テーブルの人気度に関する第２のパラメータ、及び、前記グラフデータと前記第１のパラメータと前記第２のパラメータとに基づく確率的生成モデルを用いて生成したサンプルグラフから得られた、前記頂点に割り当てるテーブルの分割を表現した行列を表す第３のパラメータ、を含むパラメータ群の初期値を生成する初期パラメータ生成部と、前記グラフデータの隣接行列、前記自然数、及び前記パラメータ群に基づいて、前記グラフデータの隣接行列に対する、前記第３のパラメータに対応する前記グラフの頂点の各々についての完全二部木から得られる隣接行列が尤もらしくなるように、前記確率的生成モデルを用いて生成されたグラフに基づいて前記パラメータ群を更新するパラメータ更新部と、前記パラメータ群の更新を終了するか否かを判定する終了判定部と、前記終了判定部により前記パラメータ群の更新を終了すると判定された場合に、前記パラメータ更新部により更新された前記第３のパラメータに対応する前記グラフの頂点の各々についての前記完全二部木から得られる隣接行列を出力する出力部と、を含む。
【００１４】
また、前記パラメータ更新部は、前記確率的生成モデルとして、前記グラフ上の距離の上限が前記自然数以下となるように前記グラフを生成する確率的生成モデルを用いて前記パラメータ群を更新する構成としてもよい。
【００１５】
また、前記パラメータ更新部は、前記確率的生成モデルを用いて前記グラフを生成する際に、前記第１のパラメータとして前記頂点の共変量及び前記テーブルの共変量を用いた基準を用いて、前記パラメータ群を更新する構成としてもよい。
【００１６】
本発明のグラフ構造推定方法は、入力部、初期パラメータ生成部、パラメータ更新部、終了判定部、及び出力部を含むグラフ構造推定装置におけるグラフ構造推定方法であって、前記入力部が、観測されるグラフデータの隣接行列及び前記グラフデータで表されるグラフ上の距離の上限を表す自然数を入力するステップと、前記初期パラメータ生成部が、前記グラフデータの隣接行列及び前記自然数に基づいて、前記グラフの頂点及び前記頂点に割り当てるテーブルに関する第１のパラメータ、前記テーブルの人気度に関する第２のパラメータ、及び、前記グラフデータと前記第１のパラメータと前記第２のパラメータとに基づく確率的生成モデルを用いて生成したサンプルグラフから得られた、前記頂点に割り当てるテーブルの分割を表現した行列を表す第３のパラメータ、を含むパラメータ群の初期値を生成するステップと、前記パラメータ更新部が、前記グラフデータの隣接行列、前記自然数、及び前記パラメータ群に基づいて、前記グラフデータの隣接行列に対する、前記第３のパラメータに対応する前記グラフの頂点の各々についての完全二部木から得られる隣接行列が尤もらしくなるように、前記確率的生成モデルを用いて生成されたグラフに基づいて前記パラメータ群を更新するステップと、前記終了判定部が、前記パラメータ群の更新を終了するか否かを判定するステップと、前記出力部が、前記終了判定部により前記パラメータ群の更新を終了すると判定された場合に、前記パラメータ更新部により更新された前記第３のパラメータに対応する前記グラフの頂点の各々についての前記完全二部木から得られる隣接行列を出力するステップと、を含む。
【００１７】
また、前記パラメータ更新部が前記パラメータ群を更新するステップは、前記確率的生成モデルとして、前記グラフ上の距離の上限が前記自然数以下となるように前記グラフを生成する確率的生成モデルを用いて前記パラメータ群を更新するようにしてもよい。
【００１８】
また、前記パラメータ更新部が前記パラメータ群を更新するステップは、前記確率的生成モデルを用いて前記グラフを生成する際に、前記第１のパラメータとして前記頂点の共変量及び前記テーブルの共変量を用いた基準を用いて、前記パラメータ群を更新するようにしてもよい。
【００１９】
本発明のグラフ構造推定プログラムは、コンピュータを、請求項１〜３の何れか１項に記載のグラフ構造推定装置の各部として機能させるためのグラフ構造推定プログラムである。
【発明の効果】
【００２０】
以上説明したように、本発明のグラフ構造推定装置、グラフ構造推定方法、及びグラフ構造推定プログラムによれば、真のグラフ構造を推定することができる、という効果が得られる。
【図面の簡単な説明】
【００２１】
【図１】グラフ構造推定装置の機能的な構成例を示すブロック図である。
【図２】グラフ構造推定処理ルーチンを示すフローチャートである。
【図３】完全二分木の一例を示す図である。
【図４】テーブル分割の行列表現の一例を示す図である。
【図５】基本的な乱択アルゴリズムの一例を示す図である。
【図６】乱択アルゴリズムのフローチャートの一例を示す図である。
【図７】テーブル分割の様子の一例を示す図である。
【図８】完全二分木が得られる様子の一例を示す図である。
【図９】乱択アルゴリズムの具体例を示す図である。
【図１０】乱択アルゴリズムの他の具体例を示す図である。
【発明を実施するための形態】
【００２２】
以下、図面を参照して、本発明の実施の形態を詳細に説明する。
【００２３】
＜本発明の実施の形態の概要＞
【００２４】
グラフデータを解析する場合、観測されるグラフデータの直径が、頂点数Ｎに関わらず定数Ｄの上限を持つという仮定のもと、真のグラフ構造を推定する技術である。
【００２５】
ここで、「グラフ」、「(グラフの) 直径」の定義については後述する。本実施形態は、直径が定数Ｄ以下の全てのグラフを解の候補として含むような、真のグラフ構造の探索を可能としたものであり、グラフデータ解析の手法の中でもノンパラメトリックベイズ推定の枠組みに基づくものである。
【００２６】
＜システム構成＞
【００２７】
図１に示すように、本実施の形態に係るグラフ構造推定装置１０は、入力部１２、初期パラメータ生成部１４、パラメータ更新部１６、終了判定部１８、及び出力部２０を備えている。
【００２８】
入力部１２は、観測されるグラフデータの隣接行列及びグラフデータで表されるグラフ上の距離の上限を表す自然数を入力する。ここで、入力部１２に入力されるグラフデータは、例えば一部のグラフが欠損している等、真のグラフ構造とは言えない不完全なグラフデータである。
【００２９】
初期パラメータ生成部１４は、入力部１２により入力された隣接行列及び自然数に基づいて、グラフの頂点及び頂点に割り当てるテーブルに関する第１のパラメータ、テーブルの人気度に関する第２のパラメータ、及び、グラフデータと第１のパラメータと第２のパラメータとに基づく確率的生成モデルを用いて生成したサンプルグラフから得られた、頂点に割り当てるテーブルの分割を表現した行列を表す第３のパラメータ、を含むパラメータ群の初期値を生成する。本実施形態では、詳細は後述するが、確率的生成モデルとして、定数直径制約に基づくモデルによる乱択法を用いてサンプルグラフを生成する。
【００３０】
パラメータ更新部１６は、グラフデータの隣接行列、自然数、及びパラメータ群に基づいて、グラフデータの隣接行列に対する、第３のパラメータに対応するグラフの頂点の各々についての完全二部木から得られる隣接行列が尤もらしくなるように、確率的生成モデルを用いて生成されたグラフに基づいて前記パラメータ群を更新する。
【００３１】
終了判定部１８は、パラメータ群の更新を終了するか否かを判定する。
【００３２】
出力部２０は、終了判定部１８によりパラメータ群の更新を終了すると判定された場合に、パラメータ更新部１６により更新された第３のパラメータに対応するグラフの頂点の各々についての完全二部木から得られる隣接行列を出力する。
【００３３】
グラフ構造推定装置１０は、例えばＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）と、後述するグラフ構造推定処理を実行するためのグラフ構造推定プログラムを記憶したＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）と、を備えたコンピュータを含んで実現される。なお、ＲＯＭに代えて不揮発性メモリを用いてもよい。また、グラフ構造推定装置１０を構成するコンピュータは、ハードディスクドライブ等の記憶部を備えていてもよい。また、ハードディスクドライブにＣＰＵが実行するプログラムが記憶されていてもよい。ＣＰＵがＲＯＭやハードディスク等の記憶部に記憶されているプログラムを読み出して実行することにより、上記のハードウェア資源とプログラムとが協働し、以下に説明する機能が実現される。
【００３４】
＜グラフ構造推定装置の作用＞
【００３５】
次に、グラフ構造推定装置１０の作用について説明する。まず、図２を参照して、本実施の形態に係るグラフ構造推定装置１０において実行されるグラフ構造推定処理の処理ルーチンについて説明する。
【００３６】
ステップＳ１００では、入力部１２が、観測されるグラフデータの隣接行列ＡＸ及び自然数Ｄを入力する。観測されるグラフデータを隣接行列の形式で表現したものを、観測されるグラフデータの隣接行列ＡＸと呼ぶ。ここで、グラフの定義について説明する。
【００３７】
グラフＧ＝（Ｖ、Ｅ）は、頂点の集合Ｖと、それらをつなぐ辺の集合Ｅで表されデータ構造である。例えば、機械同士の無線ネットワークを表すグラフにおいて、頂点は１つ１つの機械、辺は２つの機械の間の通信関係を表す。
【００３８】
本実施形態では、自己ループ（両端の頂点が等しい辺）や多重辺（ある２頂点間に複数の辺が存在する場合）を含まない単純グラフのみを扱う。
【００３９】
グラフＧ＝（Ｖ、Ｅ）の隣接行列
【数１】
2018077584.tif 000003
とは、全ての（ｉ，ｊ）の組み合わせに対し、（ｉ、ｊ）∈Ｅであれば、
【００４０】
【数２】
2018077584.tif 000004
、
【数３】
2018077584.tif 000005
であれば、
【数４】
2018077584.tif 000006
として要素を定義した行列である。
【００４１】
また、グラフＧ＝（Ｖ、Ｅ）において、或る頂点ｖ∈Ｖのｅｃｃｅｎｔｒｉｃｉｔｙをｅ（ｖ）で表し、ｅ（ｖ）＝ｍａｘｕ∈Ｖｄ（ｖ、ｕ）と定義する。ただし、ｄ（ｖ、ｕ）は頂点ｖと頂点ｕを結ぶ最短パスの長さとする。
【００４２】
グラフＧ＝（Ｖ、Ｅ）の直径は、下記（１）式で示すように、頂点集合Ｖにおけるｅｃｃｅｎｔｒｉｃｉｔｙの最大値として定義される。
【００４３】
ｅ（ｖ）＝ｍａｘv∈Ｖｅ（ｖ）    ・・・（１）
【００４４】
本実施形態では、入力部１２に対して、隣接行列ＡＸ及び自然数Ｄが入力として与えられる。ここで、隣接行列ＡＸと自然数Ｄは、以下の関係を満たす組み合わせであれば、任意に設定できる。
【００４５】
関係：入力データＡＸがＮ×Ｎの行列であるとき、すなわち、入力されたグラフデータにおける頂点数がＮであるとき、Ｄ≦Ｎ−１。
【００４６】
ステップＳ１０２では、初期パラメータ生成部１４が、入力部１２により入力された隣接行列ＡＸ及び自然数Ｄに基づいて、グラフデータで表されるグラフの頂点及び頂点に割り当てるテーブルに関する第１のパラメータ、テーブルの人気度に関する第２のパラメータ、及び、グラフデータと第１のパラメータと第２のパラメータとに基づく確率的生成モデルを用いて生成したサンプルグラフから得られた、頂点に割り当てるテーブルの分割を表現した行列を表す第３のパラメータ、を含むパラメータ群の初期値を生成する。
【００４７】
まず、正の実数α、自然数Ｋとして予め定めた任意の値を代入する。例えば、α＝０．０１、Ｋ＝１０００とすればよい。
【００４８】
また、正の実数の集合Ｍ＝｛Ｍｎ｝、ｎ＝１、・・・、Ｎと、Ｍ’＝｛Ｍｋ｝、ｋ＝１、・・・、Ｋとして、任意の値を与える。例えば、以下のように一様分布に従ってランダムに設定すればよい。
【００４９】
Ｍｎ、Ｍ’ｋ〜Ｕｎｉｆｏｒｍ（［１０、２０、・・・、３００］）
【００５０】
以降、Ｍｎ∈Ｍを頂点ｖｎの共変量、Ｍ’ｋ∈Ｍ’をテーブルｔｋの共変量と呼ぶ。テーブルｔｋは、そのテーブルを選択した頂点の集合である。なお、集合Ｍ、Ｍ’が第１のパラメータに相当する。
【００５１】
また、正の実数の集合Π＝｛πｋ｝、ｋ＝１、・・・、Ｋとして、任意の値を与える。例えば、以下のようにΓ分布に従ってランダムに設定すればよい。
【００５２】
πｋ〜Γ（１、α）
【００５３】
以降、πｋをテーブルｋの人気度と呼ぶ。なお、πｋは第２のパラメータに相当する。
【００５４】
また、サイズが（Ｎ−１）×（Ｄ−１）のＮ個の行列Ｔｎ、ｎ＝１、・・・、Ｎとして、それぞれ以下の条件１、２を満たす任意のものを与える。なお、行列Ｔｎは第３のパラメータに相当する。
【００５５】
条件１：Ｔｎから１列目の値だけ抜き出して作ったベクトルＴｎ:，1が、根の頂点以外の全ての頂点の番号を１つずつ並べたベクトルに対する置換で得られる。
【００５６】
条件２：Ｔｎから１列目を除いて作った行列Ｔｎ:，2:D+1が、以下の条件２−１〜２−３を満たす。
【００５７】
条件２−１：全ての要素が０若しくはＫ以下の自然数である。
【００５８】
条件２−２：或る（ｉ、ｊ）成分の値が０のとき、ｉ行目のｊ＋１列以降の要素の値が全て０である。
【００５９】
条件２−３：１列目（元の行列Ｔｎでの２列目にあたる）の要素の値が全て１以上である。
【００６０】
行列Ｔｎは、各頂点ｖｎを根とする１つの完全二部木に一意に変換可能な、テーブル分割の行列表現Ｔｎ＝｛Ｔｎi，j｝を表す。
【００６１】
ここで、完全二分木について説明する。
【００６２】
完全二部グラフＫｍ、ｎ＝（Ｖ、Ｅ）の定義は、以下の条件３を満たすグラフである。
【００６３】
条件３：
【数５】
2018077584.tif 000007
【００６４】
本実施形態では、完全二部木を、内部に完全二部グラフを含む木と類似したグラフとして定義する。グラフＧ＝（Ｖ、Ｅ）が完全二部木であることの正確な定義は以下の通りである。
【００６５】
完全二分木の定義：グラフの各頂点Ｕ∈νＴが、Ｖに含まれる頂点からなるクラスタを表すような、或る木Ｔ＝（νＴ、εＴ）が存在する。任意のｖ∈Ｖに対して、Ｕ∈νＴが存在し、ｖ∈Ｕを満たす。また、任意の異なるＵ，Ｗ∈νＴに対し、Ｕ∩Ｗ＝０を満たす。Ｔにおける根の頂点Ｕroot∈νＴはＶに含まれる１つの頂点を含むクラスタである。Ｔにおいて、親子関係を持つような任意の頂点対（Ｕ，Ｗ）に対し、クラスタＵとＷが完全二部グラフをなす。
【００６６】
ここで、木は完全二部木の特別な場合（内部に含む全ての完全二部グラフがＫ1,1である場合）に相当する。完全二部木の一例を図３に示す。
【００６７】
図４には、各頂点ｖｎを根とする１つの完全二部木に一意に変換可能な、テーブル分割の行列表現Ｔｎの一例を示した。図４に示す行列Ｔｎは、１列目（Ｔn:,1）が頂点の番号を表す。例えばＴni,1＝３であれば、行ｉは頂点ｖ３についての情報が格納されている。２列目以降は、１列目の番号の頂点が各深さｊ−１で選択したテーブル番号を表す。例えば、図４の３行目は、頂点ｖ５は深さ１でテーブルｔ５、深さ２でテーブルｔ３を選択したことを示している。初期値としては、例えば、確率的生成モデルとしての定数直径制約に基づくモデルからサンプルグラフを１つ生成し、その際に得られたＮ個のテーブル分割に対応するＴｎを与えればよい。なお、定数直径制約に基づくモデルについては後述する。
【００６８】
また、サイズがＮ×Ｋの行列Ｐselect＝｛Ｐselectn,k｝として、以下の条件４、５を満たす任意のものを与える。
【００６９】
条件４：全ての要素に、０以上１以下の実数が格納されている。
【００７０】
条件５：全ての行において，列方向の要素の和が１になっている。すなわち、全てのｎに対して次式を満たす。
【００７１】
【数６】
2018077584.tif 000008
【００７２】
Ｐselectの（ｎ、ｋ）成分は、テーブル分割において、頂点ｖｎがテーブルｔｋを選択する確率を表している。初期値としては、例えば、Π＝｛πｋ｝と
【数７】
2018077584.tif 000009
を用いて以下の条件６を満たすものを与えればよい。
【００７３】
条件６：各（ｎ、ｋ）成分について、
【数８】
2018077584.tif 000010
【００７４】
また、サイズがＮ×Ｋの行列Ｐremain＝｛Ｐremainn,k｝として、以下の条件７を満たす任意のものを与える。
【００７５】
条件７：全ての要素に、０以上１以下の実数が格納されている。
【００７６】
Ｐremainの（ｎ、ｋ）成分は、テーブル分割において、頂点ｖｎがテーブルｔｋを選択した条件のもとで、テーブルｔｋに留まる確率を表している。初期値としては、例えば、Ｌ（ｘ、ｙ）≡（ｘ−ｙ）２を用いて以下の条件８を満たすものを与えればよい。
【００７７】
条件８：各（ｎ、ｋ）成分について、Ｐremainn,k＝１／（Ｌ（Ｍｎ、Ｍ'ｋ）＋１.０１）
【００７８】
また、パラメータ更新の繰り返し回数の上限ＮＳとして、任意の自然数を設定する。
【００７９】
また、現在までのパラメータ更新の繰り返し回数ｎＳとして、初期値ｎＳ＝１を与える。
【００８０】
ここで、本実施形態における処理で用いる「定数直径制約に基づくモデル」について説明する。なお、定数直径制約に基づくモデルは、Ｔｎの初期値を設定する際に生成するサンプルグラフを生成する際に用いられると共に、後述するパラメータ更新部１６によるパラメータ更新の際にも用いられる。
【００８１】
パラメータ更新部１６は、ベイズ推論の枠組みを用いて、観測データと各パラメータの値から真のグラフ構造を推定すると共に、各パラメータの値の更新を行う。ベイズ推論の枠組みにおいては、一般に、事前分布と尤度関数の組み合わせにより対象をモデル化した後、このモデルに対し、観測データのフィッティングと呼ばれる操作を行うことで解析を行う。以下、定数直径制約に基づくモデルについて説明する。
【００８２】
本実施形態で用いる定数直径制約に基づくモデルは、以下の事前分布μＮと尤度関数ｆＮにより定義される。
【００８３】
＜事前分布＞
【００８４】
頂点数がＮであり、かつ直径がＤ以下のグラフ全体の集合をｇとする。事前分布μＮとしては、任意のＧ∈ｇに対して確率μＮ（Ｇ）＞０が計算でき、かつΣG∈gμＮ（Ｇ）＝１を満たすものであれば任意に設定できる。
【００８５】
＜尤度関数＞
【００８６】
尤度関数ｆＮは、真の構造として推定されたグラフＧ∈ｇと観測されたグラフデータＧＸから定義される。本実施形態では、Ｇの隣接行列Ａ＝｛Ａｉｊ｝、ＧＸの隣接行列ＡＸ＝｛ＡＸｉｊ｝ を用いて、以下のように二項分布を用いて尤度関数を定義する。
【００８７】
【数９】
2018077584.tif 000011
・・・（２）
【００８８】
ただしｐｉ，ｊをＡｉｊ≠ＡＸｉｊであればｐｉ，ｊ＝β、そうでなければｐｉ，ｊ＝１−βの値をとる変数とする。
【００８９】
＜定数直径制約に基づくモデルの実現例＞
【００９０】
上記で述べた事前分布μＮと尤度関数ｆＮから、定数直径制約に基づくモデルを構成する１つの実現例として、尤度関数を上記（２）式で定義し、事前分布をＡｌｇｏｒｉｔｈｍ１に基づいてサンプルグラフの生成を行うものと定義した場合のモデルについて説明する。
【００９１】
Ａｌｇｏｒｉｔｈｍ１は、頂点数がＮかつ直径がＤ以下の全てのグラフを０より大きい確率で生成する、確率的生成モデルの基本的な乱択アルゴリズムである。このアルゴリズムは、ステップＳ１０２の行列Ｔｎの初期値の設定において、或る確率分布Ｎに従い１つのグラフＧ∈ｇのサンプルを出力する乱択アルゴリズムに相当すると共に、後述するステップＳ１０４のパラメータの更新において、或るグラフＧ∈ｇを論理和として持つＮ個の完全二部木｛ＧＴｎ｝、ｎ＝１、・・・、Ｎが出力される確率を計算するためのアルゴリズムとしても使用される。
【００９２】
ここで、本実施形態における論理和について説明する。本実施形態では、Ｍ個のグラフＧ１＝（Ｖ１、Ｅ１）、・・・、ＧＭ＝（ＶＭ、ＥＭ）について、Ｇ１、・・・、ＧＭの論理和Ｇ∪＝（Ｖ∪、Ｅ∪）≡Ｇ１∪・・・∪ＧＭを、Ｖ∪＝Ｖ１∪、・・・、∪ＶＭ、Ｅ∪＝Ｅ１∪、・・・、∪ＥＭを満たすグラフとして定義する。
【００９３】
図５にはＡｌｇｏｒｉｔｈｍ１の概略を示し、図６にＡｌｇｏｒｉｔｈｍ１のフローチャートを示した。
【００９４】
図６に示すように、ループ１は、ｎrootを１ずつインクリメントし、１≦ｎroot≦Ｎを満たす場合にステップＳ２００〜Ｓ２１４の処理を繰り返し実行する。
【００９５】
ループ２は、ｄを１ずつインクリメントし、０≦ｄ≦Ｄ−１を満たす場合にステップＳ２０２〜Ｓ２１２の処理を繰り返し実行する。
【００９６】
ループ３は、ｋを１ずつインクリメントし、１≦ｋ≦Ｋｄを満たす場合にステップＳ２０２〜Ｓ２１０の処理を繰り返し実行する。
【００９７】
図６に示すように、ステップＳ２００では、各パラメータに初期値を設定する。ここでは、頂点ｖｎrootを根として持つ完全二分木ＧＴnrootを考える。初期値としてＧＴｎrootをＮ個の頂点の独立集合とする。また、Ｋ０を１、Ｖｔ０leaveを｛Ｖ＼ｖｎ｝、Ｖｔ０remainを｛ｖｎ｝とする。
【００９８】
ステップＳ２０２では、深さｄのテーブルｔｋにおいて、或る基準Ｚwidthに基づき、
【数１０】
2018077584.tif 000012
に含まれる各頂点についてテーブル分割を行う。
【００９９】
ステップＳ２０４では、深さｄのテーブルｔｋにおいて、或る基準Ｚdepthに基づき、テーブルｔｋの各子テーブルｔｌに含まれる各頂点ｖｎが、子テーブルｔｌに留まる
【数１１】
2018077584.tif 000013
か留まらない
【数１２】
2018077584.tif 000014
かを決定する。
【０１００】
ステップＳ２０６では、ＧＢを頂点集合
【数１３】
2018077584.tif 000015
と
【数１４】
2018077584.tif 000016
の間の完全二部グラフとする。また、
【数１５】
2018077584.tif 000017
として、
【数１６】
2018077584.tif 000018
を更新する。
【０１０１】
ステップＳ２０８では、
【数１７】
2018077584.tif 000019
が０であるか否かを判定し、肯定判定の場合はステップＳ２１０へ移行し、否定判定の場合はステップＳ２１２へ移行する。
【０１０２】
ステップＳ２１０では、
【数１８】
2018077584.tif 000020
とする。すなわち、空テーブルを無視する。
【０１０３】
ステップＳ２１２では、Ｋｄを、深さｄに存在する全テーブルについての子テーブル数の和として更新する。
【０１０４】
ステップＳ２１４では、
【数１９】
2018077584.tif 000021
として、グラフＧを更新する。
【０１０５】
ステップＳ２１６では、更新されたグラフＧを出力する。このグラフＧは、頂点数がＮで且つ直径がＤ以下のグラフとなっている。
【０１０６】
すなわち、図５、６に示されるように、Ａｌｇｏｒｉｔｈｍ１は、初期状態として根となる頂点を除く全ての頂点が深さｄ＝０の１つのテーブルに存在する状態から開始する。深さｄにおいて、各頂点は、まず予め定められた基準Ｚwidthに基づいて１つのテーブルに割り当てられる。
【０１０７】
次に、予め定めた基準Ｚdepthに基づき、各テーブルに割り当てられた頂点が現在の（深さｄの）テーブルに留まるか否かを決定する。
【０１０８】
現在のテーブルに留まらない場合は、頂点は現在のテーブルの子テーブル（深さｄ＋１）へと再び分割される。
【０１０９】
このようなテーブルの分割と、現在のテーブルに留まるか否かの判定を、或る深さのテーブルに各頂点が留まることが決定するまで繰り返す。ただし、この繰り返し処理は、深さｄ＝Ｄ−１で打ち切る。このような分割結果から、各頂点を根とした深さがＤ以下の完全二部木がそれぞれ１つずつ生成される。具体的には、親子関係にある全てのテーブルの組｛ｔparent、ｔchild｝の間に完全二部グラフを生成する。
【０１１０】
図７には、頂点ｖｊ（ｊ＝１、・・・、Ｎ）に対するテーブル分割の決定の一例を示した。
【０１１１】
図７の状態２０に示す例は、頂点ｖｉを根として持つ完全二部木において、頂点ｖｊが、（１）深さ１においてはテーブルｔ２を選択して離れ、（２）深さ２においてはテーブルｔ５を選択して離れ、（３）深さ３においては（新たに生成した）テーブルｔ８を選択し、そこに留まる、という一連の動きをすることが決定され、その結果、頂点ｖｊの割り当てられるテーブルが決定された様子を表している。なお、図７において、「○」は、そのテーブルを選択し、かつ、そのテーブルに留まった頂点を示す。例えば、状態２０において、テーブルｔ１については、選択した頂点が２個あることを示しており、テーブルｔ２については、選択した頂点が無いことを示している。
【０１１２】
ここで、図８に示すように、頂点が１つも含まれないテーブルｔ０が存在した場合（状態３０）、空テーブルであるテーブルｔ０を無視し、テーブルｔ０の子孫にあたるテーブルｔ０１を繰り上げ（状態３２）、テーブルｔ０の親テーブルとの間に完全二部グラフを生成する（状態３４）。
【０１１３】
次に、Ａｌｇｏｒｉｔｈｍ１の処理によって生成されたＮ個の完全二部木の論理和を取ることにより、目的のグラフを生成し、出力する。
【０１１４】
以下に、基準Ｚwidth、Ｚdepthの組｛Ｚwidth、Ｚdepth｝として用いることができる１つの例を説明する。
【０１１５】
基準｛Ｚwidth、Ｚdepth｝としては、以下に示す組み合わせ以外にも、全体のテーブル分割アルゴリズムが射影性を満たしているものであれば何でもよい（Ｋｏｌｍｏｇｏｒｏｖの定理）。
【０１１６】
以下では、基準｛Ｚwidth、Ｚdepth｝を定義するための指標として、下記参考文献２に記載された既存技術であるＤＩＬＮ（ｄｉｓｃｒｅｔｅ  ｉｎｆｉｎｉｔｅ  ｌｏｇｉｓｔｉｃ  ｎｏｒｍａｌ  ｄｉｓｔｒｉｂｕｔｉｏｎ）で提案された共変量と呼ばれるパラメータを用いる方法について説明する。
【０１１７】
（参考文献２）  Paisley. J, Wang. C, and Blei. D. The discrete infinite logistic normal distribution for mixed-membership modeling. In Proc. of International Conference on Artificial Intelligence and Statistics, 2011.
【０１１８】
この方法では、全ての頂点、全てのテーブルに対してそれぞれ共変量をランダムに与え、それらの集合をそれぞれＭ＝｛Ｍｎ｝、Ｍ'＝｛Ｍ’ｋ｝とする（例えば、Ｍｎ、Ｍ’Ｋ〜  Ｕｎｉｆｏｒｍ（［１０、２０、・・・、３００］）、ｎ＝１、・・・、Ｎ、ｋ＝１、・・・、Ｋとすればよい）。Ｋは本来無限であり、実装上は十分大きい自然数を与える。また、全てのテーブルの人気度をランダムに与え、その集合をΠ＝｛πｋ｝とする（例えば、πｋ〜Γ（１、α）とすればよい。
【０１１９】
Ｚwidthとしては、共変量の値に基づく分割手法を用いる。具体的には、各頂点は、深さｄで割り当てられたテーブルの子テーブル｛ｔｌ｝として１つのテーブルを選ぶ。ここで、頂点ｖｎがテーブルｔｋを選ぶ確率は、Ｐselectn,k≡Ｌ’（Ｍｎ、Ｍ’ｋ）πｋ／ΣｍＬ’（Ｍｎ、Ｍ’ｍ）πｍとする。ただし、Ｌ’（ｘ、ｙ）は任意の距離関数Ｌ（ｘ、ｙ）、例えばＬ（ｘ、ｙ）＝（ｘ−ｙ）２の値に対して単調減少な任意の関数、例えばＬ’（ｘ、ｙ）＝１／（Ｌ（ｘ、ｙ）＋１））とする。
【０１２０】
Ｚdepthに関しても、共変量の値に基づく基準を用いる。具体的には、頂点ｖｎがテーブルｔｋに留まる確率Ｐremainn,kは、Ｌ（Ｍｎ、Ｍ’ｋ）に対して単調減少するように与えるものとする。例えば、Ｐremainn,k＝１／（Ｌ（Ｍｎ、Ｍ’ｋ）＋  １．０１）とすればよい。ｖｎがテーブルｔｋを離れる場合、ｖｎは深さｄ＋１において基準Ｚwidthに基づき子テーブルへと分割される。
【０１２１】
上記の基準に基づいてサンプルグラフを生成する具体的なＡｌｇｏｒｉｔｈｍ２を図９ に示した。以下では、図５に示すＡｌｇｏｒｉｔｈｍ１で具体的な処理を説明していなかった部分について説明し、図５に示すＡｌｇｏｒｉｔｈｍ１で既に説明した部分については説明を省略する。
【０１２２】
図９に示すように、Ａｌｇｏｒｉｔｈｍ２では、Ｍ＝｛Ｍｎ｝、Ｍ'＝｛Ｍ’ｋ｝、Π＝｛πｋ｝をランダムな正の実数値として与える。
【０１２３】
また、
【数２０】
2018077584.tif 000022
に含まれる各頂点についてテーブル分割する際に、以下の基準に基づいてテーブル分割する。
【０１２４】
頂点ｖｎは、テーブルｔｌを確率
【数２１】
2018077584.tif 000023
で選択する。
【０１２５】
また、テーブルｔｋの各子テーブルｔｌに含まれる各頂点ｖｎが、子テーブルｔｌに留まる
【数２２】
2018077584.tif 000024
か留まらない
【数２３】
2018077584.tif 000025
かを決定する際に、以下の基準に基づいて決定する。
【０１２６】
基準：Ｌ（Ｍｎ、Ｍ’ｌ）（Ｌは距離関数）の値から定義される確率Ｐremainn,ｌで留まり、確率（１−Ｐremainn,ｌ）で留まらない。
【０１２７】
その他の処理は図５に示すＡｌｇｏｒｉｔｈｍ１と同様であるので、説明は省略する。
ステップＳ１０２では、初期パラメータ生成部１４が、行列Ｔｎの初期値を設定する際に、Ａｌｇｏｒｉｔｈｍ２の処理を実行してサンプルグラフを１つ生成し、その際に得られたＮ個のテーブル分割に対応するＴｎを与える。
【０１２８】
ステップＳ１０４では、パラメータ更新部１６がパラメータ群を更新する。
【０１２９】
まず、パラメータＭ、Ｍ’の更新について説明する。まず、パラメータＭ、Ｍ’の事前分布を予め定めておく。パラメータＭ、Ｍ’の事前分布は任意に定めることができる。例えば、下記（３）式のように設定することができる。
【０１３０】
Ｍｎ、Ｍｋ〜Ｕｎｉｆｏｒｍ（［１０、２０、・・・、３００］）  ・・・（３）
【０１３１】
上記（３）式の設定を用いた場合、Ｇｉｂｂｓ  ｓａｍｐｌｉｎｇによりパラメータＭ、Ｍ’を更新することができる。すなわち、パラメータが［１０、２０、・・・、３００］の各値をとる場合における条件付き事後確率を計算し、求めた条件付き事後確率に基づいてその更新値を選択する。
【０１３２】
次に、パラメータΠの更新について説明する。既存技術であるｓｔｏｃｈａｓｔｉｃ  ｇｒａｄｉｅｎｔ  Ｌａｎｇｅｖｉｎ  ｄｙｎａｍｉｃｓ（ＳＧＬＤ）（下記参考文献３参照）を用いて、マルコフ連鎖モンテカルロ法（ＭＣＭＣ）でパラメータΠの更新を行う。
【０１３３】
（参考文献３）
【０１３４】
Welling. M and Teh. Y. W. Bayesian learning via stochastic gradient Langevin dynamics. In International Conference on Machine Learning, 2011.
【０１３５】
ｎＳ回目のパラメータ更新において、下記（４）式に従いθｎｓ∈Πの値を更新する。
【０１３６】
【数２４】
2018077584.tif 000026
2018077584.tif 000027
2018077584.tif 000028
・・・（４）
【０１３７】
ここで、パラメータΠの事前分布を予め定めておく。パラメータΠの事前分布は、任意に定めることができる。例えば、下記（５）式のように設定することができる。
【０１３８】
πｋ〜Γ（１、α）      ・・・（５）
【０１３９】
上記（５）式の設定を用いた場合、∇ｌｏｇｐ（θｎｓ）は以下のように計算される。
【０１４０】
∇ｌｏｇｐ（θｎＳ）＝−１／α
【０１４１】
また、
【数２５】
2018077584.tif 000029
とおくと、ｌｏｇｐ（Ｔ｜θｎｓ）は以下のように計算できる。
【０１４２】
【数２６】
2018077584.tif 000030
【０１４３】
上記（５）式の設定を用いた場合、
【数２７】
2018077584.tif 000031
とおき、「ｘ＝ｙであれば１を、ｘ≠ｙであれば０を返す関数」をＦ（ｘ、ｙ）とおくと、ｌｏｇｐ（Ｔ｜θｎｓ）は具体的に下記（６）式から計算できる。
【０１４４】
【数２８】
2018077584.tif 000032
・・・（６）
【０１４５】
本実施形態では、前述したように、全てのパラメータθｎｓ∈｛Ｍ、Ｍ’、Π｝について１回ずつ更新を行う。１つのパラメータが更新されるごとに、ｎＳ←ｎＳ＋１とし、θｎｓを別のパラメータとする。例えばθｎｓ＝Ｍ１としてθｎｓを更新し、ｎＳ←ｎＳ＋１、θｎｓ＝Ｍ２としてθｎｓを更新し、ｎＳ←ｎＳ＋１、・・・、θｎｓ＝πｋとしてθｎｓを更新し、ｎＳ←ｎＳ＋１とする。
【０１４６】
次に、テーブルＴｎを更新する。ランダムに選ばれたある頂点ｖｎを根とする完全二部木ＧＴｎに、一意に変換可能なテーブルＴｎの更新を行う。これは、頂点ｖｎ以外の各頂点ｖｉについて一度ずつ、割り当て先テーブルの更新を行うことで実現できる。頂点ｖｉ≠ｖｎの新しい割り当て先テーブルの候補は、例えば以下のように定めることができる。
【０１４７】
（１）頂点ｖｉが深さ１にあるとき、下記（１−１）又は（１−２）のテーブルを割り当て先テーブルの候補とする。
（１−１）深さ１にあるテーブル全て（現在のテーブルも含む）。
（１−２）現在のテーブルの子テーブル（既存のテーブル全て及び新しいテーブル）。
（２）頂点ｖｉが深さ２からＤ−１にあるとき、下記（２−１）〜（２−３）の何れかのテーブルを割り当て先テーブルの候補とする。
（２−１）現在のテーブルの親テーブル。
（２−１）現在のテーブルの子テーブル（既存のテーブル全て及び新しいテーブル）。
（２−３）現在のテーブル。
（３）頂点ｖｉが深さＤにあるとき、下記（３−１）又は（３−２）のテーブルを割り当て先テーブルの候補とする。
（３−１）現在のテーブルの親テーブル。
（３−２）現在のテーブル。
【０１４８】
上記の候補のテーブルの中から、１つのテーブルを選択する。各候補のテーブルは、その候補のテーブルに頂点ｖｉを割り当てた場合における条件付き事後確率Ｐposteriorに基づいて選択されるものとする。ここで、条件付き事後確率Ｐposteriorは下記（６）式に従って計算される値である。（６）式において、隣接行列Ａは行列ＴからＡｌｇｏｒｉｇｈｍ２に従い一意に決定される目的のグラフＧの隣接行列であり、尤度関数ｐ（ＡＸ｜Ａ）は、上記（１）式で定義するものとする。従って、ステップＳ１０４では、パラメータ更新部１６が、上記（１）〜（３）で説明した新しい割り当て先テーブルの各候補について、その候補のテーブルに頂点ｖｉを割り当てた場合に相当する行列Ｔから一意に決定されるグラフＧの隣接行列Ａを生成する。そして、生成した隣接行列ＡとＡｌｇｏｒｉｇｈｍ２に基づくテーブル分割の確率計算方法を用いて、下記（７）式により条件付き事後確率Ｐposteriorを算出する。
【０１４９】
【数２９】
2018077584.tif 000033
・・・（７） 
【０１５０】
そして、前述したルールに従って根ｖｎを除く全ての頂点のテーブルＴ１〜Ｔｎを更新する。次に、更新した全ての頂点のテーブルＴ１〜Ｔｎに対応した完全二分木Ｇ１〜Ｇｎの論理和を、前述した論理和の定義に従って求めてグラフＧを生成し、生成したグラフＧから隣接行列Ａを生成することで隣接行列Ａを更新する。
【０１５１】
図２のステップＳ１０６では、終了判定部１８が、パラメータ群の更新を終了するか否かを判定する。すなわち、パラメータの更新回数がｎＳ＜ＮＳか否かを判定し、肯定判定の場合は、ステップＳ１０７でｎＳ←ｎＳ＋１とし、ステップＳ１０４へ移行する。一方、否定判定の場合、すなわちｎＳ＝ＮＳの場合は、ステップＳ１０８へ移行する。
【０１５２】
ステップＳ１０８では、出力部２０が、ステップＳ１０４の処理で更新された隣接行列Ａ、すなわち、推定された真のグラフ構造の隣接行列Ａを出力し、処理を終了する。
【０１５３】
このように、本実施形態では、与えられた上限Ｄ以下の直径を持つ任意のグラフを含むような探索を行うために、Ｎ個の完全二部木の組み合わせとして真のグラフ構造を推定し、各完全二部木の生成過程では、各頂点に対し、射影性を満たすようなテーブル分割アルゴリズムを適用した結果として表現し、事前確率の計算処理を行う。
【０１５４】
これにより、直径の上限が定数となるようなふるまいをするグラフデータに対し、直径という観点において正確な真のグラフ構造の推定結果を得ることができる。
【０１５５】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１５６】
以下では、前述したＡｌｇｏｒｉｔｈｍ１の基準Ｚwidth、Ｚdepthの組｛Ｚwidth、Ｚdepth｝として、上記で説明した共変量に基づく基準以外の例（中華料理店過程に基づく基準）について説明する。この実現例では、既存技術の中華料理店過程（参考文献４参照）を用いる。
【０１５７】
（参考文献４）
【０１５８】
Aldous. D. J. Exchangeability and related topics. Ecole d'Ete Probabilites Saint-Flour XIII 1983, 1985.
【０１５９】
初期パラメータ生成部１４では、ｎroot＝１、・・・、Ｎについて、正の実数の集合
【数３０】
2018077584.tif 000034
2018077584.tif 000035
・・・（８）
として、任意の値を与える。例えば、以下のようにランダムに設定すればよい。
【０１６０】
【数３１】
2018077584.tif 000036
【０１６１】
以降、Ｃｎ∈Ｃを頂点ｖｎのカロリーと呼ぶ。
【０１６２】
Ｚwidthとしては、中華料理店過程に基づく分割手法を用いる。具体的には、各頂点は、深さｄで割り当てられたテーブルの子テーブル｛ｔｌ｝として１つのテーブルを選ぶ。ここで、頂点ｖｎが既存のテーブルｔｌを選ぶ確率は、既にｔｌを選択した頂点数に比例するとし、新しいテーブルを選ぶ確率は入力パラメータに比例するとする。ただし、各テーブルが選ばれる確率を全て足し合わせると１になるように正規化する。ここで、選ばれたテーブルｔｋが新しいテーブルである場合、正の実数Ｃ’ｋとして、任意の値を与える。例えば、以下のようにランダムに設定すればよい。
【０１６３】
Ｃ’ｋ〜Γ（１、１）。
【０１６４】
以降、Ｃ’ｋをテーブルｔｋのカロリーと呼ぶ。
【０１６５】
Ｚdepthとしては、頂点ｖｎのカロリーＣｎと、ｖｎが割り当てられたテーブルｔｋのカロリーＣ’ｋの大小関係に基づくとする。具体的には、Ｃｎ≦Ｃ’ｋならば、ｖｎはテーブルｔｋ  に留まり、そうでなければテーブルｔｋを離れる。ｖｎがテーブルｔｋを離れる場合、ｖｎ  は深さｄ＋１において基準Ｚwidthに基づき子テーブルへと分割される。
【０１６６】
上記の基準に基づいてサンプルグラフを生成する具体的なＡｌｇｏｒｉｔｈｍ３を図１０に示した。以下では、図５に示すＡｌｇｏｒｉｔｈｍ１で具体的な処理を説明していなかった部分について説明し、図５に示すＡｌｇｏｒｉｔｈｍ１で既に説明した部分については説明を省略する。
【０１６７】
図１０に示すように、Ａｌｇｏｒｉｔｈｍ３では、ｎroot＝１、・・・、Ｎについて、上記（８）式のようにランダムな実数値として与える。
【０１６８】
また、中華料理店過程に基づき、
【数３２】
2018077584.tif 000037
に含まれる各頂点についてテーブル分割する際に、頂点ｖｎが新しいテーブルｔｌに割り当てられたとき、Ｃ’ｌをランダムな実数値として与えること、また、以下の基準に基づいて、テーブルｔｋの各子テーブルｔｌに含まれる各頂点ｖｎが、子テーブルｔｌに留まる
【数３３】
2018077584.tif 000038
か留まらない
【数３４】
2018077584.tif 000039
かを決定する。
【０１６９】
基準：（Ｃｎ≦Ｃ’ｌ）∪（ｄ＝Ｄ）が真ならば留まり、偽ならば留まらない。
【０１７０】
その他の処理は図５に示すＡｌｇｏｒｉｔｈｍ１と同様であるので、説明は省略する。
【０１７１】
なお、本実施形態では、グラフデータが表すネットワークとして、有限の面積を持つ土地の上での無線ネットワークのふるまいを例として説明したが、他のネットワーク（例えば、人間関係のネットワーク等）であっても、上記の無線ネットワークと同様な直径のふるまいをするものと仮定すれば、本発明を適用することができる。
【０１７２】
また、上述のグラフ構造推定装置１０は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【０１７３】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体、例えばＣＤ−ＲＯＭやメモリーカード等に格納して提供することも可能である。
【符号の説明】
【０１７４】
１０  グラフ構造推定装置
１２  入力部
１４  初期パラメータ生成部
１６  パラメータ更新部１６
１８  終了判定部１８
２０  出力部
【図１】
2018077584.tif 000040
【図２】
2018077584.tif 000041
【図３】
2018077584.tif 000042
【図４】
2018077584.tif 000043
【図５】
2018077584.tif 000044
【図６】
2018077584.tif 000045
【図７】
2018077584.tif 000046
【図８】
2018077584.tif 000047
【図９】
2018077584.tif 000048
【図１０】
2018077584.tif 000049