(57)【要約】【課題】潜在的なコミュニティ内での偏ったリンク構造を模擬したテストデータを生成すること。【解決手段】クラスタ生成部１１は、識別情報が付与された複数のノードから構成されるノード群を総ノード数及びクラスタ規模数で決定されるクラスタ数に無作為に分割することで、複数のクラスタを生成する。グラフデータ生成部１２は、各クラスタを構成するノード間のリンク状態を示すリンク属性情報を、当該ノード間に対して生成された乱数及び閾値を用いて設定することで、複数のクラスタそれぞれのグラフデータを生成する。テストデータ生成部１３は、クラスタ生成処理及びグラフデータ生成処理を多重帰属可能数繰り返すように制御することでグラフデータ生成部１２により生成された全てのグラフデータを識別情報に基づいて統合することで、ノード群を構成する各ノード間のリンク状態を模擬したテストデータを生成する。【選択図】図１
2012064136.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータが、
識別情報がそれぞれ付与された複数のノードから構成されるノード群を、当該ノード群の総ノード数及び所定のクラスタ規模数で決定されるクラスタ数に無作為に分割することで、複数のクラスタを生成するクラスタ生成ステップと、
前記クラスタ生成ステップにより生成された各クラスタを構成するノード間のリンク状態を示すリンク属性情報を、当該ノード間に対して生成された乱数及び所定の閾値を用いて設定することで、前記複数のクラスタそれぞれにおけるリンク構造を示すグラフデータを生成するグラフデータ生成ステップと、
前記クラスタ生成ステップによるクラスタ生成処理及び前記グラフデータ生成ステップによるグラフデータ生成処理を所定の回数繰り返すように制御することで、前記グラフデータ生成ステップにより生成された全てのグラフデータを、各ノードに付与された識別情報に基づいて統合することで、前記ノード群を構成する各ノード間のリンク状態を模擬したテストデータを生成するテストデータ生成ステップと、
を含んだことを特徴とするテストデータ生成方法。
【請求項２】
前記グラフデータ生成ステップは、前記リンク属性情報として、ノード間のリンクの有無、又は、ノード間の関係強度を示す重み付けを設定し、
前記テストデータ生成ステップは、前記リンク属性情報がノード間のリンクの有無である場合、前記グラフデータ生成ステップが生成した全てのグラフデータの論理和をとることで前記テストデータを生成し、前記リンク属性情報がノード間の関係強度を示す重み付けである場合、前記グラフデータ生成ステップが生成した全てのグラフデータの算術和をとることで前記テストデータを生成することを特徴とする請求項１に記載のテストデータ生成方法。
【請求項３】
前記クラスタ生成ステップは、第１のクラスタ生成方法として、前記複数のノードの中でクラスタとして未抽出のノード群から無作為に前記所定のクラスタ規模数のノードを抽出することでクラスタを順次生成し、さらに、クラスタとして未抽出のノード群のノード数が前記所定のクラスタ規模数より少なくなった場合、当該クラスタとして未抽出のノード群を生成済みの各クラスタに無作為に割り振ることで、前記ノード群の総ノード数を前記所定のクラスタ規模数で除算した値以下で最大となる整数個のクラスタを生成することを特徴とする請求項１又は２に記載のテストデータ生成方法。
【請求項４】
前記クラスタ生成ステップは、第２のクラスタ生成方法として、前記複数のノードの中でクラスタとして未抽出のノード群から無作為に前記所定のクラスタ規模数のノードを抽出することでクラスタを順次生成し、さらに、クラスタとして未抽出のノード群のノード数が前記所定のクラスタ規模数より少なくなった場合、当該クラスタとして未抽出のノード群を新たなクラスタとして生成することで、前記ノード群の総ノード数を前記所定のクラスタ規模数で除算した値以上で最小となる整数個のクラスタを生成することを特徴とする請求項１又は２に記載のテストデータ生成方法。
【請求項５】
前記テストデータ生成ステップは、前記クラスタ生成ステップによるクラスタ生成処理及び前記グラフデータ生成ステップによるグラフデータ生成処理が前記所定の回数実行されるごとに、前記所定のクラスタ規模数及び前記所定の閾値の少なくともいずれか一方を変化させることを特徴とする請求項１〜４にいずれか一つに記載のテストデータ生成方法。
【請求項６】
識別情報がそれぞれ付与された複数のノードから構成されるノード群を、当該ノード群の総ノード数及び所定のクラスタ規模数で決定されるクラスタ数に無作為に分割することで、複数のクラスタを生成するクラスタ生成手段と、
前記クラスタ生成手段により生成された各クラスタを構成するノード間のリンク状態を示すリンク属性情報を、当該ノード間に対して生成された乱数及び所定の閾値を用いて設定することで、前記複数のクラスタそれぞれにおけるリンク構造を示すグラフデータを生成するグラフデータ生成手段と、
前記クラスタ生成手段によるクラスタ生成処理及び前記グラフデータ生成手段によるグラフデータ生成処理を所定の回数繰り返すように制御することで、前記グラフデータ生成手段により生成された全てのグラフデータを、各ノードに付与された識別情報に基づいて統合することで、前記ノード群を構成する各ノード間のリンク状態を模擬したテストデータを生成するテストデータ生成手段と、
を備えたことを特徴とするテストデータ生成装置。
【請求項７】
請求項１〜５のいずれか一つに記載のテストデータ生成方法をコンピュータに実行させることを特徴とするテストデータ生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、テストデータ生成方法、テストデータ生成装置及びテストデータ生成プログラムに関する。
【背景技術】
【０００２】
従来、外部入力が存在する情報処理に用いるアルゴリズムの妥当性を判定することが行なわれている。ここで、外部入力が実データとして容易に取得できる場合、当該実データは、アルゴリズムの妥当性をテストするためのデータとして使用することができる。例えば、収集可能な実データとして、ＳＮＳ（Social Networking Service）内におけるユーザー間のリンク構造を分析するためのグラフデータを生成することが行なわれている。
【０００３】
一方、実データが容易に収集できない場合、アルゴリズムの妥当性を判定するためには、外部入力を擬似したテストデータが必要となる。通信網を分析対象とするアルゴリズムにおいて実データをテスト用に収集することは、分析対象が大規模であり、また、実データを逐次収集する際に収集中の実データの状態が実時間で変化してしまう場合があることから、困難である。すなわち、通信網を分析対象とするアルゴリズムの妥当性を判定するためには、テストデータを生成することが必要となる。
【０００４】
このため、電話網の出現以来、交換機などの試験では、電話網の制御アルゴリズムを検証するために、外部入力を擬似したテストデータを生成する装置が使用されてきた。電話のように通信経路が物理的回線と対応付けられ、かつ、回線の接続構造が地理的条件から自明ならば、テストデータは、比較的容易に生成することができる。すなわち、グラフ構造を容易に取得することができるので、テストデータは、例えば、乱数で通信密度を決定することで容易に生成することができる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００８−０５２４９５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ところで、現在のインターネットサービスにおける接続の概念は、物理的な機器間でないＷｅｂページ間のリンクにも存在する。また、全てのＷｅｂページ間は、リンクさえ記述すれば直接遷移が可能である。従って、インターネットサービスにおいては、電話網のように、地理的条件などに基づく自明な接続構造の抽出が困難であった。
【０００７】
また、全てのＷｅｂページ間は、同確率でランダムにリンクされるわけではなく、潜在する縁故などによって偏ったリンクが張られている。さらに、検索エンジンなどでは、潜在的なコミュニティ内での偏ったリンクによる関係性を利用したアルゴリズムの需要がある。検索アルゴリズムなどの動作検証では、テストデータが潜在的なコミュニティ内での偏ったリンク構造を模擬していないと、検証の妥当性が不確かになる。
【０００８】
しかし、上記した従来の技術は、回線の接続構造が取得できることを前提としているので、Ｗｅｂページ間のリンクのように、潜在的なコミュニティ内での偏ったリンク構造を模擬したテストデータを生成することができなかった。
【０００９】
そこで、この発明は、上述した従来技術の課題を解決するためになされたものであり、潜在的なコミュニティ内での偏ったリンク構造を模擬したテストデータを生成することが可能となるテストデータ生成方法、テストデータ生成装置及びテストデータ生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述した課題を解決し、目的を達成するために、本願の開示するテストデータ生成方法は、コンピュータが、識別情報がそれぞれ付与された複数のノードから構成されるノード群を、当該ノード群の総ノード数及び所定のクラスタ規模数で決定されるクラスタ数に無作為に分割することで、複数のクラスタを生成するクラスタ生成ステップと、前記クラスタ生成ステップにより生成された各クラスタを構成するノード間のリンク状態を示すリンク属性情報を、当該ノード間に対して生成された乱数及び所定の閾値を用いて設定することで、前記複数のクラスタそれぞれにおけるリンク構造を示すグラフデータを生成するグラフデータ生成ステップと、前記クラスタ生成ステップによるクラスタ生成処理及び前記グラフデータ生成ステップによるグラフデータ生成処理を所定の回数繰り返すように制御することで、前記グラフデータ生成ステップにより生成された全てのグラフデータを、各ノードに付与された識別情報に基づいて統合することで、前記ノード群を構成する各ノード間のリンク状態を模擬したテストデータを生成するテストデータ生成ステップと、を含んだことを特徴とする。
【００１１】
また、本願の開示するテストデータ生成装置は、識別情報がそれぞれ付与された複数のノードから構成されるノード群を、当該ノード群の総ノード数及び所定のクラスタ規模数で決定されるクラスタ数に無作為に分割することで、複数のクラスタを生成するクラスタ生成手段と、前記クラスタ生成手段により生成された各クラスタを構成するノード間のリンク状態を示すリンク属性情報を、当該ノード間に対して生成された乱数及び所定の閾値を用いて設定することで、前記複数のクラスタそれぞれにおけるリンク構造を示すグラフデータを生成するグラフデータ生成手段と、前記クラスタ生成手段によるクラスタ生成処理及び前記グラフデータ生成手段によるグラフデータ生成処理を所定の回数繰り返すように制御することで、前記グラフデータ生成手段により生成された全てのグラフデータを、各ノードに付与された識別情報に基づいて統合することで、前記ノード群を構成する各ノード間のリンク状態を模擬したテストデータを生成するテストデータ生成手段と、を備えたことを特徴とする。
【００１２】
また、本願の開示するテストデータ生成プログラムは、上記のテストデータ生成方法をコンピュータに実行させることを特徴とする。
【発明の効果】
【００１３】
本願の開示するテストデータ生成方法、テストデータ生成装置及びテストデータ生成プログラムによれば、潜在的なコミュニティ内での偏ったリンク構造を模擬したテストデータを生成することが可能となる。
【図面の簡単な説明】
【００１４】
【図１】図１は、実施例１に係るテストデータ生成装置の構成を説明するための図である。
【図２】図２は、実施例１に係るテストデータ生成装置が実行する処理の概要を説明するための図である。
【図３】図３は、実施例２に係るテストデータ生成装置の構成を説明するための図である。
【図４】図４は、図３に示す設定リストを説明するための図である。
【図５】図５は、図３に示すノードリストを説明するための図である。
【図６】図６は、図３に示すテストデータのデータ形式を説明するための図である。
【図７】図７は、実施例２に係るクラスタ生成部が実行する第１のクラスタ生成方法を説明するためのフローチャートである。
【図８】図８は、実施例２に係るクラスタ生成部が実行する第２のクラスタ生成方法を説明するためのフローチャートである。
【図９】図９は、実施例２に係るグラフデータ生成部の処理を説明するためのフローチャートである。
【図１０】図１０は、実施例２に係るテストデータ生成装置の処理を説明するためのフローチャートである。
【図１１】図１１は、従来のテストデータを説明するための図である。
【図１２】図１２は、実施例２で生成されるテストデータを説明するための図である。
【図１３】図１３は、実施例１に係るテストデータ生成プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１５】
以下、本願の開示するテストデータ生成方法、テストデータ生成装置及びテストデータ生成プログラムの実施例を詳細に説明する。以下では、本願の開示するテストデータ生成方法を実行するテストデータ生成装置を実施例として説明する。なお、以下の実施例により本発明が限定されるものではない。
【実施例１】
【００１６】
図１及び図２を用いて、実施例１に係るテストデータ生成装置について説明する。図１は、実施例１に係るテストデータ生成装置の構成を説明するための図であり、図２は、実施例１に係るテストデータ生成装置が実行する処理の概要を説明するための図である。
【００１７】
図１に示すように、実施例１に係るテストデータ生成装置１０は、クラスタ生成部１１と、グラフデータ生成部１２と、テストデータ生成部１３とを有する。
【００１８】
ここで、実施例１に係るテストデータ生成装置１０は、外部入力が存在する情報処理に用いるアルゴリズムの妥当性を判定する際、外部入力が実データとして容易に取得できない場合に、当該外部入力を擬似したテストデータを生成する装置である。例えば、実施例１に係るテストデータ生成装置は、インターネットサービスにおけるＷｅｂページの検索アルゴリズムの動作検証を行なうためのテストデータを生成する。具体的には、実施例１に係るテストデータ生成装置は、Ｗｅｂページ間のリンクのように、潜在的なコミュニティ内での偏ったリンク構造を模擬したテストデータを生成する。
【００１９】
より具体的には、クラスタ生成部１１、グラフデータ生成部１２及びテストデータ生成部１３は、テストデータ生成装置１０の操作者から、図１に示すように、設定リストを受け付けた場合に、協働してテストデータの生成を行なう。ここで、設定リストには、図２の（Ａ）に示すように、総ノード数（ｎ）、クラスタ規模数（ｍ）、多重帰属可能数（ｔ）及び閾値（ｓ）が設定される。以下、設定リストに記載された各数値を用いて実行されるクラスタ生成部１１、グラフデータ生成部１２及びテストデータ生成部１３の処理を説明する。
【００２０】
クラスタ生成部１１は、まず、識別情報がそれぞれ付与された複数のノードから構成されるノード群を設定する。
【００２１】
例えば、図２の（Ａ）に示すように、「総ノード数（ｎ）：４」と設定されている場合、クラスタ生成部１１は、４つのノードからなるノード群を設定する。ここで、クラスタ生成部１１は、４つのノードそれぞれに、ノード番号「１〜４」を識別情報として付与する。これにより、クラスタ生成部１１は、図２の（Ａ）に示すように、ノード番号「１〜４」が付与された４つのノードから構成されるノード群「Ｎ＝｛１，２，３，４｝」を設定する。なお、識別情報は、各ノードを一意に特定できるものであれば任意の情報でよく、例えば、名称であってもよい。
【００２２】
ここで、総ノード数「ｎ」が設定された場合、テストデータ生成部１３は、「ｎ×ｎ」通りのノード間のリンク状態を模擬したテストデータを生成することとなる。例えば、テストデータ生成部１３は、「ｎ×ｎ」の正方行列の各要素にノード間のリンク状態を設定することで、テストデータを生成する。ここで、テストデータ生成部１３は、テストデータを「ｎ×ｎ」の零行列又は単位行列に初期設定する。
【００２３】
すなわち、操作者がノード間の関連性の強さを模擬したテストデータを生成したい場合、各ノードが自ノードと完全に接続されていると設定することが適切であるので、操作者の指示により、テストデータ生成部１３は、生成するテストデータを「ｎ×ｎ」の単位行列に初期設定する。また、操作者がノード間のリンクの有無を模擬したテストデータを生成したい場合、自ノードをリンク先ではないと設定することが適切であるので、操作者の指示により、テストデータ生成部１３は、生成するテストデータを「ｎ×ｎ」の零行列に初期設定する。
【００２４】
例えば、ノード間の関連性の強さを模擬したテストデータを生成したい操作者の指示により、テストデータ生成部１３は、図２の（Ａ）に示すように、生成するテストデータ「Ｅａ」を「４×４」の単位行列に初期設定する。
【００２５】
そして、クラスタ生成部１１は、ノード群を、総ノード数（ｎ）及びクラスタ規模数（ｍ）で決定されるクラスタ数に無作為に分割することで、複数のクラスタを生成する。例えば、「ｍ」が「ｎ」の約数である場合、クラスタ生成部１１は、「ｃ＝ｎ／ｍ」回にわたり、ノード群を構成する「ｎ」個のノードから「ｍ」個のノードを順次無作為に選択する。これにより、クラスタ生成部１１は、「ｎ」個のノードからなるノード群を「ｍ」個のノードから構成されるクラスタ「Ｍ（１）〜Ｍ（ｃ）」に分割する。
【００２６】
図２の（Ａ）に示す一例では、クラスタ生成部１１は、設定リストにて「総ノード数（ｎ）：４、クラスタ規模数（ｍ）：２」と設定されているので、「２＝４／２」回にわたり、ノード群を構成する「４」個のノードから「２」個のノードのノードを順次無作為に選択する。これにより、クラスタ生成部１１は、「４」個のノードからなるノード群「Ｎ」を、「２」個のノードから構成されるクラスタ「Ｍ（１）及びＭ（２）」に分割する。
【００２７】
図２の（Ｂ）に示す一例では、クラスタ生成部１１は、ノード群「Ｎ」を、「Ｍ（１）＝｛１，３｝」及び「Ｍ（２）＝｛２，４｝」に分割する。なお、総ノード数がクラスタ規模数で割り切れない場合のクラスタ生成部１１の処理については、後に詳細に説明する。
【００２８】
そして、図１に示すグラフデータ生成部１２は、クラスタ生成部１１により生成された各クラスタを構成するノード間のリンク状態を示すリンク属性情報を、当該ノード間に対して生成された乱数及び閾値（ｓ）を用いて設定することで、複数のクラスタそれぞれにおけるリンク構造を示すグラフデータを生成する。
【００２９】
具体的には、グラフデータ生成部１２は、ノード番号「ｉ」からノード番号「ｊ」へのリンク属性情報「ｅ（ｉ，ｊ）」を設定する際に、まず、乱数「ｒ」を生成する。そして、グラフデータ生成部１２は、例えば、乱数「ｒ」が閾値「ｓ」より大きい値である場合、「ｅ（ｉ，ｊ）」として「ｒ」に基づくリンク属性情報を設定し、乱数「ｒ」が閾値「ｓ」以下の値である場合、「ｅ（ｉ，ｊ）」を「０」に設定する。なお、グラフデータ生成部１２は、ノード番号「ｉ」からノード番号「ｉ」へのリンク属性情報「ｅ（ｉ，ｉ）」を「０」と設定する。
【００３０】
例えば、クラスタ「Ｍ（１）」において、グラフデータ生成部１２は、図２の（Ｂ）に示すように、ノード番号「１」からノード番号「３」へのリンク属性情報を設定するための乱数「ｒ」を生成し、「ｒ」と「ｓ」との大小関係に基づいて、「ｅ（１，３）」を設定する。また、グラフデータ生成部１２は、図２の（Ｂ）に示すように、ノード番号「３」からノード番号「１」へのリンク属性情報を設定するための乱数「ｒ」、「ｒ」と「ｓ」との大小関係に基づいて、「ｅ（３，１）」を設定する。これにより、グラフデータ生成部１２は、図２の（Ｂ）に示すように、クラスタ「Ｍ（１）」のグラフデータとして、各要素にリンク属性情報が設定された「２×２」の正方行列「Ｅ１」を生成する。
【００３１】
また、グラフデータ生成部１２は、図２の（Ｂ）に示すように、クラスタ「Ｍ（２）」において、ノード番号「２」からノード番号「４」へのリンク属性情報を設定するための乱数「ｒ」を生成して「ｅ（２，４）」を設定し、ノード番号「４」からノード番号「２」へのリンク属性情報を設定するための乱数「ｒ」を生成して「ｅ（４，２）」を設定する。これにより、グラフデータ生成部１２は、図２の（Ｂ）に示すように、クラスタ「Ｍ（２）」のグラフデータとして、各要素にリンク属性情報が設定された「２×２」の正方行列「Ｅ２」を生成する。なお、リンク属性情報が設定される順番は、任意の順番でよい。
【００３２】
そして、図１に示すテストデータ生成部１３は、クラスタ生成部１１によるクラスタ生成処理及びグラフデータ生成部１２によるグラフデータ生成処理を多重帰属可能数（ｔ）繰り返すように制御することで、グラフデータ生成部１２により生成された全てのグラフデータを、各ノードに付与された識別情報に基づいて統合することで、ノード群を構成する各ノード間のリンク状態を模擬したテストデータを生成する。
【００３３】
例えば、テストデータ生成部１３は、図２の（Ｂ）に示すように、１回目の処理によりグラフデータ生成部１２が生成したＥ１及びＥ２を、ノード番号に応じて初期設定のＥａに組み込む。そして、テストデータ生成部１３は、クラスタ生成部１１及びグラフデータ生成部１２に対して２回目の処理を行なうように指示を送出する。
【００３４】
これにより、クラスタ生成部１１は、図２の（Ｃ）に示すように、２回目の処理において、ノード群「Ｎ」を、例えば、「Ｍ（１）＝｛１，４｝」及び「Ｍ（２）＝｛２，３｝」の２つのクラスタに分割する。そして、グラフデータ生成部１２は、図２の（Ｃ）に示すように、クラスタ「Ｍ（１）」において、ノード番号「１」からノード番号「４」へのリンク属性情報を設定するための乱数「ｒ」を生成して「ｅ（１，４）」を設定し、ノード番号「４」からノード番号「１」へのリンク属性情報を設定するための乱数「ｒ」を生成して「ｅ（４，１）」を設定する。これにより、グラフデータ生成部１２は、図２の（Ｃ）に示すように、クラスタ「Ｍ（１）」の２回目のグラフデータとして、「Ｅ１」を生成する。
【００３５】
また、グラフデータ生成部１２は、図２の（Ｃ）に示すように、クラスタ「Ｍ（２）」において、ノード番号「２」からノード番号「３」へのリンク属性情報を設定するための乱数「ｒ」を生成して「ｅ（２，３）」を設定し、ノード番号「３」からノード番号「２」へのリンク属性情報を設定するための乱数「ｒ」を生成して「ｅ（３，２）」を設定する。これにより、グラフデータ生成部１２は、図２の（Ｃ）に示すように、クラスタ「Ｍ（２）」の２回目のグラフデータとして、「Ｅ２」を生成する。
【００３６】
そして、テストデータ生成部１３は、１回目の処理により生成されたＥ１及びＥ２が組み込まれたＥａに対して、２回目の処理により生成されたＥ１及びＥ２をノード番号に応じて組み込む。これにより、テストデータ生成部１３は、図２の（Ｃ）に示すように、グラフデータ生成部１２の１回目及び２回目の処理結果が反映されたＥａを生成する。
【００３７】
そして、テストデータ生成部１３は、図２の（Ｃ）に示すように、クラスタ生成部１１及びグラフデータ生成部１２の処理を「ｔ」回繰り返させる。これにより、テストデータ生成部１３は、グラフデータ生成部１２が１回目からｔ回目の処理により生成した全てのグラフデータが統合されたテストデータ「Ｅａ」を生成する。なお、テストデータ生成部１３によるグラフデータの統合処理は、上述したように、グラフデータ生成部１２の処理が終了するごとに実行される場合であっても良いし、グラフデータ生成部１２のｔ回分の処理が終了した後にまとめて実行される場合であっても良い。
【００３８】
上述したように、実施例１によれば、クラスタ生成部１１は、識別情報がそれぞれ付与された複数のノードから構成されるノード群を、当該ノード群の総ノード数及びクラスタ規模数で決定されるクラスタ数に無作為に分割することで、複数のクラスタを生成する。そして、グラフデータ生成部１２は、クラスタ生成部１１により生成された各クラスタを構成するノード間のリンク状態を示すリンク属性情報を、当該ノード間に対して生成された乱数及び閾値を用いて設定することで、複数のクラスタそれぞれにおけるリンク構造を示すグラフデータを生成する。そして、テストデータ生成部１３は、クラスタ生成部１１によるクラスタ生成処理及びグラフデータ生成部１２によるグラフデータ生成処理を多重帰属可能数繰り返すように制御することで、グラフデータ生成部１２により生成された全てのグラフデータを、各ノードに付与された識別情報に基づいて統合することで、ノード群を構成する各ノード間のリンク状態を模擬したテストデータを生成する。
【００３９】
すなわち、実施例１では、クラスタ生成処理及びグラフデータ生成処理を複数回繰り返し、さらに、生成された全グラフデータを統合することでテストデータを生成する。ここで、クラスタ生成部１１により生成されたクラスタは、潜在的なコミュニティと見なすことができる。また、グラフデータ生成部１２により生成されたグラフデータは、コミュニティ内での偏ったリンク構造を模擬したデータと見なすことができる。すなわち、実施例１で生成されるデータは、偏ったリンク構造を有する複数のコミュニティが入り組んで形成される状態の通信網を模擬したデータとなる。従って、実施例１では、潜在的なコミュニティ内での偏ったリンク構造を模擬したテストデータを生成することが可能となる。
【実施例２】
【００４０】
実施例２では、実施例１で説明したクラスタ生成処理、グラフデータ生成処理及びテストデータ生成処理を詳細に説明する。
【００４１】
まず、実施例２に係るテストデータ生成装置１０を、図３などを用いて説明する。図３は、実施例２に係るテストデータ生成装置の構成を説明するための図である。
【００４２】
実施例２に係るテストデータ生成装置は、図３に示すように、入力部２０、出力部３０、入出力制御Ｉ／Ｆ部４０、記憶部５０及び処理部６０を有する。
【００４３】
入力部２０は、マウスやキーボード、ＦＤ（Flexible Disk Drive）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＭＯ（Magneto Optical Disc）、ＤＶＤ（Digital Versatile Disc）などの記録媒体の読取装置などを有し、テストデータ生成装置１０の操作者から各種設定情報を受け付ける。具体的には、入力部２０は、テストデータ生成装置１０の操作者から総ノード数（ｎ）、クラスタ規模数（ｍ）、多重帰属可能数（ｔ）及び閾値（ｓ）が設定された設定リストの登録を受け付ける。
【００４４】
出力部３０は、モニタやスピーカなどを有し、例えば、後述する処理部６０の処理結果などをモニタに表示する。
【００４５】
入出力制御Ｉ／Ｆ部４０は、入力部２０および出力部３０と、記憶部５０および処理部６０との間におけるデータ転送を制御する。
【００４６】
記憶部５０は、処理部６０による各種処理に用いるデータと、処理部６０による各種処理結果を記憶する。記憶部５０は、例えば、ＨＤＤ（Hard Disc Drive）やＲＡＭ（Random Access Memory）などである。具体的には、記憶部５０は、図３に示すように、設定リスト５１、ノードリスト５２、クラスタ別グラフデータ５３及びテストデータ５４を有する。
【００４７】
設定リスト５１は、入力部２０が受け付けた設定リストを記憶する。図４は、図３に示す設定リストを説明するための図である。
【００４８】
設定リスト５１は、例えば、図４の（Ａ）に示すように、「総ノード数：ｎ、多重帰属可能数：ｔ、クラスタ規模数：ｍ、閾値：ｓ」が設定された設定リストを記憶する。あるいは、設定リスト５１は、例えば、図４の（Ｂ）に示すように、「総ノード数：ｎ、多重帰属可能数：ｔ」と、ｔ個のクラスタ規模数が配列された「ｍ１，ｍ２，・・・・・・・・，ｍｔ」と、ｔ個の閾値が配列された「ｓ１，ｓ２，・・・・・・・・，ｓｔ」とが設定された設定リストを記憶する。
【００４９】
すなわち、図４の（Ａ）に示す一例では、ｔ回繰り返されるクラスタ生成処理を全て同じクラスタ規模数にて実行し、かつ、ｔ回繰り返されるグラフデータ生成処理を全て同じ閾値にて実行するように設定されている。一方、図４の（Ｂ）に示す一例では、ｔ回繰り返されるクラスタ生成処理に用いられるクラスタ規模数が変化するように設定され、ｔ回繰り返されるグラフデータ生成処理に用いられる閾値が変化するように設定されている。なお、ｔ個のクラスタ規模数それぞれは、互いに異なる値であってもよいし、一部又は全部が同じ値である場合であってもよい。同様に、ｔ個の閾値それぞれは、互いに異なる値であってもよいし、一部又は全部が同じ値である場合であってもよい。
【００５０】
ノードリスト５２は、設定リスト５１が記憶する設定リストの総ノード数「ｎ」に基づいて、処理部６０のクラスタ生成部１１が設定したノード群を構成する複数のノードのリストを記憶する。ノードリスト５２の記憶部５０における領域規模は、総ノード数に応じて、例えば、クラスタ生成部１１により確保される。図５は、図３に示すノードリストを説明するための図である。
【００５１】
ノードリスト５２は、例えば、図５の（Ａ）に示すように、「ｎ」個のノードそれぞれに、ノード番号「１，２，３、・・・・、ｎ−１、ｎ」が識別情報として付与された形式のノードリストを記憶する。あるいは、ノードリスト５２は、例えば、図５の（Ｂ）に示すように、名称「名称（１），名称（２），名称（３）、・・・・、名称（ｎ−１）、名称（ｎ）」が識別情報として付与された形式のノードリストを記憶する。なお、以下では、ノードリスト５２が、「ｎ」個のノードそれぞれに、ノード番号が識別情報として付与された形式のノードリストを記憶する場合について説明する。
【００５２】
図３に戻って、クラスタ別グラフデータ５３は、処理部６０のクラスタ生成部１１が生成した各クラスタを構成するノードのリスト及び処理部６０のグラフデータ生成部１２が生成した各クラスタのリンクリストを記憶する。すなわち、クラスタ別グラフデータ５３は、クラスタ生成部１１が生成した各クラスタを構成するノードのリストを、クラスタ別にまとめたクラスタ別ノードリストを記憶する。また、クラスタ別グラフデータ５３は、クラスタ生成部１１が生成した各クラスタを構成するノード間のリンク属性情報のリストを、クラスタ別にまとめたクラスタ別リンクリストを記憶する。換言すれば、クラスタ別グラフデータ５３は、クラスタ別ノードリストとクラスタ別リンクリストとをクラスタごとにペアとして記憶することで、各クラスタのグラフデータを記憶する。
【００５３】
なお、クラスタ別ノードリストの記憶部５０における領域規模は、総ノード数、クラスタ規模数、多重帰属可能数及び後述するクラスタ生成法に応じて、例えば、クラスタ生成部１１及びグラフデータ生成部１２により確保される。すなわち、クラスタ別ノードリストの領域規模は、クラスタ生成部１１が多重帰属可能数分繰り返して生成した各クラスタを構成するノード数を加算した領域規模となる。また、クラスタ別リンクリストの領域規模は、クラスタ生成部１１が多重帰属可能数分繰り返して生成した各クラスタを構成するノード数を二乗した数を加算した領域規模となる。
【００５４】
テストデータ５４は、処理部６０のテストデータ生成部１３が生成したテストデータを記憶する。総ノード数「ｎ」が設定された場合、ノード間のリンク状態を模擬したテストデータは、「ｎ×ｎ」通りのノード間のリンク状態を模擬したデータとなる。すなわち、テストデータ５４の記憶部５０における領域規模は、総ノード数の二乗個に相当する領域規模として、例えば、テストデータ生成部１３により確保される。図６は、図３に示すテストデータのデータ形式を説明するための図である。
【００５５】
例えば、テストデータ５４は、図６の（Ａ）に示すように、「ｎ×ｎ」の正方行列のデータ形式にてテストデータを記憶する。図６の（Ａ）に示す一例では、ｉ行目、ｊ 列目の要素が、リンク元であるｉ番目のノードからリンク先であるｊ番目のノードへのリンク属性情報となる。
【００５６】
あるいは、テストデータ５４は、図６の（Ｂ）に示すように、「リンク元、リンク先、リンク属性情報」といったｎ個の配列情報のデータ形式にてテストデータを記憶する。なお、以下では、テストデータ５４が、図６の（Ａ）に示す「ｎ×ｎ」の正方行列のデータ形式にてテストデータを記憶する場合について説明する。
【００５７】
図３に戻って、処理部６０は、設定リスト５１が記憶する設定リストに基づいて、テストデータを生成するために、クラスタ生成部１１、グラフデータ生成部１２及びテストデータ生成部１３を有する。
【００５８】
クラスタ生成部１１は、まず、識別情報がそれぞれ付与された複数のノードから構成されるノード群を設定し、設定したノード群をノードリストとしてノードリスト５２に格納する。例えば、クラスタ生成部１１は、図５の（Ａ）に例示したノードリストをノードリスト５２に格納する。
【００５９】
そして、クラスタ生成部１１は、設定したノード群を、総ノード数（ｎ）及びクラスタ規模数（ｍ）で決定されるクラスタ数に無作為に分割することで、複数のクラスタを生成する。そして、クラスタ生成部１１は、生成した各クラスタを構成するノードのリストを、クラスタ別ノードリストとしてクラスタ別グラフデータ５３に格納する。
【００６０】
ここで、「ｍ」が「ｎ」の約数である場合、クラスタ生成部１１は、「ｃ＝ｎ／ｍ」回にわたり、ノード群を構成する「ｎ」個のノードから「ｍ」個のノードを順次無作為に選択する。これにより、クラスタ生成部１１は、「ｎ」個のノードからなるノード群を「ｍ」個のノードから構成されるクラスタ「Ｍ（１）〜Ｍ（ｃ）」に分割する。
【００６１】
しかし、「ｍ」が「ｎ」の約数でない場合、クラスタ生成部１１は、「ｎ」を「ｍ」を除算した余りの数分のノードを処理する必要がある。そこで、実施例２に係るクラスタ生成部１１は、以下に説明する第１のクラスタ生成方法、又は、第２のクラスタ生成方法により、クラスタ生成処理を行なう。
【００６２】
まず、実施例２に係るクラスタ生成部１１は、第１のクラスタ生成方法及び第２のクラスタ生成方法双方において、複数のノードの中でクラスタとして未抽出のノード群から無作為にクラスタ規模数のノードを抽出することでクラスタを順次生成する。
【００６３】
ここで、「ｍ」が「ｎ」の約数である場合、実施例２に係るクラスタ生成部１１は、上記の処理のみで、クラスタ生成処理を実行することとなる。一方、「ｍ」が「ｎ」の約数でないと、上記の処理を「ノード群の総ノード数をクラスタ規模数で除算した値以下で最大となる整数回」繰り返すと、クラスタとして未抽出のノード群のノード数は、クラスタ規模「ｍ」より少なくなる。
【００６４】
そこで、実施例２に係るクラスタ生成部１１は、第１のクラスタ生成方法として、クラスタとして未抽出のノード群のノード数がクラスタ規模数より少なくなった場合、当該クラスタとして未抽出のノード群を生成済みの各クラスタに無作為に割り振る。これにより、実施例２に係るクラスタ生成部１１は、第１のクラスタ生成方法を実行することで、ノード群の総ノード数をクラスタ規模数で除算した値以下で最大となる整数個のクラスタを生成する。
【００６５】
あるいは、実施例２に係るクラスタ生成部１１は、第２のクラスタ生成方法として、クラスタとして未抽出のノード群のノード数がクラスタ規模数より少なくなった場合、当該クラスタとして未抽出のノード群を新たなクラスタとして生成する。これにより、実施例２に係るクラスタ生成部１１は、第２のクラスタ生成方法を実行することで、ノード群の総ノード数をクラスタ規模数で除算した値以上で最小となる整数個のクラスタを生成する。
【００６６】
以下、第１のクラスタ生成方法及び第２のクラスタ生成方法それぞれについて、図７及び図８のフローチャートを用いて詳細に説明する。図７は、実施例２に係るクラスタ生成部が実行する第１のクラスタ生成方法を説明するためのフローチャートであり、図８は、実施例２に係るクラスタ生成部が実行する第２のクラスタ生成方法を説明するためのフローチャートである。
【００６７】
第１のクラスタ生成方法を実行する場合、図７に示すように、クラスタ生成部１１は、設定リストを参照して、総ノード数「ｎ」のノード群「Ｎ」を設定し、クラスタ規模数「ｍ」を取得する（ステップＳＡ１）。ここで、クラスタ生成部１１は、内部処理用データとして、ノード群Ｎ（０）〜Ｎ（Ｃ）を準備する。第１のクラスタ生成方法を実行する場合、「Ｃ」は、総ノード数「ｎ」をクラスタ規模数「ｍ」で除算した値以下で最大となる整数から「１」を差し引いた値となる。
【００６８】
そして、クラスタ生成部１１は、「Ｎ（０）＝Ｎ」とし、クラスタ管理用変数「ｉ」を「０」とし（ステップＳＡ２）、Ｎ（ｉ）からランダムにｍ個の要素を選択してＭ（ｉ＋１）の要素とする（ステップＳＡ３）。
【００６９】
その後、クラスタ生成部１１は、「ｉ」をインクリメントして、「ｉ＝ｉ＋１」とし（ステップＳＡ４）、「Ｎ（ｉ）＝Ｎ（ｉ−１）−Ｍ（ｉ）」とする（ステップＳＡ５）。
【００７０】
そして、クラスタ生成部１１は、Ｎ（ｉ）の要素数がｍ以上か否かを判定する（ステップＳＡ６）。ここで、Ｎ（ｉ）の要素数がｍ以上である場合（ステップＳＡ６肯定）、クラスタ生成部１１は、ステップＳＡ３に戻って、Ｎ（ｉ）からクラスタＭ（ｉ＋１）を構成する要素の選択処理を行なう。
【００７１】
一方、Ｎ（ｉ）の要素数がｍより小さい値である場合（ステップＳＡ６否定）、クラスタ生成部１１は、剰余ノード分配管理用変数（Ｊ）を「Ｊ＝０」とし（ステップＳＡ７）、Ｎ（ｉ）からランダムに１個の要素を選択してＭ（Ｊ＋１）に追加し、追加した要素をＮ（ｉ）から取り除く（ステップＳＡ８）。
【００７２】
そして、クラスタ生成部１１は、「Ｊ＝（Ｊ＋１）ｍｏｄ（ｎ／ｍを超えない最大整数）」とし（ステップＳＡ９）、Ｎ（ｉ）の要素数が「０」となったか否かを判定する（ステップＳＡ１０）。ここで、Ｎ（ｉ）の要素数が「０」でない場合（ステップＳＡ１０否定）、クラスタ生成部１１は、ステップＳＡ８に戻って、剰余ノードの分配処理を行なう。
【００７３】
一方、Ｎ（ｉ）の要素数が「０」となった場合（ステップＳＡ１０肯定）、クラスタ生成部１１は、処理を終了する。
【００７４】
また、第２のクラスタ生成方法を実行する場合、図８に示すように、クラスタ生成部１１は、設定リストを参照して、総ノード数「ｎ」のノード群「Ｎ」を設定し、クラスタ規模数「ｍ」を取得する（ステップＳＢ１）。ここで、クラスタ生成部１１は、内部処理用データとして、ノード群Ｎ（０）〜Ｎ（Ｃ）を準備する。第２のクラスタ生成方法を実行する場合、「Ｃ」は、総ノード数「ｎ」をクラスタ規模数「ｍ」で除算した値以下で最大となる整数となる。
【００７５】
そして、クラスタ生成部１１は、「Ｎ（０）＝Ｎ」とし、クラスタ管理用変数「ｉ」を「０」とし（ステップＳＢ２）、Ｎ（ｉ）からランダムにｍ個の要素を選択してＭ（ｉ＋１）の要素とする（ステップＳＢ３）。
【００７６】
その後、クラスタ生成部１１は、「ｉ」をインクリメントして、「ｉ＝ｉ＋１」とし（ステップＳＡ４）、「Ｎ（ｉ）＝Ｎ（ｉ−１）−Ｍ（ｉ）」とする（ステップＳＢ５）。
【００７７】
そして、クラスタ生成部１１は、Ｎ（ｉ）の要素数がｍ以上か否かを判定する（ステップＳＢ６）。ここで、Ｎ（ｉ）の要素数がｍ以上である場合（ステップＳＢ６肯定）、クラスタ生成部１１は、ステップＳＢ３に戻って、Ｎ（ｉ）からクラスタＭ（ｉ＋１）を構成する要素の選択処理を行なう。
【００７８】
一方、Ｎ（ｉ）の要素数がｍより小さい値である場合（ステップＳＢ６否定）、クラスタ生成部１１は、「Ｍ（ｉ＋１）＝Ｎ（ｉ）」とし（ステップＳＢ７）、処理を終了する。
【００７９】
すなわち、第１のクラスタ生成方法は、「ｎ」を「ｍ」を除算した余りの数分のノードを、生成済みのクラスタ（要素数：ｍ）に分配する方法である。一方、第２のクラスタ生成方法は、「ｎ」を「ｍ」を除算した余りの数分のノードを、そのまま新たなクラスタとするものである。第１のクラスタ生成方法及び第２のクラスタ生成方法のどちらを用いるかは、各クラスタを構成するノード数をなるべく均等にすることを優先するか、各クラスタを構成するノード数をなるべく「ｍ」から変えないことを優先するかに依存する。操作者は、テストデータを使用するテスト対象アルゴリズムの目的に応じて、第１のクラスタ生成方法又は第２のクラスタ生成方法のいずれかを選択する。例えば、クラスタ生成部１１が第１のクラスタ生成方法を実行するか、第２のクラスタ生成方法を実行するかは、設定リストの登録時や、クラスタ生成部１１の処理開始前などに操作者により指定される。
【００８０】
図３に戻って、グラフデータ生成部１２は、クラスタ生成部１１により生成された各クラスタを構成するノード間のリンク状態を示すリンク属性情報を、当該ノード間に対して生成された乱数及び閾値（ｓ）を用いて設定することで、複数のクラスタそれぞれにおけるリンク構造を示すグラフデータを生成する。そして、グラフデータ生成部１２は、各クラスタから生成したグラフデータにて設定されたノード間のリンク属性情報のリストをクラスタ別リンクリストとして、生成対象であるクラスタのクラスタ別ノードリストに対応付けてクラスタ別グラフデータ５３に格納する。
【００８１】
ここで、グラフデータ生成部１２は、ノード間のリンク状態を示すリンク属性情報として、ノード間のリンクの有無、又は、ノード間の関係強度を示す重み付けを設定する。リンク属性情報の種別は、操作者の指示により決定される。以下では、リンク属性情報として、グラフデータ生成部１２がノード間の関係強度を示す重み付けを設定する場合について説明する。
【００８２】
具体的には、グラフデータ生成部１２は、ノード番号「ｉ」からノード番号「ｊ」への重み付け「ｅ（ｉ，ｊ）」を設定する際に、まず、乱数「ｒ」を生成する。例えば、グラフデータ生成部１２は、「０〜１」の範囲にある実数を乱数として生成する。グラフデータ生成部１２は、乱数「ｒ」が閾値「ｓ」以下の値である場合、「ｅ（ｉ，ｊ）」を「０」に設定する。また、グラフデータ生成部１２は、「ｉ＝ｊ」の場合、重み付け「ｅ（ｉ，ｊ）」を「０」に設定する。
【００８３】
一方、グラフデータ生成部１２は、「ｉ＝ｊ」でなく、乱数「ｒ」が閾値「ｓ」より大きい値である場合、「ｅ（ｉ，ｊ）」を「ｒ」に基づいて設定する。具体的には、グラフデータ生成部１２は、以下で説明する３つの設定方法のいずれかの方法により、「ｅ（ｉ，ｊ）」を設定する。
【００８４】
第１の設定方法は、「ｒ＞ｓ」ならば、乱数「ｒ」をそのまま「ｅ（ｉ，ｊ）」と設定する方法である。また、第２の設定方法は、「ｒ＞ｓ」ならば「ｒ−ｓ」を「ｅ（ｉ，ｊ）」として設定する方法である。また、第３の設定方法は、「ｒ＞ｓ」ならば「（ｒ−ｓ）／（１−ｓ）」を「ｅ（ｉ，ｊ）」として設定する方法である。なお、グラフデータ生成部１２は、操作者が第１〜第３の設定方法から指定した設定方法により、ノード間の重み付けを設定する。例えば、グラフデータ生成部１２が第１の設定方法、第２の設定方法、又は、第３の設定方法のいずれかを実行するかは、設定リストの登録時や、グラフデータ生成部１２の処理開始前などに操作者により指定される。
【００８５】
なお、グラフデータ生成部１２は、リンク属性情報としてノード間のリンクの有無を設定する場合、例えば、乱数「ｒ」が閾値「ｓ」より大きい値であるならば、「ｅ（ｉ，ｊ）」を「リンク有」に設定し、乱数「ｒ」が閾値「ｓ」以下の値であるならば、「ｅ（ｉ，ｊ）」を「リンク無」に設定する。なお、グラフデータ生成部１２は、「ｉ＝ｊ」の場合、「ｅ（ｉ，ｊ）」を「リンク無」に設定する。
【００８６】
以下、グラフデータ生成部１２の処理について、図９を用いて説明する。図９は、実施例２に係るグラフデータ生成部の処理を説明するためのフローチャートである。なお、図９は、グラフデータ生成部１２がリンク属性情報としてノード間の関係強度を示す重み付けを第２の設定方法により設定する場合について説明する。
【００８７】
図９に示すように、実施例２に係るグラフデータ生成部１２は、クラスタ別グラフデータ５３のクラスタ別ノードリスト及び設定リスト５１を参照して、要素数「ｙ」のクラスタ及び閾値「ｓ」を取得する（ステップＳＣ１）。
【００８８】
そして、グラフデータ生成部１２は、リンクの発着ノード番号であるリンク元ノード番号管理用変数（ｉ）とリンク先ノード番号管理用変数（ｊ）を「ｉ＝１，ｊ＝１」とし、クラスタ別グラフデータを格納する行列「Ｅ＝［ｙ×ｙ］」を零行列に初期化する（ステップＳＣ２）。
【００８９】
その後、グラフデータ生成部１２は、「ｉ＝ｊ」であるか否かを判定する（ステップＳＣ３）。ここで、「ｉ＝ｊ」である場合（ステップＳＣ３肯定）、グラフデータ生成部１２は、ノード番号「ｉ」からノード番号「ｊ」への重み付け「ｅ（ｉ，ｊ）」を「０」と設定する（ステップＳＣ７）。
【００９０】
「ｉ＝ｊ」でない場合（ステップＳＣ３否定）、グラフデータ生成部１２は、「０〜１」の範囲内で乱数（ｒ）を発生する（ステップＳＣ４）。そして、グラフデータ生成部１２は、「ｒ＞ｓ」であるか否かを判定する（ステップＳＣ５）。ここで、「ｒ」が「ｓ」以下である場合（ステップＳＣ５否定）、グラフデータ生成部１２は、「ｅ（ｉ，ｊ）」を「０」と設定する（ステップＳＣ７）。
【００９１】
一方、「ｒ＞ｓ」である場合（ステップＳＣ５肯定）、グラフデータ生成部１２は、「ｅ（ｉ，ｊ）」を「ｒ−ｓ」と設定する（ステップＳＣ６）。なお、第１の設定方法を行なう場合、グラフデータ生成部１２は、「ｅ（ｉ，ｊ）」を「ｒ」と設定する。また、第３の設定方法を行なう場合、グラフデータ生成部１２は、「ｅ（ｉ，ｊ）」を「（ｒ−ｓ）／（１−ｓ）」と設定する。
【００９２】
ステップＳＣ６の処理、又は、ステップＳＣ７の処理を行なった後、グラフデータ生成部１２は、「ｊ」をインクリメントして「ｊ＝ｊ＋１」とし（ステップＳＣ８）、「ｊ＞ｙ」であるか否かを判定する（ステップＳＣ９）。ここで、「ｊ」が「ｙ」以下である場合（ステップＳＣ９否定）、グラフデータ生成部１２は、ステップＳＣ３に戻って「ｉ＝ｊ」であるか否かの判定処理を行なう。
【００９３】
一方、「ｊ＞ｙ」である場合（ステップＳＣ９肯定）、グラフデータ生成部１２は、「ｉ」をインクリメントして「ｉ＝ｉ＋１」とし、「ｊ」をリセットして「ｊ＝１」とし、（ステップＳＣ１０）、「ｉ＞ｙ」であるか否かを判定する（ステップＳＣ１１）。ここで、「ｉ」が「ｙ」以下である場合（ステップＳＣ１１否定）、グラフデータ生成部１２は、ステップＳＣ３に戻って「ｉ＝ｊ」であるか否かの判定処理を行なう。
【００９４】
一方、「ｉ＞ｙ」である場合（ステップＳＣ１１肯定）、グラフデータ生成部１２は、処理を終了する。
【００９５】
なお、図９では、リンク先ノード番号管理用変数（ｊ）をインクリメントした後に、リンク元ノード番号管理用変数（ｉ）をインクリメントする場合について説明した。しかし、グラフデータ生成処理は、リンク元ノード番号管理用変数（ｉ）をインクリメントした後に、リンク先ノード番号管理用変数（ｊ）をインクリメントする場合であってもよい。
【００９６】
図３に戻って、テストデータ生成部１３は、クラスタ生成部１１によるクラスタ生成処理及びグラフデータ生成部１２によるグラフデータ生成処理を多重帰属可能数（ｔ）繰り返すように制御する。そして、テストデータ生成部１３は、グラフデータ生成部１２により生成された全てのグラフデータを、各ノードに付与された識別情報に基づいて統合することで、ノード群を構成する各ノード間のリンク状態を模擬したテストデータを生成する。そして、テストデータ生成部１３は、生成したテストデータをテストデータ５４に格納する。
【００９７】
具体的には、テストデータ生成部１３は、リンク属性情報がノード間の関係強度を示す重み付けである場合、グラフデータ生成部１２が生成した全てのグラフデータの算術和をとることでテストデータを生成する。例えば、テストデータ生成部１３は、「ｎ×ｎ」の単位行列に初期設定したテストデータ（Ｅａ）に対して、グラフデータ生成部１２が生成した全てのグラフデータ（ノード間の関係強度）の算術和をとることでテストデータを生成する。
【００９８】
なお、テストデータ生成部１３は、リンク属性情報がノード間のリンクの有無である場合、グラフデータ生成部１２が生成した全てのグラフデータの論理和をとることでテストデータを生成する。例えば、テストデータ生成部１３は、「ｎ×ｎ」の零行列に初期設定したテストデータ（Ｅａ）に対して、グラフデータ生成部１２が生成した全てのグラフデータ（リンクの有無）の論理和をとることでテストデータを生成する。
【００９９】
ここで、テストデータ生成部１３は、クラスタ生成処理及びグラフデータ生成処理が多重帰属可能数（ｔ）実行されるごとに、クラスタ規模数及び閾値の少なくともいずれか一方を変化させても良い。例えば、図４の（Ｂ）に示すように、ｔ回繰り返されるクラスタ生成処理に用いられるクラスタ規模数が変化するように設定されている場合、クラスタ生成部１１は、テストデータ生成部１３の制御により、現に実行する繰り返し回数に該当するクラスタ規模数を設定リストから取得して、図７又は図８で例示したクラスタ生成処理を行なう。
【０１００】
また、図４の（Ｂ）に示すように、ｔ回繰り返されるグラフデータ生成処理に用いられる閾値が変化するように設定された設定リストが格納されている場合、グラフデータ生成部１２は、テストデータ生成部１３の制御により、現に実行する繰り返し回数に該当する閾値を設定リストから取得して、図９で例示したグラフデータ生成処理を行なう。なお、クラスタ規模数及び閾値は、図４の（Ｂ）に示すように、双方が繰り返し回数ごとに設定されている場合であっても良いし、いずれか一方が、一つの値である場合であっても良い。
【０１０１】
また、クラスタ生成部１１は、例えば、操作者からの指示に基づくテストデータ生成部１３の制御により、繰り返し回数ごとに、第１のクラスタ生成方法又は第２のクラスタ生成方法のいずれかを実行する場合であってもよい。例えば、繰り返し回数ごとに、クラスタ生成部１１が第１のクラスタ生成方法を実行するか、第２のクラスタ生成方法を実行するかは、設定リストの登録時や、クラスタ生成部１１の処理開始前などに操作者により指定される。また、グラフデータ生成部１２は、重み付けを設定する際に、例えば、操作者からの指示に基づくテストデータ生成部１３の制御により、繰り返し回数ごとに、第１の設定方法、第２の設定方法、又は、第３の設定方法のいずれかを実行する場合であってもよい。例えば、繰り返し回数ごとに、グラフデータ生成部１２が第１の設定方法、第２の設定方法、又は、第３の設定方法のいずれかを実行するかは、設定リストの登録時や、グラフデータ生成部１２の処理開始前などに操作者により指定される。
【０１０２】
続いて、図１０を用いて、実施例２に係るテストデータ生成装置１０による処理の手順を説明する。図１０は、実施例２に係るテストデータ生成装置の処理を説明するためのフローチャートである。なお、図１０は、リンク属性情報がノード間の関係強度を示す重み付けである場合の処理を説明するためのフローチャートである。
【０１０３】
図１０に示すように、実施例２に係るテストデータ生成装置１０は、設定リスト５１に設定リストが格納されたか否かを判定する（ステップＳ１０１）。ここで、設定リストが格納されていない場合（ステップＳ１０１否定）、テストデータ生成装置１０は、待機状態となる。
【０１０４】
一方、設定リストが格納された場合（ステップＳ１０１肯定）、テストデータ生成部１３は、多重帰属可能数管理用変数（ｋ）を「ｋ＝０」とし、テストデータを格納するための「ｎ×ｎ」の正方行列（Ｅａ）を「Ｅａ＝単位行列」とする（ステップＳ１０２）。なお、リンク属性情報がノード間のリンクの有無である場合、ステップＳ１０２において、テストデータ生成部１３は、「Ｅａ＝零行列」とする。
【０１０５】
そして、クラスタ生成部１１は、クラスタ生成処理を行なう（ステップＳ１０３）。具体的には、クラスタ生成部１１は、図７で説明した第１のクラスタ生成処理、又は図８で説明した第２のクラスタ生成処理を行なう。
【０１０６】
その後、テストデータ生成部１３は、クラスタ番号管理用カウンタ変数（Ｌ）を「Ｌ＝０」とし（ステップＳ１０４）、グラフデータ生成部１２は、グラフデータ生成処理を行なう（ステップＳ１０５）。例えば、グラフデータ生成部１２は、重み付けの設定方法が第１の設定方法として設定されている場合、図９で説明したグラフデータ生成処理を行なう。
【０１０７】
そして、テストデータ生成部１３は、「Ｌ」をインクリメントして「Ｌ＝１」とし（ステップＳ１０６）、「Ｌ」がステップＳ１０３で生成されたクラスタ数以上であるか否かを判定する（ステップＳ１０７）。ここで、「Ｌ」がステップＳ１０３で生成されたクラスタ数より小さい場合（ステップＳ１０７否定）、テストデータ生成部１３は、グラフデータが未生成のクラスタが存在すると判断し、グラフデータ生成部１２は、テストデータ生成部１３の制御により、ステップＳ１０５に戻って、残りのクラスタに対するグラフデータ生成処理を行なう。
【０１０８】
一方、「Ｌ」がステップＳ１０３で生成されたクラスタ数以上である場合（ステップＳ１０７肯定）、テストデータ生成部１３は、「ｋ＝ｋ＋１」とし（ステップＳ１０８）、ｋのグラフデータ群を「Ｅ」とする（ステップＳ１０９）。すなわち、「Ｌ」がステップＳ１０３で生成されたクラスタ数以上である場合、テストデータ生成部１３は、ステップＳ１０３で生成されたクラスタ数分のグラフデータが生成されたと判断する。
【０１０９】
そして、テストデータ生成部１３は、「Ｅａ＝Ｅａ＋Ｅ」としてテストデータを更新し（ステップＳ１１０）、「ｋ＝ｔ（多重帰属可能数）」であるか否かを判定する（ステップＳ１１１）。
【０１１０】
ここで、「ｋ」が「ｔ」に到達していない場合（ステップＳ１１１否定）、テストデータ生成部１３は、多重帰属可能数分のグラフデータ群が生成されていないと判断し、クラスタ生成部１１は、テストデータ生成部１３の制御により、ステップＳ１０３に戻って、再度、クラスタ生成処理を行なう。
【０１１１】
一方、「ｋ＝ｔ」である場合（ステップＳ１１１肯定）、テストデータ生成部１３は、ステップＳ１１０で更新された「Ｅａ」をテストデータとし、処理を終了する。
【０１１２】
なお、図１０では、「Ｅａ」が順次更新される場合について説明したが、本実施例２は、多重帰属可能数分のグラフデータ群が生成された後に、一括して統合されることで「Ｅａ」が生成される場合であっても良い。また、図１０では、多重帰属可能数分のクラスタ生成処理及びグラフデータ生成処理が順次行なわれる場合について説明したが、本実施例２は、例えば、多重帰属可能数分のクラスタ生成処理及びグラフデータ生成処理が並列に行なわれる場合であっても良い。また、図１０では、クラスタ番号管理用カウンタ変数（Ｌ）を用いたテストデータ生成部１３の制御により、グラフデータ生成部１２がクラスタごとにグラフデータを生成する場合について説明したが、本実施例２は、ステップＳ１０３で生成された複数のクラスタに対するグラフデータ生成処理が並列に行なわれる場合であっても良い。
【０１１３】
上述したように、実施例２によれば、実施例１と同様に、クラスタ生成部１１、グラフデータ生成部１２及びテストデータ生成部１３の処理によりテストデータを生成する。
【０１１４】
例えば、電話網では、通信経路が物理的回線と対応付けられ、かつ、回線の接続構造が地理的条件から自明である。このため、電話網の制御アルゴリズムを検証するためのテストデータは、図１１の（Ａ）に示すように、例えば、乱数で通信密度を決定することで、通信経路に対応した情報の流れを模擬したグラフ構造として生成することができた。また、ランダムグラフによるテストデータの生成方法では、全てのノード間が結線される可能性を与えたうえで、乱数により、図１１の（Ｂ）に示すように、結線の有無を決定したり、結線に重み付けを付与したりしていた。しかし、図１１に示す方法では、Ｗｅｂページ間のリンクのように、潜在的なコミュニティ内での偏ったリンク構造を模擬したテストデータを生成することができなかった。なお、図１１は、従来のテストデータを説明するための図である。
【０１１５】
しかし、実施例２では、図１２の（Ａ）に示すように、ノード群からクラスタを生成する処理を複数回行ない、さらに、図１２の（Ｂ）に示すように、複数回行なわれたクラスタ生成処理ごとに、各クラスタのグラフ構造（グラフデータ）を生成する。そして、実施例２では、図１２の（Ｃ）に示すように、各クラスタのグラフ構造を統合する。すなわち、実施例２で生成されるテストデータは、図１１に示す従来のテストデータとは異なり、偏ったリンク構造を有する複数のコミュニティが入り組んで形成される状態の通信網を模擬したデータとなる。なお、図１２は、実施例２で生成されるテストデータを説明するための図である。
【０１１６】
従って、実施例２では、実施例１と同様に、潜在的なコミュニティ内での偏ったリンク構造を模擬したテストデータを生成することができる。
【０１１７】
また、実施例２では、グラフデータ生成部１２は、リンク属性情報として、ノード間のリンクの有無、又は、ノード間の関係強度を示す重み付けを設定する。そして、テストデータ生成部１３は、リンク属性情報がノード間のリンクの有無である場合、全てのグラフデータの論理和をとることでテストデータを生成する。また、グラフデータ生成部１２は、リンク属性情報がノード間の関係強度を示す重み付けである場合、全てのグラフデータの算術和をとることでテストデータを生成する。
【０１１８】
従って、実施例２では、操作者の要望するタイプに応じて、潜在的なコミュニティ内での偏ったリンク有無を模擬したテストデータや、潜在的なコミュニティ内での偏ったリンク密度を模擬したテストデータを生成することが可能となる。
【０１１９】
また、実施例２では、クラスタ生成部１１は、第１のクラスタ生成方法として、複数のノードの中でクラスタとして未抽出のノード群から無作為にクラスタ規模数のノードを抽出することでクラスタを順次生成し、さらに、クラスタとして未抽出のノード群のノード数がクラスタ規模数より少なくなった場合、当該クラスタとして未抽出のノード群を生成済みの各クラスタに無作為に割り振ることで、総ノード数をクラスタ規模数で除算した値以下で最大となる整数個のクラスタを生成する。あるいは、クラスタ生成部１１は、第２のクラスタ生成方法として、複数のノードの中でクラスタとして未抽出のノード群から無作為にクラスタ規模数のノードを抽出することでクラスタを順次生成し、さらに、クラスタとして未抽出のノード群のノード数がクラスタ規模数より少なくなった場合、当該クラスタとして未抽出のノード群を新たなクラスタとして生成することで、総ノード数をクラスタ規模数で除算した値以上で最小となる整数個のクラスタを生成する。
【０１２０】
従って、実施例２では、各クラスタを構成するノード数をなるべく均等にすることを優先するか、各クラスタを構成するノード数をなるべくクラスタ規模数から変えないことを優先するかという操作者の要望に応じて、クラスタ生成処理を行なうことができる。また、実施例２では、第１のクラスタ生成方法及び第２のクラスタ生成方法を、クラスタ生成処理を行なうごとに変更させることもできる。
【０１２１】
また、実施例２では、テストデータ生成部１３は、設定リストの設定値に応じて、クラスタ生成処理及びグラフデータ生成処理が多重帰属可能数実行されるごとに、クラスタ規模数及び閾値の少なくともいずれか一方を変化させる。すなわち、実施例２では、想定するコミュニティの多様性を増大することができる。従って、実施例２では、潜在的なコミュニティ内での偏ったリンク構造を模擬したテストデータの多様性を任意に変更することが可能となる。
【０１２２】
すなわち、操作者は、テストデータ生成装置１０を用いる際に、模擬しようとする対象の性質に応じて、設定リストに設定する値を調整することで、自身が要望するテストデータを生成させることができる。例えば、インターネット上のサイト間交流の密度（関係強度）を対象とする場合、操作者が設定リストに設定する値は、以下のようになる。
【０１２３】
まず、多重帰属可能数は、あるサイトがアクセスされるコミュニティの想定数を表す値として設定される。インターネット上で絶対数が多い個人サイトを多く含む通信網を対象とする場合、多重帰属可能数は、個人が持ちうる興味分野の数などから推定して設定できる。例えば、非常に多趣味な人物が多い社会を想定しても、同時に興味を持てる範囲は、人間の脳の構造などから限界がある。近年の脳構造に関する知見から、人間の短期記憶は、高々１０個の数字が保持できる程度であることが判明している。
【０１２４】
ここで、短期記憶が可能な情報量は、実用化されている検索システムにおける結果一覧にて参照される件数などとも類似する。このため、潜在的な興味が広くても、実際のサイト作成において目立つ場所におかれるリンクは、１０件前後であることが多い。このような性質に鑑みれば、多重帰属可能数は、「１０」に設定されることが望ましい。あるいは、模擬したいサイト群によっては、多重帰属可能数は、例えば、「７」と、「１０」より小さい値に設定されてもよい。
【０１２５】
また、クラスタ規模数は、コミュニティの想定最大規模を表す値として設定される。例えば、クラスタ規模数を低めに設定すると、狭いコミュニティを模擬したことになる。また、クラスタ規模数を高めに設定すると、広いコミュニティを模擬したことになる。
【０１２６】
また、閾値は、上述したグラフデータ生成処理において、各発・宛ノードの対が接続されない確率を表す値である。例えば、閾値を低めに設定するとリンクが濃密なコミュニティを模擬したことになり、閾値を高めに設定するとリンクが希薄なコミュニティを模擬したことになる。
【０１２７】
すなわち、クラスタ規模数と閾値とを設定することで、様々なリンク密度及び規模を有するコミュニティを模擬することができる。例えば、閾値を低めに設定し、クラスタ規模数を低めに設定すると、リンクが濃密な狭いコミュニティを模擬したことになる。また、閾値を高めに設定し、クラスタ規模数を高めに設定すると、リンクが希薄な広いコミュニティを模擬したことになる。
【０１２８】
ここで、実施例１や２では、リンク生成のランダム性の結果として、想定コミュニティ内の連結性を保障しない。つまり、実施例１や２では、グラフデータ生成部１２が生成した複数のグラフデータにおいて、コミュニティ内の連結性が記述されたグラフデータの数が、設定したクラスタ規模数を下回っている可能性がある。コミュニティ内の連結性が記述されたグラフデータの数がクラスタ規模数を下回る確率は、クラスタ規模数及び閾値双方の大きさに依存する。すなわち、閾値が高い場合は、全てのノードが互いに到達可能なパスを持たないデータが生成する確率が高まり、その結果、コミュニティ内の連結性が記述されたグラフデータの数がクラスタ規模数を下回る確率が大きくなる。このため、クラスタ規模数は、閾値との組み合わせで決定されることが望ましい。
【０１２９】
なお、模擬対象が潜在的なコミュニティであって互いにリンクを張ることに消極的な傾向にあるサイト群であるならば、閾値は、リンクが希薄なため全ノードが連結されていない状態を示すテストデータを生成するために高めに設定する場合であっても良い。
【０１３０】
このようにして設定された設定データを用いて生成されるテストデータは、クラスタにに属するノード間の縁故を模擬したリンクを多重帰属可能数通りのクラスタ分割について重ね合わせたものになっている。例えば、ノードがＷｅｂサイト、クラスタがＷｅｂサイト運営者の属するコミュニティを模擬すると見なせば、各運営者がｔ個以内のコミュニティに多重帰属することで、直接同じコミュニティに属さないＷｅｂサイト間にも関わりが発生する様子を模擬できる。従って、本実施例２で生成されるテストデータを用いることで、操作者は、例えば、Ｗｅｂサイト間の関係強度を決定するための重要な経路を検証することができる。
【０１３１】
なお、上記した実施例１及び２では、テストデータ生成方法が一つの装置にて実行される場合について説明した。しかし、実施例１及び２で説明したテストデータ生成方法は、複数の装置にて分散されて実行される場合であっても良い。例えば、実施例１及び２で説明したテストデータ生成方法は、クラスタ生成部１１及びグラフデータ生成部１２の機能を有する装置と、テストデータ生成部１３の機能を有する装置とが一つの仮想的なテストデータ生成装置１０として機能することにより実現される場合であっても良い。また、１装置または２以上の装置からなるシステム内に、仮想マシンが起動される環境であって、この仮想マシン上で複数の仮想化されたコンピュータが動作するものであり、この仮想化されたコンピュータ上で実施例１及び２で説明したテストデータ生成方法が実行される場合であってもよい。
【０１３２】
また、上記した実施例１及び２で説明したテストデータ生成方法は、あらかじめ用意されたテストデータ生成プログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。そこで以下では、図１３を用いて、上記の実施例１に示したテストデータ生成装置１０と同様の機能を有するテストデータ生成プログラムを実行するコンピュータの一例を説明する。図１３は、実施例１に係るテストデータ生成プログラムを実行するコンピュータを示す図である。なお、以下では、テストデータ生成方法が一つのコンピュータにて実行される場合について説明する。しかし、実施例１及び２で説明したテストデータ生成方法は、上述したように、複数のコンピュータにて分散されて実行される場合であっても良い。また、実施例１及び２で説明したテストデータ生成方法は、上述したように、仮想化されたコンピュータ上で実行される場合であっても良い。
【０１３３】
図１３に示すように、ＰＣ（Personal Computer）などの情報処理装置であるコンピュータ１００は、ＣＰＵ（Central  Processing  Unit）１１０、入力装置１２０、出力装置１３０、媒体読取装置１４０、及びネットワークインタフェース１５０を有する。ＣＰＵ１１０は、各種の演算処理を実行する。入力装置１２０は、各種データの入力を利用者から受け付ける。出力装置１３０は、ＣＰＵ１１０により処理された各種データを出力する。媒体読取装置１４０は、記憶媒体からプログラム等を読み取る。ネットワークインタフェース１５０は、ネットワークを介して他のコンピュータとの間でデータの授受を行う。例えば、ネットワークインタフェース１５０は、設定リストを、ネットワークを介して受信することもできる。
【０１３４】
また、コンピュータ１００は、ＲＡＭ１６０及びＨＤＤ１７０を有する。ＲＡＭ１６０は、ＣＰＵ１１０により処理される各種情報を一時的に記憶する。ＨＤＤ１７０は、各種データや各種プログラムを記憶する。
【０１３５】
そして、例えば、ＨＤＤ１７０は、図１に示したクラスタ生成部１１、グラフデータ生成部１２及びテストデータ生成部１３それぞれと同様の機能を有するクラスタ生成プログラム１７１、グラフデータ生成プログラム１７２及びテストデータ生成プログラム１７３を記憶する。また、ＣＰＵ１１０は、ＨＤＤ１７０からクラスタ生成プログラム１７１、グラフデータ生成プログラム１７２及びテストデータ生成プログラム１７３を読み出してＲＡＭ１６０に、クラスタ生成プログラム１７１、グラフデータ生成プログラム１７２及びテストデータ生成プログラム１７３を、クラスタ生成プログラム１６１、グラフデータ生成プログラム１６２及びテストデータ生成プログラム１６３として展開する。
【０１３６】
その後、ＣＰＵ１１０は、クラスタ生成プログラム１６１、グラフデータ生成プログラム１６２及びテストデータ生成プログラム１６３それぞれを、クラスタ生成プロセス１１１、グラフデータ生成プロセス１１２及びテストデータ生成プロセス１１３として実行する。
【０１３７】
なお、クラスタ生成プログラム１７１、グラフデータ生成プログラム１７２及びテストデータ生成プログラム１７３は、必ずしもＨＤＤ１７０に格納されている必要はなく、例えば、ＣＤ−ＲＯＭ等の記憶媒体に記憶され、記憶媒体から読み出されて実行されてもよい。又は、クラスタ生成プログラム１７１、グラフデータ生成プログラム１７２及びテストデータ生成プログラム１７３は、他のコンピュータによって記憶され、公衆回線、インターネット、ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）等を介して取得されて実行されてもよい。
【産業上の利用可能性】
【０１３８】
以上のように、本発明に係るテストデータ生成方法、テストデータ生成装置及びテストデータ生成プログラムは、外部入力が存在する情報処理に用いるアルゴリズムの妥当性を判定するために、外部入力を模擬したテストデータを生成する場合に有用であり、特に、潜在的なコミュニティ内での偏ったリンク構造を模擬したテストデータを生成することに適する。
【符号の説明】
【０１３９】
１０  テストデータ生成装置
１１  クラスタ生成部
１２  グラフデータ生成部
１３  テストデータ生成部
２０  入力部
３０  出力部
４０  入出力制御Ｉ／Ｆ部
５０  記憶部
５１  設定リスト
５２  ノードリスト
５３  クラスタ別グラフデータ
５４  テストデータ
６０  処理部
【図１】
2012064136.tif 000003
【図２】
2012064136.tif 000004
【図３】
2012064136.tif 000005
【図４】
2012064136.tif 000006
【図５】
2012064136.tif 000007
【図６】
2012064136.tif 000008
【図７】
2012064136.tif 000009
【図８】
2012064136.tif 000010
【図９】
2012064136.tif 000011
【図１０】
2012064136.tif 000012
【図１１】
2012064136.tif 000013
【図１２】
2012064136.tif 000014
【図１３】
2012064136.tif 000015