JP6511951B2 - 情報処理装置及びプログラム - Google Patents

Description

本発明は情報処理装置及びプログラムに関する。

従来、ベクトル型データについていわゆるコミュニティ（クラスタ）分解を行い、大域的特徴を解析する場合があった。コミュニティ分解は、ノードと、ノードを結ぶリンクとを含むネットワーク型データに対して行われる場合もある。

下記特許文献１には、複数のメンバ投稿者の間のグループ情報に基づいて、１つ以上のコミュニティグループに分類し、コミュニティグループ毎に各属性要素の割合値を算出して、属性種別毎に抽出した属性要素を投稿者のプロフィール情報とする投稿者分析装置が記載されている。

下記特許文献２には、第１の利用者に係る電話番号或いはメールアドレスを、他の利用者の利用者データから検索して、一方向ソーシャルラインを設定し、一方向ソーシャルラインが設定された第２の利用者に係る電話帳データと、第１の利用者に係る電話帳データに双方向ソーシャルラインを設定する電話帳管理システムが記載されている。

下記特許文献３には、複数のクライアント端末が参加可能な仮想コミュニティに投稿されるメッセージを話題毎に分類、蓄積し、メッセージ相互間の階層関係に関する表示方法を設定する知識蓄積支援システムが記載されている。

特開２０１３−１９６０７０号公報 特開２０１０−００４２２９号公報 特開２００３−０３０２１６号公報

ネットワーク型データをコミュニティ分解する方法として、例えば、凝集型クラスタリングと呼ばれる方法や、分割最適化の方法が知られている。凝集型クラスタリングでは、所定の方法でノード間の距離を評価し、距離の近いノードを１つのコミュニティ（クラスタ）に凝集する処理を繰り返して、段階的にコミュニティを大きくしていく。また、分割最適化の方法では、仮定された分割について評価関数の値を算出し、評価関数の値が最大（又は最小）となる分割を探ることで最適なコミュニティ分解を求める。

凝集型クラスタリングの方法では、コミュニティが適切な解像度で形成されているか否かが必ずしも明らかでなかった。この点、分割最適化の方法では、仮定する分割の数は任意であり、異なる解像度によるコミュニティ分解が行える。

しかし、分割最適化の方法では、ある解像度により得られたコミュニティと、他の解像度により得られたコミュニティとの関係が必ずしも明らかでなかった。

そこで、本発明は、２以上の解像度により得られたコミュニティ間の関係を導く情報処理装置及びプログラムの提供を目的とする。

上記課題を解決するために、請求項１に記載の情報処理装置は、リンクで結ばれる注目ノード及び隣接ノードを含むネットワーク情報を取得するネットワーク情報取得手段と、前記ネットワーク情報の予め定められた数の複数のコミュニティそれぞれに前記注目ノードが分類される分類割合を、前記複数のコミュニティそれぞれに前記隣接ノードが分類される分類割合と、所与の解像度に応じた相関を有するようにして算出する分類割合算出手段と、前記解像度の第１の値に応じて算出された、前記注目ノードに関する前記分類割合から、前記注目ノードが属する、前記ネットワーク情報の１以上の第１種コミュニティを生成する第１種コミュニティ生成手段と、前記注目ノードに関する前記分類割合を、前記複数のコミュニティそれぞれに前記隣接ノードが分類される分類割合と、前記解像度の第２の値に応じた相関を有するようにして更新する分類割合更新手段と、前記分類割合更新手段により更新された前記注目ノードに関する前記分類割合から、前記注目ノードが属する、前記ネットワーク情報の１以上の第２種コミュニティを生成する第２種コミュニティ生成手段と、を備える。

また、請求項２に記載の情報処理装置は、前記１以上の第２種コミュニティのうち１つの上層コミュニティが、前記１以上の第１種コミュニティのうち１つの下層コミュニティに依存する割合を示す依存度を、前記上層コミュニティに分類される１以上の前記ノードと、前記下層コミュニティに分類される１以上の前記ノードとの重複が多いほど大きくなるように算出する依存度算出手段をさらに備える。

また、請求項３に記載の情報処理装置は、前記複数のコミュニティのうち１つのコミュニティの重要度を、前記複数のコミュニティ全体に対して当該１つのコミュニティが占める割合が大きいほど大きな値となるように、前記分類割合算出手段により算出された前記分類割合を用いて算出する重要度算出手段と、前記分類割合更新手段により更新された前記分類割合を用いて前記重要度算出手段により算出された前記重要度を更新する重要度更新手段と、前記重要度更新手段により更新された前記重要度の、更新前後の変化の量を算出する重要度変化算出手段と、前記重要度変化算出手段により算出された変化の量が予め定められた量よりも大きいか否かを判定する重要度変化判定手段と、をさらに備える。

また、請求項４に記載の情報処理装置は、前記重要度変化判定手段により前記重要度の変化の量が予め定められた量よりも大きいと判定された場合における前記解像度の値を取得する解像度取得手段と、前記解像度取得手段により取得された２つの前記解像度の値の間の値を有する安定解像度を算出する安定解像度算出手段と、をさらに備え、前記依存度算出手段は、前記安定解像度を用いて、前記依存度を算出する。

また、請求項５に記載の情報処理装置は、前記安定解像度算出手段は、前記解像度取得手段により取得された２つの前記解像度の値の中点の値を前記安定解像度として算出する。

また、請求項６に記載の情報処理装置は、前記分類割合算出手段は、逐次計算により、前記分類割合を算出し、前記分類割合更新手段は、前記分類割合算出手段による逐次計算の回数よりも少ない回数の逐次計算により、前記第１の分類割合を前記第２の分類割合に更新する。

また、請求項７に記載の情報処理装置は、前記分類割合更新手段による更新の前に、前記１以上の第１種コミュニティのうち少なくとも１つが、２以上の独立した部分を含むか否かを判定する独立部分判定手段と、前記独立部分判定手段により、前記１以上の第１種コミュニティのうち少なくとも１つが、２以上の独立した部分を含むと判定される場合に、当該２以上の独立した部分が２以上の第１種コミュニティとなるように前記１以上の第１種コミュニティを修正するコミュニティ修正手段と、をさらに備える。

また、請求項８に記載の情報処理装置は、前記第１種コミュニティ生成手段及び前記第２種コミュニティ生成手段は、２以上の前記第１種コミュニティ及び２以上の前記第２種コミュニティをそれぞれ生成する。

また、請求項９に記載の発明は、情報処理装置に備えられたコンピュータを、リンクで結ばれる注目ノード及び隣接ノードを含むネットワーク情報を取得するネットワーク情報取得手段、前記ネットワーク情報の予め定められた数の複数のコミュニティそれぞれに前記注目ノードが分類される分類割合を、前記複数のコミュニティそれぞれに前記隣接ノードが分類される分類割合と、所与の解像度に応じた相関を有するようにして算出する分類割合算出手段、前記解像度の第１の値に応じて算出された、前記注目ノードに関する前記分類割合から、前記注目ノードが属する、前記ネットワーク情報の１以上の第１種コミュニティを生成する第１種コミュニティ生成手段、前記注目ノードに関する前記分類割合を、前記複数のコミュニティそれぞれに前記隣接ノードが分類される分類割合と、前記解像度の第２の値に応じた相関を有するようにして更新する分類割合更新手段、前記分類割合更新手段により更新された前記注目ノードに関する前記分類割合から、前記注目ノードが属する、前記ネットワーク情報の１以上の第２種コミュニティを生成する第２種コミュニティ生成手段、として機能させるプログラムである。

請求項１及び９に記載の発明によれば、２以上の解像度により得られたコミュニティ間の関係を導く情報処理装置及びプログラムが得られる。

請求項２に記載の発明によれば、上層コミュニティと下層コミュニティの親子関係を算出する情報処理装置が得られる。

請求項３に記載の発明によれば、コミュニティに階層構造が表れる解像度の値を導出する情報処理装置が得られる。

請求項４に記載の発明によれば、安定的な計算結果が得られる解像度を用いる情報処理装置が得られる。

請求項５に記載の発明によれば、安定的な計算結果が得られる解像度をより少ない計算量で求める情報処理装置が得られる。

請求項６に記載の発明によれば、２以上の解像度それぞれについて独立してコミュニティの生成を行う場合に比較して、少ない計算量で２以上の解像度それぞれについてコミュニティの生成を行う情報処理装置が得られる。

請求項７に記載の発明によれば、コミュニティの生成を比較的粗い精度で行った場合であっても、より精度良くコミュニティ生成を行った場合と同等の分類結果を導出する情報処理装置が得られる。

請求項８に記載の発明によれば、１つのノードが複数のコミュニティに重複して分類され得る情報処理装置が得られる。

本発明の実施形態に係る情報処理装置の機能ブロック図である。 本発明の実施形態に係る情報処理装置に取得されるネットワーク情報の例を示す図である。 本発明の実施形態に係る情報処理装置における、第１種コミュニティ生成のフローチャートである。 本発明の実施形態に係る情報処理装置における、第２種コミュニティ生成のフローチャートである。 本発明の実施形態に係る情報処理装置によって算出される重要度と、解像度の関係を示す図である。 本発明の実施形態に係る情報処理装置によって生成されるコミュニティの階層を示す概略図である。 本発明の実施形態に係る情報処理装置における、依存度算出のフローチャートである。 本発明の実施形態に係る情報処理装置によって算出される、第３階層のコミュニティと第２階層のコミュニティの間の依存度を示す表である。 本発明の実施形態に係る情報処理装置によって算出される、第２階層のコミュニティと第１階層のコミュニティの間の依存度を示す表である。

