(57)【要約】【課題】複数層のネットワークであり、一部または全部のノードが各層に共通して含まれるネットワークにおいて、ある層でコミュニティ抽出を行う際に他の層のコミュニティ構造を反映したコミュニティ抽出を行う。【解決手段】制御部１０は、少なくとも一部のノードが各層に共通して含まれる多層ネットワークにおいて、制約層における共有ノードのコミュニティへの第１所属確率を算出する。制御部１０は、抽出層の各ノードのコミュニティへの所属確率についての確率モデルの評価式であり、第１所属確率と抽出層における共有ノードのコミュニティへの所属確率を加えた評価式の値を最大化する第２所属確率の算出結果によりコミュニティ抽出を行う。【選択図】図１
2019040285.tif 000002
【特許請求の範囲】
【請求項１】
多層ネットワークにおいて、制約層における共有ノードのコミュニティへの第１所属確率を算出する算出手段と、
抽出層の各ノードのコミュニティへの所属確率についての確率モデルの評価式であり、前記第１所属確率と前記抽出層における共有ノードのコミュニティへの第２所属確率を加えた評価式の値を最大化する前記第２所属確率の算出結果により前記抽出層のコミュニティ抽出を行う抽出手段と
を備える情報処理装置。
【請求項２】
前記制約層が複数である請求項１に記載の情報処理装置。
【請求項３】
複数の前記制約層の各々は、他の制約層に対して共有ノード以外のノードの属性が異なる
請求項２に記載の情報処理装置。
【請求項４】
前記抽出層は、時間の経過により変化した層であり、複数の前記制約層は、時間軸上で前記抽出層より過去または未来の時点の層である
請求項２に記載の情報処理装置。
【請求項５】
複数の前記制約層の各々が重みを有し、
前記抽出手段は、前記重みを含めて前記第２所属確率を算出する
請求項３または請求項４に記載の情報処理装置。
【請求項６】
前記共有ノードが複数であり、
複数の前記共有ノードの各々が重みを有し、
前記抽出手段は、前記重みを含めて前記第２所属確率を算出する
請求項１に記載の情報処理装置。
【請求項７】
前記多層ネットワークは、前記制約層に対する共有ノードと前記抽出層に対する共有ノードとが異なる中間層を有し、
前記抽出手段は、当該中間層を介して前記第２所属確率を算出する
請求項１に記載の情報処理装置。
【請求項８】
前記抽出手段の抽出結果から複数の前記制約層の各々と前記抽出層との関連性を算出する算出手段
を有する請求項２に記載の情報処理装置。
【請求項９】
複数の前記制約層の各々が重みを有し、
前記抽出手段は、前記重みを含めて前記第２所属確率を算出し、
前記重みを前記算出手段の算出結果に応じて設定する
請求項８に記載の情報処理装置。
【請求項１０】
コンピュータを、
多層ネットワークにおいて、制約層における共有ノードのコミュニティへの第１所属確率を算出する算出手段と、
抽出層の各ノードのコミュニティへの所属確率についての確率モデルの評価式であり、前記第１所属確率と、前記抽出層における共有ノードのコミュニティへの第２所属確率を加えた評価式の値を最大化する前記第２所属確率の算出結果により前記抽出層のコミュニティ抽出を行う抽出手段
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置およびプログラムに関する。
【背景技術】
【０００２】
マルチレイヤー構造を有する要素集合グラフに対してクラスタリングを行う発明として、例えば特許文献１に開示された要素集団抽出システムがある。このシステムは、マルチレイヤー構造を有する要素集合グラフにおいて、ノードのクラスタリングを行う層の順位を決定し、クラスタリングを行う層に属するノードを対象としてクラスタを抽出する。そして、ある層におけるクラスタと、そのクラスタを構成するノードとの層間のエッジでリンクされる下位の層のノードから構成されるクラスタとを一つの集団として抽出する。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００９−１７６０７２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
複数層のネットワークであり、一部または全部のノードが各層に共通して含まれるネットワークにおいて、ある層のコミュニティ構造に依存する特徴を持つ別の層のコミュニティを抽出する場合、ある層のコミュニティ構造を無視した構造でコミュニティ抽出が行われてしまうことがある。
【０００５】
本発明は、複数層のネットワークであり、一部または全部のノードが各層に共通して含まれるネットワークにおいて、ある層でコミュニティ抽出を行う際に他の層のコミュニティ構造を反映したコミュニティ抽出を行うことを目的とする。
【課題を解決するための手段】
【０００６】
本発明の請求項１に係る情報処理装置は、多層ネットワークにおいて、制約層における共有ノードのコミュニティへの第１所属確率を算出する算出手段と、抽出層の各ノードのコミュニティへの所属確率についての確率モデルの評価式であり、前記第１所属確率と前記抽出層における共有ノードのコミュニティへの第２所属確率を加えた評価式の値を最大化する前記第２所属確率の算出結果により前記抽出層のコミュニティ抽出を行う抽出手段とを備える。
【０００７】
本発明の請求項２に係る情報処理装置は、前記制約層が複数である。
【０００８】
本発明の請求項３に係る情報処理装置においては、複数の前記制約層の各々は、他の制約層に対して共有ノード以外のノードの属性が異なる。
【０００９】
本発明の請求項４に係る情報処理装置においては、前記抽出層は、時間の経過により変化した層であり、複数の前記制約層は、時間軸上で前記抽出層より過去または未来の時点の層である。
【００１０】
本発明の請求項５に係る情報処理装置においては、複数の前記制約層の各々が重みを有し、前記抽出手段は、前記重みを含めて前記第２所属確率を算出する。
【００１１】
本発明の請求項６に係る情報処理装置においては、前記共有ノードが複数であり、複数の前記共有ノードの各々が重みを有し、前記抽出手段は、前記重みを含めて前記第２所属確率を算出する。
【００１２】
本発明の請求項７に係る情報処理装置においては、前記多層ネットワークは、前記制約層に対する共有ノードと前記抽出層に対する共有ノードとが異なる中間層を有し、前記抽出手段は、当該中間層を介して前記第２所属確率を算出する。
【００１３】
本発明の請求項８に係る情報処理装置は、前記抽出手段の抽出結果から複数の前記制約層の各々と前記抽出層との関連性を算出する算出手段を有する。
【００１４】
本発明の請求項９に係る情報処理装置は、複数の前記制約層の各々が重みを有し、前記抽出手段は、前記重みを含めて前記第２所属確率を算出し、前記重みを前記算出手段の算出結果に応じて設定する。
【００１５】
本発明の請求項１０に係るプログラムは、コンピュータを、多層ネットワークにおいて、制約層における共有ノードのコミュニティへの第１所属確率を算出する算出手段と、抽出層の各ノードのコミュニティへの所属確率についての確率モデルの評価式であり、前記第１所属確率と前記抽出層における共有ノードのコミュニティへの第２所属確率を加えた評価式の値を最大化する前記第２所属確率の算出結果により前記抽出層のコミュニティ抽出を行う抽出手段として機能させるためのプログラムである。
【発明の効果】
【００１６】
本発明の請求項１に係る情報処理装置によれば、複数層のネットワークであり、一部または全部のノードが各層に共通して含まれるネットワークにおいて、ある層でコミュニティ抽出を行う際に他の層のコミュニティ構造を反映したコミュニティ抽出を行うことができる。
本発明の請求項２に係る情報処理装置によれば、ある層でコミュニティ抽出を行う際に他の複数層のコミュニティ構造を反映したコミュニティ抽出を行うことができる。
本発明の請求項３に係る情報処理装置によれば、多様な複数の制約層を基に抽出層のコミュニティ抽出を行うことができる。
本発明の請求項４に係る情報処理装置によれば、時間の経過で変化したネットワークについて、抽出層から見て過去または未来のコミュニティの抽出結果を基にコミュニティの抽出を行うことができる。
本発明の請求項５に係る情報処理装置によれば、抽出層とより関連する制約層におけるコミュニティの抽出結果を反映して抽出層のコミュニティを抽出することができる。
本発明の請求項６に係る情報処理装置によれば、共有ノードの重みを反映して抽出層のコミュニティを抽出することができる。
本発明の請求項７に係る情報処理装置によれば、制約層と抽出層との間で共有ノードがなくとも、制約層におけるコミュニティの抽出結果を反映して抽出層でコミュニティを抽出することができる。
本発明の請求項８に係る情報処理装置によれば、制約層と抽出層の関連を知ることができる。
本発明の請求項９に係る情報処理装置によれば、抽出層により関連した制約層におけるコミュニティの抽出結果を反映して抽出層でコミュニティを抽出することができる。
本発明の請求項１０に係るプログラムによれば、複数層のネットワークであり、一部または全部のノードが各層に共通して含まれるネットワークにおいて、ある層でコミュニティ抽出を行う際に他の層のコミュニティ構造を反映したコミュニティ抽出を行うことができる。
【図面の簡単な説明】
【００１７】
【図１】本発明の一実施形態に係る情報処理装置の構成を示した図。
【図２】多層ネットワークの一例を示した図。
【図３】制御部１０が行う処理の流れを示したフローチャート。
【図４】多層ネットワークの一例を示した図。
【図５】多層ネットワークの一例を示した図。
【図６】多層ネットワークの一例を示した図。
【図７】多層ネットワークの一例を示した図。
【図８】多層ネットワークの一例を示した図。
【発明を実施するための形態】
【００１８】
［実施形態］
図１は、本発明に係る情報処理装置１の構成の一例を示した図である。情報処理装置１は、コンピュータ装置であり、制御部１０、記憶部１１、操作部１２、表示部１３および通信部１４を備える。
【００１９】
通信部１４は、通信回線に接続されており、他のコンピュータ装置と通信を行う通信インターフェースの機能を有する。表示部１３は、ディスプレイ装置であり、制御部１０が行った処理の結果を表示する。操作部１２は、例えば情報処理装置１を操作するためのキーボードやマウス等である。
【００２０】
記憶部１１は、データを永続的に記憶する記憶装置を含み、ネットワークデータを記憶する。ネットワークデータは、一部または全部のノードが各層に共通して含まれる多層ネットワーク（図２）を表すデータである。ネットワークデータは、層の集合{l1,l2,・・・,ll,・・・,lL}を持ち、各層llはノードの集合{nl1,nl2,・・・,nln,・・・,nlN}とリンクの集合{el1,el2,・・・,ele,・・・,elE}で表され、各リンクeleは同じ層に含まれるノードペア{nlm,nln}で表される。
【００２１】
例えば、図２の層ｌ１と層ｌ２おいては、丸形のノードは人を表している。また、層ｌ１においては、三角形のノードは映画のタイトルを表しており、層ｌ２においては、四角形のノードはドラマのタイトルを表している。また、図２のリンクは、層ｌ１においては、各人の映画の視聴履歴を表し、層ｌ２においては、各人のドラマの視聴履歴を表している。
【００２２】
また、記憶部１１は、制御部１０が実行するプログラムを記憶する。記憶部１１に記憶されるプログラムは、通信部１４により電気通信回線を介して取得したものや、コンピュータ読み取り可能な記録媒体から取得したものであってもよい。記憶部１１が記憶するプログラムは、多層ネットワークにおいてコミュニティ抽出を行うプログラムであり、本実施形態においては、ある層で他の層のコミュニティ構造を反映してコミュニティ抽出を行う。以下の説明においては、例えば、図２に例示したように、層ｌ１のコミュニティｋ´の構造を反映して層ｌ２でコミュニティ抽出を行う場合、コミュニティ構造の反映の基となる層ｌ１を制約層と称し、コミュニティの抽出が行われる層ｌ２を抽出層と称する。また、制約層と抽出層の両方に含まれるノード、即ち、人を表す丸形のノードを共有ノードと称する。
【００２３】
制御部１０は、ＣＰＵ（Central Processing Unit）とＲＡＭ（Random Access Memory）を備えており、記憶部１１に記憶されているプログラムを実行する。記憶部１１に記憶されているプログラムを制御部１０が実行すると、取得部１０１、算出部１０２、および抽出部１０３が実現し、多層ネットワークにおいてコミュニティ抽出を行う機能が実現する。
【００２４】
取得部１０１は、ネットワークデータを記憶部１１から取得する。算出部１０２は、取得したネットワークデータを用いて、制約層における共有ノードｎｓのコミュニティｋ´への所属確率Ｐ（ｎｓ｜ｋ´）を算出する。抽出部１０３は、算出部１０２の算出結果と、ネットワークデータを用いて抽出層でコミュニティ抽出を行う際に制約層のコミュニティ構造を反映したコミュニティ抽出を行う。
【００２５】
制御部１０が抽出層についてコミュニティ抽出を行う方法としては、例えば、各ノードのコミュニティ所属確率についての確率モデルを与え、確率モデルの評価式Ｑ（例えば尤度や事後確率）を最大化することでデータに合うコミュニティ所属確率を得る方法を採用している。この方法としては、例えば、本願の出願人に係る特開２０１６−２９５２６号公報に記載された方法がある。
【００２６】
本実施形態においては、特開２０１６−２９５２６号公報に記載された評価式Ｑに対して、制約層における共有ノードｎｓのコミュニティｋ´への所属確率Ｐ（ｎｓ｜ｋ´）と、抽出層における共有ノードｎｓのコミュニティｋへの所属確率Ｐ（ｎｓ｜ｋ）とのＫＬＤ（Kullback-Leibler Divergence）を制約項として加えた評価式Ｑ´を求めた。所属確率Ｐ（ｎｓ｜ｋ´）は、本発明に係る第１所属確率の一例であり、所属確率ｐ（ｎｓ｜ｋ）は、本発明に係る第２所属確率の一例である。
【００２７】
【数１】
2019040285.tif 000003
【００２８】
上記の式においてＰ（ｎｓ｜ｋ´）とｐ（ｎｓ｜ｋ）とのＫＬＤとして加えられた制約項は、数２で示した項である。λはＫＬＤによる制約の強さを決めるパラメータであり、ベクトルｃ（ｋ）は、抽出層のコミュニティｋが、どの制約層のコミュニティｋ´から制約を受けるかを決めるone-hotベクトルである。本実施形態においては、ベクトルｃ（ｋ）は、ｘ番目の要素をベクトルｃ（ｋ）ｘとすると、ｘ≡ｋ  ｍｏｄ  Ｋ´のときにベクトルｃ（ｋ）ｘ＝１となり、それ以外のときにベクトルｃ（ｋ）ｘ＝０となる。
【００２９】
【数２】
2019040285.tif 000004
【００３０】
本実施形態では、評価式Ｑ´を最大化するためにＥＭアルゴリズムを採用し、ＥＭアルゴリズムの更新式として数３に示した（１）〜（４）の式を得た。
【００３１】
【数３】
2019040285.tif 000005
【００３２】
ｋは抽出層のコミュニティの識別子、Ｋは抽出層のコミュニティの数、ｋ´は制約層のコミュニティの識別子、Ｋ´は制約層のコミュニティの数である。また、ｎｓは共有ノードの識別子、ｎ-ｓは抽出層における共有ノード以外のノードの識別子、Ｓは共有ノードの集合、λは、ＫＬＤによる制約の強さを決めるパラメータである。割合γｔ（ｄ）（ｋ）は、複数のコミュニティ全体に対してコミュニティｋが占める割合を表す。所属確率Ｐｔ（ｎｓ｜ｋ）は、抽出層のコミュニティについて、共有ノードがコミュニティに分類される割合を表す。所属確率Ｐｔ（ｎ-ｓ｜ｋ）は、抽出層のコミュニティについて、共有ノード以外のノードがコミュニティに分類される割合を表す。重要度πｔ（ｋ）は、抽出層のコミュニティｋの重要度を表す。他のパラメータについては、本出願人に係る特開２０１６−２９５２６号公報を参照されたい。
【００３３】
次に、数３で示した式により抽出層においてコミュニティ抽出を行う処理の流れについて説明する。図３は、制御部１０が、抽出層においてコミュニティ抽出を行う処理の流れを示したフローチャートである。まず制御部１０（算出部１０２）は、予め定められた方法で、ネットワークデータから制約層における共有ノードｎｓのコミュニティｋ´への所属確率Ｐ（ｎｓ｜ｋ´）を算出する（ステップＳＡ１）。所属確率Ｐ（ｎｓ｜ｋ´）を算出する方法としては、例えば、Ｌｏｕｖａｉｎ法やＩｎｆｏＭａｐ法などの周知の方法がある。
【００３４】
制御部１０（抽出部１０３）は、ステップＳＡ１の処理を終えると、パラメータを決定する（ステップＳＡ２）。ここで制御部１０は、λとベクトルｃ（ｋ）を決定する。本実施形態においては、λ＝Ｋ／Ｋ´とする。
【００３５】
次に制御部１０（抽出部１０３）は、ネットワークデータが表すネットワークのノード間をランダムに遷移する場合における定常確率分布ｐｓｔ（ｎ）を算出する（ステップＳＡ３）。ここで制御部１０は、例えば周知のアルゴリズムであるＰａｇｅｒａｎｋのアルゴリズムによって定常確率分布ｐｓｔ（ｎ）を算出する。
【００３６】
次に制御部１０（抽出部１０３）は、複数のノード間を複数のリンクに沿ってランダムに遷移する場合に通過するノードを示す複数の通過情報τｎ（ｄ）を生成する（ステップＳＡ４）。本実施形態では、制御部１０は、通過情報について、ステップＳＡ３で算出した定常確率分布ｐｓｔ（ｎ）に従って選出されたノード［ｎ］についてτｎ（ｄ）＝１、かつ、ノード［ｎ］を起点としてノード［ｍ］に遷移する確率を与える遷移確率行列Ｔｎｍに従って選出されたノード［ｍ］についてτｍ（ｄ）＝１として生成し、このようなＮ次元ベクトルを、Ｄ回生成する。通過情報τｎ（ｄ）は、Σｎτｎ（ｄ）＝２を満たす量である。通過情報τｎ（ｄ）は、仮想エージェントがノード間をリンクに沿ってランダムに遷移する場合に、仮想エージェントをノード［ｎ］とノード［ｍ］とを結ぶリンク上に見出す場合を表している。遷移確率行列Ｔｎｍはネットワーク内のノードｍからノードｎへリンクを辿ってエージェントが遷移（ランダムウォーク）する確率を行列として表したものである。遷移確率行列は、ネットワークデータに含まれていてもよく、また、ネットワークデータから生成してもよい。遷移確率行列Ｔｎｍについては、例えば、特開２０１６−２９５２６号公報も参照されたい。
【００３７】
次に制御部１０（抽出部１０３）は、ＥＭアルゴリズムの繰り返し計算を開始するにあたり、所属確率Ｐｔ（ｎｓ｜ｋ）の初期値であるｐ０（ｎｓ｜ｋ）と、重要度πｔ（ｋ）の初期値であるπ０（ｋ）を決定する（ステップＳＡ５）。ここでは、Σｎｐ０（ｎｓ｜ｋ）＝１、Σｋπ０（ｋ）＝１を満たす値を与えるものとする。ｐ０（ｎｓ｜ｋ）は、ｋ＝１〜Ｋのコミュニティについて、ｎ＝１〜Ｎのノードが分類される割合を示すものであるから、仮決めではＫ×Ｎ−１個の正の実数を与えることになる。なお、−１はΣｎｐ０（ｎｓ｜ｋ）＝１の条件による。また、π０（ｋ）は、ｋ＝１〜Ｋに分類されたネットワークのコミュニティについて、重要度を示すものであるから、仮決めではＫ−１個の正の実数を与えることになる。
【００３８】
次に制御部１０（抽出部１０３）は、ＥＭアルゴリズムの繰り返し計算の回数をカウントするカウンタｇの値を初期化する（ステップＳＡ６）。制御部１０（抽出部１０３）は、カウンタｇの値を初期化すると、数３の（１）の式により、割合γｔ（ｄ）（ｋ）を算出する（ステップＳＡ７）。このステップは、ＥＭアルゴリズムのＥステップに相当する。ここで、ｔは正の整数であり、逐次計算の回数を表す。γｔ（ｄ）（ｋ）は、繰り返し計算における一つ前の計算により得られるｐｔ−１（ｎ｜ｋ）およびπｔ−１（ｋ）より算出される。ステップＳＡ５の後に行われる第一回目の計算では、ｐ０（ｎ｜ｋ）およびπ０（ｋ）を用いてγｔ（ｄ）（ｋ）を求めることになる。
【００３９】
次に制御部１０（抽出部１０３）は、数３の（２）〜（４）の式により、所属確率Ｐｔ（ｎｓ｜ｋ）、所属確率Ｐｔ（ｎ-ｓ｜ｋ）および重要度πｔ（ｋ）を算出する（ステップＳＡ８）。このステップは、ＥＭアルゴリズムのＭステップに相当する。所属確率Ｐｔ（ｎｓ｜ｋ）、所属確率Ｐｔ（ｎ-ｓ｜ｋ）および重要度πｔ（ｋ）は、繰り返し計算における一つ前の計算により得られるｐｔ−１（ｎｓ｜ｋ）およびγｔ−１（ｄ）（ｋ）より算出される。ステップＳＡ５の後に行われる第一回目の計算では、ｐ０（ｎ｜ｋ）およびステップＳＡ７で得られたγｔ（ｄ）（ｋ）を用いて求めることとなる。
【００４０】
また、αは予め設定されているまたは記憶部１１に記憶された粒度αであり、正の実数である。粒度αは、情報処理装置１によってネットワークデータをソフトクラスタリングする場合に、クラスタの大きさを定めるパラメータである。本実施形態では、粒度αは、αが０に近付くほど分解の粒度が細かくなり、αが無限大に近付くほど分解の粒度が粗くなるパラメータである。
【００４１】
制御部１０（抽出部１０３）は、ステップＳＡ８の処理を終えると、Ｐｔ−１（ｎ｜ｋ）とπｔ−１（ｋ）を更新する（ステップＳＡ９）。具体的には、制御部１０は、Ｐｔ−１（ｎ｜ｋ）＝Ｐｔ（ｎ｜ｋ）とし、πｔ−１（ｋ）＝πｔ（ｋ）とする。
【００４２】
次に制御部１０（抽出部１０３）は、カウンタｇの値をインクリメントし（ステップＳＡ１０）、カウンタｇの値が予め定められた値Ｇ以上であるか判断する（ステップＳＡ１１）。制御部１０（抽出部１０３）は、カウンタｇの値が値Ｇ未満である場合（ステップＳＡ１１でＮＯ）、処理の流れをステップＳＡ７へ移し、ステップＳＡ７〜ステップＳＡ１０の処理を繰り返す。
【００４３】
制御部１０（抽出部１０３）は、カウンタｇの値が値Ｇ以上である場合（ステップＳＡ１１でＹＥＳ）、所属確率Ｐ（ｎｓ｜ｋ）、所属確率Ｐ（ｎ-ｓ｜ｋ）および重要度πｋを決定する（ステップＳＡ１２）。ここで制御部１０は、繰り返し計算の最後に得られた所属確率Ｐｔ（ｎｓ｜ｋ）を、抽出層のコミュニティにおいて共有ノードｎｓがコミュニティに分類される所属確率Ｐ（ｎｓ｜ｋ）とし、Ｐｔ（ｎ-ｓ｜ｋ）を、抽出層のコミュニティにおいて共有ノード以外のノードｎ-ｓがコミュニティに分類される所属確率Ｐ（ｎ-ｓ｜ｋ）とし、πｔ（ｋ）を、抽出層のコミュニティｋの重要度πｋとし、所属確率Ｐ（ｎｓ｜ｋ）、所属確率Ｐ（ｎ-ｓ｜ｋ）およびπｋをコミュニティの抽出結果として得る。
【００４４】
なお、ノードｎ（ｎｓまたはｎ−ｓ）が紐づくコミュニティの集合をＫｎとすると、数４の式によりコミュニティの抽出結果からコミュニティに関連する代表的なノードを知ることができる。また、数５の式により、各ノードがどのコミュニティに属するかを知ることができる。
【００４５】
【数４】
2019040285.tif 000006
【００４６】
【数５】
2019040285.tif 000007
【００４７】
［変形例］
以上、本発明の実施形態について説明したが、本発明は上述した実施形態に限定されることなく、他の様々な形態で実施可能である。例えば、上述の実施形態を以下のように変形して本発明を実施してもよい。なお、上述した実施形態および以下の変形例は、各々を組み合わせてもよい。
【００４８】
上述した実施形態においては、制約層が一つの場合に抽出層からコミュニティ抽出を行う構成について説明したが、複数の制約層のコミュニティ構造を反映して抽出層からコミュニティ抽出を行ってもよい。例えば、図４に例示したように、層ｌ１から層ｌＡまでの複数（Ａ枚）の制約層のコミュニティ構造を反映して抽出層ｌＡ＋１からコミュニティ抽出を行う場合、評価式Ｑ´は、数６に示した式となる。
【００４９】
【数６】
2019040285.tif 000008
【００５０】
また、複数（Ａ枚）の制約層のコミュニティ構造を反映して抽出層からコミュニティ抽出を行う場合、ＥＭアルゴリズムの更新式として数７の式を得る。
【００５１】
【数７】
2019040285.tif 000009
【００５２】
制御部１０は、複数の制約層のコミュニティ構造を反映して抽出層からコミュニティ抽出を行う場合、ステップＳＡ７においては、数３の（１）の式に替えて、数７の（１）の式で割合γｔ（ｄ）（ｋ）を算出する。また、制御部１０は、複数の制約層のコミュニティ構造を反映して抽出層からコミュニティ抽出を行う場合、ステップＳＡ８において、数３の（２）〜（４）に替えて、数７の（２）〜（４）の式で所属確率Ｐｔ（ｎｓ｜ｋ）、所属確率Ｐｔ（ｎ-ｓ｜ｋ）および重要度πｔ（ｋ）を算出する。
【００５３】
また、上述したように制約層が複数である場合、抽出層と各制約層との関連性に応じて制約層毎に重みを付与し、制約層に付与した重みを反映して抽出層におけるコミュニティ抽出を行ってもよい。例えば、図５に示したように、層ｌ１の制約層には重みｗ１、層ｌ２の制約層には重みｗ２、・・・層ｌ１から数えてＡ番目の層ｌＡの制約層には重みｗＡを付与する。各制約層に付与する重みについては、情報処理装置１の操作者が任意に設定してもよい。各制約層に重みを付与し、層ｌ１から層ｌＡまでの複数（Ａ枚）の制約層のコミュニティ構造と各制約層の重みを反映して抽出層ｌＡ＋１からコミュニティ抽出を行う場合、評価式Ｑ´は、数８に示した式となる。
【００５４】
【数８】
2019040285.tif 000010
【００５５】
また、層ｌ１から層ｌ１Ａまでの複数（Ａ枚）の制約層のコミュニティ構造と各制約層の重みを反映して抽出層ｌＡ＋１からコミュニティ抽出を行う場合、ＥＭアルゴリズムの更新式として数９の式を得る。
【００５６】
【数９】
2019040285.tif 000011
【００５７】
上記数８の式は、制約層に付与した重みｗａが付加されている点が数６の式と相違している。また、上記数９の式は、制約層に付与した重みｗａが付加されている点が数７の式と相違している。
【００５８】
制御部１０は、重みが付与された複数の制約層のコミュニティ構造を反映して抽出層からコミュニティ抽出を行う場合、ステップＳＡ７においては、数３の（１）の式に替えて、数９の（１）の式で割合γｔ（ｄ）（ｋ）を算出する。また、制御部１０は、複数の制約層のコミュニティ構造を反映して抽出層からコミュニティ抽出を行う場合、ステップＳＡ８において、数３の（２）〜（４）に替えて、数９の（２）〜（４）の式で所属確率Ｐｔ（ｎｓ｜ｋ）、所属確率Ｐｔ（ｎ-ｓ｜ｋ）および重要度πｔ（ｋ）を算出する。
【００５９】
上述した実施形態においては、抽出層に対して共有ノードがある制約層について、制約層のコミュニティ構造を反映して抽出層のコミュニティを抽出しているが、制約層と抽出層との間で共有ノードがない状態であっても、抽出層のコミュニティ抽出を行ってもよい。例えば、図６に例示したように、制約層と中間層との間で丸形のノードが共有ノードであり、中間層と抽出層との間で五角形のノードが共有ノードであって、制約層と抽出層との間に共有ノードがない場合を想定する。この場合、制約層と抽出層のそれぞれに共有ノードを持つ中間層を介してコミュニティ抽出を行うことで、制約層の影響を受けた状態で抽出層からコミュニティ抽出を行うことができる。
【００６０】
本発明においては、時間の経過によって、共有ノード以外のノードが変化するネットワークデータについて、ある時点のネットワークを抽出層とし、ある時点より前または後の複数の時点のネットワークを制約層とし、制約層におけるコミュニティの抽出結果を反映して抽出層においてコミュニティ抽出を行ってもよい。例えば、図７に例示したように、時点ｔＡのときのネットワークを抽出層ｌＡとし、時点ｔ１のときのネットワークと時点ｔ２のときのネットワークを制約層とする場合を想定する。このようなネットワークの一例としては、例えば、組織内の人と、所属する部署のネットワークがあり、共有ノードが人となり、共有ノードにリンクするノードは例えば部署名となる。この場合、時点ｔ１の制約層ｌ１と時点ｔ２の制約層ｌ２とに重みｗａを付与する。重みｗａは、数１０の式または数１１の式により値を定める。そして、重みｗａの項を含む数９の式により、抽出層においてコミュニティ抽出を行う。数１０の式によれば、重みｗａは時間軸上で抽出層ｌＡから制約層までの時間が長くなるにつれて線形減衰し、数１１の式によれば、重みｗａは時間軸上で抽出層ｌＡから制約層までの時間が長くなるにつれて指数減衰する。
【００６１】
【数１０】
2019040285.tif 000012
【００６２】
【数１１】
2019040285.tif 000013
【００６３】
本発明においては、制約層のコミュニティ構造を反映して抽出層でコミュニティ抽出を行う場合、複数の共有ノード毎に重みを付与し、共有ノードに付与した重みを反映して抽出層におけるコミュニティ抽出を行ってもよい。例えば、図８に示したように、氏名がyamadaである共有ノードについて重みｗｎ１、氏名がtanakaである共有ノードについて重みｗｎ２、氏名がtanakaである共有ノードについて重みｗｎ３を付与する。各共有ノードに付与する重みについては、情報処理装置１の操作者が任意に設定してもよく、また、共有ノード毎に抽出層におけるリンク数の逆数を設定してもよい。共有ノード毎の重みを反映して抽出層からコミュニティ抽出を行う場合、評価式Ｑ´は、数１２に示した式となる。
【００６４】
【数１２】
2019040285.tif 000014
【００６５】
また、共有ノードの重みを反映して抽出層からコミュニティ抽出を行う場合、ＥＭアルゴリズムの更新式として数１３の式を得る。
【００６６】
【数１３】
2019040285.tif 000015
【００６７】
上記数１２の式は、共有ノードに付与した重みｗｎsが付加されている点が数１の式と相違している。また、上記数１３の式は、制約層に付与した重みｗｎｓが付加されている点が数３の式と相違している。
【００６８】
制御部１０は、共有ノードの重みを反映して抽出層からコミュニティ抽出を行う場合、ステップＳＡ７においては、数３の（１）の式に替えて、数１３の（１）の式で割合γｔ（ｄ）（ｋ）を算出する。また、制御部１０は、共有ノードの重みを反映して抽出層からコミュニティ抽出を行う場合、ステップＳＡ８において、数３の（２）〜（４）に替えて、数１３の（２）〜（４）の式で所属確率Ｐｔ（ｎｓ｜ｋ）、所属確率Ｐｔ（ｎ-ｓ｜ｋ）および重要度πｔ（ｋ）を算出する。
【００６９】
本発明においては、複数の制約層のコミュニティ構造を反映して抽出層からコミュニティ抽出を行った後、コミュニティの抽出結果から制約層毎に抽出層との関連性ｄ１を例えば数１４の式により求めてもよい。
【００７０】
【数１４】
2019040285.tif 000016
【００７１】
数１４の式において、所属確率Ｐ（ｎｓ｜ｋ１）は、関連性を求める制約層における共有ノードｎｓのコミュニティｋ１への所属確率を表す。所属確率Ｐ（ｎｓ｜ｋ）は、抽出層における共有ノードｎｓのコミュニティｋへの所属確率を表す。複数の制約層毎に抽出層との関連性ｄ１を算出することにより、抽出層は、どの抽出層と依存関係が強いかを知ることができる。また、算出した関連性ｄ１に応じて、制約層毎に重みを付与し、上述した変形例のように制約層に付与した重みを反映して抽出層のコミュニティを抽出してもよい。
【００７２】
なお、抽出層との間で共有ノードを有していない制約層については、制約層と抽出層との関連性を算出しなくてもよい。
また、制約層と抽出層との関連性を算出する場合、抽出層におけるコミュニティの抽出結果と、各層における共有ノードのリンク数を反映して制約層と抽出層との関連性を算出してもよい。
また、抽出層におけるコミュニティの抽出結果から、各制約層における共有ノード毎に、対応する抽出層の共有ノードとの関連性を算出してもよい。
また、図７の場合のように、制約層が時間の経過により変化する場合、抽出層と制約層との時間差を反映して制約層と抽出層との関連性を算出してもよい。
【００７３】
本発明においては、上述したように制約層が複数である場合、各制約層で共有ノードの数は同じではなく、共有ノードの数が異なっていてもよい。
【符号の説明】
【００７４】
１…情報処理装置、１０…制御部、１１…記憶部、１２…操作部、１３…表示部、１４…通信部、１０１…取得部、１０２…算出部、１０３…抽出部。
【図１】
2019040285.tif 000017
【図２】
2019040285.tif 000018
【図３】
2019040285.tif 000019
【図４】
2019040285.tif 000020
【図５】
2019040285.tif 000021
【図６】
2019040285.tif 000022
【図７】
2019040285.tif 000023
【図８】
2019040285.tif 000024