(57)【要約】【課題】ネットワークにおけるコミュニティ構造で各コミュニティに属するノード数がベキ則に従うものを抽出することができるシステムを提供する。【解決手段】ノード群を備えたネットワークの構造を学習するネットワーク構造学習システムであって、ノード及びリンクに関する観測データを入力する入力手段１と、入力手段１が入力した観測データと現時点でのベキ則型学習パラメータとに基づいて、ノードが属するコミュニティを推定するベキ則型コミュニティ推定手段２と、観測データとベキ則型コミュニティ推定手段２が推定した推定結果とに基づいて、ベキ則型学習パラメータを学習するベキ則型パラメータ学習手段３と、ベキ則型パラメータ学習手段３が学習したベキ則型学習パラメータの値が収束した場合に、ベキ則型コミュニティ推定手段２が推定した推定結果を出力する出力手段４とを備えている。【選択図】図１
2012137940.tif 000002
【特許請求の範囲】
【請求項１】
ノード群を備えたネットワークの構造を学習するネットワーク構造学習システムであって、
前記ノード及びリンクに関する観測データを入力する入力手段と、
前記入力手段が入力した観測データと現時点でのベキ則型学習パラメータとに基づいて、ノードが属するコミュニティを推定するベキ則型コミュニティ推定手段と、
前記観測データと前記ベキ則型コミュニティ推定手段が推定した推定結果とに基づいて、ベキ則型学習パラメータを学習するベキ則型パラメータ学習手段と、
前記ベキ則型パラメータ学習手段が学習したベキ則型学習パラメータの値が収束した場合に、前記ベキ則型コミュニティ推定手段が推定した推定結果を出力する出力手段とを
備えたことを特徴とするネットワーク構造学習システム。
【請求項２】
ベキ則型パラメータ学習手段は、学習したベキ則型学習パラメータの値が収束したか否かを判定し、収束していないと判定した場合に、前記学習後のベキ則型学習パラメータをベキ則型コミュニティ推定手段に出力し、
前記ベキ則型コミュニティ推定手段は、観測データと出力した前記学習後のベキ則型学習パラメータとに基づいて、ノードが属するコミュニティを推定する
請求項１記載のネットワーク構造学習システム。
【請求項３】
ベキ則型パラメータ学習手段は、学習したベキ則型学習パラメータの値が収束したか否かを判定し、収束したと判定した場合に、出力手段に通知し、
前記出力手段は、前記ベキ則型パラメータ学習手段から通知を受けると、ベキ則型コミュニティ推定手段が推定した推定結果を出力する
請求項１又は請求項２記載のネットワーク構造学習システム。
【請求項４】
ベキ則型コミュニティ推定手段２は、観測データとベキ則型学習パラメータとに基づいて、ノードの複数のコミュニティへのベキ則型所属確率を推定し、
ベキ則型パラメータ学習手段は、前記観測データと前記ベキ則型コミュニティ推定手段が推定したベキ則型所属確率とに基づいて、ベキ則型学習パラメータを学習する
請求項１から請求項３のうちのいずれか１項に記載のネットワーク構造学習システム。
【請求項５】
出力手段は、ベキ則型コミュニティ推定手段が推定したノードの複数のコミュニティへのベキ則型所属確率を出力する
請求項４記載のネットワーク構造学習システム。
【請求項６】
ノード群を備えたネットワークの構造を学習するネットワーク構造学習方法であって、
前記ノード及びリンクに関する観測データを入力し、
入力した観測データと現時点でのベキ則型学習パラメータとに基づいて、ノードが属するコミュニティを推定し、
前記観測データと推定した前記推定結果とに基づいて、ベキ則型学習パラメータを学習し、
学習したベキ則型学習パラメータの値が収束した場合に、推定した前記推定結果を出力する
ことを特徴とするネットワーク構造学習方法。
【請求項７】
学習したベキ則型学習パラメータの値が収束したか否かを判定し、収束していないと判定した場合に、観測データと前記学習後のベキ則型学習パラメータとに基づいて、ノードが属するコミュニティを推定する
請求項６記載のネットワーク構造学習方法。
【請求項８】
ノード群を備えたネットワークの構造を学習させるためのネットワーク構造学習用プログラムであって、
コンピュータに、
前記ノード及びリンクに関する観測データを入力する入力処理と、
入力した観測データと現時点でのベキ則型学習パラメータとに基づいて、ノードが属するコミュニティを推定するベキ則型コミュニティ推定処理と、
前記観測データと推定した推定結果とに基づいて、ベキ則型学習パラメータを学習するベキ則型パラメータ学習処理とを
実行させるためのネットワーク構造学習用プログラム。
【請求項９】
コンピュータに、
ベキ則型パラメータ学習処理で、学習したベキ則型学習パラメータの値が収束したか否かを判定し、収束していないと判定した場合に、前記学習後のベキ則型学習パラメータを出力する処理を実行させ、
ベキ則型コミュニティ推定処理で、観測データと出力した前記学習後のベキ則型学習パラメータとに基づいて、ノードが属するコミュニティを推定する処理を実行させる
請求項８記載のネットワーク構造学習用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク構造学習システム、ネットワーク構造学習方法およびネットワーク構造学習用プログラムに関する。
【背景技術】
【０００２】
ネットワーク構造学習システムの一例が、非特許文献１に記載されている。このネットワーク構造学習システムは、入力手段と、コミュニティ推定手段と、パラメータ学習手段と、出力手段とから構成されている。
【０００３】
このような構成を有するネットワーク構造学習システムは、つぎのように動作する。すなわち、入力手段から入力された観測対象のデータ（観測対象のノードやリンクのデータ。以下、単に観測データともいう）に基づいて、各ノードが属するコミュニティを各ノードに対して複数個推定する。そして、この推定結果と観測データとに基づいてパラメータを学習し、これをパラメータが収束するまで繰り返し、最後に各ノードが属する複数個のコミュニティの推定結果を出力する。
【０００４】
また、関連する技術として、例えば、特許文献１にもノード群を備えたネットワーク構造を学習するシステムが記載されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１０−１６５０４７号公報
【非特許文献】
【０００６】
【非特許文献１】K. Miller, T. Griffiths, and M. I. Jordan. Nonparametric latent feature models for link prediction. Advances in Neural Information Processing Systems (NIPS) 22, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、上述のシステムでは、各コミュニティに属するノードの数がベキ則に従っていないため、実世界における多くの現象を精確にモデル化できない。その理由は、ノードの数がベキ則に従わないようなモデルを用いているためである。
【０００８】
具体的に、ソーシャルネットワークサービスを例に説明する。ソーシャルネットワークサービスにおいて、有名な芸能人や人気のゲームなどの応援コミュニティには、非常にたくさんの人が参加している。そのかわり、そういった超人気コミュニティの数自体は普通少ない。逆に、マイナーな芸能人やゲームの応援コミュニティは、参加する人は少ない。そのかわり、コミュニティ数自体は非常に多い。
【０００９】
関連する技術で用いているモデルは、１０００人の人がいて１００個のコミュニティがあった場合に、どのコミュニティも平均して１００人くらいの参加者がいるということを前提にしている。しかし、現実的には、１０００人が参加しているコミュニティが１つくらい、１００人が参加しているコミュニティが１０くらい、１０人しか参加していないコミュニティが１００くらいあるという状態であることが多い。そのため、このような状態を上記のモデルを用いて表現することができない。
【００１０】
そこで、本発明は、ネットワークにおけるコミュニティ構造で各コミュニティに属するノード数がベキ則に従うものを抽出することができるネットワーク構造学習システム、ネットワーク構造学習方法およびネットワーク構造学習用プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明によるネットワーク構造学習システムは、ノード群を備えたネットワークの構造を学習するネットワーク構造学習システムであって、ノード及びリンクに関する観測データを入力する入力手段と、入力手段が入力した観測データと現時点でのベキ則型学習パラメータとに基づいて、ノードが属するコミュニティを推定するベキ則型コミュニティ推定手段と、観測データとベキ則型コミュニティ推定手段が推定した推定結果とに基づいて、ベキ則型学習パラメータを学習するベキ則型パラメータ学習手段と、ベキ則型パラメータ学習手段が学習したベキ則型学習パラメータの値が収束した場合に、ベキ則型コミュニティ推定手段が推定した推定結果を出力する出力手段とを備えたことを特徴とする。
【００１２】
本発明によるネットワーク構造学習方法は、ノード群を備えたネットワークの構造を学習するネットワーク構造学習方法であって、ノード及びリンクに関する観測データを入力し、入力した観測データと現時点でのベキ則型学習パラメータとに基づいて、ノードが属するコミュニティを推定し、観測データと推定した推定結果とに基づいて、ベキ則型学習パラメータを学習し、学習したベキ則型学習パラメータの値が収束した場合に、推定した推定結果を出力することを特徴とする。
【００１３】
本発明によるネットワーク構造学習用プログラムは、ノード群を備えたネットワークの構造を学習させるためのネットワーク構造学習用プログラムであって、コンピュータに、ノード及びリンクに関する観測データを入力する入力処理と、入力した観測データと現時点でのベキ則型学習パラメータとに基づいて、ノードが属するコミュニティを推定するベキ則型コミュニティ推定処理と、観測データと推定した推定結果とに基づいて、ベキ則型学習パラメータを学習するベキ則型パラメータ学習処理とを実行させることを特徴とする。
【発明の効果】
【００１４】
本発明によれば、ネットワークにおけるコミュニティ構造で各コミュニティに属するノード数がベキ則に従うものを抽出することができる。
【図面の簡単な説明】
【００１５】
【図１】本発明によるネットワーク構造学習システムの構成の一例を示すブロック図である。
【図２】ネットワーク構造学習システムが実行する処理例を示す流れ図である。
【図３】ネットワークの一例を示す説明図である。
【発明を実施するための形態】
【００１６】
次に、本発明の実施形態について図面を参照して説明する。図１は、本発明によるネットワーク構造学習システムの構成の一例を示すブロック図である。図１を参照すると、ネットワーク構造学習システムは、入力手段１と、ベキ則型コミュニティ推定手段２と、ベキ則型パラメータ学習手段３と、出力手段４とを含む。ネットワーク構造学習システムは、例えば、プログラムに従って動作するパーソナルコンピュータ等の情報処理装置によって実現される。また、これらの手段はそれぞれ概略つぎのように動作する。
【００１７】
入力手段１は、観測対象のデータ（観測対象のノードやノード間のリンクを示すデータ。単に観測データともいう）を入力する機能を備えている。入力手段１によるデータ入力元の例としては、ネットワーク上の外部装置（観測対象のノード）や、マウス、キーボード等の入力装置が挙げられる。
【００１８】
ベキ則型コミュニティ推定手段２は、現時点でのベキ則型学習パラメータと観測データとに基づいて、各ノードが属する複数のベキ則型コミュニティを推定し、その結果をベキ則型パラメータ学習手段３に出力する機能を備えている。ベキ則型コミュニティ推定手段２は、具体的には、プログラムに従って動作する情報処理装置のＣＰＵによって実現される。
【００１９】
ベキ則型パラメータ学習手段３は、現時点でのベキ則型コミュニティ推定結果と観測データとに基づいてベキ則型パラメータを学習し、その結果をベキ則型コミュニティ推定手段２に出力する機能を備えている。また、ベキ則型パラメータ学習手段３は、ベキ則型パラメータの値が収束した場合には、出力手段４に通知する機能を備えている。ベキ則型パラメータ学習手段３は、例えば、前回用いたベキ則型パラメータの値と学習後のベキ則型パラメータとの差が所定値以内である場合に、収束したと判定する。ベキ則型パラメータ学習手段３は、具体的には、プログラムに従って動作する情報処理装置のＣＰＵによって実現される。
【００２０】
出力手段４は、推定した各ノードのベキ則型コミュニティ属性（すなわち、ベキ則型コミュニティ推定手段２による推定結果であり、例えば、後述するベキ則型所属確率Ｚ）を出力する機能を備えている。出力手段４によるデータ出力先の例としては、ネットワーク上の外部装置や、ディスプレイ装置等の表示装置が挙げられる。
【００２１】
次に、図１及び図２を参照して本実施形態の全体の動作について説明する。図２は、ネットワーク構造学習システムが実行する処理例を示す流れ図である。
【００２２】
まず、入力手段１は、観測対象のデータを取り込む（図２のステップＡ１）。
【００２３】
次に、ベキ則型コミュニティ推定手段２は、現時点でのベキ則型パラメータに基づいて、各ノードの各コミュニティへのベキ則型所属確率を推定する（図２のステップＡ２）。
【００２４】
さらに、ベキ則型パラメータ学習手段３は、現時点での観測結果（観測データ）と各ノードの各コミュニティへのベキ則型所属確率とに基づいて、ベキ則型パラメータの値を学習する（図２のステップＡ３）。
【００２５】
最後に、出力手段４は、ステップＡ２で学習した各ノードのベキ則型コミュニティ属性を出力する（図２のステップＡ４）。
【００２６】
次に、具体的な実施例を用いて本実施形態の動作を説明する。以下の説明では、図３に示すようなＮ個のノードを想定し、これらのノードからなるネットワークを考える。このネットワークにおけるノードＶｉからＶｊへのリンクの有無を｛１，０}で表したＮ×Ｎ隣接行列をＸとし、行列の各要素をＸｉｊで表す。
【００２７】
また、Ｎ個のノードがＫ個のコミュニティのいくつかに属するとき，これをＮ×Ｋの二値行列Ｚで表し、行列の各要素をＺｉｋで表す。また、ノードＶｉがコミュニティｋに属するときＺｉｋ＝１となる。
【００２８】
ここでは、Ｚの分布として、以下の文献１で提案されたノンパラメトリックベイズ手法を用いることとする。これにより、事前にＫの値を定めることなく学習が可能となり、かつコミュニティがベキ則に従うようになる。
【００２９】
文献１「Y.W. Teh and D. Gorur. Indian Buffet Processes with Power-law Behavior. Advances in Neural Information Processing Systems (NIPS) 22, 2010.」
【００３０】
このときのＺの事前分布を、Ｚ｜α，c，σ〜IBPPL（α，c，σ）と書くことにする。ここでα，c，σは、ハイパーパラメータである．
【００３１】
次に、コミュニティｋに属するノードとコミュニティｌに属するノードとを結ぶリンクを生成する分布のパラメータを、ｗｋｌ｜σｗ〜Normal（０，σｗ２）とする。ここでσｗは、ハイパーパラメータである。
【００３２】
最後に、ノードＶｉが複数コミュニティＺｉに属し、さらにノードＶｊが複数コミュニティＺｊに属しているとき、ノードＶｉとノードＶｊとを結ぶリンクが生成される確率分布を、Ｘｉｊ｜Ｚｉ，Ｚｊ，σｗ〜logistic(ＺｉＷＺｊＴ)とする。ここでＷはｗｋｌを要素とする行列である。
【００３３】
この式から、複数のコミュニティに属するノードは各々のコミュニティの特性を併せ持つ。
【００３４】
以上より、このネットワークのリンクの生成確率は、Ｐ（Ｘ｜α，c，σ，σw)＝ΣＺ∫ｄｗＰ（Ｘ，Ｚ，ｗ｜α，c，σ，σw）＝ΣＺ∫ｄｗＰ（Ｘ｜Ｚ，ｗ）Ｐ（Ｚ｜α，c，σ）Ｐ（ｗ｜σw）と書くことができ、これを最大化するようにコミュニティの割り当てＺを推定し、パラメータＷを学習する。
【００３５】
なお、簡単のため、ハイパーパラメータα，c，σ，σwの値は、あらかじめ与えられているものとする。
【００３６】
まず、入力手段１は、現時点での観測対象のデータＸを入力する（ステップＡ１）。入力手段１は、入力した観測対象のデータを、ベキ則型コミュニティ推定手段２とベキ則型パラメータ学習手段３とに出力する。
【００３７】
次に、ベキ則型コミュニティ推定手段２は、入力手段１から現時点での観測対象のデータＸを入力し、ベキ則型パラメータ学習手段３から現時点でのベキ則型学習パラメータＷを入力する。そして、ベキ則型コミュニティ推定手段２は、それら観測対象のデータＸ及びベキ則型学習パラメータＷに基づいて、各ノードの各コミュニティへのベキ則型所属確率Ｚを、Ｐ（Ｚ｜Ｘ，Ｗ，α，c，σ）∝Ｐ（Ｘ｜Ｚ，Ｗ）Ｐ（Ｚ｜α，c，σ）により推定する（ステップＡ２）。
【００３８】
さらに、ベキ則型コミュニティ推定手段２は、推定した各ノードの各コミュニティへのベキ則型所属確率Ｚを、ベキ則型パラメータ学習手段３及び出力手段４に出力する。
【００３９】
ベキ則型パラメータ学習手段３は、入力手段１から現時点での観測対象のデータＸを入力し、ベキ則型コミュニティ推定手段２から各ノードの各コミュニティへのベキ則型所属確率Ｚを入力する。そして、ベキ則型パラメータ学習手段３は、それら観測対象のデータＸ及び各ノードの各コミュニティへのベキ則型所属確率Ｚに基づいて、ベキ則型パラメータの値ＷをＰ（Ｗ｜Ｘ，Ｚ,）∝Ｐ（Ｘ｜Ｚ，Ｗ）Ｐ（Ｗ｜σw）により学習する（ステップＡ３）。ここでの学習とは、Ｐ（Ｗ｜Ｘ，Ｚ,）∝Ｐ（Ｘ｜Ｚ，Ｗ）Ｐ（Ｗ｜σw）を用いて、ベキ則型パラメータの値Ｗを更新することである。
【００４０】
ここで、ベキ則型パラメータ学習手段３は、学習したベキ則型パラメータの値Ｗが収束したかどうかを判断する。
【００４１】
判断の結果、パラメータの値Ｗが収束していない場合には、ベキ則型パラメータ学習手段３は、学習したベキ則型パラメータの値Ｗを、ベキ則型コミュニティ推定手段２に出力する。
【００４２】
ベキ則型コミュニティ推定手段２は、再度、ベキ則型コミュニティ推定を行う。
【００４３】
一方、判断の結果、ベキ則型パラメータの値Ｗが収束した場合には、ベキ則型パラメータ学習手段３は、出力手段４に通知する。
【００４４】
最後に、出力手段４は、ベキ則型パラメータ学習手段３から通知を受けると、ベキ則型コミュニティ推定手段２で推定された各ノードの各コミュニティのベキ則型属性Ｚを、データ出力する（ステップＡ４）。
【００４５】
次に、本実施形態の効果について説明する。本実施形態では、複数のベキ則型に従うコミュニティに同時に属するようなノードの取り扱いができるように構成されている。そのため、あるノードに対して所属する複数のコミュニティをベキ則に従って割り当てることができる。その結果、実世界における多様な現象のモデル化に用いることができる。
【００４６】
以上に説明したように、本発明によるネットワーク構造学習システムは、ベキ則型コミュニティ推定手段と、ベキ則型パラメータ学習手段とを備え、各ノードに複数のコミュニティをベキ則に従って割り当てるよう動作する。このような構成を採用し、あるノードが複数のコミュニティにベキ側にしたがって属する場合には、その性質を持つよう振舞うことにより本発明の目的を達成することができる。
【００４７】
すなわち、本発明によれば、複数のコミュニティにベキ側に従って同時に属するようなノードの取り扱いができる。その理由は、あるノードが複数のコミュニティにベキ側に従って属することが可能なモデルを用いているためである。
【００４８】
なお、本実施形態では、以下の（１）〜（５）に示すようなネットワーク構造学習システムの特徴的構成が示されている。
【００４９】
（１）ネットワーク構造学習システムは、ノード群を備えたネットワークの構造を学習するネットワーク構造学習システムであって、ノード及びリンクに関する観測データを入力する入力手段（例えば、入力手段１によって実現される）と、入力手段が入力した観測データと現時点でのベキ則型学習パラメータとに基づいて、ノードが属するコミュニティを推定するベキ則型コミュニティ推定手段（例えば、ベキ則型コミュニティ推定手段２によって実現される）と、観測データとベキ則型コミュニティ推定手段が推定した推定結果とに基づいて、ベキ則型学習パラメータを学習するベキ則型パラメータ学習手段（例えば、ベキ則型パラメータ学習手段３によって実現される）と、ベキ則型パラメータ学習手段が学習したベキ則型学習パラメータの値（例えば、Ｗ）が収束した場合に、ベキ則型コミュニティ推定手段が推定した推定結果を出力する出力手段（例えば、出力手段４によって実現される）とを備えたことを特徴とする。
【００５０】
（２）ネットワーク構造学習システムにおいて、ベキ則型パラメータ学習手段は、学習したベキ則型学習パラメータの値が収束したか否かを判定し、収束していないと判定した場合に、ベキ則型学習パラメータをベキ則型コミュニティ推定手段に出力し、ベキ則型コミュニティ推定手段は、観測データと出力したベキ則型学習パラメータとに基づいて、ノードが属するコミュニティを推定するように構成されていてもよい。
【００５１】
（３）ネットワーク構造学習システムにおいて、ベキ則型パラメータ学習手段は、学習したベキ則型学習パラメータの値が収束したか否かを判定し、収束したと判定した場合に、出力手段に通知し、出力手段は、ベキ則型パラメータ学習手段から通知を受けると、ベキ則型コミュニティ推定手段が推定した推定結果を出力するように構成されていてもよい。
【００５２】
（４）ネットワーク構造学習システムにおいて、ベキ則型コミュニティ推定手段２は、観測データとベキ則型学習パラメータとに基づいて、ノードの複数のコミュニティへのベキ則型所属確率（例えば、Ｚ）を推定し、ベキ則型パラメータ学習手段は、観測データとベキ則型コミュニティ推定手段が推定したベキ則型所属確率とに基づいて、ベキ則型学習パラメータを学習するように構成されていてもよい。
【００５３】
（５）ネットワーク構造学習システムにおいて、出力手段は、ベキ則型コミュニティ推定手段が推定したノードの複数のコミュニティへのベキ則型所属確率を出力するように構成されていてもよい。
【産業上の利用可能性】
【００５４】
本発明によれば、ネットワークによってつながれたコンピュータ群があった場合に、お互いに相関を持って稼動しているコンピュータをグループ化することができ、しかも複数のグループに属するようなネットワーク上で中心的な役割を果たすコンピュータについて、それらを適切に抽出することができる。これにより、本発明は、複雑なコンピュータ・ネットワークシステムを、その働きによってクラスタ化し管理・監視するといった用途に適用できる。
【符号の説明】
【００５５】
１  入力手段
２  ベキ則型コミュニティ推定手段
３  ベキ則型パラメータ学習手段
４  出力手段
【図１】
2012137940.tif 000003
【図２】
2012137940.tif 000004
【図３】
2012137940.tif 000005