以下、本発明の実施の形態について、図面を参照しながら説明する。

図１は、本発明の実施形態に係る情報処理装置１の構成図である。情報処理装置１は、ネットワーク情報１０及び解像度１２を取得し、入力部１１、制御部１３、記憶部１４、及び表示部１５を含む。

記憶部１０は、例えばRAM（Random Access Memory）やROM（Read Only Memory）を含む。記憶部１０は、制御部１２が実行するプログラムを格納するとともに、制御部１２のワークメモリとしても機能する。なお、記憶部１０に格納される制御部１２が実行するプログラムは、電気通信回線を介して提供されるものであってもよいし、半導体記憶素子等のコンピュータで読み取り可能な情報記憶媒体に格納されて提供されるものであってもよい。

ネットワーク情報１０は、リンクで結ばれる注目ノード及び隣接ノードを含む。ネットワーク情報１０は、複数のノード及び複数のノードを結ぶ複数のリンクを含み、複数のノードのうち１つが注目ノードとなる。ネットワーク情報１０は、例えば相互参照を含むＨＴＭＬデータ、組織の所属関係のデータ、友人関係のデータ等であってよい。ネットワーク情報１０は、少なくともノード間の結び付きの関係（ノードとリンクの関係）を示すものであればよく、ノードが含む具体的な内容（ＨＴＭＬデータの内容等）を示すものでなくてもよい。

入力部１１は、例えばキーボードやマウス等であり、ユーザの指示を制御部１２に伝達する。解像度１２は、正の実数であって、情報処理装置１によってネットワーク情報１０をコミュニティに分類する場合に、コミュニティの大きさを定めるパラメータである。

制御部１３は、例えばＣＰＵ（Central Processing Unit）を含んでおり、記憶部１４に格納されるプログラムを実行することにより、情報処理装置１の全体を制御する。制御部１２は、機能的に、ネットワーク情報取得部１３０、第１種コミュニティ生成部１３１、第２種コミュニティ生成部１３２、依存度算出部１３３、独立部分判定部１３４及びコミュニティ修正部１３５を含む。ここで、第１種コミュニティ生成部１３１は、分類割合算出部１３１ａ、重要度算出部１３１ｂ及び帰属度算出部１３１ｃを含む。また、第２種コミュニティ生成部１３２は、分類割合更新部１３２ａ、重要度更新部１３２ｂ、帰属度更新部１３２ｃ、重要度変化算出部１３２ｄ、重要度変化判定部１３２ｅ、解像度取得部１３２ｆ及び安定解像度算出部１３２ｇを含む。制御部１３の行う制御については、後に詳細に説明する。

記憶部１４は、例えばRAM（Random Access Memory）やROM（Read Only Memory）を含んで構成される。記憶部１０は、制御部１３が実行するプログラムを格納するとともに、制御部１３のワークメモリとしても機能する。なお、記憶部１４に格納される制御部１３が実行するプログラムは、電気通信回線を介して提供されるものであってもよいし、半導体記憶素子等のコンピュータで読み取り可能な情報記憶媒体に格納されて提供されるものであってもよい。表示部１５は、制御部１３により処理された情報をユーザに表示するものであり、例えば液晶表示装置である。

なお、ネットワーク情報１０及び解像度１２は、入力部１１によりユーザによって入力されるものであってもよいし、記憶部１４に格納されるものであってもよいし、電気通信回線を介して提供されるものであってもよい。

図２は、本発明の実施形態に係る情報処理装置１に取得されるネットワーク情報１０の例を示す図である。本例のネットワーク情報１０は、７つのノードと、９つのリンクの情報を含むものである。各ノードには、１から７までのノード番号が付与されており、例えばノード番号１であるノード（以下、ノード［１］と表す）は、ノード［２］及びノード［４］のノードとリンクを有する。本実施形態では、説明を簡明にするため７つのノードを有するネットワークの場合を示すが、ノード数及びリンク数はこれより多くてもよく、例えば１０万程度であってもよい。本例のネットワーク情報１０では、ノード間を結ぶリンクは方向を持たないこととしているが、リンクは一方通行であってもよい。

行列Ｔは、ノード間をリンクに沿ってランダムに遷移する場合における遷移確率を表すものである。例えば、ノード［１］を起点としてリンクに沿ってランダムに他のノードに遷移する場合、１／２の確率でノード［２］に遷移し、１／２の確率でノード［４］に遷移する。これらの遷移確率をまとめて表したものが、行列Ｔの第１列である。他の行列要素についても同様に構成されている。一般に、ノード［ｎ］とノード［ｍ］がリンクで接続されている場合にＡ_ｎｍ＝１、ノード［ｎ］とノード［ｍ］がリンクで接続されていない場合にＡ_ｎｍ＝０となる行列Ａを用いて、ノードの総数をＮとする場合に、行列Ｔは以下の数式（１）で定義される。遷移確率の総和は１であるから、任意のノード［ｍ］について、Σ_ｎＴ_ｎｍ＝１が成り立つ。

図３は、本発明の実施形態に係る情報処理装置１における、第１種コミュニティ生成のフローチャートである。第１種コミュニティを生成する処理では、ネットワーク情報１０及び解像度１２を入力として、ネットワークに含まれるＮ個のノードをＫ個以下の複数のコミュニティに分類する。ここで、Ｎ及びＫは正の整数である。また、本実施形態に係る情報処理装置１は、１つのノードが複数のコミュニティに分類され得るように、コミュニティを生成する。なお、成分の総数Ｋはユーザが仮決めすることのできるパラメータであり、例えばＫ＝Ｎと定めることができるが、後述するように、コミュニティの総数は、第１種コミュニティの生成により自動的に定まる。第１種コミュニティ生成、複数のコミュニティそれぞれについて、複数のノードそれぞれが当該コミュニティに分類される分類割合を求め、複数のコミュニティの重要度を求める。すなわち、コミュニティ［ｋ］について、ノード［ｎ］がコミュニティ［ｋ］に分類される分類割合ｐ（ｎ｜ｋ）を求め、コミュニティ［ｋ］の重要度π（ｋ）を求める。分類割合ｐ（ｎ｜ｋ）、及び重要度π（ｋ）を求めるにあたって、第ｄ番目の通過情報τ^（ｄ）に基づく、複数のコミュニティ全体に対するコミュニティ［ｋ］が占める割合γ^（ｄ）（ｋ）を求めることとなる。ここで、第ｄ番目の通過情報τ^（ｄ）はＮ次元のベクトルであり、τ^（１）、τ^（２）…τ^（Ｄ）（Ｄは正の整数）というＤ個のデータである。

第１種コミュニティ生成処理では、はじめに、ネットワーク情報１０が表すネットワークのノード間をランダムに遷移する場合における定常確率分布ｐ^ｓｔ（ｎ）を算出する（Ｓ１）。定常確率分布ｐ^ｓｔ（ｎ）は、以下の数式（２）で定められる連立Ｎ次方程式を解くことにより求められる。定常確率分布ｐ^ｓｔ（ｎ）は、行列Ｔの固有ベクトルであって、固有値が１のものである。

いわゆるランクシンク等の問題が懸念され、定常確率分布の値が特定のノードに集中するおそれがある場合、数式（２）を変形し、例えば、ｐ^ｓｔ（ｎ）＝（１−ｒ）Σ_ｍＴ_ｎｍｐ^ｓｔ（ｍ）＋ｒという関係によって定常確率分布ｐ^ｓｔ（ｎ）を求めることとしてもよい。ここで、ｒは０以上１以下の実数である。ｒは、ノード間をリンクに沿わずにランダムに遷移する確率を表す。

次に、複数のノード間を複数のリンクに沿ってランダムに遷移する場合に通過するノードを示す複数の通過情報τ_ｎ ^（ｄ）を生成する（Ｓ２）。本実施形態では、通過情報は、定常確率分布ｐ^ｓｔ（ｎ）に従って選出されたノード［ｎ］についてτ_ｎ ^（ｄ）＝１、かつ、ノード［ｎ］を起点としてノード［ｍ］に遷移する確率を与えるＴ_ｍｎに従って選出されたノード［ｍ］についてτ_ｍ ^（ｄ）＝１として生成する。このようなＮ次元ベクトルを、Ｄ回生成する。通過情報τ_ｎ ^（ｄ）は、Σ_ｎτ_ｎ ^（ｄ）＝２を満たす量である。通過情報τ_ｎ ^（ｄ）は、仮想エージェントがノード間をリンクに沿ってランダムに遷移する場合に、仮想エージェントをノード［ｎ］とノード［ｍ］とを結ぶリンク上に見出す場合を表している。

