"複数のノードがリンクを介して接続されたネットワークにおけるコミュニティ構造を検出するコミュニティ構造検出装置あって、前記複数のノードのうち一のノードを開始ノードとし、当該開始ノードからSAWself-avoidingwalkによる訪問を開始し、当該SAWによる訪問の終了までを1回とし、所定の回数実行するSAW実行手段と、前記SAW実行手段により、前記複数のノードのそれぞれを開始ノードとして前記SAWを実行し、各々のノードへの訪問回数を前記開始ノードに対応付けて訪問回数記憶手段に記憶する全ノード実行手段と、前記全ノード実行手段によって前記訪問回数記憶手段に記憶されたノードの訪問回数に基づいて、各々のノードの訪問率によって示される重要度を算出する重要度算出手段と、前記重要度算出手段が算出した重要度が大きい順に、ノードを順次取り除くノード除去手段と、前記ノード除去手段がノードを1つ取り除くごとに、前記ネットワークが複数のサブネットワークに分割されたか否かを判別する分割判別手段と、前記分割判別手段によって分割されていないと判別された場合に前記ノード除去手段による除去及び前記分割判別手段による判別を繰り返し、前記分割判別手段によって分割されたと判別された場合に、前記取り除いたノードの集合をバウンダリノードの集合と特定するバウンダリノード特定手段と、前記バウンダリノード特定手段によって特定されたノードと、前記サブネットワークとを直接にリンクしたネットワークをコミュニティとして検出するコミュニティ検出手段と、を備えるコミュニティ構造検出装置。前記コミュニティ検出手段は、前記バウンダリノード特定手段によって特定されたバウンダリノードの集合が、当該バウンダリノードの集合を構成するノード間のリンクを介して接続されたネットワークであるか否かを判別するコミュニティ判別手段をさらに備え、前記コミュニティ判別手段によって、前記特定されたバウンダリノードの集合がネットワークであると判別された場合、そのネットワークをコミュニティとして検出する、請求項1に記載のコミュニティ構造検出装置。前記コミュニティ検出手段は、ノード間のリンクの数に基づいてコミュニティの密度を計算するコミュニティ密度計算手段と、コミュニティを検出するごとに、前記コミュニティ密度計算手段によってコミュニティの密度を計算し、検出したコミュニティの密度の平均が最大になるコミュニティの集合を検出するコミュニティ集合検出手段と、をさらに備える、請求項1又は2に記載のコミュニティ構造検出装置。複数のノードがリンクを介して接続されたネットワークにおけるコミュニティ構造を検出するコミュニティ構造検出装置が実行する方法あって、前記複数のノードのうち一のノードを開始ノードとし、当該開始ノードからSAWself-avoidingwalkによる訪問を開始し、当該SAWによる訪問の終了までを1回とし、所定の回数実行するSAW実行ステップにより、前記複数のノードのそれぞれを開始ノードとして前記SAWを実行し、各々のノードへの訪問回数を前記開始ノードに対応付けて訪問回数記憶手段に記憶する全ノード実行ステップと、前記全ノード実行ステップによって前記訪問回数記憶手段に記憶されたノードの訪問回数に基づいて、各々のノードの訪問率によって示される重要度を算出する重要度算出ステップと、前記重要度算出ステップが算出した重要度が大きい順に、ノードを順次取り除くノード除去ステップと、前記ノード除去ステップがノードを1つ取り除くごとに、前記ネットワークが複数のサブネットワークに分割されたか否かを判別する分割判別ステップと、前記分割判別ステップによって分割されていないと判別された場合に前記ノード除去ステップによる除去及び前記分割判別ステップによる判別を繰り返し、前記分割判別ステップによって分割されたと判別された場合に、前記取り除いたノードの集合をバウンダリノードの集合と特定するバウンダリノード特定ステップと、前記バウンダリノード特定ステップによって特定されたノードと、前記サブネットワークとを直接にリンクしたネットワークをコミュニティとして検出するコミュニティ検出ステップと、を備える方法。しかしながら、非特許文献1に記載された技術は、ノードが複数のコミュニティにオーバーラップして所属することがありうるコミュニティを検出することができなかった。また、非特許文献2は、ネットワークの媒介中心性betweennessをコミュニティ間の接続に関するノードの重要度もしくは複数のコミュニティにオーバーラップしている可能性の高さの指標として用いる。例えば、媒介中心性が最大のノードを1つ1つ取り除いてコミュニティを求める場合、取り除くことでできる新たなネットワークトポロジーごとに、媒介中心性を再計算する必要がある。また、取り除くノードの順番によっては、当初のネットワークでは媒介中心性が大きいノードであっても、そのノードの周辺のノードが取り除かれることで媒介中心性が小さくなってしまう場合がある。例えば、図91において、ノード1を取り除くと、ノード7の媒介中心性が小さくなる。このようなノードは、オーバーラップしているノードとして見なされず、例えば、図92、図93のようにノード12、ノード7の順に取り除かれる対象となる場合があり、図94のようにオーバーラップするコミュニティを正しく検出することができなくなってしまう場合がある。また、図101から図103のように、最短パスを構成するノードを取り除く対象とした場合、図104のように、ノード1とノード5とのネットワークをコミュニティとして検出してしまう場合があった。非特許文献3に記載された技術は、コミュニティを検索するために、コミュニティの特徴となるパラメタk-cliquecommunityのkの値を指定する必要がある。このため、1回の検索で適切なパラメタを、コミュニティを検索する前に指定することは困難であった。そのためパラメタの値を変えて検索を数回実行する必要があり、検索時間を要した。そこで、既存のアルゴリズムに比べ少ない計算量で、適切なコミュニティを検出できる装置が求められている。本発明は、既存のアルゴリズムに比べ少ない計算量で、適切なコミュニティを効率よく検出できるコミュニティ構造検出装置及び方法を提供することを目的とする。本発明は、ネットワークに存在する構造を検索する手法を提供する。ネットワークに存在する構造とは、一般的にはモジュールもしくはコミュニティと呼ばれ、具体的には、ノードが同じコミュニティのノードとはリンクを多く持ち、ネットワークの残りのノードとのリンクは少ないという特徴を持ったノード集合をいう。本発明では、各ノードがコミュニティ間を接続するバウンダリとなっている度合の観点からの、ノードの重要度を導入し、バウンダリとなっているノードを特定することでコミュニティを検索可能とするものである。具体的には、以下のような解決手段を提供する。1複数のノードがリンクを介して接続されたネットワークにおけるコミュニティ構造を検出するコミュニティ構造検出装置あって、前記複数のノードのうち一のノードを開始ノードとし、当該開始ノードからSAWself-avoidingwalkによる訪問を開始し、当該SAWによる訪問の終了までを1回とし、所定の回数実行するSAW実行手段と、前記SAW実行手段により、前記複数のノードのそれぞれを開始ノードとして前記SAWを実行し、各々のノードへの訪問回数を前記開始ノードに対応付けて訪問回数記憶手段に記憶する全ノード実行手段と、前記複数のノードのうち一のノードを開始ノードとして、当該開始ノードごとに前記リンクをたどってノードを訪問した回数を、前記開始ノードに対応付けたノードに記憶する訪問回数記憶手段と、前記開始ノードからSAWself-avoidingwalkによる訪問を開始し、前記SAWによる訪問の終了までを所定の回数行い、前記SAWによってノードを訪問するたびに、前記訪問回数記憶手段において前記開始ノードに対応付けられた訪問したノードにカウントして訪問回数を記憶させるSAW実行手段と、前記SAW実行手段による訪問を、前記複数のノードのそれぞれを開始ノードとして行う全ノード実行手段と、前記全ノード実行手段によって前記訪問回数記憶手段に記憶されたノードの訪問回数に基づいて、各々のノードの訪問率によって示される重要度を算出する重要度算出手段と、前記重要度算出手段が算出した重要度が大きい順に、ノードを順次取り除くノード除去手段と、前記ノード除去手段がノードを1つ取り除くごとに、前記ネットワークが複数のサブネットワークに分割されたか否かを判別する分割判別手段と、前記分割判別手段によって分割されていないと判別された場合に前記ノード除去手段による除去及び前記分割判別手段による判別を繰り返し、前記分割判別手段によって分割されたと判別された場合に、前記取り除いたノードの集合をバウンダリノードの集合と特定するバウンダリノード特定手段と、前記バウンダリノード特定手段によって特定されたノードと、前記サブネットワークとを直接にリンクしたネットワークをコミュニティとして検出するコミュニティ検出手段と、を備えるコミュニティ構造検出装置。1の構成によれば、本発明に係るコミュニティ構造検出装置は、複数のノードのそれぞれを開始ノードとしてSAWself-avoidingwalkによる訪問を実行し、各々のノードへの訪問回数を開始ノードに対応付けて訪問回数記憶手段に記憶する。次に、訪問回数記憶手段に記憶されたノードの訪問回数に基づいて、各々のノードの訪問率によって示される重要度を算出し、算出した重要度が大きい順に、ノードを順次取り除き、ノードを1つ取り除くごとに、ネットワークが複数のサブネットワークに分割されたか否かを判別する。そして、コミュニティ構造検出装置は、ネットワークが分割されていないと判別した場合に、ノードの除去及び分割の判別を繰り返し、ネットワークに分割されたと判別した場合に、取り除いたノードの集合をバウンダリノードの集合と特定し、特定したノードと、サブネットワークとを直接にリンクしたネットワークをコミュニティとして検出する。すなわち、本発明に係るコミュニティ構造検出装置は、コミュニティ同士の接続に関する各ノードの重要度を計算し、計算したノードの重要度が大きい順にノードを仮想的にネットワークから取り除くことでコミュニティが他のコミュニティと交わるバウンダリの役割を担うノード集合を特定し、特定したバウンダリのノード集合を使って、ネットワーク内のコミュニティを検出する。具体的には、コミュニティ構造検出装置は、コミュニティ同士の接続に関する各ノードの重要度を計算するために、仮想的に、各ノードから開始したself-avoidingwalk自身とリンクで接続されている隣接ノードを、次回の訪問先ノードとしてランダムに選択し、他のノードを順次訪問すること。ただし既に訪問したノードは次回訪問先としては選ばない。以下、SAWというを数回行う。そして、自身及び他のノードから開始したSAWによって、各ノードを訪問した回数の合計値を計算し、全てのSAWの実施回数を使って訪問回数の合計値を正規化し、正規化した値をノードの重要度とする。さらに、コミュニティ構造検出装置は、ネットワークからノードの重要度が大きい順にノードを1つ取り除き、取り除くたびに連結なネットワーク各ノードが他の全てのノードに至るパスがあるネットワークが複数のサブネットワークに分割されたか否かを確認する。ここで、サブネットワークに分割されている状態とは、1つのサブネットワークのいずれかのノードから、他のサブネットワークのいずれかのノードへのパスが存在しない状態をいう。分割されたことが確認された場合、サブネットワーク間を接続するバウンダリの役割を担うノードを、既に取り除いたノードの中から特定し、サブネットワークとそのバウンダリの役割を担うノードで構成するコミュニティを特定する。したがって、本発明に係るコミュニティ構造検出装置は、既存のアルゴリズムに比べ少ない計算量で、適切なコミュニティを効率よく検出することができる。2前記コミュニティ検出手段は、前記バウンダリノード特定手段によって特定されたバウンダリノードの集合が、当該バウンダリノードの集合を構成するノード間のリンクを介して接続されたネットワークであるか否かを判別するコミュニティ判別手段をさらに備え、前記コミュニティ判別手段によって、前記特定されたバウンダリノードの集合がネットワークであると判別された場合、そのネットワークをコミュニティとして検出する、1に記載のコミュニティ構造検出装置。すなわち、2のコミュニティ構造検出装置は、ネットワークからノードの重要度が大きい順にノードを1つ取り除くたびに、2ノード以上の取り除いたノードのみで構成するサブネットワークの存在有無を確認し、そのようなサブネットワークが存在する場合は、そのサブネットワークをコミュニティとして特定する。したがって、2に係るコミュニティ構造検出装置は、適切なコミュニティをさらに検出することができる。3前記コミュニティ検出手段は、ノード間のリンクの数に基づいてコミュニティの密度を計算するコミュニティ密度計算手段と、コミュニティを検出するごとに、前記コミュニティ密度計算手段によってコミュニティの密度を計算し、検出したコミュニティの密度の平均が最大になるコミュニティの集合を検出するコミュニティ集合検出手段と、をさらに備える、1又は2に記載のコミュニティ構造検出装置。すなわち、3に係るコミュニティ構造検出装置は、ネットワークからノードの重要度が大きい順にノードを順次取り除いて、より小規模なサブネットワークに分割さていくそれぞれの段階で、コミュニティの密度コミュニティを構成するノード間に実在するリンク数を、コミュニティを構成するノード間で論理的にとり得る最大のリンク数で割った値を計算し、コミュニティの密度の平均値が最大となる段階のコミュニティの集合を検出して提示する。したがって、3に係るコミュニティ構造検出装置は、適切な分割によるコミュニティを検出することができる。4複数のノードがリンクを介して接続されたネットワークにおけるコミュニティ構造を検出するコミュニティ構造検出装置が実行する方法あって、前記複数のノードのうち一のノードを開始ノードとし、当該開始ノードからSAWself-avoidingwalkによる訪問を開始し、当該SAWによる訪問の終了までを1回とし、所定の回数実行するSAW実行ステップにより、前記複数のノードのそれぞれを開始ノードとして前記SAWを実行し、各々のノードへの訪問回数を前記開始ノードに対応付けて訪問回数記憶手段に記憶する全ノード実行ステップと、前記全ノード実行ステップによって前記訪問回数記憶手段に記憶されたノードの訪問回数に基づいて、各々のノードの訪問率によって示される重要度を算出する重要度算出ステップと、前記重要度算出ステップが算出した重要度が大きい順に、ノードを順次取り除くノード除去ステップと、前記ノード除去ステップがノードを1つ取り除くごとに、前記ネットワークが複数のサブネットワークに分割されたか否かを判別する分割判別ステップと、前記分割判別ステップによって分割されていないと判別された場合に前記ノード除去ステップによる除去及び前記分割判別ステップによる判別を繰り返し、前記分割判別ステップによって分割されたと判別された場合に、前記取り除いたノードの集合をバウンダリノードの集合と特定するバウンダリノード特定ステップと、前記バウンダリノード特定ステップによって特定されたノードと、前記サブネットワークとを直接にリンクしたネットワークをコミュニティとして検出するコミュニティ検出ステップと、を備える方法。したがって、4に係る方法は、1と同様に、既存のアルゴリズムに比べ少ない計算量で、適切なコミュニティを効率よく検出することができる。本発明によれば、既存のアルゴリズムに比べ少ない計算量で、適切なコミュニティを効率よく検出できるコミュニティ構造検出装置及び方法を提供することができる。さらに、本発明は、社会ネットワークやインターネット等のネットワーク中に存在するコミュニティ構造を分散的に検索する機能を提供することができる。以下、本発明の実施形態について図を参照しながら説明する。図1は、本発明の一実施形態におけるコミュニティ構造検出装置10がコミュニティ構造を検出することを説明する図である。図1のように、ノードの識別子が1、2、3、4、5の5つのノードで構成するネットワークを例に説明する。この例ではリンクL1~L6に方向はなく、ノード1はノード2、3とリンクL1、L2を持ち、ノード2はノード1、3とリンクL1、L3を持ち、ノード3はノード1、2、4、5とリンクL2、L3、L4、L5を持ち、ノード4はノード3、5とリンクL4、L6を持ち、ノード5はノード3、4とリンクL5、L6を持つものとする。この例では、ネットワークには2つのコミュニティが存在する。1つ目はノード1、2、3で構成するコミュニティC1であり、2つ目はノード3、4、5で構成するコミュニティC2である。ノード3は、コミュニティC1とコミュニティC2とを接続する役割を担い、2つのコミュニティにオーバーラップしているノードとなる。図2は、図1において、コミュニティ構造検出装置10がコミュニティを提示する手順について説明する図である。図3は、本発明の一実施形態に係る訪問回数テーブル31の例を示す図である。図4は、本発明の一実施形態に係るコミュニティ構造検出装置10が、図1のネットワークからコミュニティを検出する過程の例を示す図である。手順1コミュニティ構造検出装置10は、各ノードから開始するself-avoidingwalk以下、SAWというを10回実行する。一のノードから他のノードを訪問するSAWは、自身とリンクで接続されている隣接ノードを、次回の訪問先ノードとしてランダムに選択し、他のノードを順次訪問する。ただし既に訪問したノードは次回訪問先としては選ばない。例えばノード1から開始するSAWの1回目は、ノード1の隣接ノード2と3との中から無作為にそれぞれ1/2の確率で1つのノードを選び、それが例えばノード3だとすると、ノード3に進み、次にノード3の隣接ノードただし既に訪問しているノード1を除くとなるノード2、4、5の中から無作為にそれぞれ1/3の確率でノードを1つ選び、それが例えばノード2だとすると、ノード2に進み、ノード2の隣接ノードには未だ訪問していないノードは存在しないことからノード2でSAWを停止する。同様にして、ノード1から開始するSAWを残り9回実行する。同様にして、他のノードから開始するSAWをそれぞれ10回実行する。手順2コミュニティ構造検出装置10は、全てのSAWの実行を通じて、各ノードを訪問した回数を合計する。例えば、ノード2であれば、ノード1から開始したSAWを10回実行した中で訪問があった6回、ノード2から開始したSAWを10回実行した中で訪問があった10回、ノード3から開始したSAWを10回実行した中で訪問があった5回、ノード4から開始したSAWを10回実行した中で訪問があった8回、ノード5から開始したSAWを10回実行した中で訪問があった8回、の合計610588を、全SAWの実行回数となる50で割り、割った値を、コミュニティ同士の接続に関するノード2の重要度を表す指標とする。このようなSAWによる訪問回数を、訪問回数テーブル31は、図3のように記憶している。手順3コミュニティ構造検出装置10は、重要度が最大のノード3をネットワークから仮想的に取り除き、ネットワークがサブネットワークに分割されるか否かを確認する。図41で示されるノード1、2、3、4、5で構成するネットワークは、図42に示すように、ノード3を取り除くことで、ノード1と2とで構成するサブネットワークと、ノード4と5とで構成するサブネットワークに分割されることを確認する。ネットワークがサブネットワークに分割された状態は、1つのサブネットワークのいずれかのノードから、他のサブネットワークのいずれかのノードへのリンクが1つも存在しない状態である。取り除いたノード3は、分割によりできたノード1と2とで構成するサブネットワークと、ノード4と5とで構成するサブネットワークとのバウンダリの役割を担うノードである。そこで、コミュニティ構造検出装置10は、取り除いたノード3がノード1と2との隣接ノードであると判断し、ノード1、2、3で構成するコミュニティを特定する。同様にしてノード3,4,5で構成するコミュニティを特定する。手順4コミュニティ構造検出装置10は、ノード1、2,3,4,5で構成する分割前のネットワークの密度を計算すると0.6になる。コミュニティの密度は、コミュニティを構成するノード間に実在するリンク数、本例の場合6を、コミュニティを構成するノード間で論理的にとり得る最大のリンク数、本例の場合10で割った値である。一方、ノード3を取り除くことで得た2つのコミュニティの密度の平均値は1.0となる。これにより、コミュニティ構造検出装置10は、その2つのコミュニティを、検出したコミュニティとして提示する。上述の内容を一般的な数式で表現する。Self‐avoidingwalkの意味1ノードvをSelf‐avoidingwalkが通過する確率pは、ノードvがコミュニティ同士の接続に関わる重要度に比例2ノードsと残りの全てのノードtとのコミュニケーション情報交換を考えたときに、sとtがコミュニケーションする際のパスxstの要素に、vがなる確率p3グラフGにおいて、ノードsから始まりノードvを経由してノードtで終わるパスxistvの生成確率pxiSTv|Gの和Betweennessの一般化標準のBetweenness一般化したBetweenness一般化したBetweennessを、self‐avoidingwalkを使って具体化1の一般化したBetweennessに対して、全ページに示したself‐avoidingwalkを使って定義した項2、3、4を代入。図5は、本発明の一実施形態に係るコミュニティ構造検出装置10の機能構成を示す機能ブロック図である。コミュニティ構造検出装置10は、訪問回数記憶手段としての訪問回数テーブル31と、SAW実行手段11と、全ノード実行手段12と、重要度算出手段13と、ノード除去手段14と、分割判別手段15と、バウンダリノード特定手段16と、コミュニティ検出手段17と、を備える。図6は、本発明の一実施形態に係るコミュニティ構造検出装置10が、図1とは別のネットワークについてコミュニティを検出する例を示す図である。図7は、図6における訪問回数テーブル31の例を示す図である。図8は、図6におけるコミュニティの密度を記憶する密度テーブル32の例を示す図である。以下、コミュニティ構造検出装置10が行うコミュニティ構造の検出を、図6を例として各手段ごとに詳述する。訪問回数テーブル31は、複数のノードのうち一のノードを開始ノードとして、当該開始ノードごとに前記リンクをたどってノードを訪問した回数を、前記開始ノードに対応付けたノードに記憶する。SAW実行手段11は、複数のノードのうち一のノードを開始ノードとし、当該開始ノードからSAWself-avoidingwalkによる訪問を開始し、当該SAWによる訪問の終了までを1回とし、所定の回数実行する。全ノード実行手段12は、SAW実行手段11により、複数のノードのそれぞれを開始ノードとしてSAWを実行し、各々のノードへの訪問回数を開始ノードに対応付けて訪問回数テーブル31に記憶する。具体的には、SAW実行手段11は、図61において、ノード1を開始ノードとして、例えばノード9までのSAWを1回として行い、図7に示すように訪問回数テーブル31の開始ノード1に対応付けられた訪問したノードにカウントする。次に、再びノード1を開始ノードとして、例えばノード3までノード1-ノード2-ノード4-ノード3のSAWを行い、図7に示すように訪問回数テーブル31の開始ノード1に対応付けられた訪問したノードにカウントする。このように、SAW実行手段11は、ノード1を開始ノードとするSAWを、例えば10回行い、訪問回数テーブル31に訪問回数を記憶する。そして、全ノード実行手段12は、SAW実行手段11により、図61において、ノード1を開始ノードとするSAWから、ノード9を開始ノードとするSAWまでをそれぞれ、例えば10回実行し、訪問回数テーブル31に訪問回数を記憶する。重要度算出手段13は、全ノード実行手段12によって訪問回数テーブル31に記憶されたノードの訪問回数に基づいて、各々のノードの訪問率によって示される重要度を算出する。具体的には、重要度算出手段13は、図7に示すように、ノードごとの訪問回数の合計を計算し、ノードごとの訪問回数について、全訪問回数に対する訪問率を計算し、訪問回数テーブル31の重要度に記憶させる。ノード除去手段14は、重要度算出手段13が算出した重要度が大きい順に、ノードを順次取り除く。具体的には、ノード除去手段14は、図62において、訪問回数テーブル31に基づいて、例えば重要度が最大のノード5を取り除く。分割判別手段15は、ノード除去手段14がノードを1つ取り除くごとに、ネットワークが複数のサブネットワークに分割されたか否かを判別する。具体的には、分割判別手段15は、ノード5を取り除いた場合に、ノード1からノード4のサブネットワークと、ノード6からノード9のサブネットワークとの間で、サブネットワークのノード1から、他のサブネットワークのノード6へのパスが存在するので、分割されていないと判別する。バウンダリノード特定手段16は、分割判別手段15によって分割されていないと判別された場合にノード除去手段14による除去及び分割判別手段15による判別を繰り返し、分割判別手段15によって分割されたと判別された場合に、取り除いたノードの集合をバウンダリノードの集合と特定する。具体的には、バウンダリノード特定手段16は、分割判別手段15によって分割されていないと判別された図62において、次に重要度が大きいノード6の除去と、ノード6を除去した場合の判別を繰り返す。そして、バウンダリノード特定手段16は、図63において、次に重要度の大きいノード1の除去と、ノード1を除去した場合の判別により、ノード2、3及び4のサブネットワークと、ノード7、8及び9のサブネットワークとに分割されたと判別されて、取り除いたノード5、6及び1のノードの集合をバウンダリノードの集合と特定する。コミュニティ検出手段17は、バウンダリノード特定手段16によって特定されたノードと、サブネットワークとを直接にリンクしたネットワークをコミュニティとして検出する。具体的には、コミュニティ検出手段17は、図64において、ノード2、3及び4のサブネットワークに直接にリンクするノード1及び5を加えたネットワークと、ノード7、8及び9のサブネットワークに直接にリンクするノード1及び6を加えたネットワークと、をそれぞれコミュニティC1、C2として検出する。さらに、コミュニティ検出手段17は、コミュニティ判別手段171と、コミュニティ密度計算手段172と、コミュニティ集合検出手段173とを備える。コミュニティ判別手段171は、バウンダリノード特定手段16によって特定されたバウンダリノードの集合が、当該バウンダリノードの集合を構成するノード間のリンクを介して接続されたネットワークであるか否かを判別する。具体的には、コミュニティ判別手段171は、図65において、バウンダリノードの集合がノード1、5及び6の間のリンクを介して接続されたネットワークであるか否かを判別する。そして、コミュニティ検出手段17は、コミュニティ判別手段171によってノード1、5及び6のバウンダリノードがネットワークであると判別された場合、ノード1、5及び6のバウンダリノードの集合をコミュニティC3として検出する。コミュニティ密度計算手段172は、ノード間のリンクの数に基づいてコミュニティの密度を計算する。具体的には、コミュニティ密度計算手段172は、図61においてコミュニティを構成するノード間に実在するリンク数17を、コミュニティを構成するノード間で論理的にとり得る最大のリンク数36で割り、値0.47を算出する。コミュニティ密度計算手段172は、コミュニティC1、C2、C3の密度を計算し、それぞれ1.0を算出する。コミュニティ集合検出手段173は、コミュニティを検出するごとに、コミュニティ密度計算手段172によってコミュニティの密度を計算し、検出したコミュニティの密度の平均が最大になるコミュニティの集合を検出する。具体的には、コミュニティ集合検出手段173は、図65において、コミュニティC1,C2,C3の密度の平均を計算し、1.0を算出する。このように、コミュニティ構造検出装置10は、コミュニティを検出するごとに、コミュニティの密度の平均を計算し、密度の平均が最大になるコミュニティの集合を検出し、コミュニティを検出するための分割を適切に終了することができるので、適切なコミュニティを効率よく検出することができる。このように、コミュニティ構造検出装置10は、ネットワークから適切なコミュニティを検出することができるので、例えば、コンテンツ配信ネットワークでの用途において、コンテンツの配布コストを抑制することができる。すなわち、コミュニティ構造検出装置10は、コミュニティを検出して、複数のコミュニティ間を接続する役割を担っている重要なノードノードの例としては、WebやFTPのミラーサイト等にコンテンツの複製を配置することでつまり多くのノードにとって共通の通信路となるノードにコンテンツを置くことで、コンテンツの配布コストを抑制することができる。コミュニティ構造検出装置10は、例えば、社会ネットワークでの用途において、サービス会社の良いうわさを社会ネットワークに広く伝搬させることができる。すなわち、コミュニティ構造検出装置10は、複数のコミュニティ間を接続する役割を担っている重要なユーザを見つけることで、社会ネットワークにおける重要人物を定量的に見つけ、その情報を提供することができる。提供された情報に基づいて、サービス提供装置は、優先的にサービスを施すことで、サービス会社の良いうわさを社会ネットワークに広く伝搬させることができる。コミュニティ構造検出装置10は、例えば、社会ネットワークやWebでの用途において、コミュニティを見つけて、その情報を提供することができる。提供された情報に基づいて、トレンド変化抽出装置は、そのコミュニティの規模例えば、ゴルフに興味があるユーザが集まったコミュニティのユーザ数の変化を観察することで、トレンドの変化何が流行っているか等を知ることができる。コミュニティ構造検出装置10は、例えば、インターネットでの用途において、悪意のある行為を排除するようにさせることができる。すなわち、コミュニティ構造検出装置10は、インターネットで形成される、悪意のあるユーザが複数の偽のユーザIDを使って作成したコミュニティを検出し、セキュリティーアッタックSybilattackと呼ばれるをするコミュニティをネットワークの中から同定し、その情報を提供することができる。提供された情報に基づいて、ネットワーク監視装置は、それらの行為を排除することができる。また、コミュニティ構造検出装置10は、例えば、コミュニティ構造を検索して、その検索結果に基づいてネットワークを制御するための情報を提供することができる。ネットワーク監視装置は、例えば、社会ネットワークで小規模化が進むコミュニティ構造に関する情報を、他のコミュニティに属するユーザに提供する等して、小規模化の抑制を図ることができる。本実施形態のコミュニティ構造検出装置10は、コンピュータ及びその周辺装置によって実現され、本実施形態における各部は、コンピュータ及びその周辺装置が備えるハードウェア並びに該ハードウェアを制御するソフトウェアによって構成される。本実施形態によれば、コミュニティ構造検出装置10は、複数のノードのそれぞれを開始ノードとしてSAWによる訪問を実行し、各々のノードの訪問回数を開始ノードに対応付けて訪問回数テーブル31に記憶する。次に、コミュニティ構造検出装置10は、訪問回数テーブル31に記憶されたノードの訪問回数に基づいて、各々のノードの訪問率によって示される重要度を算出し、算出した重要度が大きい順に、ノードを順次取り除き、ノードを1つ取り除くごとに、ネットワークが複数のサブネットワークに分割されたか否かを判別する。そして、コミュニティ構造検出装置10は、ネットワークが分割されていないと判別した場合に、ノードの除去及び分割の判別を繰り返し、ネットワークに分割されたと判別した場合に、取り除いたノードの集合をバウンダリノードの集合と特定し、特定したノードと、サブネットワークとを直接にリンクしたネットワークをコミュニティとして検出する。さらに、コミュニティ構造検出装置10は、バウンダリノードの集合が、当該バウンダリノードの集合を構成するノード間のリンクを介して接続されたネットワークであるか否かを判別し、ネットワークであると判別した場合、コミュニティとして検出し、コミュニティを検出するごとに、コミュニティの密度を計算し、検出したコミュニティの密度の平均が最大になるコミュニティの集合を検出する。したがって、コミュニティ構造検出装置10は、既存のアルゴリズムに比べ少ない計算量で、適切なコミュニティを効率よく検出することができる。以上、本発明の実施形態について説明したが、本発明は上述した実施形態に限るものではない。また、本発明の実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本発明の実施形態に記載されたものに限定されるものではない。"