(57)【要約】【課題】一つのノードが二つ以上のコミュニティに属することができるネットワーク構造学習システム、ネットワーク構造学習方法及びプログラムを提供する。【解決手段】ノード群を備えたネットワークの構造を学習し、ノードが属するコミュニティを推定するネットワーク構造学習システムであって、ノード及びリンクに関する観測データを入力する入力手段と、入力手段で入力された観測データと、学習パラメータとに基づいて、ノードの複数のコミュニティへの所属確率を推定するコミュニティ推定手段と、入力手段で入力された観測データと、コミュニティ推定手段で推定されたノードの複数のコミュニティへの所属確率とに基づいて、新たな学習パラメータを学習し、新たな学習パラメータをコミュニティ推定手段へ出力するパラメータ学習手段と、コミュニティ推定手段で推定されたノードの複数のコミュニティの属性を、データ出力する出力手段と、を有する。【選択図】図１
2010165047.tif 000002
【特許請求の範囲】
【請求項１】
ノード群を備えたネットワークの構造を学習し、前記ノードが属するコミュニティを推定するネットワーク構造学習システムであって、
前記ノード及びリンクに関する観測データを入力する入力手段と、
前記入力手段で入力された観測データと、学習パラメータとに基づいて、前記ノードの複数のコミュニティへの所属確率を推定するコミュニティ推定手段と、
前記入力手段で入力された観測データと、前記コミュニティ推定手段で推定された前記ノードの複数のコミュニティへの所属確率とに基づいて、新たな学習パラメータを学習し、前記新たな学習パラメータを前記コミュニティ推定手段へ出力するパラメータ学習手段と、
前記コミュニティ推定手段で推定された前記ノードの複数のコミュニティの属性を、データ出力する出力手段と、
を有することを特徴とするネットワーク構造学習システム。
【請求項２】
前記パラメータ学習手段は、
前記新たな学習パラメータの値が収束したかどうかの判断を行い、
前記判断の結果、前記新たな学習パラメータの値が収束していない場合、前記新たな学習パラメータを前記コミュニティ推定手段へ出力し、
前記判断の結果、前記新たな学習パラメータの値が収束した場合、前記出力手段に通知することを特徴とする請求項１記載のネットワーク構造学習システム。
【請求項３】
前記出力手段は、前記パラメータ学習手段から通知を受けた場合、予め前記コミュニティ推定手段で推定された前記ノードの複数のコミュニティ属性をデータ出力することを特徴とする請求項１又は２記載のネットワーク構造学習システム。
【請求項４】
情報処理装置が、ノード群を備えたネットワークの構造を学習し、前記ノードが属するコミュニティを推定するネットワーク構造学習方法であって、
前記ノード及びリンクに関する観測データを入力する入力ステップと、
前記入力ステップで入力された観測データと、学習パラメータとに基づいて、前記ノードの複数のコミュニティへの所属確率を推定するコミュニティ推定ステップと、
前記入力ステップで入力された観測データと、前記コミュニティ推定ステップで推定された前記ノードの複数のコミュニティへの所属確率とに基づいて、前記コミュニティ推定ステップで使用される新たな学習パラメータを学習するパラメータ学習ステップと、
前記コミュニティ推定ステップで推定された前記ノードの複数のコミュニティの属性を、データ出力する出力ステップと、
を有することを特徴とするネットワーク構造学習方法。
【請求項５】
前記パラメータ学習ステップで学習された新たな学習パラメータの値が収束したかどうかの判断を行う収束判断ステップを有し、
前記収束判断ステップでの判断の結果、前記新たな学習パラメータの値が収束していない場合、前記コミュニティ推定ステップへ戻り、前記新たな学習パラメータを前記コミュニティ推定ステップで使用し、
前記収束判断ステップでの判断の結果、前記新たな学習パラメータの値が収束した場合、前記出力ステップを開始することを特徴とする請求項４記載のネットワーク構造学習方法。
【請求項６】
コンピュータに、ノード群を備えたネットワークの構造を学習し、前記ノードが属するコミュニティを推定する処理を実行させるためのプログラムであって、
前記ノード及びリンクに関する観測データを入力する入力処理と、
前記入力処理で入力された観測データと、学習パラメータとに基づいて、前記ノードの複数のコミュニティへの所属確率を推定するコミュニティ推定処理と、
前記入力処理で入力された観測データと、前記コミュニティ推定処理で推定された前記ノードの複数のコミュニティへの所属確率とに基づいて、前記コミュニティ推定処理で使用される新たな学習パラメータを学習するパラメータ学習処理と、
前記コミュニティ推定処理で推定された前記ノードの複数のコミュニティの属性を、データ出力する出力処理と、
をコンピュータに実行させることを特徴とするプログラム。
【請求項７】
前記パラメータ学習処理で学習された新たな学習パラメータの値が収束したかどうかの判断を行う収束判断処理と、
前記収束判断処理での判断の結果、前記新たな学習パラメータの値が収束していない場合、前記コミュニティ推定処理へ戻り、前記新たな学習パラメータを前記コミュニティ推定処理で使用する処理と、
前記収束判断処理での判断の結果、前記新たな学習パラメータの値が収束した場合、前記出力処理を開始する処理と、
をコンピュータに実行させることを特徴とする請求項６記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ノード群を備えたネットワーク構造を学習するネットワーク構造学習システム、ネットワーク構造学習方法及びプログラムに関する。
【背景技術】
【０００２】
本発明に関連するネットワーク構造学習システムの一例が、非特許文献１に開示されている。このネットワーク構造学習システムは、入力手段と、コミュニティ推定手段と、パラメータ学習手段と、出力手段とから構成されており、次のように動作する。まず、入力手段から入力された観測対象のデータ（観測対象のノードやリンクのデータ。観測データ）を基に、各ノードが属するコミュニティを、各ノードに対して一つだけ推定する。この推定結果と観測データを基にパラメータを学習し、この学習をパラメータが収束するまで繰り返し、最後に、各ノードが属するコミュニティの推定結果を出力する。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Jean-Jacques Daudin , Franck Picard , and Stephane Robin , “A mixture model for random graphs” Statistics and Computing, Vol. 18, No. 2, Springer, 2008.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記非特許文献１のネットワーク構造学習システムには、重なり合ったコミュニティを抽出することができないという問題がある。その理由は、一つのノードが一つのコミュニティのみに属するようなモデルを用いているためである。
【０００５】
本発明は、上記事情に鑑みてなされたものであり、一つのノードが二つ以上のコミュニティに属することができるネットワーク構造学習システム、ネットワーク構造学習方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
かかる目的を達成するために、本発明のネットワーク構造学習システムは、ノード群を備えたネットワークの構造を学習し、ノードが属するコミュニティを推定するネットワーク構造学習システムであって、ノード及びリンクに関する観測データを入力する入力手段と、入力手段で入力された観測データと、学習パラメータとに基づいて、ノードの複数のコミュニティへの所属確率を推定するコミュニティ推定手段と、入力手段で入力された観測データと、コミュニティ推定手段で推定されたノードの複数のコミュニティへの所属確率とに基づいて、新たな学習パラメータを学習し、新たな学習パラメータをコミュニティ推定手段へ出力するパラメータ学習手段と、コミュニティ推定手段で推定されたノードの複数のコミュニティの属性を、データ出力する出力手段と、を有することを特徴とする。
【０００７】
本発明のネットワーク構造学習方法は、情報処理装置が、ノード群を備えたネットワークの構造を学習し、ノードが属するコミュニティを推定するネットワーク構造学習方法であって、ノード及びリンクに関する観測データを入力する入力ステップと、入力ステップで入力された観測データと、学習パラメータとに基づいて、ノードの複数のコミュニティへの所属確率を推定するコミュニティ推定ステップと、入力ステップで入力された観測データと、コミュニティ推定ステップで推定されたノードの複数のコミュニティへの所属確率とに基づいて、コミュニティ推定ステップで使用される新たな学習パラメータを学習するパラメータ学習ステップと、コミュニティ推定ステップで推定されたノードの複数のコミュニティの属性を、データ出力する出力ステップと、を有することを特徴とする。
【０００８】
本発明のプログラムは、コンピュータに、ノード群を備えたネットワークの構造を学習し、ノードが属するコミュニティを推定する処理を実行させるためのプログラムであって、ノード及びリンクに関する観測データを入力する入力処理と、入力処理で入力された観測データと、学習パラメータとに基づいて、ノードの複数のコミュニティへの所属確率を推定するコミュニティ推定処理と、入力処理で入力された観測データと、コミュニティ推定処理で推定されたノードの複数のコミュニティへの所属確率とに基づいて、コミュニティ推定処理で使用される新たな学習パラメータを学習するパラメータ学習処理と、コミュニティ推定処理で推定されたノードの複数のコミュニティの属性を、データ出力する出力処理と、をコンピュータに実行させることを特徴とする。
【発明の効果】
【０００９】
本発明によれば、ネットワークにおける、重なり合ったコミュニティ構造を抽出することが可能となる。
【図面の簡単な説明】
【００１０】
【図１】本発明の一実施形態に係るネットワーク構造学習システムのハードウェア構成を示すブロック図である。
【図２】本発明の一実施形態に係るネットワーク構造学習システムの機能構成を示すブロック図である。
【図３】本発明の一実施形態に係るネットワーク構造学習システムの動作を示すフローチャートである。
【発明を実施するための形態】
【００１１】
以下、本発明を実施するための最良の形態について添付図面を参照して詳細に説明する。
【００１２】
本発明の一実施形態であるネットワーク構造学習システムについて説明する。図３は、本実施形態のネットワーク構造学習システムのハードウェア構成を示すブロック図である。図３に示す本実施形態のネットワーク構造学習システムは、コンピュータ、サーバ、ワークステーション、又は、その他の計算デバイス、機器などの情報処理装置である。
【００１３】
図３に示すように、本実施形態のネットワーク構造学習システムは、ＣＰＵ（Central Processing Unit）１、メモリ２、ＨＤＤ（Hard Disk Drive）３、ネットワークインターフェース４、Ｉ／Ｏ（In/Out）インターフェース５を有する。これら各部は、バスライン６を介して接続されている。なお、バスライン６には、アドレスバス、データバス等を利用することができる。
【００１４】
ＣＰＵ１は、制御デバイス（プロセッサ）の一例であり、メモリ２に格納されているプログラムを読み出し、そのプログラムに従って、システム全体を制御し、プログラムの動作を実行する。
【００１５】
メモリ２は、記憶デバイスの一例であり、例として、各種データを一時的に記憶するエリアを形成するＲＡＭ（Random Access Memory）２１と、ＣＰＵ１を制御するプログラム等の固定的なデータを予め格納したＲＯＭ（Read Only Memory）２２、とから構成される。
【００１６】
ＨＤＤ３は、大容量記憶デバイスの一例であり、各種データの書き込み、及び、読出しを行う機能を有する。
【００１７】
ネットワークインターフェース４は、入出力デバイスの一例であり、ＣＰＵ１等によって制御され、ネットワーク上の装置等とデータ通信を行う。図示していないが、ネットワークインターフェース４の接続先としては、ＩＰ（Internet Protocol）ネットワーク等が挙げられる。なお、ネットワークインターフェース４は、イーサネット（登録商標）インターフェース、ＩＥＥＥ１２８４インターフェース、又は、その他のインターフェースでも構成可能である。
【００１８】
Ｉ／Ｏインターフェース５は、入出力デバイスの一例であり、ＣＰＵ１等によって制御され、システム外部の装置等とデータ通信を行う。図示していないが、Ｉ／Ｏインターフェース５の接続先としては、ディスプレイ、プリンタ、スピーカ、マイク、マウス、タッチパネル、キーボード等が挙げられる。
【００１９】
図１は、図３に示す本実施形態のネットワーク構造学習システムの機能構成を示すブロック図である。図１に示すように、本実施形態のネットワーク構造学習システムは、入力手段１１と、コミュニティ推定手段１２と、パラメータ学習手段１３と、出力手段１４とを有している。
【００２０】
入力手段１１は、観測（推定）対象のノード及び／又はリンクに関する観測対象のデータ（観測値、観測データ）をシステム内部に取り込み、取り込んだ観測対象のデータを、コミュニティ推定手段１２及びパラメータ学習手段１３へ送出する。入力手段１１によるデータ入力元の例としては、ネットワーク上の外部装置（観測対象のノード）や、マウス、キーボード等が挙げられる。
【００２１】
コミュニティ推定手段１２は、現時点での観測対象のデータ及び学習パラメータに基づいて、各ノードが属する複数のコミュニティを推定し、その推定結果をパラメータ学習手段１３及び出力手段１４に送る。
【００２２】
パラメータ学習手段１３は、現時点での観測対象のデータ及び推定結果に基づいて、パラメータを学習する。そして、パラメータ学習手段１３は、学習したパラメータ（学習パラメータ）の値が収束していなければ、学習パラメータをコミュニティ推定手段１２に送る。パラメータの値が収束した場合、パラメータ学習手段１３は、出力手段１４に通知する。
【００２３】
出力手段１４は、パラメータ学習手段１３から通知を受けると、推定結果である各ノードのコミュニティ属性を、データ出力する。出力手段１４によるデータ出力先の例としては、ネットワーク上の外部装置や、ディスプレイ、プリンタ等が挙げられる。
【００２４】
以上、本実施形態の各手段について説明したが、図１に示す機能ブロックは、図３に示すハードウェア構成によって実現される。図１に示す機能ブロックの動作は、図３に示すメモリ２のＲＯＭ２２にプログラムとして格納されており、動作時にはＣＰＵ１がＲＯＭ２２からプログラムを読み出して実行する。各機能ブロックが動作するときに必要な情報は、ＨＤＤ３やＲＡＭ２に格納されており、必要に応じて読み出し及び書き込みが行われる。
【００２５】
次に、図１及び図２のフローチャートを参照して、本実施形態のネットワーク構造学習システムにおける動作（本発明のネットワーク構造学習方法の一実施形態）について詳細に説明する。
【００２６】
以下の説明では、例として、N個のノードからなるネットワークを考える。このネットワークにおけるノードViからVjへのリンクの有無を[1,0]で表したN×N隣接行列をXとし、行列の各要素をXijで表す。
【００２７】
また、N個のノードがK個のコミュニティのいくつかに属するとき、これをN×Kの二値行列Zで表し、行列の各要素をZikで表す。
【００２８】
また、ノードViがコミュニティkに属するときZik=1となる。
【００２９】
ここではZの分布として、ノンパラメトリックベイズ手法を用いることとする。これにより、事前にKの値を定めることなく学習が可能となる。なお、上記ノンパラメトリックベイズ手法の例としては、文献「T. Griffiths, Z. Ghahramani, "Infinite Latent Feature Models and the Indian Buffet Process," In Advances in Neural Information Processing Systems 18 (NIPS-2005), 2006.」で提案されたものが挙げられる。
【００３０】
このときのZの事前分布を、
Z|α 〜 IBP(α)
と書くことにする。ここでαは、ハイパーパラメータである。
【００３１】
次に、コミュニティkに属するノードとコミュニティlに属するノードを結ぶリンクを生成する分布のパラメータを、
ηkl|β 〜 Beta(β,β)
とする。ここでβは、ハイパーパラメータである。
【００３２】
最後に、ノードViがコミュニティZi1,…,ZiKiに属し、さらにノードVjがコミュニティZj1,…,ZjKjに属しているとき、ノードViとノードVjを結ぶリンクが生成される確率分布を、
Xij|Zi1,…,ZiKi,Zj1,…,ZjKj,η 〜 Bernoulli(f(ηZi1,Zj1,…, ηZiKi,ZjKj))
とする。ここでKi,Kjは、ノードVi ,Vjが属するコミュニティ数、f(・)は、適当な関数で0≦f≦1とする。
【００３３】
この式から、複数のコミュニティに属するノードは各々のコミュニティの特性を併せ持つ。
【００３４】
以上により、このネットワークのリンクの生成確率は、
P(X,Z, η|α, β) = P(X|Z, η)P(Z|α)P(η|β)
と書くことができ、これを最大化するようにコミュニティの割り当てZを推定し、パラメータηを学習する。
【００３５】
なお、簡単のため、ハイパーパラメータα, βの値は、あらかじめ与えられているものとする。
【００３６】
まず、入力手段１１は、現時点での観測対象のデータXを入力する（ステップＳ１）。入力手段１１は、入力した観測対象のデータを、コミュニティ推定手段１２とパラメータ学習手段１３へ出力する。
【００３７】
次に、コミュニティ推定手段１２は、入力手段１１から現時点での観測対象のデータXを入力し、パラメータ学習手段１３から現時点での学習パラメータηを入力し、それら観測対象のデータX及び学習パラメータηに基づいて、各ノードの各コミュニティへの所属確率Zを、
P(Z|X,η,α) ∝ P(X|Z, η)P(Z|α)
により推定する（ステップＳ２）。
【００３８】
コミュニティ推定手段１２は、推定した各ノードの各コミュニティへの所属確率Zを、パラメータ学習手段１３及び出力手段１４へ出力する。
【００３９】
さらに、パラメータ学習手段１３は、入力手段１１から現時点での観測対象のデータXを入力し、コミュニティ推定手段１２から各ノードの各コミュニティへの所属確率Zを入力し、それら観測対象のデータX及び各ノードの各コミュニティへの所属確率Zに基づいて、パラメータの値ηを、
P(η|X,Z,β) ∝ P(X|Z, η)P(η|β)
により学習する（ステップＳ３）。
【００４０】
ここで、パラメータ学習手段１３は、学習したパラメータの値ηが収束したかどうかを判断する（ステップＳ４）。
【００４１】
判断の結果、パラメータの値ηが収束していない場合（ステップＳ４／ＮＯ）、パラメータ学習手段１３は、学習したパラメータの値ηを、コミュニティ推定手段１２へ出力する。
【００４２】
コミュニティ推定手段１２は、再度、コミュニティ推定を行う（ステップＳ３）。
【００４３】
一方、判断の結果、パラメータの値ηが収束した場合は（ステップＳ４／ＹＥＳ）、パラメータ学習手段１３は、出力手段１４に通知する。
【００４４】
最後に、出力手段１４は、パラメータ学習手段１３から通知を受けると、コミュニティ推定手段１２で推定された各ノードの各コミュニティの属性Zを、データ出力する（ステップＳ５）。
【００４５】
このように、本実施形態のネットワーク構造学習システムでは、一つのノードに複数のコミュニティを割り当てるように動作する。よって、あるノードが複数のコミュニティに属する場合には、属するコミュニティすべての性質を持つように振舞う。
【００４６】
以上説明したように、本実施形態によれば、あるノードが複数のコミュニティに属することが可能なモデルを用いているため、複数のコミュニティに同時に属するようなノードの取り扱いができる。よって、あるノードに対して所属する複数のコミュニティを割り当てることができる。その結果、重なり合ったコミュニティ構造を抽出することが可能となる。
【００４７】
以上、本発明の実施形態について説明したが、上記実施形態に限定されるものではなく、その要旨を逸脱しない範囲において種々の変形が可能である。
【００４８】
例えば、上述した各実施形態における動作は、ハードウェア、または、ソフトウェア、あるいは、両者の複合構成によって実行することも可能である。
【００４９】
ソフトウェアによる処理を実行する場合には、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれているコンピュータ内のメモリにインストールして実行させてもよい。あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させてもよい。
【００５０】
例えば、プログラムは、記録媒体としてのハードディスクやＲＯＭ（Read Only Memory）に予め記録しておくことが可能である。あるいは、プログラムは、ＣＤ−ＲＯＭ(Compact Disc Read Only Memory)，ＭＯ(Magneto optical)ディスク，ＤＶＤ(Digital Versatile Disc)、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的、あるいは、永続的に格納（記録）しておくことが可能である。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウエアとして提供することが可能である。
【００５１】
なお、プログラムは、上述したようなリムーバブル記録媒体からコンピュータにインストールする他、ダウンロードサイトから、コンピュータに無線転送してもよい。または、ＬＡＮ(Local Area Network)、インターネットといったネットワークを介して、コンピュータに有線で転送してもよい。コンピュータでは、転送されてきたプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることが可能である。
【００５２】
また、上記実施形態で説明した処理動作に従って時系列的に実行されるのみならず、処理を実行する装置の処理能力、あるいは、必要に応じて並列的にあるいは個別に実行するように構築することも可能である。
【００５３】
また、上記実施形態で説明したシステムは、複数の装置の論理的集合構成にしたり、各装置の機能を混在させたりするように構築することも可能である。
【産業上の利用可能性】
【００５４】
本発明は、ネットワークによってつながれたコンピュータ群があった場合に、お互いに相関を持って稼動しているコンピュータをグループ化することができ、しかも複数のグループに属するようなネットワーク上で中心的な役割を果たすコンピュータについて、それらを適切に抽出することができる。これにより、複雑なコンピュータ・ネットワークシステムを、その働きによってクラスタ化し、管理・監視するといった用途に適用できる。
【符号の説明】
【００５５】
１    ＣＰＵ
２    メモリ
３    ＨＤＤ
４    ネットワークインターフェース
５    Ｉ／Ｏインターフェース
６    バスライン
１１    入力手段
１２    コミュニティ推定手段
１３    パラメータ学習手段
１４    出力手段
２１    ＲＡＭ
２２    ＲＯＭ
【図１】
2010165047.tif 000003
【図２】
2010165047.tif 000004
【図３】
2010165047.tif 000005