本実施形態に係る分類割合算出部１３１ａ及び重要度算出部１３１ｂは、逐次計算により分類割合ｐ（ｎ｜ｋ）及び重要度π（ｋ）をそれぞれ算出する。分類割合算出部１３１ａは、ネットワーク情報１０の予め定められた数の複数のコミュニティそれぞれに注目ノードが分類される分類割合を、複数のコミュニティそれぞれに、注目ノードとリンクで結ばれる隣接ノードが分類される分類割合と、所与の解像度１２に応じた相関を有するようにして算出する。逐次計算を開始するにあたって、ｐ_０（ｎ｜ｋ）、π_０（ｋ）、γ_０ ^（ｄ）（ｋ）を仮決めする（Ｓ３）。ここで、Σ_ｎｐ_０（ｎ｜ｋ）＝１、Σ_ｋπ_０（ｋ）＝１を満たす値を与えるものとする。ｐ_０（ｎ｜ｋ）は、ｋ＝１〜Ｋの成分について、ｎ＝１〜Ｎのノードが分類される割合を示すものであるから、仮決めではＫ×Ｎ−１個の正の実数を与えることになる。また、π_０（ｋ）は、ｋ＝１〜Ｋに分類されたネットワークのコミュニティについて、重要度を示すものであるから、仮決めではＫ−１個の正の実数を与えることになる。γ_０ ^（ｄ）（ｋ）は、複数のコミュニティ全体に対するコミュニティ［ｋ］が占める割合を表す係数であり、ｄ＝１〜Ｄの通過情報τ^（ｄ）に対応して定まる係数であるから、仮決めではＫ×Ｄ個の正の実数を与えることになる。

また、本実施形態に係る分類割合算出部１３１ａ及び重要度算出部１３１ｂは、ネットワークのコミュニティの大きさを定めるパラメータとして、解像度１２を第１の値α_０に設定する（Ｓ４）。ここで、α_０はユーザが自由に定めることのできる値であるが、ネットワーク情報１０のコミュニティ分類が、十分に細かくなるような値を設定することが望ましい。解像度１２の値は０以上であるから、α_０として０に近い値を設定することが望ましい。

逐次計算の第１ステップでは、第ｔ回目の逐次計算による分類割合ｐ_ｔ（ｎ｜ｋ）を計算する（Ｓ５）。ここで、ｔは正の整数であり、逐次計算の回数を表す。ｐ_ｔ（ｎ｜ｋ）は、１つ前の逐次計算により得られるｐ_ｔ−１（ｎ｜ｋ）、π_ｔ−１（ｋ）、及びγ_ｔ−１ ^（ｄ）（ｋ）より算出される。例えば、仮決め（Ｓ３）の後行われる第一回目の逐次計算では、ｐ_０（ｎ｜ｋ）、π_０（ｋ）、及びγ_０ ^（ｄ）（ｋ）を用いてｐ_１（ｎ｜ｋ）を求めることになる。

本実施形態に係る分類割合算出部１３１ａは、以下の数式（３）で定められる関係により第ｔ回目の逐次計算による分類割合ｐ_ｔ（ｎ｜ｋ）を算出する（Ｓ５）。

ここで、α_０はＳ４において設定された解像度１２であり、正の実数である。本実施形態では、解像度１２は、α_０が０に近付くほど分解の粒度が細かくなり、α_０が無限大に近付くほど分解の粒度が粗くなるパラメータである。また、Ｄ_ｔ−１（ｋ）はγ_ｔ−１ ^（ｄ）（ｋ）から定まる係数であり、Ｄ_ｔ−１（ｋ）＝Σ_ｄγ_ｔ−１ ^（ｄ）（ｋ）である。

分類割合ｐ_ｔ（ｎ｜ｋ）は、ノード［ｎ］との間でリンクを有するノード（Ｔ_ｎｍ≠０であるノード［ｍ］）のコミュニティ［ｋ］に関する分類割合ｐ_ｔ−１（ｍ｜ｋ）が大きいほど大きな値となる第１の寄与（右辺第一項）と、複数のコミュニティ全体に対するコミュニティ［ｋ］が占める割合γ_ｔ−１ ^（ｄ）（ｋ）が大きいほど大きな値となる第２の寄与（右辺第二項）とから構成される値により算出される。

また、第１の寄与は、解像度１２を粗くすると（α_０を無限大に近付けると）１に近付く第１の係数α_０／（α_０＋２Ｄ_ｔ−１（ｋ））と、ノード［ｎ］との間でリンクを有するノード（Ｔ_ｎｍ≠０であるノード［ｍ］）に関して直前に算出された分類割合ｐ_ｔ−１（ｍ｜ｋ）と、から定められる。また、第２の寄与は、解像度１２を粗くすると（α_０を無限大に近付けると）０に近付く第２の係数１／（α_０＋２Ｄ_ｔ−１（ｋ））と、複数の通過情報τ_ｎ ^（ｄ）と、複数のコミュニティ全体に対するコミュニティ［ｋ］が占める割合γ_ｔ−１ ^（ｄ）（ｋ）と、から定められる。なお、以下に示すように、複数のコミュニティ全体に対するコミュニティ［ｋ］が占める割合γ_ｔ−１ ^（ｄ）（ｋ）は、直前に算出された分類割合ｐ_ｔ−１（ｎ｜ｋ）及び重要度π_ｔ−１（ｋ）から算出される。

次に、直前に算出された分類割合ｐ_ｔ−１（ｎ｜ｋ）及び重要度π_ｔ−１（ｋ）、並びに複数の通過情報τ_ｎ ^（ｄ）から、複数のコミュニティ全体に対するコミュニティ［ｋ］が占める割合γ_ｔ ^（ｄ）（ｋ）を算出する（Ｓ６）。本実施形態では、以下の数式（４）により割合γ_ｔ ^（ｄ）（ｋ）を算出する。割合γ_ｔ ^（ｄ）（ｋ）は、コミュニティ全体の中で重要度が相対的に大きいコミュニティについて大きな値をとる。

さらに、ネットワークのコミュニティ［ｋ］の重要度π_ｔ（ｋ）を算出する（Ｓ７）。重要度π_ｔ（ｋ）は、複数のコミュニティ全体に対するコミュニティ［ｋ］が占める割合γ_ｔ ^（ｄ）（ｋ）が大きいほど大きな値となるように算出される。重要度算出部１３１ｂは、複数のコミュニティのうち１つのコミュニティ［ｋ］の重要度π_ｔ（ｋ）を、複数のコミュニティ全体に対して当該１つのコミュニティ［ｋ］が占める割合γ_ｔ ^（ｄ）（ｋ）が大きいほど大きな値となるように、分類割合算出部１３１ａにより算出された分類割合ｐ_ｔ−１（ｎ｜ｋ）を用いて算出する。本実施形態では、以下の数式（５）によりコミュニティ［ｋ］の重要度π_ｔ（ｋ）を算出する。

以上の数式（３）、（４）及び（５）により、直前に算出された分類割合ｐ_ｔ−１（ｎ｜ｋ）、重要度π_ｔ−１（ｋ）及び割合γ_ｔ−１ ^（ｄ）（ｋ）、並びに通過情報τ_ｎ ^（ｄ）から、分類割合ｐ_ｔ（ｎ｜ｋ）、重要度π_ｔ（ｋ）及び割合γ_ｔ ^（ｄ）（ｋ）が算出される。

第１コミュニティ生成処理では、逐次計算の前後における評価値Ｑ_ｔの差の絶対値｜Ｑ_ｔ−Ｑ_ｔ−１｜が予め定められた基準値εより小さいか否かを判定し、逐次計算を終了するか否かを決定する（Ｓ８）。本実施形態において、評価値Ｑ_ｔは以下の数式（６）で定められる量である。

｜Ｑ_ｔ−Ｑ_ｔ−１｜＜εが成立しない場合、最新の分類割合ｐ_ｔ（ｎ｜ｋ）、重要度π_ｔ（ｋ）及び割合γ_ｔ ^（ｄ）（ｋ）を直前の分類割合、重要度及び割合であるとして更新する（Ｓ９）。その後、分類割合ｐ_ｔ＋１（ｎ｜ｋ）を算出する工程（Ｓ５）、割合γ_ｔ＋１ ^（ｄ）（ｋ）を算出する工程（Ｓ６）、重要度π_ｔ＋１（ｋ）を算出する工程（Ｓ７）を行い、｜Ｑ_ｔ＋１−Ｑ_ｔ｜＜εが成立するか否かを判定する（Ｓ８）、という一連の工程を繰り返す。本実施形態に係る分類割合算出部１３１ａ及び重要度算出部１３１ｂは、評価値の差の絶対値が予め定められた値より小さくなるまで、以上の工程を繰り返し、逐次計算により分類割合及び重要度を算出する。これにより、ネットワーク情報１０のコミュニティ分類が漸近的に行われる。

