(57)【要約】      （修正有）【課題】既存のアルゴリズムに比べ少ない計算量で、適切なコミュニティを効率よく検出できるコミュニティ構造検出装置及び方法を提供する。【解決手段】コミュニティ構造検出装置は、複数のノードのそれぞれを開始ノードとしてＳＡＷによる訪問を実行し、各々のノードへの訪問回数を開始ノードに対応付けて訪問回数テーブルに記憶する。次に、訪問回数テーブルに記憶されたノードの訪問回数に基づいて、各々のノードの重要度を算出し、算出した重要度が大きい順に、ノードを順次取り除き、複数のサブネットワークに分割されたか否かを判別する。そして、コミュニティ構造検出装置は、ノードの除去及び分割の判別を繰り返し、ネットワークに分割されたと判別した場合に、取り除いたノードと、サブネットワークとを直接にリンクしたネットワークをコミュニティとして検出する。【選択図】図１
2012216943.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードがリンクを介して接続されたネットワークにおけるコミュニティ構造を検出するコミュニティ構造検出装置あって、
前記複数のノードのうち一のノードを開始ノードとし、当該開始ノードからＳＡＷ（ｓｅｌｆ−ａｖｏｉｄｉｎｇ  ｗａｌｋ）による訪問を開始し、当該ＳＡＷによる訪問の終了までを１回とし、所定の回数実行するＳＡＷ実行手段と、
前記ＳＡＷ実行手段により、前記複数のノードのそれぞれを開始ノードとして前記ＳＡＷを実行し、各々のノードへの訪問回数を前記開始ノードに対応付けて訪問回数記憶手段に記憶する全ノード実行手段と、
前記全ノード実行手段によって前記訪問回数記憶手段に記憶されたノードの訪問回数に基づいて、各々のノードの訪問率によって示される重要度を算出する重要度算出手段と、
前記重要度算出手段が算出した重要度が大きい順に、ノードを順次取り除くノード除去手段と、
前記ノード除去手段がノードを１つ取り除くごとに、前記ネットワークが複数のサブネットワークに分割されたか否かを判別する分割判別手段と、
前記分割判別手段によって分割されていないと判別された場合に前記ノード除去手段による除去及び前記分割判別手段による判別を繰り返し、前記分割判別手段によって分割されたと判別された場合に、前記取り除いたノードの集合をバウンダリノードの集合と特定するバウンダリノード特定手段と、
前記バウンダリノード特定手段によって特定されたノードと、前記サブネットワークとを直接にリンクしたネットワークをコミュニティとして検出するコミュニティ検出手段と、
を備えるコミュニティ構造検出装置。
【請求項２】
前記コミュニティ検出手段は、
前記バウンダリノード特定手段によって特定されたバウンダリノードの集合が、当該バウンダリノードの集合を構成するノード間のリンクを介して接続されたネットワークであるか否かを判別するコミュニティ判別手段をさらに備え、前記コミュニティ判別手段によって、前記特定されたバウンダリノードの集合がネットワークであると判別された場合、そのネットワークをコミュニティとして検出する、請求項１に記載のコミュニティ構造検出装置。
【請求項３】
前記コミュニティ検出手段は、
ノード間のリンクの数に基づいてコミュニティの密度を計算するコミュニティ密度計算手段と、
コミュニティを検出するごとに、前記コミュニティ密度計算手段によってコミュニティの密度を計算し、検出したコミュニティの密度の平均が最大になるコミュニティの集合を検出するコミュニティ集合検出手段と、をさらに備える、請求項１又は２に記載のコミュニティ構造検出装置。
【請求項４】
複数のノードがリンクを介して接続されたネットワークにおけるコミュニティ構造を検出するコミュニティ構造検出装置が実行する方法あって、
前記複数のノードのうち一のノードを開始ノードとし、当該開始ノードからＳＡＷ（ｓｅｌｆ−ａｖｏｉｄｉｎｇ  ｗａｌｋ）による訪問を開始し、当該ＳＡＷによる訪問の終了までを１回とし、所定の回数実行するＳＡＷ実行ステップにより、前記複数のノードのそれぞれを開始ノードとして前記ＳＡＷを実行し、各々のノードへの訪問回数を前記開始ノードに対応付けて訪問回数記憶手段に記憶する全ノード実行ステップと、
前記全ノード実行ステップによって前記訪問回数記憶手段に記憶されたノードの訪問回数に基づいて、各々のノードの訪問率によって示される重要度を算出する重要度算出ステップと、
前記重要度算出ステップが算出した重要度が大きい順に、ノードを順次取り除くノード除去ステップと、
前記ノード除去ステップがノードを１つ取り除くごとに、前記ネットワークが複数のサブネットワークに分割されたか否かを判別する分割判別ステップと、
前記分割判別ステップによって分割されていないと判別された場合に前記ノード除去ステップによる除去及び前記分割判別ステップによる判別を繰り返し、前記分割判別ステップによって分割されたと判別された場合に、前記取り除いたノードの集合をバウンダリノードの集合と特定するバウンダリノード特定ステップと、
前記バウンダリノード特定ステップによって特定されたノードと、前記サブネットワークとを直接にリンクしたネットワークをコミュニティとして検出するコミュニティ検出ステップと、
を備える方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク中に存在するコミュニティ構造を検出する技術に関する。
【背景技術】
【０００２】
従来より、人間関係を表した社会ネットワークにおいて、一般に形成されるネットワークを同定することで、誰がどのネットワークに属しているかを知ることができる。そして、そのネットワークに相応しい情報やサービスを提供することで、そのネットワークに属する個人が満足するような情報やサービスを提供することが可能になる。また社会ネットワークの複数ネットワーク間の関係を同定することができれば、それらの勢力関係の理解やネットワークの発生理由の解明等が可能になる。
【０００３】
このようなネットワークや、ネットワーク中に存在するコミュニティの構造を同定するための方法が数多く提案されている。例えば、特許文献１には、転送されるメッセージを利用して各ノードが分散的に処理を実行して、ネットワークの運用中にコミュニティ構造を検出する技術が開示されている。また、非特許文献１には、ノードとノードとの間のリンクをたどり、コミュニティを検出する方法が記載されている。非特許文献２には、ネットワークの媒介中心性（ｂｅｔｗｅｅｎｎｅｓｓ）をコミュニティ間の接続に関するノードの重要度として用いる方法が記載されている。非特許文献３には、コミュニティの特徴となるパラメタ（ｋ−ｃｌｉｑｕｅ  ｃｏｍｍｕｎｉｔｙのｋの値）を指定して、コミュニティを検索する方法が記載されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１０−１４１４４２号公報
【非特許文献】
【０００５】
【非特許文献１】Ｍ．Ｎｅｗｍａｎ  ｅｔ  ａｌ．，“Ｆｉｎｄｉｎｇ  ａｎｄ  ｅｖａｌｕａｔｉｎｇ  ｃｏｍｍｕｎｉｔｙ  ｓｔｒｕｃｔｕｒｅ  ｉｎ  ｎｅｔｗｏｒｋｓ，”Ｐｈｙｓｉｃａｌ  Ｒｅｖｉｅｗ  Ｅ，６９，０２６１１３，２００４．
【非特許文献２】Ｓｔｅｖｅ  Ｇｒｅｇｏｒｙ，”Ａｎ  Ａｌｇｏｒｉｔｈｍ  ｔｏ  Ｆｉｎｄ  Ｏｖｅｒｌａｐｐｉｎｇ  Ｃｏｍｍｕｎｉｔｙ  Ｓｔｒｕｃｔｕｒｅ  ｉｎ  Ｎｅｔｗｏｒｋｓ，”Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １１ｔｈ  Ｅｕｒｏｐｅａｎ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｐｒｉｎｃｉｐｌｅｓ  ａｎｄ  Ｐｒａｃｔｉｃｅ  ｏｆ  Ｋｎｏｗｌｅｄｇｅ  Ｄｉｓｃｏｖｅｒｙ  ｉｎ  Ｄａｔａｂａｓｅｓ，２００７．
【非特許文献３】Ｇｅｒｇｅｌｙ  Ｐａｌｌａ  ｅｔ  ａｌ．，“Ｕｎｃｏｖｅｒｉｎｇ  ｔｈｅ  ｏｖｅｒｌａｐｐｉｎｇ  ｃｏｍｍｕｎｉｔｙ  ｓｔｒｕｃｔｕｒｅ  ｏｆ  ｃｏｍｐｌｅｘ  ｎｅｔｗｏｒｋｓ  ｉｎ  ｎａｔｕｒｅ  ａｎｄ  ｓｏｃｉｅｔｙ，”Ｎａｔｕｒｅ  ４３５，ｐｐ．８１４−８１８，９  Ｊｕｎｅ  ２００５．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献１に記載された技術は、ノードが複数のコミュニティにオーバーラップして所属することがありうるコミュニティを検出することができなかった。
【０００７】
また、非特許文献２は、ネットワークの媒介中心性（ｂｅｔｗｅｅｎｎｅｓｓ）をコミュニティ間の接続に関するノードの重要度（もしくは複数のコミュニティにオーバーラップしている可能性の高さの指標）として用いる。例えば、媒介中心性が最大のノードを１つ１つ取り除いてコミュニティを求める場合、取り除くことでできる新たなネットワークトポロジーごとに、媒介中心性を再計算する必要がある。また、取り除くノードの順番によっては、当初のネットワークでは媒介中心性が大きいノードであっても、そのノードの周辺のノードが取り除かれることで媒介中心性が小さくなってしまう場合がある。例えば、図９（１）において、ノード１を取り除くと、ノード７の媒介中心性が小さくなる。このようなノードは、オーバーラップしているノードとして見なされず、例えば、図９（２）、図９（３）のようにノード１２、ノード７の順に取り除かれる対象となる場合があり、図９（４）のようにオーバーラップするコミュニティを正しく検出することができなくなってしまう場合がある。また、図１０（１）から図１０（３）のように、最短パスを構成するノードを取り除く対象とした場合、図１０（４）のように、ノード１とノード５とのネットワークをコミュニティとして検出してしまう場合があった。
【０００８】
非特許文献３に記載された技術は、コミュニティを検索するために、コミュニティの特徴となるパラメタ（ｋ−ｃｌｉｑｕｅ  ｃｏｍｍｕｎｉｔｙのｋの値）を指定する必要がある。このため、１回の検索で適切なパラメタを、コミュニティを検索する前に指定することは困難であった。そのためパラメタの値を変えて検索を数回実行する必要があり、検索時間を要した。
【０００９】
そこで、既存のアルゴリズムに比べ少ない計算量で、適切なコミュニティを検出できる装置が求められている。
【００１０】
本発明は、既存のアルゴリズムに比べ少ない計算量で、適切なコミュニティを効率よく検出できるコミュニティ構造検出装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明は、ネットワークに存在する構造を検索する手法を提供する。ネットワークに存在する構造とは、一般的にはモジュールもしくはコミュニティと呼ばれ、具体的には、ノードが同じコミュニティのノードとはリンクを多く持ち、ネットワークの残りのノードとのリンクは少ないという特徴を持ったノード集合をいう。本発明では、各ノードがコミュニティ間を接続するバウンダリとなっている度合の観点からの、ノードの重要度を導入し、バウンダリとなっているノードを特定することでコミュニティを検索可能とするものである。具体的には、以下のような解決手段を提供する。
【００１２】
（１）  複数のノードがリンクを介して接続されたネットワークにおけるコミュニティ構造を検出するコミュニティ構造検出装置あって、前記複数のノードのうち一のノードを開始ノードとし、当該開始ノードからＳＡＷ（ｓｅｌｆ−ａｖｏｉｄｉｎｇ  ｗａｌｋ）による訪問を開始し、当該ＳＡＷによる訪問の終了までを１回とし、所定の回数実行するＳＡＷ実行手段と、前記ＳＡＷ実行手段により、前記複数のノードのそれぞれを開始ノードとして前記ＳＡＷを実行し、各々のノードへの訪問回数を前記開始ノードに対応付けて訪問回数記憶手段に記憶する全ノード実行手段と、前記複数のノードのうち一のノードを開始ノードとして、当該開始ノードごとに前記リンクをたどってノードを訪問した回数を、前記開始ノードに対応付けたノードに記憶する訪問回数記憶手段と、前記開始ノードからＳＡＷ（ｓｅｌｆ−ａｖｏｉｄｉｎｇ  ｗａｌｋ）による訪問を開始し、前記ＳＡＷによる訪問の終了までを所定の回数行い、前記ＳＡＷによってノードを訪問するたびに、前記訪問回数記憶手段において前記開始ノードに対応付けられた訪問したノードにカウントして訪問回数を記憶させるＳＡＷ実行手段と、前記ＳＡＷ実行手段による訪問を、前記複数のノードのそれぞれを開始ノードとして行う全ノード実行手段と、前記全ノード実行手段によって前記訪問回数記憶手段に記憶されたノードの訪問回数に基づいて、各々のノードの訪問率によって示される重要度を算出する重要度算出手段と、前記重要度算出手段が算出した重要度が大きい順に、ノードを順次取り除くノード除去手段と、前記ノード除去手段がノードを１つ取り除くごとに、前記ネットワークが複数のサブネットワークに分割されたか否かを判別する分割判別手段と、前記分割判別手段によって分割されていないと判別された場合に前記ノード除去手段による除去及び前記分割判別手段による判別を繰り返し、前記分割判別手段によって分割されたと判別された場合に、前記取り除いたノードの集合をバウンダリノードの集合と特定するバウンダリノード特定手段と、前記バウンダリノード特定手段によって特定されたノードと、前記サブネットワークとを直接にリンクしたネットワークをコミュニティとして検出するコミュニティ検出手段と、を備えるコミュニティ構造検出装置。
【００１３】
（１）の構成によれば、本発明に係るコミュニティ構造検出装置は、複数のノードのそれぞれを開始ノードとしてＳＡＷ（ｓｅｌｆ−ａｖｏｉｄｉｎｇ  ｗａｌｋ）による訪問を実行し、各々のノードへの訪問回数を開始ノードに対応付けて訪問回数記憶手段に記憶する。次に、訪問回数記憶手段に記憶されたノードの訪問回数に基づいて、各々のノードの訪問率によって示される重要度を算出し、算出した重要度が大きい順に、ノードを順次取り除き、ノードを１つ取り除くごとに、ネットワークが複数のサブネットワークに分割されたか否かを判別する。そして、コミュニティ構造検出装置は、ネットワークが分割されていないと判別した場合に、ノードの除去及び分割の判別を繰り返し、ネットワークに分割されたと判別した場合に、取り除いたノードの集合をバウンダリノードの集合と特定し、特定したノードと、サブネットワークとを直接にリンクしたネットワークをコミュニティとして検出する。
【００１４】
すなわち、本発明に係るコミュニティ構造検出装置は、コミュニティ同士の接続に関する各ノードの重要度を計算し、計算したノードの重要度が大きい順にノードを仮想的にネットワークから取り除くことでコミュニティが他のコミュニティと交わるバウンダリの役割を担うノード集合を特定し、特定したバウンダリのノード集合を使って、ネットワーク内のコミュニティを検出する。
具体的には、コミュニティ構造検出装置は、コミュニティ同士の接続に関する各ノードの重要度を計算するために、仮想的に、各ノードから開始したｓｅｌｆ−ａｖｏｉｄｉｎｇ  ｗａｌｋ（自身とリンクで接続されている隣接ノードを、次回の訪問先ノードとしてランダムに選択し、他のノードを順次訪問すること。ただし既に訪問したノードは次回訪問先としては選ばない。以下、ＳＡＷという）を数回行う。
そして、自身及び他のノードから開始したＳＡＷによって、各ノードを訪問した回数の合計値を計算し、全てのＳＡＷの実施回数を使って訪問回数の合計値を正規化し、正規化した値をノードの重要度とする。
さらに、コミュニティ構造検出装置は、ネットワークからノードの重要度が大きい順にノードを１つ取り除き、取り除くたびに連結なネットワーク（各ノードが他の全てのノードに至るパスがあるネットワーク）が複数のサブネットワークに分割されたか否かを確認する。ここで、サブネットワークに分割されている状態とは、１つのサブネットワークのいずれかのノードから、他のサブネットワークのいずれかのノードへのパスが存在しない状態をいう。
分割されたことが確認された場合、サブネットワーク間を接続するバウンダリの役割を担うノードを、既に取り除いたノードの中から特定し、サブネットワークとそのバウンダリの役割を担うノードで構成するコミュニティを特定する。
したがって、本発明に係るコミュニティ構造検出装置は、既存のアルゴリズムに比べ少ない計算量で、適切なコミュニティを効率よく検出することができる。
【００１５】
（２）  前記コミュニティ検出手段は、前記バウンダリノード特定手段によって特定されたバウンダリノードの集合が、当該バウンダリノードの集合を構成するノード間のリンクを介して接続されたネットワークであるか否かを判別するコミュニティ判別手段をさらに備え、前記コミュニティ判別手段によって、前記特定されたバウンダリノードの集合がネットワークであると判別された場合、そのネットワークをコミュニティとして検出する、（１）に記載のコミュニティ構造検出装置。
【００１６】
すなわち、（２）のコミュニティ構造検出装置は、ネットワークからノードの重要度が大きい順にノードを１つ取り除くたびに、２ノード以上の取り除いたノードのみで構成するサブネットワークの存在有無を確認し、そのようなサブネットワークが存在する場合は、そのサブネットワークをコミュニティとして特定する。
したがって、（２）に係るコミュニティ構造検出装置は、適切なコミュニティをさらに検出することができる。
【００１７】
（３）  前記コミュニティ検出手段は、ノード間のリンクの数に基づいてコミュニティの密度を計算するコミュニティ密度計算手段と、コミュニティを検出するごとに、前記コミュニティ密度計算手段によってコミュニティの密度を計算し、検出したコミュニティの密度の平均が最大になるコミュニティの集合を検出するコミュニティ集合検出手段と、をさらに備える、（１）又は（２）に記載のコミュニティ構造検出装置。
【００１８】
すなわち、（３）に係るコミュニティ構造検出装置は、ネットワークからノードの重要度が大きい順にノードを順次取り除いて、より小規模なサブネットワークに分割さていくそれぞれの段階で、コミュニティの密度（コミュニティを構成するノード間に実在するリンク数を、コミュニティを構成するノード間で論理的にとり得る最大のリンク数で割った値）を計算し、コミュニティの密度の平均値が最大となる段階のコミュニティの集合を検出して提示する。
したがって、（３）に係るコミュニティ構造検出装置は、適切な分割によるコミュニティを検出することができる。
【００１９】
（４）  複数のノードがリンクを介して接続されたネットワークにおけるコミュニティ構造を検出するコミュニティ構造検出装置が実行する方法あって、前記複数のノードのうち一のノードを開始ノードとし、当該開始ノードからＳＡＷ（ｓｅｌｆ−ａｖｏｉｄｉｎｇ  ｗａｌｋ）による訪問を開始し、当該ＳＡＷによる訪問の終了までを１回とし、所定の回数実行するＳＡＷ実行ステップにより、前記複数のノードのそれぞれを開始ノードとして前記ＳＡＷを実行し、各々のノードへの訪問回数を前記開始ノードに対応付けて訪問回数記憶手段に記憶する全ノード実行ステップと、前記全ノード実行ステップによって前記訪問回数記憶手段に記憶されたノードの訪問回数に基づいて、各々のノードの訪問率によって示される重要度を算出する重要度算出ステップと、前記重要度算出ステップが算出した重要度が大きい順に、ノードを順次取り除くノード除去ステップと、前記ノード除去ステップがノードを１つ取り除くごとに、前記ネットワークが複数のサブネットワークに分割されたか否かを判別する分割判別ステップと、前記分割判別ステップによって分割されていないと判別された場合に前記ノード除去ステップによる除去及び前記分割判別ステップによる判別を繰り返し、前記分割判別ステップによって分割されたと判別された場合に、前記取り除いたノードの集合をバウンダリノードの集合と特定するバウンダリノード特定ステップと、前記バウンダリノード特定ステップによって特定されたノードと、前記サブネットワークとを直接にリンクしたネットワークをコミュニティとして検出するコミュニティ検出ステップと、を備える方法。
【００２０】
したがって、（４）に係る方法は、（１）と同様に、既存のアルゴリズムに比べ少ない計算量で、適切なコミュニティを効率よく検出することができる。
【発明の効果】
【００２１】
本発明によれば、既存のアルゴリズムに比べ少ない計算量で、適切なコミュニティを効率よく検出できるコミュニティ構造検出装置及び方法を提供することができる。
さらに、本発明は、社会ネットワークやインターネット等のネットワーク中に存在するコミュニティ構造を分散的に検索する機能を提供することができる。
【図面の簡単な説明】
【００２２】
【図１】本発明の一実施形態におけるコミュニティ構造検出装置がコミュニティ構造を検出することを説明する図である。
【図２】図１において、コミュニティ構造検出装置がコミュニティを提示する手順について説明する図である。
【図３】本発明の一実施形態に係る訪問回数テーブルの例を示す図である。
【図４】本発明の一実施形態に係るコミュニティ構造検出装置が、図１のネットワークからコミュニティを検出する過程の例を示す図である。
【図５】本発明の一実施形態に係るコミュニティ構造検出装置の機能構成を示す機能ブロック図である。
【図６】本発明の一実施形態に係るコミュニティ構造検出装置が、図１とは別のネットワークについてコミュニティを検出する例を示す図である。
【図７】図６における訪問回数テーブルの例を示す図である。
【図８】図６におけるコミュニティの密度を記憶する密度テーブルの例を示す図である。
【図９】従来のノードｂｅｔｗｅｅｎｎｅｓｓの例を示す図である。
【図１０】従来のノードｂｅｔｗｅｅｎｎｅｓｓ（最短パス）の例を示す図である。
【発明を実施するための形態】
【００２３】
以下、本発明の実施形態について図を参照しながら説明する。
【００２４】
図１は、本発明の一実施形態におけるコミュニティ構造検出装置１０がコミュニティ構造を検出することを説明する図である。図１のように、ノードの識別子が１、２、３、４、５の５つのノードで構成するネットワークを例に説明する。この例ではリンクＬ１〜Ｌ６に方向はなく、ノード１はノード２、３とリンクＬ１、Ｌ２を持ち、ノード２はノード１、３とリンクＬ１、Ｌ３を持ち、ノード３はノード１、２、４、５とリンクＬ２、Ｌ３、Ｌ４、Ｌ５を持ち、ノード４はノード３、５とリンクＬ４、Ｌ６を持ち、ノード５はノード３、４とリンクＬ５、Ｌ６を持つものとする。この例では、ネットワークには２つのコミュニティが存在する。１つ目はノード１、２、３で構成するコミュニティＣ１であり、２つ目はノード３、４、５で構成するコミュニティＣ２である。ノード３は、コミュニティＣ１とコミュニティＣ２とを接続する役割を担い、２つのコミュニティにオーバーラップしているノードとなる。
【００２５】
図２は、図１において、コミュニティ構造検出装置１０がコミュニティを提示する手順について説明する図である。図３は、本発明の一実施形態に係る訪問回数テーブル３１の例を示す図である。図４は、本発明の一実施形態に係るコミュニティ構造検出装置１０が、図１のネットワークからコミュニティを検出する過程の例を示す図である。
【００２６】
手順１）コミュニティ構造検出装置１０は、各ノードから開始するｓｅｌｆ−ａｖｏｉｄｉｎｇ  ｗａｌｋ（以下、ＳＡＷという）を１０回実行する。一のノードから他のノードを訪問するＳＡＷは、自身とリンクで接続されている隣接ノードを、次回の訪問先ノードとしてランダムに選択し、他のノードを順次訪問する。ただし既に訪問したノードは次回訪問先としては選ばない。
例えばノード１から開始するＳＡＷの１回目は、ノード１の隣接ノード２と３との中から無作為に（それぞれ１／２の確率で）１つのノードを選び、それが例えばノード３だとすると、ノード３に進み、次にノード３の隣接ノード（ただし既に訪問しているノード１を除く）となるノード２、４、５の中から無作為に（それぞれ１／３の確率で）ノードを１つ選び、それが例えばノード２だとすると、ノード２に進み、ノード２の隣接ノードには未だ訪問していないノードは存在しないことからノード２でＳＡＷを停止する。同様にして、ノード１から開始するＳＡＷを残り９回実行する。同様にして、他のノードから開始するＳＡＷをそれぞれ１０回実行する。
【００２７】
手順２）コミュニティ構造検出装置１０は、全てのＳＡＷの実行を通じて、各ノードを訪問した回数を合計する。例えば、ノード２であれば、ノード１から開始したＳＡＷを１０回実行した中で訪問があった６回、ノード２から開始したＳＡＷを１０回実行した中で訪問があった１０回、ノード３から開始したＳＡＷを１０回実行した中で訪問があった５回、ノード４から開始したＳＡＷを１０回実行した中で訪問があった８回、ノード５から開始したＳＡＷを１０回実行した中で訪問があった８回、の合計（６＋１０＋５＋８＋８）を、全ＳＡＷの実行回数となる５０で割り、割った値を、コミュニティ同士の接続に関するノード２の重要度を表す指標とする。
このようなＳＡＷによる訪問回数を、訪問回数テーブル３１は、図３のように記憶している。
【００２８】
手順３）コミュニティ構造検出装置１０は、重要度が最大のノード３をネットワークから仮想的に取り除き、ネットワークがサブネットワークに分割されるか否かを確認する。図４（１）で示されるノード１、２、３、４、５で構成するネットワークは、図４（２）に示すように、ノード３を取り除くことで、ノード１と２とで構成するサブネットワークと、ノード４と５とで構成するサブネットワークに分割されることを確認する。ネットワークがサブネットワークに分割された状態は、１つのサブネットワークのいずれかのノードから、他のサブネットワークのいずれかのノードへのリンクが１つも存在しない状態である。
取り除いたノード３は、分割によりできたノード１と２とで構成するサブネットワークと、ノード４と５とで構成するサブネットワークとのバウンダリの役割を担うノードである。そこで、コミュニティ構造検出装置１０は、取り除いたノード３がノード１と２との隣接ノードであると判断し、ノード１、２、３で構成するコミュニティを特定する。同様にしてノード３，４，５で構成するコミュニティを特定する。
【００２９】
手順４）コミュニティ構造検出装置１０は、ノード１、２，３，４，５で構成する分割前のネットワークの密度を計算すると０．６になる。コミュニティの密度は、コミュニティを構成するノード間に実在するリンク数、本例の場合６を、コミュニティを構成するノード間で論理的にとり得る最大のリンク数、本例の場合１０で割った値である。
一方、ノード３を取り除くことで得た２つのコミュニティの密度の平均値は１．０となる。これにより、コミュニティ構造検出装置１０は、その２つのコミュニティを、検出したコミュニティとして提示する。
【００３０】
上述の内容を一般的な数式で表現する。
【００３１】
Ｓｅｌｆ‐ａｖｏｉｄｉｎｇ  ｗａｌｋの意味
（１）ノードｖをＳｅｌｆ‐ａｖｏｉｄｉｎｇ  ｗａｌｋが通過する確率ｐは、ノードｖがコミュニティ同士の接続に関わる重要度に比例
（２）ノードｓと残りの全てのノードｔとのコミュニケーション（情報交換）を考えたときに、ｓとｔがコミュニケーションする際のパスｘｓｔの要素に、ｖがなる確率ｐ
（３）グラフＧにおいて、ノードｓから始まりノードｖを経由してノードｔで終わるパスｘｉｓｔ（ｖ）の生成確率ｐ（ｘｉＳＴ（ｖ）｜Ｇ）の和
【００３２】
Ｂｅｔｗｅｅｎｎｅｓｓの一般化
標準のＢｅｔｗｅｅｎｎｅｓｓ
【数１】
2012216943.tif 000003
【００３３】
一般化したＢｅｔｗｅｅｎｎｅｓｓ
【数２】
2012216943.tif 000004
【００３４】
一般化したＢｅｔｗｅｅｎｎｅｓｓを、ｓｅｌｆ‐ａｖｏｉｄｉｎｇ  ｗａｌｋを使って具体化
【数３】
2012216943.tif 000005
【００３５】
（１）の一般化したＢｅｔｗｅｅｎｎｅｓｓに対して、全ページに示したｓｅｌｆ‐ａｖｏｉｄｉｎｇ  ｗａｌｋを使って定義した項（２）、（３）、（４）を代入。
【数４】
2012216943.tif 000006
【００３６】
図５は、本発明の一実施形態に係るコミュニティ構造検出装置１０の機能構成を示す機能ブロック図である。コミュニティ構造検出装置１０は、訪問回数記憶手段としての訪問回数テーブル３１と、ＳＡＷ実行手段１１と、全ノード実行手段１２と、重要度算出手段１３と、ノード除去手段１４と、分割判別手段１５と、バウンダリノード特定手段１６と、コミュニティ検出手段１７と、を備える。図６は、本発明の一実施形態に係るコミュニティ構造検出装置１０が、図１とは別のネットワークについてコミュニティを検出する例を示す図である。図７は、図６における訪問回数テーブル３１の例を示す図である。図８は、図６におけるコミュニティの密度を記憶する密度テーブル３２の例を示す図である。以下、コミュニティ構造検出装置１０が行うコミュニティ構造の検出を、図６を例として各手段ごとに詳述する。
【００３７】
訪問回数テーブル３１は、複数のノードのうち一のノードを開始ノードとして、当該開始ノードごとに前記リンクをたどってノードを訪問した回数を、前記開始ノードに対応付けたノードに記憶する。
【００３８】
ＳＡＷ実行手段１１は、複数のノードのうち一のノードを開始ノードとし、当該開始ノードからＳＡＷ（ｓｅｌｆ−ａｖｏｉｄｉｎｇ  ｗａｌｋ）による訪問を開始し、当該ＳＡＷによる訪問の終了までを１回とし、所定の回数実行する。全ノード実行手段１２は、ＳＡＷ実行手段１１により、複数のノードのそれぞれを開始ノードとしてＳＡＷを実行し、各々のノードへの訪問回数を開始ノードに対応付けて訪問回数テーブル３１に記憶する。
具体的には、ＳＡＷ実行手段１１は、図６（１）において、ノード１を開始ノードとして、例えばノード９までのＳＡＷを１回として行い、図７に示すように訪問回数テーブル３１の開始ノード１に対応付けられた訪問したノードにカウントする。次に、再びノード１を開始ノードとして、例えばノード３まで（ノード１−ノード２−ノード４−ノード３）のＳＡＷを行い、図７に示すように訪問回数テーブル３１の開始ノード１に対応付けられた訪問したノードにカウントする。このように、ＳＡＷ実行手段１１は、ノード１を開始ノードとするＳＡＷを、例えば１０回行い、訪問回数テーブル３１に訪問回数を記憶する。そして、全ノード実行手段１２は、ＳＡＷ実行手段１１により、図６（１）において、ノード１を開始ノードとするＳＡＷから、ノード９を開始ノードとするＳＡＷまでをそれぞれ、例えば１０回実行し、訪問回数テーブル３１に訪問回数を記憶する。
【００３９】
重要度算出手段１３は、全ノード実行手段１２によって訪問回数テーブル３１に記憶されたノードの訪問回数に基づいて、各々のノードの訪問率によって示される重要度を算出する。具体的には、重要度算出手段１３は、図７に示すように、ノードごとの訪問回数の合計を計算し、ノードごとの訪問回数について、全訪問回数に対する訪問率を計算し、訪問回数テーブル３１の重要度に記憶させる。
【００４０】
ノード除去手段１４は、重要度算出手段１３が算出した重要度が大きい順に、ノードを順次取り除く。具体的には、ノード除去手段１４は、図６（２）において、訪問回数テーブル３１に基づいて、例えば重要度が最大のノード５を取り除く。
【００４１】
分割判別手段１５は、ノード除去手段１４がノードを１つ取り除くごとに、ネットワークが複数のサブネットワークに分割されたか否かを判別する。具体的には、分割判別手段１５は、ノード５を取り除いた場合に、ノード１からノード４のサブネットワークと、ノード６からノード９のサブネットワークとの間で、サブネットワークのノード１から、他のサブネットワークのノード６へのパスが存在するので、分割されていないと判別する。
【００４２】
バウンダリノード特定手段１６は、分割判別手段１５によって分割されていないと判別された場合にノード除去手段１４による除去及び分割判別手段１５による判別を繰り返し、分割判別手段１５によって分割されたと判別された場合に、取り除いたノードの集合をバウンダリノードの集合と特定する。具体的には、バウンダリノード特定手段１６は、分割判別手段１５によって分割されていないと判別された図６（２）において、次に重要度が大きいノード６の除去と、ノード６を除去した場合の判別を繰り返す。そして、バウンダリノード特定手段１６は、図６（３）において、次に重要度の大きいノード１の除去と、ノード１を除去した場合の判別により、ノード２、３及び４のサブネットワークと、ノード７、８及び９のサブネットワークとに分割されたと判別されて、取り除いたノード５、６及び１のノードの集合をバウンダリノードの集合と特定する。
【００４３】
コミュニティ検出手段１７は、バウンダリノード特定手段１６によって特定されたノードと、サブネットワークとを直接にリンクしたネットワークをコミュニティとして検出する。具体的には、コミュニティ検出手段１７は、図６（４）において、ノード２、３及び４のサブネットワークに直接にリンクするノード１及び５を加えたネットワークと、ノード７、８及び９のサブネットワークに直接にリンクするノード１及び６を加えたネットワークと、をそれぞれコミュニティＣ１、Ｃ２として検出する。
さらに、コミュニティ検出手段１７は、コミュニティ判別手段１７１と、コミュニティ密度計算手段１７２と、コミュニティ集合検出手段１７３とを備える。
【００４４】
コミュニティ判別手段１７１は、バウンダリノード特定手段１６によって特定されたバウンダリノードの集合が、当該バウンダリノードの集合を構成するノード間のリンクを介して接続されたネットワークであるか否かを判別する。具体的には、コミュニティ判別手段１７１は、図６（５）において、バウンダリノードの集合がノード１、５及び６の間のリンクを介して接続されたネットワークであるか否かを判別する。そして、コミュニティ検出手段１７は、コミュニティ判別手段１７１によってノード１、５及び６のバウンダリノードがネットワークであると判別された場合、ノード１、５及び６のバウンダリノードの集合をコミュニティＣ３として検出する。
【００４５】
コミュニティ密度計算手段１７２は、ノード間のリンクの数に基づいてコミュニティの密度を計算する。具体的には、コミュニティ密度計算手段１７２は、図６（１）においてコミュニティを構成するノード間に実在するリンク数１７を、コミュニティを構成するノード間で論理的にとり得る最大のリンク数３６で割り、値０．４７を算出する。コミュニティ密度計算手段１７２は、コミュニティＣ１、Ｃ２、Ｃ３の密度を計算し、それぞれ１．０を算出する。
【００４６】
コミュニティ集合検出手段１７３は、コミュニティを検出するごとに、コミュニティ密度計算手段１７２によってコミュニティの密度を計算し、検出したコミュニティの密度の平均が最大になるコミュニティの集合を検出する。具体的には、コミュニティ集合検出手段１７３は、図６（５）において、コミュニティＣ１，Ｃ２，Ｃ３の密度の平均を計算し、１．０を算出する。このように、コミュニティ構造検出装置１０は、コミュニティを検出するごとに、コミュニティの密度の平均を計算し、密度の平均が最大になるコミュニティの集合を検出し、コミュニティを検出するための分割を適切に終了することができるので、適切なコミュニティを効率よく検出することができる。
【００４７】
このように、コミュニティ構造検出装置１０は、ネットワークから適切なコミュニティを検出することができるので、例えば、コンテンツ配信ネットワークでの用途において、コンテンツの配布コストを抑制することができる。すなわち、コミュニティ構造検出装置１０は、コミュニティを検出して、複数のコミュニティ間を接続する役割を担っている重要なノード（ノードの例としては、ＷｅｂやＦＴＰのミラーサイト等）にコンテンツの複製を配置することで（つまり多くのノードにとって共通の通信路となるノードにコンテンツを置くことで）、コンテンツの配布コストを抑制することができる。
コミュニティ構造検出装置１０は、例えば、社会ネットワークでの用途において、サービス会社の良いうわさを社会ネットワークに広く伝搬させることができる。すなわち、コミュニティ構造検出装置１０は、複数のコミュニティ間を接続する役割を担っている重要なユーザを見つけることで、社会ネットワークにおける重要人物を定量的に見つけ、その情報を提供することができる。提供された情報に基づいて、サービス提供装置は、優先的にサービスを施すことで、サービス会社の良いうわさを社会ネットワークに広く伝搬させることができる。
コミュニティ構造検出装置１０は、例えば、社会ネットワークやＷｅｂでの用途において、コミュニティを見つけて、その情報を提供することができる。提供された情報に基づいて、トレンド変化抽出装置は、そのコミュニティの規模（例えば、ゴルフに興味があるユーザが集まったコミュニティのユーザ数）の変化を観察することで、トレンドの変化（何が流行っているか等）を知ることができる。
コミュニティ構造検出装置１０は、例えば、インターネットでの用途において、悪意のある行為を排除するようにさせることができる。すなわち、コミュニティ構造検出装置１０は、インターネットで形成される、悪意のあるユーザが複数の偽のユーザＩＤを使って作成したコミュニティを検出し、セキュリティー・アッタック（Ｓｙｂｉｌ  ａｔｔａｃｋと呼ばれる）をするコミュニティをネットワークの中から同定し、その情報を提供することができる。提供された情報に基づいて、ネットワーク監視装置は、それらの行為を排除することができる。また、コミュニティ構造検出装置１０は、例えば、コミュニティ構造を検索して、その検索結果に基づいてネットワークを制御するための情報を提供することができる。ネットワーク監視装置は、例えば、社会ネットワークで小規模化が進むコミュニティ構造に関する情報を、他のコミュニティに属するユーザに提供する等して、小規模化の抑制を図ることができる。
【００４８】
本実施形態のコミュニティ構造検出装置１０は、コンピュータ及びその周辺装置によって実現され、本実施形態における各部は、コンピュータ及びその周辺装置が備えるハードウェア並びに該ハードウェアを制御するソフトウェアによって構成される。
【００４９】
本実施形態によれば、コミュニティ構造検出装置１０は、複数のノードのそれぞれを開始ノードとしてＳＡＷによる訪問を実行し、各々のノードの訪問回数を開始ノードに対応付けて訪問回数テーブル３１に記憶する。次に、コミュニティ構造検出装置１０は、訪問回数テーブル３１に記憶されたノードの訪問回数に基づいて、各々のノードの訪問率によって示される重要度を算出し、算出した重要度が大きい順に、ノードを順次取り除き、ノードを１つ取り除くごとに、ネットワークが複数のサブネットワークに分割されたか否かを判別する。そして、コミュニティ構造検出装置１０は、ネットワークが分割されていないと判別した場合に、ノードの除去及び分割の判別を繰り返し、ネットワークに分割されたと判別した場合に、取り除いたノードの集合をバウンダリノードの集合と特定し、特定したノードと、サブネットワークとを直接にリンクしたネットワークをコミュニティとして検出する。さらに、コミュニティ構造検出装置１０は、バウンダリノードの集合が、当該バウンダリノードの集合を構成するノード間のリンクを介して接続されたネットワークであるか否かを判別し、ネットワークであると判別した場合、コミュニティとして検出し、コミュニティを検出するごとに、コミュニティの密度を計算し、検出したコミュニティの密度の平均が最大になるコミュニティの集合を検出する。
したがって、コミュニティ構造検出装置１０は、既存のアルゴリズムに比べ少ない計算量で、適切なコミュニティを効率よく検出することができる。
【００５０】
以上、本発明の実施形態について説明したが、本発明は上述した実施形態に限るものではない。また、本発明の実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本発明の実施形態に記載されたものに限定されるものではない。
【符号の説明】
【００５１】
１０    コミュニティ構造検出装置
１１    ＳＡＷ実行手段
１２    全ノード実行手段
１３    重要度算出手段
１４    ノード除去手段
１５    分割判別手段
１６    バウンダリノード特定手段
１７    コミュニティ検出手段
１７１  コミュニティ判別手段
１７２  コミュニティ密度計算手段
１７３  コミュニティ集合検出手段
３１    訪問回数テーブル
３２    密度テーブル
【図１】
2012216943.tif 000007
【図２】
2012216943.tif 000008
【図３】
2012216943.tif 000009
【図４】
2012216943.tif 000010
【図５】
2012216943.tif 000011
【図６】
2012216943.tif 000012
【図７】
2012216943.tif 000013
【図８】
2012216943.tif 000014
【図９】
2012216943.tif 000015
【図１０】
2012216943.tif 000016