(57)【要約】【課題】ユーザの目的に応じてノードやリンクの重要度を動的に変動させることができるネットワーク順位付けシステム、ネットワーク順位付け方法及びプログラムを提供する。【解決手段】ネットワーク上に配置されるノード及び当該ノードが有するリンクに対し、順位付けを行うネットワーク順位付けシステムであって、ユーザの操作によって指定されたノード及びリンクに関するクエリデータを入力する入力手段と、入力手段で入力されたクエリデータに関連するネットワーク属性に基づいて、ノード又はリンクの重要度を算出する計算手段と、計算手段で算出された重要度に従ってノード及びリンクの順位付けを行い、結果をデータ出力する出力手段と、を有する。【選択図】図１
2010165051.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク上に配置されるノード及び当該ノードが有するリンクに対し、順位付けを行うネットワーク順位付けシステムであって、
ユーザの操作によって指定された前記ノード及び前記リンクに関するクエリデータを入力する入力手段と、
前記入力手段で入力されたクエリデータに関連するネットワーク属性に基づいて、前記ノード又は前記リンクの重要度を算出する計算手段と、
前記計算手段で算出された重要度に従って前記ノード及び前記リンクの順位付けを行い、結果をデータ出力する出力手段と、
を有することを特徴とするネットワーク順位付けシステム。
【請求項２】
前記入力手段で入力されたクエリデータに関連するネットワーク属性の問い合せを、前記計算手段から受けた場合、予め蓄積しているネットワーク属性の中から、前記クエリデータに関連するネットワーク属性を検索し、検索したネットワーク属性を示すデータを、問い合せ結果として前記計算手段へ送出する蓄積手段をさらに有することを特徴とする請求項１記載のネットワーク順位付けシステム。
【請求項３】
前記計算手段は、前記ネットワーク属性に基づいて適切な属性の重みを増加させ、重要度として算出することを特徴とする請求項１又は２記載のネットワーク順位付けシステム。
【請求項４】
情報処理装置が、ネットワーク上に配置されるノード及び当該ノードが有するリンクに対し、順位付けを行うネットワーク順位付け方法であって、
ユーザの操作によって指定された前記ノード及び前記リンクに関するクエリデータを入力する入力ステップと、
前記入力ステップで入力されたクエリデータに関連するネットワーク属性に基づいて、前記ノード又は前記リンクの重要度を算出する計算ステップと、
前記計算ステップで算出された重要度に従って前記ノード及び前記リンクの順位付けを行い、結果をデータ出力する出力ステップと、
を有することを特徴とするネットワーク順位付け方法。
【請求項５】
前記入力ステップで入力されたクエリデータに関連するネットワーク属性を、予めネットワーク属性を蓄積している蓄積手段の中から検索する検索ステップをさらに有し、
前記計算ステップでは、検索されたネットワーク属性に基づいて前記重要度を算出することを特徴とする請求項４記載のネットワーク順位付けシステム。
【請求項６】
前記計算ステップでは、前記ネットワーク属性に基づいて適切な属性の重みを増加させ、重要度として算出することを特徴とする請求項４又は５記載のネットワーク順位付けシステム。
【請求項７】
コンピュータに、ネットワーク上に配置されるノード及び当該ノードが有するリンクに対し、順位付け処理を実行させるためのプログラムであって、
ユーザの操作によって指定された前記ノード及び前記リンクに関するクエリデータを入力する入力処理と、
前記入力処理で入力されたクエリデータに関連するネットワーク属性に基づいて、前記ノード又は前記リンクの重要度を算出する計算処理と、
前記計算処理で算出された重要度に従って前記ノード及び前記リンクの順位付けを行い、結果をデータ出力する出力処理と、
をコンピュータに実行させることを特徴とするプログラム。
【請求項８】
前記入力処理で入力されたクエリデータに関連するネットワーク属性を、予めネットワーク属性を蓄積している蓄積手段の中から検索する検索処理をさらにコンピュータに実行させ、
前記計算処理で用いられるネットワーク属性は、前記検索処理で検索されたものであることを特徴とする請求項７記載のプログラム。
【請求項９】
前記計算処理は、前記ネットワーク属性に基づいて適切な属性の重みを増加させ、重要度として算出する処理であることを特徴とする請求項７又は８記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク構造を基にノードやリンクの重要度を計算し、順位付けを行うネットワーク順位付けシステム、ネットワーク順位付け方法及びプログラムに関する。
【背景技術】
【０００２】
本発明に関連するネットワーク順位付けシステムの一例が、非特許文献１に開示されている。このネットワーク順位付けシステムは、入力手段と、ハブ度計算手段と、オーソリティ度計算手段と、出力手段とから構成されており、次のように動作する。まず、入力手段から入力された観測対象のデータ（観測対象のノードやリンクのデータ）を基に、リンクを張っている各ノードのハブ度の和を、各ノードのオーソリティ度として計算する。そして、リンクを張っている各ノードのオーソリティ度の和を、各ノードのハブ度として計算し、これを計算結果が収束するまで繰り返す。最後に、各ノードのハブ度とオーソリティ度をデータ出力する。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Jon M. Kleinberg, “Authoritative sources in a hyperlinked environment” Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. Extended version in Journal of the ACM 46(1999).
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記非特許文献１のネットワーク順位付けシステムには、ネットワークのノードやリンクの重要度がネットワーク構造のみから一意に定まるという問題がある。その理由は、ネットワーク構造のみからノードやリンクの重要度を計算するモデルを用いているためである。
【０００５】
本発明は、上記事情に鑑みてなされたものであり、ユーザの目的に応じてノードやリンクの重要度を動的に変動させることができるネットワーク順位付けシステム、ネットワーク順位付け方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
かかる目的を達成するために、本発明のネットワーク順位付けシステムは、ネットワーク上に配置されるノード及び当該ノードが有するリンクに対し、順位付けを行うネットワーク順位付けシステムであって、ユーザの操作によって指定されたノード及びリンクに関するクエリデータを入力する入力手段と、入力手段で入力されたクエリデータに関連するネットワーク属性に基づいて、重要度を算出する計算手段と、計算手段で算出された重要度に従ってノード及びリンクの順位付けを行い、結果をデータ出力する出力手段と、を有することを特徴とする。
【０００７】
本発明のネットワーク順位付け方法は、情報処理装置が、ネットワーク上に配置されるノード及び当該ノードが有するリンクに対し、順位付けを行うネットワーク順位付け方法であって、ユーザの操作によって指定されたノード及びリンクに関するクエリデータを入力する入力ステップと、入力ステップで入力されたクエリデータに関連するネットワーク属性に基づいて、重要度を算出する計算ステップと、計算ステップで算出された重要度に従ってノード及びリンクの順位付けを行い、結果をデータ出力する出力ステップと、を有することを特徴とする。
【０００８】
本発明のプログラムは、コンピュータに、ネットワーク上に配置されるノード及び当該ノードが有するリンクに対し、順位付け処理を実行させるためのプログラムであって、ユーザの操作によって指定されたノード及びリンクに関するクエリデータを入力する入力処理と、入力処理で入力されたクエリデータに関連するネットワーク属性に基づいて、重要度を算出する計算処理と、計算処理で算出された重要度に従ってノード及びリンクの順位付けを行い、結果をデータ出力する出力処理と、をコンピュータに実行させることを特徴とする。
【発明の効果】
【０００９】
本発明によれば、ユーザの目的に応じてノードやリンクの重要度を動的に変動させることが可能となる。
【図面の簡単な説明】
【００１０】
【図１】本発明の一実施形態に係るネットワーク順位付けシステムのハードウェア構成を示すブロック図である。
【図２】本発明の一実施形態に係るネットワーク順位付けシステムの機能構成を示すブロック図である。
【図３】本発明の一実施形態に係るネットワーク順位付けシステムの動作を示すフローチャートである。
【発明を実施するための形態】
【００１１】
以下、本発明を実施するための最良の形態について添付図面を参照して詳細に説明する。
【００１２】
本発明の一実施形態であるネットワーク順位付けシステムについて説明する。図３は、本実施形態のネットワーク順位付けシステムのハードウェア構成を示すブロック図である。図３に示す本実施形態のネットワーク順位付けシステムは、コンピュータ、サーバ、ワークステーション、又は、その他の計算デバイス、機器などの情報処理装置である。
【００１３】
図３に示すように、本実施形態のネットワーク順位付けシステムは、ＣＰＵ（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となる。
【００２９】
ノードViの生成確率を、
p(Xi|θ) = Πj=1 J θj Xij (1-θj) 1-Xij
とする。これに共役な分布として、
p(θ|α,β) =Πj=1 J Beta(αj,βj)
を用いる。
【００３０】
次に、あるN個のノード集合Dc1=[Vn]をクエリとした場合に、これらの生成確率を、
p(Dc1|α,β)
とする。
【００３１】
このとき，クエリDc1が与えられたときのあるノードViの重要度を、
Score1 = log p(Xi|Dc1,α,β) / p(Xi|α,β)
とする。
【００３２】
この計算は、例えば、文献「Z. Ghahramani and K. Heller, "Bayesian Sets," In Advances in Neural Information Processing Systems (NIPS 2005), 2006.」の方法を用いて解くことができる。
【００３３】
次に、あるN個のリンク集合Dc2=[(Vni, Vnj)]をクエリとした場合に、これらの生成確率を、
p(Dc2|α,β)
とする。
【００３４】
このとき、クエリDc2が与えられたときのあるノードViの重要度を、
Score2 = log p(Xi|Dc2,α,β) / p(Xi|α,β)
とする。
【００３５】
この計算は、例えば、文献「R. Silva, K. Heller and Z. Ghahramani, "Analogical Reasoning with Relational Bayesian Sets," In the 11th International Conference on AI and Statistics (AISTATS 2007), 2007.」の方法を用いて解くことができる。
【００３６】
ノード集合Dc1を自己へのリンク集合Dc2とみなせば，すべてScore2を用いて統一的に計算可能である。
【００３７】
また、明示的なリンクを表すXの代わりに潜在的なコミュニティを表すZを用いても同様に解くことが可能である（このときのスコアをScore1およびScore2と同様に計算してScore3およびScore4とする）。
【００３８】
このときScore1およびScore2は明示的なリンクベースの重要度を表しており、局所的な関係に基づいて重要度を決めていることを意味する。
【００３９】
それに対してScore3およびScore4は潜在的なコミュニティベースの重要度を表しており、直接リンクを持たないノード関係も含めた大局的な関係に基づいて重要度を決めていることを意味する。
【００４０】
この２種類のスコアを用いて例えばScore=f(Score2, Score4)とすることで、様々な関係を考慮した重要度を計算することも可能である。ここでf(・)は適当な関数である。
【００４１】
まず、クエリ入力手段１１は、ユーザの操作により指定されたクエリ（ノード及びリンクのうち少なくとも１つに関するデータ）Dch (h=1,2,3,4；以下同様)を入力する（ステップＳ１）。
【００４２】
クエリ入力手段１１は、入力したクエリDchを、重要度計算手段１２へ出力する。
【００４３】
次に、重要度計算手段１２は、クエリ入力手段１１からクエリDchを入力し、入力したクエリに関連するネットワーク属性X,Zを、ネットワーク属性蓄積手段１３へ問い合せる（ステップＳ２）。
【００４４】
ネットワーク属性蓄積手段１３は、重要度計算手段１２から、クエリDchに関連するネットワーク属性X,Zの問い合せを入力すると、予め蓄積しているネットワーク属性X,Zの中から、問い合せを受けたクエリDchに関連するネットワーク属性X,Zを検索する。
【００４５】
そして、ネットワーク属性蓄積手段１３は、検索したネットワーク属性X,Zを示すデータを、問い合せ結果として重要度計算手段１２へ送出する（ステップＳ３）。
【００４６】
重要度計算手段１２は、ネットワーク属性蓄積手段３から問い合せ結果（ネットワーク属性X,Z）を受け取ると、その問い合せ結果に基づいて適切な属性の重みα,βを増加させ、各ノードまたはリンクの重要度を算出する（ステップＳ４）。
【００４７】
重要度計算手段１２は、算出した重要度を重要度出力手段１４へ出力する。
【００４８】
重要度出力手段１４は、重要度計算手段１２で算出された重要度に従って、ノードやリンクを順位付けしてデータ出力する（ステップＳ５）。出力手段１４によるデータ出力先の例としては、ネットワーク上の外部装置や、ディスプレイ、プリンタ等が挙げられる。
【００４９】
このように、本実施形態のネットワーク順位付けシステムでは、入力されたクエリに応じて各ノードやリンクの重要度を動的に変動させるように動作する。よって、入力されたクエリに応じて動的に各ノードやリンクをランキングしリストアップできる。
【００５０】
以上説明したように、本実施形態によれば、ネットワーク構造だけでなくユーザの目的に応じてノードやリンクの重要度を動的に変動させることができる。よって、ユーザにより入力されたクエリに応じた最適なノードやリンクのランキングができる。
【００５１】
以上、本発明の実施形態について説明したが、上記実施形態に限定されるものではなく、その要旨を逸脱しない範囲において種々の変形が可能である。
【００５２】
例えば、上述した各実施形態における動作は、ハードウェア、または、ソフトウェア、あるいは、両者の複合構成によって実行することも可能である。
【００５３】
ソフトウェアによる処理を実行する場合には、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれているコンピュータ内のメモリにインストールして実行させてもよい。あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させてもよい。
【００５４】
例えば、プログラムは、記録媒体としてのハードディスクやＲＯＭ（Read Only Memory）に予め記録しておくことが可能である。あるいは、プログラムは、ＣＤ−ＲＯＭ(Compact Disc Read Only Memory)，ＭＯ(Magneto optical)ディスク，ＤＶＤ(Digital Versatile Disc)、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的、あるいは、永続的に格納（記録）しておくことが可能である。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウエアとして提供することが可能である。
【００５５】
なお、プログラムは、上述したようなリムーバブル記録媒体からコンピュータにインストールする他、ダウンロードサイトから、コンピュータに無線転送してもよい。または、ＬＡＮ(Local Area Network)、インターネットといったネットワークを介して、コンピュータに有線で転送してもよい。コンピュータでは、転送されてきたプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることが可能である。
【００５６】
また、上記実施形態で説明した処理動作に従って時系列的に実行されるのみならず、処理を実行する装置の処理能力、あるいは、必要に応じて並列的にあるいは個別に実行するように構築することも可能である。
【００５７】
また、上記実施形態で説明したシステムは、複数の装置の論理的集合構成にしたり、各装置の機能を混在させたりするように構築することも可能である。
【産業上の利用可能性】
【００５８】
本発明によれば、ネットワークによってつながれたコンピュータ群があり、お互いに相関を持って稼動しているコンピュータがグループ化されているときに、通常であれば複数のグループに属するようなネットワーク上で中心的な役割を果たすコンピュータが重要とされるが、ユーザが特定のノードやリンクをクエリとして与えることで、真にそれらと相関の強いノードやリンクを動的に適切に抽出することができる。これにより、複雑なコンピュータ・ネットワークシステムにおいて、その相関に基づいて集中的に管理・監視するといった用途に適用できる。
【符号の説明】
【００５９】
１    ＣＰＵ
２    メモリ
３    ＨＤＤ
４    ネットワークインターフェース
５    Ｉ／Ｏインターフェース
６    バスライン
１１    クエリ入力手段（入力手段の一例）
１２    重要度計算手段（計算手段の一例）
１３    ネットワーク属性蓄積手段（蓄積手段の一例）
１４    重要度出力手段（出力手段の一例）
２１    ＲＡＭ
２２    ＲＯＭ
【図１】
2010165051.tif 000003
【図２】
2010165051.tif 000004
【図３】
2010165051.tif 000005