一方、｜Ｑ_ｔ−Ｑ_ｔ−１｜＜εが成立する場合、ノード［ｎ］がコミュニティ［ｋ］に分類される分類割合をｐ^（Ｉ）（ｎ｜ｋ）＝ｐ_ｔ（ｎ｜ｋ）により定め、コミュニティ［ｋ］の重要度をπ^（Ｉ）（ｋ）＝π_ｔ（ｋ）により定める（Ｓ１０）。ここで、添字（Ｉ）は、これらの値が第１種コミュニティ生成のために用いられる値であることを示す。本実施形態に係る情報処理装置１によれば、予め定められた値εを調整することで、任意の精度で分類割合ｐ^（Ｉ）（ｎ｜ｋ）及び重要度π^（Ｉ）（ｋ）を求め、ネットワークのコミュニティ分類を任意の精度で行う。なお、逐次計算の回数を予め定めておき、定められた回数だけ逐次計算を行った場合におけるｐ_ｔ（ｎ｜ｋ）及びπ_ｔ（ｋ）の値を、それぞれ分類割合ｐ^（Ｉ）（ｎ｜ｋ）及び重要度π^（Ｉ）（ｋ）と決定することとしてもよい。

次に、帰属度算出部１３１ｃにより、複数のノードそれぞれについて、ノード［ｎ］がコミュニティ［ｋ］に分類される分類割合ｐ（ｎ｜ｋ）が大きいほど、大きな値となるように帰属度を算出する（Ｓ１１）。本実施形態では、ノード［ｎ］がコミュニティ［ｋ］に帰属する帰属度ｑ^（Ｉ）（ｋ｜ｎ）は、以下の数式（７）によって求められる。

数式（７）から読み取れるように、帰属度ｑ（ｋ｜ｎ）は、Σ_ｋｑ（ｋ｜ｎ）＝１を満たす量である。すなわち、あるノードが各コミュニティに帰属する帰属度の総和は１となる。帰属度ｑ（ｋ｜ｎ）は、あるノード［ｎ］が、コミュニティ［ｋ］に帰属する度合いをコミュニティ全体に関して相対的に測った量である。

第１種コミュニティ生成部１３１は、解像度１２の第１の値α_０に応じた相関を有するようにして算出された、注目ノード［ｎ］に関する分類割合ｐ^（Ｉ）（ｎ｜ｋ）から、注目ノード［ｎ］が属する、ネットワーク情報１０の１以上の第１種コミュニティを生成する（Ｓ１２）。第１種コミュニティ生成部１３１は、注目ノード［ｎ］がコミュニティ［ｋ］に属する割合を、分類割合ｐ^（Ｉ）（ｎ｜ｋ）の値によって定めてよい。また、第１種コミュニティ生成部１３１は、分類割合ｐ^（Ｉ）（ｎ｜ｋ）及び重要度π^（Ｉ）（ｋ）から算出される帰属度ｑ^（Ｉ）（ｋ｜ｎ）に基づき、注目ノード［ｎ］が属する第１種コミュニティを生成してもよい。その場合、注目ノード［ｎ］がコミュニティ［ｋ］に属する割合を、帰属度ｑ^（Ｉ）（ｋ｜ｎ）の値によって定める。いずれの場合も、第１種コミュニティ生成部１３１は、注目ノード［ｎ］が属する２以上の第１種コミュニティを生成する。そのため、本実施形態に係る第１種コミュニティ生成部１３１によれば、１つのノードが複数の属性を有する場合を表現したコミュニティ分類が行われる。

以上のように、本実施形態に係る第１種コミュニティ生成部１３１は、逐次計算により第１種コミュニティを生成する。逐次計算の精度は、数式（６）のεで定められる。εを十分に小さく設定しなかった場合、独立した部分を含むコミュニティが生成される場合がある。本実施形態に係る独立部分判断部１３４は、分類割合更新部１３２ａによる更新の前に、１以上の第１種コミュニティのうち少なくとも１つが、２以上の独立した部分を含むか否かを判定する。ここで、コミュニティに含まれる独立した部分とは、ノードの集合であって、当該集合に含まれるノード間は互いにリンクで直接結ばれているが、当該コミュニティに含まれ、当該集合に含まれないノードとは、リンクで直接結ばれていない集合をいう。

本実施形態に係るコミュニティ修正部１３５は、独立部分判定部１３４により、１以上の第１種コミュニティのうち少なくとも１つが、２以上の独立した部分を含むと判定される場合に、当該２以上の独立した部分が２以上の第１種コミュニティとなるように１以上の第１種コミュニティを修正する。これにより、コミュニティの生成を比較的粗い精度で行った場合であっても、より精度良くコミュニティ生成を行った場合と同等の分類結果が得られる。

図４は、本発明の実施形態に係る情報処理装置１における、第２種コミュニティ生成のフローチャートである。第２種コミュニティ生成部１３２は、第１種コミュニティ生成部１３１により逐次計算で求められた分類割合ｐ^（Ｉ）（ｎ｜ｋ）及び重要度π^（Ｉ）（ｋ）を計算の出発点として、解像度１２を第１の値α_０からわずかに増加させた第２の値α_１＝α_０＋Δαとして、解像度１２の第２の値α_１に応じた相関を有するようにして分類割合、重要度及び帰属度を更新する。また、第２種コミュニティ生成部１３２は、第２種コミュニティ生成部１３２により更新された分類割合、重要度及び帰属度を、わずかに増加させた解像度１２に応じた相関を有するように更新していく。

第２種コミュニティ生成処理は、第１種コミュニティ生成処理のＳ１において算出された定常確率分布ｐ^ｓｔ（ｎ）を取得することから始まる（Ｓ２１）。また、第１種コミュニティ生成処理のＳ２において生成された通過情報τ_ｎ ^（ｄ）を取得する（Ｓ２２）。さらに、第１種コミュニティ生成処理のＳ１０において算出された分類割合ｐ^（Ｉ）（ｎ｜ｋ）、重要度π^（Ｉ）（ｋ）及び割合γ_（Ｉ） ^（ｄ）（ｋ）を取得する（Ｓ２３）。ここで、割合γ_（Ｉ） ^（ｄ）（ｋ）は、｜Ｑ_ｔ−Ｑ_ｔ−１｜＜εが成立した場合における割合γ_ｔ ^（ｄ）（ｋ）の値である。

本実施形態に係る分類割合更新部１３２ａは、注目ノード［ｎ］に関する分類割合ｐ^（Ｉ）（ｎ｜ｋ）を、複数のコミュニティそれぞれに隣接ノードが分類される分類割合と、解像度１２の第２の値α_１＝α_０＋Δαに応じた相関を有するようにして更新する。そのため、第２種コミュニティ生成部１３２は、解像度１２として、第１の値α_０を増加させた第２の値α_１＝α_０＋Δαを設定する（Ｓ２４）。本実施形態の場合、解像度１２を粗くすることは解像度１２の値を大きくすることに対応するため、増加量Δαは正の値である。しかし、解像度１２を粗くすることが解像度１２の値を小さくすることに対応する場合、Δαは負の値であってよい。

本実施形態に係る分類割合更新部１３２ａは、分類割合等の変化が比較的小さくなる程度（準静的な変化となる程度）の変化量Δαによって、解像度１２の第２の値α_１＝α_０＋Δαを設定する。例えば、分類割合更新部１３２ａは、分類割合等の変化が、数式（６）において逐次計算の収束性の判定に用いた値ε以下となるように解像度１２の変化量Δαを定めて、解像度１２を第２の値α_１に設定してよい。

分類割合更新部１３２ａは、具体的に、以下の数式（８）によって分類割合を更新する（Ｓ２５）。ここで、分類割合ｐ^（ＩＩ）（ｎ｜ｋ）は、第２種コミュニティを生成するために用いられる更新された分類割合である。また、Ｄ^（Ｉ）（ｋ）＝Σ_ｋγ_（Ｉ） ^（ｄ）（ｋ）である。

数式（８）は、数式（３）の解像度１２の第１の値α_０を第２の値α_１に置き換え、第ｔ回目の逐次計算による分類割合ｐ_ｔ（ｎ｜ｋ）及び割合γ_ｔ ^（ｄ）（ｋ）を、それぞれ第１種コミュニティ分類処理で算出された分類割合ｐ^（Ｉ）（ｎ｜ｋ）及び割合γ_（Ｉ） ^（ｄ）（ｋ）に置き換えたものである。

また、本実施形態に係る重要度更新部１３２ｂは、第１種コミュニティ分類処理で算出された重要度π^（Ｉ）（ｋ）を、第２種コミュニティを生成するために用いられるπ^（ＩＩ）（ｋ）に更新する。具体的には、重要度更新部１３２ｂは、第１種コミュニティ分類処理で算出された割合γ_（Ｉ） ^（ｄ）（ｋ）を以下の数式（９）で割合γ_（ＩＩ） ^（ｄ）（ｋ）に更新する。

数式（９）は、数式（４）における第ｔ−１回目の逐次計算による分類割合ｐ_ｔ−１（ｎ｜ｋ）及び重要度π_ｔ−１（ｋ）を、第１種コミュニティ分類処理で算出された分類割合ｐ^（Ｉ）（ｎ｜ｋ）及び重要度π^（Ｉ）（ｋ）に置き換えたものである。重要度更新部１３２ｂは、分類割合更新部１３２ａにより更新された分類割合ｐ^（ＩＩ）（ｎ｜ｋ）を用いて重要度算出部１３１ｂにより算出された重要度π^（Ｉ）（ｋ）を更新する。具体的に、重要度更新部１３２ｂは、更新された割合γ_（ＩＩ） ^（ｄ）（ｋ）を用いて、以下の数式（１０）によって重要度を更新する（Ｓ２５）。

数式（１０）は、数式（５）における第ｔ回目の逐次計算による割合γ_ｔ ^（ｄ）（ｋ）を、更新された割合γ_（ＩＩ） ^（ｄ）（ｋ）に置き換えたものである。

さらに、帰属度更新部１３２ｃは、第１種コミュニティ分類処理で算出された帰属度ｑ^（Ｉ）（ｋ｜ｎ）を、以下の数式（１１）によって、第２種コミュニティを生成するために用いられる帰属度ｑ^（ＩＩ）（ｋ｜ｎ）に更新する（Ｓ２６）。

数式（１１）は、数式（７）における第１種コミュニティ分類処理で算出された分類割合ｐ^（Ｉ）（ｎ｜ｋ）及び重要度π^（Ｉ）（ｋ）を、第２種コミュニティ分類処理で更新された分類割合ｐ^（ＩＩ）（ｎ｜ｋ）及び重要度π^（ＩＩ）（ｋ）に置き換えたものである。

第２種コミュニティ生成部１３２は、分類割合更新部１３２ａにより更新された注目ノード［ｎ］に関する分類割合ｐ^（ＩＩ）（ｎ｜ｋ）から、注目ノード［ｎ］が属する、ネットワーク情報１０の１以上の第２種コミュニティを生成する（Ｓ２７）。第２種コミュニティ生成部１３２は、注目ノード［ｎ］がコミュニティ［ｋ］に属する割合を、分類割合ｐ^（ＩＩ）（ｎ｜ｋ）の値によって定めてよい。また、第２種コミュニティ生成部１３２は、分類割合ｐ^（ＩＩ）（ｎ｜ｋ）及び重要度π^（ＩＩ）（ｋ）から算出される帰属度ｑ^（ＩＩ）（ｋ｜ｎ）に基づき、注目ノード［ｎ］が属する第２種コミュニティを生成してもよい。その場合、注目ノード［ｎ］がコミュニティ［ｋ］に属する割合を、帰属度ｑ^（ＩＩ）（ｋ｜ｎ）の値によって定める。いずれの場合も、第２種コミュニティ生成部１３２は、注目ノード［ｎ］が属する２以上の第２種コミュニティを生成する。そのため、本実施形態に係る第２種コミュニティ生成部１３２によれば、１つのノードが複数の属性を有する場合を表現したコミュニティ分類が行われる。

また、本実施形態に係る第１種コミュニティ生成部１３１及び第２種コミュニティ生成部１３２によれば、第１種コミュニティ生成処理において算出された分類割合ｐ^（Ｉ）（ｎ｜ｋ）、重要度π^（Ｉ）（ｋ）及び割合γ_（Ｉ） ^（ｄ）（ｋ）を計算の出発点として第２種コミュニティ生成処理が行われ、２以上の解像度（解像度１２の第１の値α_０と第２の値α_１）により得られたコミュニティ間の関係が導かれる。また、第１種コミュニティ生成部１３１により、逐次計算の収束性の判定を行い、第２種コミュニティ生成部１３２において第１種コミュニティ生成部１３１による算出結果を用いることで、十分に精度良く分類されたコミュニティを更新することとなり、２以上の解像度それぞれについて独立してコミュニティの生成を行う場合に比較して、少ない計算量で２以上の解像度それぞれについてコミュニティの生成が行われる。本実施形態では、第２種コミュニティ生成部１３２は、数式（８）、（９）及び（１０）によって一度の計算で分類割合、割合及び重要度を更新することとしたが、これらの値を数回の逐次計算（分類割合算出部１３１ａ及び重要度算出部１３１ｂによる逐次計算の回数よりも少ない回数の逐次計算）によって更新することとしてもよい。第１種コミュニティ生成部１３１により十分精度良くコミュニティ生成がされているから、第２種コミュニティ生成部１３２における逐次計算の回数が第１種コミュニティ生成部１３１における逐次計算の回数よりも少なくても、第２種コミュニティ生成部１３２によって、十分な精度でコミュニティ生成が行われる。

以上の説明において、第２種コミュニティ生成部１３２は、第１種コミュニティ生成処理において算出された分類割合ｐ^（Ｉ）（ｎ｜ｋ）、重要度π^（Ｉ）（ｋ）及び割合γ_（Ｉ） ^（ｄ）（ｋ）並びに解像度１２の第２の値α_１＝α_０＋Δαを入力として、更新された分類割合ｐ^（ＩＩ）（ｎ｜ｋ）、重要度π^（ＩＩ）（ｋ）、割合γ_（ＩＩ） ^（ｄ）（ｋ）及び帰属度ｑ^（ＩＩ）（ｋ｜ｎ）を算出した。第２種コミュニティ生成部１３２は、さらに、第２種コミュニティ生成処理において算出された分類割合ｐ^（ＩＩ）（ｎ｜ｋ）、重要度π^（ＩＩ）（ｋ）及び割合γ_（ＩＩ） ^（ｄ）（ｋ）並びに解像度１２の第３の値α_０＋２Δαを入力として、更新された分類割合、重要度、割合及び帰属度を算出する。このように、解像度１２の値をΔαずつ増加させて、分類割合、重要度、割合及び帰属度を更新していくことで、解像度１２の値に対するコミュニティ形成状態の変化が追跡される。次図において、解像度１２の値を第１の値α_０から増加させた場合における、重要度π^（ＩＩ）（ｋ）の変化の様子を示す。

図５は、本発明の実施形態に係る情報処理装置１によって算出される重要度π（ｋ）と、解像度１２の関係を示す図である。同図では、横軸に解像度１２の値αを示し、縦軸に重要度π（ｋ）の値を示している。

同図の縦軸に最も近い３つのデータ点は、図２に示すネットワーク情報１０について、解像度１２の値が第１の値α_０である場合において、重要度算出部１３１ｂにより算出された重要度π^（０）（ｋ）の値を表している。ここで、重要度π^（０）（ｋ）は、第１種コミュニティの重要度であるが、添字を（０）に変更し、解像度１２の第１の値α_０に対応した添字としている。

重要度π^（０）（ｋ）は、ｋ＝１、２、３について０でない値を有し、それ以外のｋについて０である。このことは、ネットワーク情報１０を解像度１２の第１の値α_０に応じた相関を有するようにコミュニティ分類すると、３つの第１種コミュニティに分類されることを表している。

同図には、解像度１２を第１の値α_０からΔαだけ増加させて第２の値α_１とした場合において、重要度更新部１３２ｂにより算出された重要度π^（１）（ｋ）の値が表されている。ここで、重要度π^（１）（ｋ）は、第２種コミュニティの重要度であるが、添字を（１）に変更し、解像度１２の第２の値α_１に対応した添字としている。重要度π^（１）（ｋ）は、ｋ＝１、２、３について重要度π^（０）（ｋ）とほぼ変わらない値を有する。

本発明の発明者は、解像度１２の値を増加させて第２種コミュニティ生成部１３２による重要度の更新を繰返していくと、重要度π（ｋ）の値が比較的大きく変化する不安定領域が表れ、１以上のコミュニティについて重要度の値が０になることを見出した。同図の場合、解像度１２の値を増加させていくと、第１の不安定領域Ｒ１が表れ、π（ｋ＝２）の値が０に変化している。また、第１の不安定領域Ｒ１において、π（ｋ＝１）＜π（ｋ＝２）からπ（ｋ＝１）＞π（ｋ＝２）へ入れ替わりが生じている。これらの変化は、解像度１２の値を増加させて解像度１２を粗くしていくと、コミュニティ［２］が消滅してコミュニティ［１］に吸収され、相対的にコミュニティ［３］の重要度が減少したために生じていると解釈される。

本実施形態に係る重要度変化算出部１３２ｄは、重要度更新部１３２ｂにより更新された重要度の、更新前後の変化の量を算出する。すなわち、重要度変化算出部１３２ｄは、解像度の値がΔαだけ異なる場合において算出された、２つの重要度の変化の量を、各コミュニティについて算出する。

また、本実施形態に係る重要度変化判定部１３２ｅは、重要度変化算出部１３２ｄにより算出された変化の量が予め定められた量よりも大きいか否かを判定する。予め定められた量（基準量）としては、安定領域（不安定領域以外の領域）における重要度の変化の量を採用してよい。図５の例の場合、｜π^（１）（ｋ）−π^（０）（ｋ）｜のうち最も値が大きいコミュニティ［ｋ］についての変化量を基準量とすることができる。

重要度変化算出部１３２ｄは、解像度１２の値がΔα増加した場合における、π（１）、π（２）及びπ（３）の変化量を算出する。それぞれの変化量は、第１の不安定領域Ｒ１において、基準量より大きいから、重要度変化判定部１３２ｅは、π（１）、π（２）及びπ（３）の変化の量が予め定められた量よりも大きいと判定する。

本実施形態に係る解像度取得部１３２ｆは、重要度変化判定部１３２ｅにより重要度の変化の量が予め定められた量よりも大きいと判定された場合における解像度１２の値を取得する。本例の場合、重要度変化判定部１３２ｅは、第１の不安定領域Ｒ１において、重要度の変化の量が予め定められた量よりも大きいと判定するため、解像度取得部１３２ｆは、第１の不安定領域Ｒ１に属する解像度１２の値を取得する。解像度取得部１３２ｆは、第１の不安定領域Ｒ１に属する解像度１２の値のうち中点の値を取得してもよい。これにより、コミュニティに階層構造が表れる解像度１２の値が判別される。

解像度１２の値をさらに増加させ、重要度の値の更新を続けると、解像度１２の値がα_２である場合の重要度の値はπ^（２）（ｋ）となる。さらに重要度の更新を続けると、第２の不安定領域Ｒ２が表れる。第２の不安定領域Ｒ２では、コミュニティ［２］の重要度が０になり、コミュニティ［１］の重要度が１に漸近する。このことは、コミュニティ［２］が消滅してコミュニティ［１］に吸収され、全体として１つのコミュニティになったと解釈される。第２の不安定領域Ｒ２を過ぎて、重要度の値の更新を続けると、解像度１２の値がα_３である場合の重要度の値はπ^（３）（ｋ）となる。

本実施形態に係る安定解像度算出部１３２ｇは、解像度取得部１３２ｆにより取得された２つの解像度１２の値の間の値を有する安定解像度を算出する。具体的に、安定解像度算出部１３２ｇは、解像度取得部１３２ｆにより取得された２つの解像度１２の値の中点の値を安定解像度として算出する。図５の例において、安定解像度算出１３２ｇは、第１の不安定領域Ｒ１の上端と、第２の不安定領域Ｒ２の下端との中点の値を安定解像度α_２として算出する。算出された安定解像度は、後に詳細に説明する依存度算出部１３３によるコミュニティ間の依存度の算出を行う場合に用いられる。仮に、コミュニティ間の依存度を不安定領域において算出すると、計算結果が不安定となり、計算時間が長くなったり、計算結果の精度が悪くなったりする場合がある。本実施形態に係る依存度算出部１３３は、安定解像度を用いて依存度を算出することで、安定的な計算結果を得る。また、本実施形態に係る安定解像度算出部１３２ｇは、解像度取得部１３２ｆにより取得された２つの解像度１２の値の中点の値を安定解像度として用いることで、安定的な計算結果が得られる解像度をより少ない計算量で求めている。

以下の説明において、重要度の値がπ^（１）（ｋ）である場合の３つのコミュニティを第１階層コミュニティ、重要度の値がπ^（２）（ｋ）である場合の２つのコミュニティを第２階層コミュニティ、重要度の値がπ^（３）（ｋ）である場合の１つのコミュニティを第３階層コミュニティと称する。第２階層コミュニティは、第１階層コミュニティに対する上層コミュニティである。逆に、第１階層コミュニティは、第２階層コミュニティに対する下層コミュニティである。同様に、第３階層コミュニティは、第２階層コミュニティに対する上層コミュニティであり、第２階層コミュニティは、第３階層コミュニティに対する下層コミュニティである。

図６は、本発明の実施形態に係る情報処理装置１によって生成されるコミュニティの階層を示す概略図である。同図には、解像度１２の値を示す縦軸が示され、解像度１２の値がα_１、α_２、α_３の場合におけるネットワーク情報１０のコミュニティが破線で示されている。解像度１２の値がα_１である場合、ノード［２］及び［３］を含む第１の第１階層コミュニティ２ａと、ノード［１］及び［４］を含む第２の第１階層コミュニティ２ｂと、ノード［５］、［６］及び［７］を含む第３の第１階層コミュニティ２ｃが破線で示されている。また、解像度１２の値がα_２である場合、ノード［１］、［２］、［３］及び［４］を含む第１の第２階層コミュニティ３ａと、ノード［５］、［６］及び［７］を含む第２の第２階層コミュニティ３ｂが破線で示されている。また、解像度１２の値がα_３である場合、ノード［１］乃至［７］を含む第３階層コミュニティ４が破線で示されている。

それぞれの階層のコミュニティ間には、破線矢印で、依存度ｐ（Ｃ^（ａ） _ｋ｜Ｃ^（ｂ） _ｌ）が示されている。ここで、Ｃ^（ａ） _ｋは、第ａ階層のコミュニティ［ｋ］を示す記号であり、依存度ｐ（Ｃ^（ａ） _ｋ｜Ｃ^（ｂ） _ｌ）は、第ａ階層のコミュニティ［ｋ］が、第ｂ階層のコミュニティ［ｌ］に依存する割合を示す。本実施形態に係る依存度算出部１３３は、１以上の第２種コミュニティのうち１つの上層コミュニティが、１以上の第１種コミュニティのうち１つの下層コミュニティに依存する割合を示す依存度を、上層コミュニティに分類される１以上のノードと、下層コミュニティに分類される１以上のノードとの重複が多いほど大きくなるように算出する。

図７は、本発明の実施形態に係る情報処理装置１における、依存度算出のフローチャートである。本実施形態に係る依存度算出部１３３は、はじめに第１種コミュニティ生成部１３１により算出された定常確率分布ｐ^ｓｔ（ｎ）を取得する（Ｓ３１）。そして、第２種コミュニティ生成部１３２の帰属度更新部１３２ｃにより算出された各階層の帰属度ｑ^（ａ）（ｋ｜ｎ）を取得する（Ｓ３２）。各階層の帰属度ｑ^（ａ）（ｋ｜ｎ）は、安定解像度の下で算出された分類割合及び重要度から求められることが望ましい。

その後、依存度算出部１３３は、第ａ階層のコミュニティ［ｋ］と第ｂ階層のコミュニティ［ｌ］との間の絶対重みｐ（Ｃ^（ａ） _ｋ、Ｃ^（ｂ） _ｌ）を算出する（Ｓ３３）。本実施形態に係る依存度算出部１３３は、以下の数式（１２）によって、絶対重みｐ（Ｃ^（ａ） _ｋ、Ｃ^（ｂ） _ｌ）を算出する。

ここで、Ｉ（ｎ∈Ｃ^（ａ） _ｋ）は、ノード［ｎ］が第ａ階層のコミュニティ［ｋ］に属する場合に１、ノード［ｎ］が第ａ階層のコミュニティ［ｋ］に属さない場合に０となる関数である。ノード［ｎ］が第ａ階層のコミュニティ［ｋ］に属するか否かは、第ａ階層の帰属度ｑ^（ａ）（ｋ｜ｎ）により判定する。任意のノード［ｎ］について、帰属度ｑ^（ａ）（ｋ｜ｎ）はΣ_ｋｑ^（ａ）（ｋ｜ｎ）＝１を満たすから、帰属度が最も大きいコミュニティが存在する（仮に、複数のコミュニティについて帰属度が同じ値で最大となる場合、当該複数のコミュニティのうちからランダムに１つのコミュニティを選んでよい）。本実施形態に係る依存度算出部１３３は、第ａ階層において、ノード［ｎ］は、帰属度ｑ^（ａ）（ｋ｜ｎ）の値が最も大きいコミュニティ［ｋ］に属すると判定する。

次に、依存度算出部１３３は、第ａ階層のコミュニティ［ｋ］について、固有重みｐ（Ｃ^（ａ） _ｋ）を算出する（Ｓ３４）。本実施形態に係る依存度算出部１３３は、以下の数式（１３）によって、第ａ階層のコミュニティ［ｋ］の固有重みｐ（Ｃ^（ａ） _ｋ）を算出する。

以上説明した絶対重みｐ（Ｃ^（ａ） _ｋ、Ｃ^（ｂ） _ｌ）及び固有重みｐ（Ｃ^（ａ） _ｋ）を算出する第１の方法は、１つの例であり、他にも絶対重み及び固有重みを算出する方法がある。後に絶対重み及び固有重みを算出する第２の方法及び第３の方法を詳細に説明する。

絶対重みｐ（Ｃ^（ａ） _ｋ、Ｃ^（ｂ） _ｌ）及び固有重みｐ（Ｃ^（ａ） _ｋ）に基づいて、依存度算出部１３３は、第ａ階層のコミュニティ［ｋ］と第ｂ階層のコミュニティ［ｌ］との間の相対重み（依存度）ｐ（Ｃ^（ａ） _ｋ｜Ｃ^（ｂ） _ｌ）を算出する（Ｓ３５）。本実施形態に係る依存度算出部１３３は、以下の数式（１４）によって、第ａ階層のコミュニティ［ｋ］が第ｂ階層のコミュニティ［ｌ］に依存する割合である依存度ｐ（Ｃ^（ａ） _ｋ｜Ｃ^（ｂ） _ｌ）を算出する。

図８は、本発明の実施形態に係る情報処理装置１によって算出される、第１階層のコミュニティと第２階層のコミュニティの間の依存度ｐ（Ｃ^（１） _ｋ｜Ｃ^（２） _ｌ）を示す表である。また、図９は、本発明の実施形態に係る情報処理装置１によって算出される、第２階層のコミュニティと第３階層のコミュニティの間の依存度ｐ（Ｃ^（２） _ｋ｜Ｃ^（３） _ｌ）を示す表である。両図には、絶対重みｐ（Ｃ^（１） _ｋ、Ｃ^（２） _ｌ）及びｐ（Ｃ^（２） _ｋ、Ｃ^（３） _ｌ）と、固有重みｐ（Ｃ^（２） _ｋ）及びｐ（Ｃ^（３） _ｋ）も示している。

図２に示すネットワーク情報１０について、解像度１２の値α_１でコミュニティ分類を行うと３つの第１階層のコミュニティが検出される。ノード［２］及び［３］について第１階層の帰属度ｑ^（１）（ｋ｜ｎ）が最も大きいコミュニティはコミュニティ［１］であり、Ｉ（［２］∈Ｃ^（１） _ｋ）＝｛１（ｋ＝１の場合）、０（ｋ＝２及び３の場合）｝となり、Ｉ（［３］∈Ｃ^（１） _ｋ）＝｛１（ｋ＝１の場合）、０（ｋ＝２及び３の場合）｝となる。同様に、Ｉ（［１、４］∈Ｃ^（１） _ｋ）＝｛１（ｋ＝２の場合）、０（ｋ＝１及び３の場合）｝となる。また、Ｉ（［５〜７］∈Ｃ^（１） _ｋ）＝｛３（ｋ＝１の場合）、０（ｋ＝１及び２の場合）｝となる。

また、第２階層の帰属度ｑ^（２）（ｋ｜ｎ）から、Ｉ（［１〜４］∈Ｃ^（２） _ｋ）＝｛１（ｋ＝１の場合）、０（ｋ＝２の場合）｝となり、Ｉ（［５〜７］∈Ｃ^（２） _ｋ）＝｛１（ｋ＝２の場合）、０（ｋ＝１の場合）｝となる。

これらのＩ（ｎ∈Ｃ^（１） _ｋ）及びＩ（ｎ∈Ｃ^（２） _ｋ）と、取得された定常確率分布ｐ^ｓｔ（ｎ）から、数式（１２）に従って絶対重みｐ（Ｃ^（１） _ｋ、Ｃ^（２） _ｌ）を算出すると、図８の左の表に示す値が得られる。絶対重みｐ（Ｃ^（１） _ｋ、Ｃ^（２） _ｌ）は、Σ_ｋ、ｌｐ（Ｃ^（１） _ｋ、Ｃ^（２） _ｌ）＝１を満たす。これらの値から、第１階層のコミュニティ［１］及び［２］は、第２階層のコミュニティ［１］と関係性があるが、第２階層のコミュニティ［２］とは関係性が無いことがわかる。また、第１階層のコミュニティ［３］は、第２階層のコミュニティ［１］と関係性が無く、第２階層のコミュニティ［２］と関係性があることがわかる。

Ｉ（ｎ∈Ｃ^（２） _ｋ）と、取得された定常確率分布ｐ^ｓｔ（ｎ）から、数式（１３）に従って第２階層のコミュニティの固有重みｐ（Ｃ^（２） _ｋ）を算出すると、図８の中央の表に示す値が得られる。固有重みｐ（Ｃ^（２） _ｋ）は、固有重みΣ_ｋｐ（Ｃ^（２） _ｋ）＝１を満たす。これらの値から、第２階層では、コミュニティ［１］がコミュニティ［２］より相対的に大きいことが読み取れる。

算出された絶対重みｐ（Ｃ^（１） _ｋ、Ｃ^（２） _ｌ）と、固有重みｐ（Ｃ^（２） _ｋ）から、数式（１４）に従って第１階層のコミュニティと第２階層のコミュニティの間の依存度ｐ（Ｃ^（１） _ｋ｜Ｃ^（２） _ｌ）を算出すると、図８の右の表に示す値が得られる。依存度ｐ（Ｃ^（１） _ｋ｜Ｃ^（２） _ｌ）は、第２階層のコミュニティそれぞれについて（任意のｌについて）、Σ_ｋｐ（Ｃ^（１） _ｋ｜Ｃ^（２） _ｌ）＝１を満たす。これらの値から、第１階層のコミュニティ［１］及び［２］は、第２階層のコミュニティ［１］に依存し、第２階層のコミュニティ［２］には依存しないことがわかる。また、第１階層のコミュニティ［１］が第２階層のコミュニティ［１］に依存する割合は０．５２３であり、第１階層のコミュニティ［２］が第２階層のコミュニティ［１］に依存する割合は０．４７７であって、第１階層のコミュニティ［１］の方が、依存度が僅かに大きいことがわかる。また、第１階層のコミュニティ［３］は、第２階層のコミュニティ［２］に依存し、第２階層のコミュニティ［１］には依存しない。

同様に、図９には、第２階層の２つのコミュニティと、第３階層の１つのコミュニティについて、絶対重みｐ（Ｃ^（２） _ｋ、Ｃ^（３） _ｌ）と、固有重みｐ（Ｃ^（３） _ｋ）と、依存度ｐ（Ｃ^（２） _ｋ｜Ｃ^（３） _ｌ）と、をそれぞれ表に示している。第３階層には１つのコミュニティしかないので、第２階層のコミュニティは、それぞれ第３階層のコミュニティ［１］に依存している。ただし、依存の割合は、第２階層のコミュニティ［１］が０．６２であり、第２階層のコミュニティ［２］は０．３８であり、偏りがあることがわかる。

本実施形態に係る依存度算出部１３３によれば、ネットワーク情報１０の異なる階層のコミュニティについて、コミュニティの吸収を反映した上層コミュニティと下層コミュニティの親子関係が算出される。コミュニティは、必ずしも１対１の親子関係を有するとは限らず、２以上のコミュニティが１つのコミュニティに統合され、親子関係をつくる場合もある。図６に示す例では、第１階層のコミュニティ［１］及び［２］が、第２階層のコミュニティ［１］に統合されており、第２階層のコミュニティ［１］は２つのコミュニティを親に持つといえる。このように、本実施形態に係る依存度算出部１３３によれば、２以上のコミュニティを親に持つコミュニティが判別され、より詳細なコミュニティの親子関係を導出される。

以下では、第ａ階層のコミュニティ［ｋ］と第ｂ階層のコミュニティ［ｌ］との間の絶対重みｐ（Ｃ^（ａ） _ｋ、Ｃ^（ｂ） _ｌ）と、第ａ階層のコミュニティ［ｋ］の固有重みｐ（Ｃ^（ａ） _ｋ）を算出する第２の方法及び第３の方法について説明する。第２の方法は、ノード［ｎ］が属するコミュニティを１つに定めず、１つのノードが複数のコミュニティに属することを許容しつつ、これらの量を求める方法である。第３の方法は、リンクが向きを有する場合に、これらの量を求める方法である。

第２の方法では、第ａ階層のコミュニティ［ｋ］と第ｂ階層のコミュニティ［ｌ］との間の絶対重みｐ（Ｃ^（ａ） _ｋ、Ｃ^（ｂ） _ｌ）は、以下の数式（１５）により求められる。

ここで、Ｓ^{（ａ）、（ｂ）} _ｋ、ｌ（ｎ）は、以下の数式（１６）により、逐次計算により求められる。ここで、Ｋ_ａは、第ａ階層のコミュニティの総数であり、Ｋ_ｂは、第ｂ階層のコミュニティの総数である。

Ｓ^{（ａ）、（ｂ）} _ｋ、ｌ（ｎ）を求めるにあたって、はじめにＳ^{（ａ）、（ｂ）} _ｋ、ｌ（ｎ）の値を仮決めする。その後、仮決めしたＳ^{（ａ）、（ｂ）} _ｋ、ｌ（ｎ）と、帰属度更新部１３２ｃにより算出された第ａ階層の帰属度ｑ^（ａ）（ｋ｜ｎ）及び第ｂ階層の帰属度ｑ^（ｂ）（ｋ｜ｎ）とを用いて、数式（１６）によりρ^{（ａ）、（ｂ）} _ｋ、ｌ（ｎ）を算出する。さらに、算出されたρ^{（ａ）、（ｂ）} _ｋ、ｌ（ｎ）を用いて、数式（１６）によりＳ^{（ａ）、（ｂ）} _ｋ、ｌ（ｎ）の値を更新する。以上の計算をＳ^{（ａ）、（ｂ）} _ｋ、ｌ（ｎ）の値の変動が十分に小さくなるまで繰返す。Ｓ^{（ａ）、（ｂ）} _ｋ、ｌ（ｎ）の値の収束性の判定は、逐次計算前後のＳ^{（ａ）、（ｂ）} _ｋ、ｌ（ｎ）の値の変化が、数式（６）のε以下となるか否かによって行ってよい。

第２の方法では、第ａ階層のコミュニティ［ｋ］の固有重みｐ（Ｃ^（ａ） _ｋ）は、以下の数式（１７）により求められる。

数式（１５）により算出された絶対重みｐ（Ｃ^（ａ） _ｋ、Ｃ^（ｂ） _ｌ）及び数式（１６）により算出された固有重みｐ（Ｃ^（ａ） _ｋ）から、第１の方法においても、数式（１４）により第ａ階層のコミュニティ［ｋ］と第ｂ階層のコミュニティ［ｌ］との間の相対重み（依存度）ｐ（Ｃ^（ａ） _ｋ｜Ｃ^（ｂ） _ｌ）が算出される。第１の方法の特徴は、１つのノードが複数のコミュニティに属する場合に、コミュニティ間の親子関係を導出する点である。そのため、上層コミュニティは、潜在的に全ての下層コミュニティを親として持つこととなる。

次に、依存度を求める第３の方法について説明する。第３の方法は、ネットワーク情報１０が向きを持ったリンクを含む場合に適用される。図２に示すネットワーク情報１０の例では、リンクは向きを持たないが、全てのリンクそれぞれを、向きが互いに逆である２つのリンクに置き換えることで、第３の方法を適用することができる。図２に示すネットワーク情報１０の例では、リンクの総数は９だが、全てのリンクを有向リンクに置き換えると、リンクの総数は１８となる。

第３の方法では、第ａ階層のコミュニティ［ｋ］と第ｂ階層のコミュニティ［k’］との間の絶対重みｐ（Ｃ^（ａ） _ｋ、Ｃ^（ｂ） _ｋ’）は、以下の数式（１８）により求められる。ここで、ｐ^〜（ｌ）は、ネットワーク情報１０に含まれるリンクの確率分布であり、数式（１９）で与えられる。また、Ｌはネットワーク情報１０に含まれるリンクの総数である。Ｉ（ｌ∈Ｃ^（ａ） _ｋ）は、リンク［ｌ］が第ａ階層のコミュニティ［ｋ］に属する場合に１、リンク［ｌ］が第ａ階層のコミュニティ［ｋ］に属さない場合に０となる関数である。Ｉ（ｌ∈Ｃ^（ａ） _ｋ）は、リンク［ｌ］がコミュニティ［ｋ］に属するか否かを表す関数といえる。

ｐ^〜（ｌ）の具体的な表式は、以下の数式（１９）で与えられる。ｐ^〜（ｌ）は、リンク［ｌ］の出発ノード［ｎ_ｌ］の定常確率分布ｐ^ｓｔ（ｎ_ｌ）を、ノード［ｎ_ｌ］から発するリンクの数ｄ^ｏｕｔ（ｎ_ｌ）で割った値である。ここで、出発ノード［ｎ_ｌ］は、リンク［ｌ］が結ぶ２つのノードのうち出発側のノードを表す。ｐ^〜（ｌ）は、ノードの定常確率分布を、当該ノードに繋がるリンクの数で割ったものであり、Σ_ｌｐ^〜（ｌ）＝１を満たす。

第３の方法では、第ａ階層のコミュニティ［ｋ］の固有重みｐ（Ｃ^（ａ） _ｋ）は、以下の数式（２０）により求められる。

数式（１８）により算出された絶対重みｐ（Ｃ^（ａ） _ｋ、Ｃ^（ｂ） _ｋ’）及び数式（２０）により算出された固有重みｐ（Ｃ^（ａ） _ｋ）から、第３の方法においても、数式（１４）により第ａ階層のコミュニティ［ｋ］と第ｂ階層のコミュニティ［ｋ’］との間の相対重み（依存度）ｐ（Ｃ^（ａ） _ｋ｜Ｃ^（ｂ） _ｋ’）が算出される。第３の方法の特徴は、ネットワーク情報１０に含まれる有向リンクに着目し、コミュニティの親子関係を、リンクがいずれのコミュニティに属するかという観点から算出する点である。そのため、ネットワーク情報１０を構成するリンクの接続状態に応じて、異なる階層間のコミュニティの親子関係が導出される。

１ 情報処理装置、１０ ネットワーク情報、１１ 入力部、１２ 解像度、１３ 制御部、１４ 記憶部、１５ 表示部、１３０ ネットワーク情報取得部、１３１ 第１階層コミュニティ生成部、１３１ａ 分類割合算出部、１３１ｂ 重要度算出部、１３１ｃ 帰属度算出部、１３２ 第２階層コミュニティ生成部、１３２ａ 分類割合更新部、１３２ｂ 重要度更新部、１３２ｃ 帰属度更新部、１３２ｄ 重要度変化算出部、１３２ｅ 重要度変化判定部、１３２ｆ 解像度取得部、１３２ｇ 安定解像度算出部、１３３ 依存度算出部、１３４ 独立部分判定部、１３５ コミュニティ修正部。

Claims (9)

1. リンクで結ばれる注目ノード及び隣接ノードを含むネットワーク情報を取得するネットワーク情報取得手段と、
   前記ネットワーク情報の予め定められた数の複数のコミュニティそれぞれに前記注目ノードが分類される分類割合を、前記複数のコミュニティそれぞれに前記隣接ノードが分類される分類割合と、所与の解像度に応じた相関を有するようにして算出する分類割合算出手段と、
   前記解像度の第１の値に応じて算出された、前記注目ノードに関する前記分類割合から、前記注目ノードが属する、前記ネットワーク情報の１以上の第１種コミュニティを生成する第１種コミュニティ生成手段と、
   前記注目ノードに関する前記分類割合を、前記複数のコミュニティそれぞれに前記隣接ノードが分類される分類割合と、前記解像度の第２の値に応じた相関を有するようにして更新する分類割合更新手段と、
   前記分類割合更新手段により更新された前記注目ノードに関する前記分類割合から、前記注目ノードが属する、前記ネットワーク情報の１以上の第２種コミュニティを生成する第２種コミュニティ生成手段と、
   を備える情報処理装置。
2. 前記１以上の第２種コミュニティのうち１つの上層コミュニティが、前記１以上の第１種コミュニティのうち１つの下層コミュニティに依存する割合を示す依存度を、前記上層コミュニティに分類される１以上の前記ノードと、前記下層コミュニティに分類される１以上の前記ノードとの重複が多いほど大きくなるように算出する依存度算出手段をさらに備える
   請求項１に記載の情報処理装置。
3. 前記複数のコミュニティのうち１つのコミュニティの重要度を、前記複数のコミュニティ全体に対して当該１つのコミュニティが占める割合が大きいほど大きな値となるように、前記分類割合算出手段により算出された前記分類割合を用いて算出する重要度算出手段と、
   前記分類割合更新手段により更新された前記分類割合を用いて前記重要度算出手段により算出された前記重要度を更新する重要度更新手段と、
   前記重要度更新手段により更新された前記重要度の、更新前後の変化の量を算出する重要度変化算出手段と、
   前記重要度変化算出手段により算出された変化の量が予め定められた量よりも大きいか否かを判定する重要度変化判定手段と、
   をさらに備える請求項２に記載の情報処理装置。
4. 前記重要度変化判定手段により前記重要度の変化の量が予め定められた量よりも大きいと判定された場合における前記解像度の値を取得する解像度取得手段と、
   前記解像度取得手段により取得された２つの前記解像度の値の間の値を有する安定解像度を算出する安定解像度算出手段と、をさらに備え、
   前記依存度算出手段は、前記安定解像度を用いて、前記依存度を算出する
   請求項３に記載の情報処理装置。
5. 前記安定解像度算出手段は、前記解像度取得手段により取得された２つの前記解像度の値の中点の値を前記安定解像度として算出する
   請求項４に記載の情報処理装置。
6. 前記分類割合算出手段は、逐次計算により、前記分類割合を算出し、
   前記分類割合更新手段は、前記分類割合算出手段による逐次計算の回数よりも少ない回数の逐次計算により、前記第１の分類割合を前記第２の分類割合に更新する
   請求項１乃至５のいずれか１項に記載の情報処理装置。
7. 前記分類割合更新手段による更新の前に、前記１以上の第１種コミュニティのうち少なくとも１つが、２以上の独立した部分を含むか否かを判定する独立部分判定手段と、
   前記独立部分判定手段により、前記１以上の第１種コミュニティのうち少なくとも１つが、２以上の独立した部分を含むと判定される場合に、当該２以上の独立した部分が２以上の第１種コミュニティとなるように前記１以上の第１種コミュニティを修正するコミュニティ修正手段と、
   をさらに備える請求項１乃至６のいずれか１項に記載の情報処理装置。
8. 前記第１種コミュニティ生成手段及び前記第２種コミュニティ生成手段は、２以上の前記第１種コミュニティ及び２以上の前記第２種コミュニティをそれぞれ生成する
   請求項１乃至７のいずれか１項に記載の情報処理装置。
9. 情報処理装置に備えられたコンピュータを、
   リンクで結ばれる注目ノード及び隣接ノードを含むネットワーク情報を取得するネットワーク情報取得手段、
   前記ネットワーク情報の予め定められた数の複数のコミュニティそれぞれに前記注目ノードが分類される分類割合を、前記複数のコミュニティそれぞれに前記隣接ノードが分類される分類割合と、所与の解像度に応じた相関を有するようにして算出する分類割合算出手段、
   前記解像度の第１の値に応じて算出された、前記注目ノードに関する前記分類割合から、前記注目ノードが属する、前記ネットワーク情報の１以上の第１種コミュニティを生成する第１種コミュニティ生成手段、
   前記注目ノードに関する前記分類割合を、前記複数のコミュニティそれぞれに前記隣接ノードが分類される分類割合と、前記解像度の第２の値に応じた相関を有するようにして更新する分類割合更新手段、
   前記分類割合更新手段により更新された前記注目ノードに関する前記分類割合から、前記注目ノードが属する、前記ネットワーク情報の１以上の第２種コミュニティを生成する第２種コミュニティ生成手段、
   として機能させるプログラム。

Images