(57)【特許請求の範囲】
【請求項１】
ノードデータをリンクで接続したグラフデータを有するデータベースを管理する関係性グラフデータベースシステムであって、
コンピュータネットワークに接続した端末装置において行われた操作に対応するノードデータを生成するノード生成部と、
複数のノードデータをリンクで接続した部分グラフデータを生成する部分グラフ生成部と、
複数の部分グラフデータを合成することでグラフデータを生成し、生成されたグラフデータを前記データベースに記憶させるグラフ生成部と、
を備え、
前記ノード生成部は、前記端末装置において行われる複数種類の操作に対応して、複数種類のノードデータを生成可能であり、
前記部分グラフ生成部は、同一の端末装置において行われた複数の操作が所定の関係性を有する場合には、当該複数の操作に対応する複数のノードデータ同士をリンクで接続して部分グラフデータを生成し、
前記グラフ生成部は、
共通するノードデータを有する複数の部分グラフデータを当該共通するノードデータにおいてグラフ合成することでグラフデータを生成する、又は、
共通するノードデータを有する部分グラフデータとグラフデータとを、当該共通するノードデータにおいてグラフ合成することで、新たなグラフデータを生成する
ことを特徴とする関係性グラフデータベースシステム。
【請求項２】
前記所定の関係性には、複数の操作の時間間隔が所定時間以下であること、
が含まれる請求項１記載の関係性グラフデータベースシステム。
【請求項３】
前記所定の関係性には、複数の操作が、同一のトランザクション内において行われたこと、が含まれる請求項１又は２記載の関係性グラフデータベースシステム。
【請求項４】
前記グラフ生成部は、前記部分グラフ又は前記グラフ生成部によって生成されたグラフデータを、グラフデータを生成することができる他のシステムによって生成された他のグラフデータと合成する
請求項１〜３のいずれか１項に記載の関係性グラフデータベースシステム。
【請求項５】
前記部分グラフ生成部は、同一の端末において行われた複数の操作が所定の関係性を有する場合には、当該複数の操作に対応する複数のノードデータ同士が、同一種類であるか異なる種類であるかを問わず、リンクで接続して部分グラフデータを生成する
請求項１〜４のいずれか１項に記載の関係性グラフデータベースシステム。
【請求項６】
前記ノード生成部は、前記端末装置の位置情報に基づいて、位置に対応するノードデータを生成可能であり、
前記部分グラフ生成部は、位置に対応するノードデータと操作に対応するノードデータとが、所定の関係性を有する場合には、位置に対応するノードデータと操作に対応するノードデータとをリンクで接続して部分グラフデータを生成する
請求項１〜５のいずれか１項に記載の関係性グラフデータベースシステム。
【請求項７】
前記部分グラフ生成部は、前記リンクの生成に関するリンク情報をも生成する
請求項１〜６のいずれか１項に記載の関係性グラフデータベースシステム。
【請求項８】
前記グラフ生成部は、共通するノードデータ対の間のリンクそれぞれを維持しつつ、当該ノードデータ対においてグラフ合成を行う
請求項１〜７のいずれか１項に記載の関係性グラフデータベースシステム。
【請求項９】
前記グラフ生成部は、共通するノードデータ対の間のリンクそれぞれを一本のリンクに合成しつつ、当該ノード対においてグラフ合成を行う
請求項１〜７のいずれか１項に記載の関係性グラフデータベースシステム。
【請求項１０】
前記データベースに記憶されたグラフデータのリンクを消滅させるリンク消滅部をさらに備える
請求項１〜９のいずれか１項に記載の関係性グラフデータベースシステム。
【請求項１１】
前記リンク消滅部は、前記データベースに記憶されたグラフデータのリンクのリンク距離を時間経過に応じて長くし、リンク距離が所定の長さになるとリンクを消滅させる
請求項１０記載の関係性グラフデータベースシステム。
【請求項１２】
前記ノードデータ生成部によってノードデータが生成される操作は、前記端末装置において行われる商品購入操作、前記端末装置において行われるＷｅｂサイト表示操作、前記端末装置において行われるコンテンツ閲覧操作のうちの少なくともいずれか一つを含む
請求項１〜１１のいずれか１項に記載の関係性グラフデータベースシステム。
【請求項１３】
前記端末装置からの入力に基づいて、前記グラフデータに含まれるノードデータの中から、複数の基準ノードデータを選択する基準ノード選択部と、
複数の基準ノードからみた中心性に基づいて、前記グラフデータからノードデータを抽出する抽出部と、
を更に備える請求項１〜１２のいずれか１項に記載の関係性グラフデータベースシステム。
【請求項１４】
前記抽出部は、複数の基準ノードデータそれぞれからみて中心にあるノードデータを中心ノードデータとして選択し、中心ノードデータからの経路長に基づいて、前記グラフデータからノードデータを抽出する
請求項１３記載の関係性グラフデータベースシステム。
【請求項１５】
前記抽出部は、前記グラフデータから、複数の基準ノードデータからの経路長が所定値以下であるノードデータからなる局所グラフデータを特定し、前記局所グラフデータにおける中心性に基づいてノードデータを抽出する
請求項１３記載の関係性グラフデータベースシステム。
【請求項１６】
前記抽出部は、前記局所グラフデータにおいて複数の基準ノードデータを結ぶ最短経路上のノードデータそれぞれからの経路長から求められる中心性に基づいてノードデータを抽出する
請求項１５記載の関係性グラフデータベースシステム。
【請求項１７】
前記抽出部は、前記局所グラフデータにおいて複数の基準ノードデータ及び複数の基準ノードデータの近傍のノードデータそれぞれからの経路長から求められる中心性に基づいてノードデータを抽出する
請求項１５記載の関係性グラフデータベースシステム。
【請求項１８】
前記抽出部によって抽出されたノードデータを前記端末装置に表示させる表示制御部を更に備える請求項１１〜１７のいずれか１項に記載の関係性グラフデータベースシステム。
【請求項１９】
前記抽出部によって抽出されたノードデータを前記端末装置に表示させる表示制御部を更に備え、
前記表示制御部は、抽出された各ノードデータを、複数の基準ノードのうち、経路長が最も小さくなる基準ノードの付近に集中させて表示させる
請求項１３〜１７のいずれか１項に記載の関係性グラフデータベースシステム。
【請求項２０】
前記抽出部によって抽出されたノードデータを前記端末装置に表示させる表示制御部を更に備え、
前記表示制御部は、抽出されたノードデータを、複数の基準ノードデータそれぞれからみた中心性に基づいて、中心性の高さを識別可能に表示する
請求項１３〜１７のいずれか１項に記載の関係性グラフデータベースシステム。
【請求項２１】
前記グラフのノードデータ対の間のリンクの数が多いほど当該ノードデータ対の間のリンク距離が小さいものとみなして経路長を求める
請求項１３〜２０のいずれか１項に記載の関係性グラフデータベースシステム。
【請求項２２】
基準ノードデータとして選択されることが予測される複数のノードデータの組み合わせについて、前記抽出部におけるノードデータの抽出の処理の一部又は全部を予め実行した処理結果を記憶する記憶部を更に備え、
複数の基準ノードデータが実際に選択されると、前記抽出部は、前記記憶部に記憶されている処理結果を用いて、ノードデータの抽出を行う
請求項１３〜２１のいずれか１項に記載の関係性グラフデータベースシステム。
【請求項２３】
前記基準ノード選択部は、複数のノードデータを一つのノードデータとみなして、基準ノードデータの一つとして選択可能であり、
一つのノードデータとみなされる複数のノードデータは、前記ネットワーク型データに含まれる複数のノードデータのち、クラスタリング処理によってクラスター化された複数のノードデータである
請求項１３〜２２のいずれか１項に記載の関係性グラフデータベースシステム。
【請求項２４】
コンピュータを、請求項１〜２３のいずれか１項に記載の関係性グラフデータベースシステムとして機能させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、関係性グラフデータベースシステムに関するものである。
【背景技術】
【０００２】
高度なサービスの実現のために、個々のデータに詳細な属性情報をもたせることが取り組まれているが、一方で、データ間の関係性をサービスに活用する試みが検討されている（非特許文献１参照）。特に、人と人との関係性や人の移動のコンテキストとロケーションとの関係性といったソーシャルな関係性が注目を集めている。こういったデータの関係性は、データをノード、データ間の直接的なつながりをリンクで表すグラフデータとして表現される。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】R.Shinkuma et al., "New Generation Information Network Architecture Based on Social Metric", IEICE Society Conference, Sept. 2010
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明は、グラフデータを生成する新規な手法を提供することを目的とする。また、本発明の他の目的は、グラフデータからデータを抽出する新規な手法を提供することである。
【課題を解決するための手段】
【０００５】
（１）本発明は、ノードデータをリンクで接続したグラフデータを有するデータベースを管理する関係性グラフデータベースシステムであって、
コンピュータネットワークに接続した端末装置において行われた操作に対応するノードデータを生成するノード生成部と、
複数のノードデータをリンクで接続した部分グラフデータを生成する部分グラフ生成部と、
複数の部分グラフデータを合成することでグラフデータを生成し、生成されたグラフデータを前記データベースに記憶させるグラフ生成部と、
を備え、
前記ノード生成部は、前記端末装置において行われる複数種類の操作に対応して、複数種類のノードデータを生成可能であり、
前記部分グラフ生成部は、同一の端末装置において行われた複数の操作が所定の関係性を有する場合には、当該複数の操作に対応する複数のノードデータ同士をリンクで接続して部分グラフデータを生成し、
前記グラフ生成部は、
共通するノードデータを有する複数の部分グラフデータを当該共通するノードデータにおいてグラフ合成することでグラフデータを生成する、又は、
共通するノードデータを有する部分グラフデータとグラフデータとを、当該共通するノードデータにおいてグラフ合成することで、新たなグラフデータを生成する
ことを特徴とする関係性グラフデータベースシステムである。
【０００６】
（２）前記所定の関係性には、複数の操作の時間間隔が所定時間以下であること、が含まれるのが好ましい。
【０００７】
（３）前記所定の関係性には、複数の操作が、同一のトランザクション内において行われたこと、が含まれるのが好ましい。
【０００８】
（４）前記グラフ生成部は、前記部分グラフ又は前記グラフ生成部によって生成されたグラフデータを、グラフデータを生成することができる他のシステムによって生成された他のグラフデータと合成するのが好ましい。
【０００９】
（５）前記部分グラフ生成部は、同一の端末において行われた複数の操作が所定の関係性を有する場合には、当該複数の操作に対応する複数のノードデータ同士が、同一種類であるか異なる種類であるかを問わず、リンクで接続して部分グラフデータを生成するのが好ましい。
【００１０】
（６）前記ノード生成部は、前記端末装置の位置情報に基づいて、位置に対応するノードデータを生成可能であり、
前記部分グラフ生成部は、位置に対応するノードデータと操作に対応するノードデータとが、所定の関係性を有する場合には、位置に対応するノードデータと操作に対応するノードデータとをリンクで接続して部分グラフデータを生成するのが好ましい。
【００１１】
（７）前記部分グラフ生成部は、前記リンクの生成に関するリンク情報をも生成するのが好ましい。
【００１２】
（８）前記グラフ生成部は、共通するノードデータ対の間のリンクそれぞれを維持しつつ、当該ノードデータ対においてグラフ合成を行うのが好ましい。
【００１３】
（９）前記グラフ生成部は、共通するノードデータ対の間のリンクそれぞれを一本のリンクに合成しつつ、当該ノード対においてグラフ合成を行うのが好ましい。
【００１４】
（１０）前記データベースに記憶されたグラフデータのリンクを消滅させるリンク消滅部をさらに備えるのが好ましい。
【００１５】
（１１）  前記リンク消滅部は、前記データベースに記憶されたグラフデータのリンクのリンク距離を時間経過に応じて長くし、リンク距離が所定の長さになるとリンクを消滅させるのが好ましい。
【００１６】
（１２）前記ノードデータ生成部によってノードデータが生成される操作は、前記端末装置において行われる商品購入操作、前記端末装置において行われるＷｅｂサイト表示操作、前記端末装置において行われるコンテンツ閲覧操作のうちの少なくともいずれか一つを含むのが好ましい。
【００１７】
（１３）前記端末装置からの入力に基づいて、前記グラフデータに含まれるノードデータの中から、複数の基準ノードデータを選択する基準ノード選択部と、
複数の基準ノードからみた中心性に基づいて、前記グラフデータからノードデータを抽出する抽出部と、
を更に備えるのが好ましい。
【００１８】
（１４）前記抽出部は、複数の基準ノードデータそれぞれからみて中心にあるノードデータを中心ノードデータとして選択し、中心ノードデータからの経路長に基づいて、前記グラフデータからノードデータを抽出するのが好ましい。
【００１９】
（１５）前記抽出部は、前記グラフデータから、複数の基準ノードデータからの経路長が所定値以下であるノードデータからなる局所グラフデータを特定し、前記局所グラフデータにおける中心性に基づいてノードデータを抽出するのが好ましい。
【００２０】
（１６）前記抽出部は、前記局所グラフデータにおいて複数の基準ノードデータを結ぶ最短経路上のノードデータそれぞれからの経路長から求められる中心性に基づいてノードデータを抽出するのが好ましい。
【００２１】
（１７）前記抽出部は、前記局所グラフデータにおいて複数の基準ノードデータ及び複数の基準ノードデータの近傍のノードデータそれぞれからの経路長から求められる中心性に基づいてノードデータを抽出するのが好ましい。
【００２２】
（１８）前記抽出部によって抽出されたノードデータを前記端末装置に表示させる表示制御部を更に備えるのが好ましい。
【００２３】
（１９）前記抽出部によって抽出されたノードデータを前記端末装置に表示させる表示制御部を更に備え、前記表示制御部は、抽出された各ノードデータを、複数の基準ノードのうち、経路長が最も小さくなる基準ノードの付近に集中させて表示させるのが好ましい。
【００２４】
（２０）前記抽出部によって抽出されたノードデータを前記端末装置に表示させる表示制御部を更に備え、前記表示制御部は、抽出されたノードデータを、複数の基準ノードデータそれぞれからみた中心性に基づいて、中心性の高さを識別可能に表示するのが好ましい。
【００２５】
（２１）前記グラフのノードデータ対の間のリンクの数が多いほど当該ノードデータ対の間のリンク距離が小さいものとみなして経路長を求めるのが好ましい。
【００２６】
（２２）基準ノードデータとして選択されることが予測される複数のノードデータの組み合わせについて、前記抽出部におけるノードデータの抽出の処理の一部又は全部を予め実行した処理結果を記憶する記憶部を更に備え、
複数の基準ノードデータが実際に選択されると、前記抽出部は、前記記憶部に記憶されている処理結果を用いて、ノードデータの抽出を行うのが好ましい。
【００２７】
（２３）前記基準ノード選択部は、複数のノードデータを一つのノードデータとみなして、基準ノードデータの一つとして選択可能であり、
一つのノードデータとみなされる複数のノードデータは、前記グラフデータに含まれる複数のノードデータのち、クラスタリング処理によってクラスター化された複数のノードデータであるのが好ましい。
【００２８】
（２４）他の観点からみた本発明は、コンピュータを、前記（１）〜（２４）のいずれか１項に記載の関係性グラフデータベースシステムとして機能させるためのコンピュータプログラムである。
【図面の簡単な説明】
【００２９】
【図１】関係性グラフデータベースシステムの構成図である。
【図２】処理サーバの構成図である。
【図３】ノード生成からグラフデータ生成までの過程を示す図である。
【図４】グラフデータ更新の過程を示す図である。
【図５】他のグラフデータと合成されたグラフデータを示す図である。
【図６】ノード抽出処理のフローチャートである。
【図７】ノード抽出処理の説明図である。
【図８】抽出されたノードの表示例を示す図である。
【図９】ノード抽出処理のフローチャートである。
【図１０】ノード抽出処理の説明図である。
【図１１】クラスターノードを含むグラフデータの例を示す図である。
【発明を実施するための形態】
【００３０】
以下、本発明の好ましい実施形態について添付図面を参照しながら説明する。
【００３１】
［１．全体構成］
図１は、関係性グラフデータベースシステム１の全体構成の概要を示している。関係性グラフデータベースシステム１は、処理サーバ２と、ソーシャルネットワークデータベース３と、キャッシュサーバ（記憶部）４と、を備えている。
なお、関係性グラフデータベースシステム１の各機能は、処理サーバ２などとして機能するコンピュータの記憶装置にインストールされたコンピュータプログラムが、コンピュータに実行されることによって発揮される。そのコンピュータプログラムは、記録媒体に記録して、譲渡・販売することができる。
【００３２】
処理サーバ２は、インターネットなどのコンピュータネットワーク５を介して、端末装置６と通信可能である。端末装置６は、パーソナルコンピュータ、携帯電話、及びその他コンピュータネットワーク５に接続可能な装置であれば、特に限定されない。
【００３３】
ソーシャルネットワークデータベース（以下、単に「データベース」という）３は、ノード間の関係性を示すグラフデータを記憶するためのものである。グラフデータは、ノードデータ（以下、単に「ノード」という）をリンクで接続したものである。本実施形態のグラフデータには、一種類のもの（例えば、人）を表すノードだけでなく、人、物、場所、団体、電子的な物（コンテンツ）などの多種類のものに対応した多種類のノードが存在する。
【００３４】
キャッシュサーバ４は、処理サーバ２において行われる処理の結果を予め記憶しておくことで、処理サーバ２における処理を迅速化させるためのものである。キャッシュサーバ４の詳細については後述する。
【００３５】
図２に示すように処理サーバ２は、グラフデータの生成（更新）に関する処理を行う第１処理部２１と、グラフデータからのノードの抽出に関する処理を行う第２処理部２２と、を備えている。
【００３６】
［２．グラフデータの生成］
グラフデータの生成（更新）に関する処理を行う第１処理部２１は、情報取得部２１１と、ノード生成部２１２と、判定部２１３と、部分グラフ生成部２１４と、グラフ生成部２１５と、リンク消滅部２１６と、を備えている。
【００３７】
情報取得部２１１は、端末装置６において行われた操作内容を示す操作情報を取得する。操作情報は、情報取得部２１１が、端末装置６において行われた操作履歴を、当該端末装置６から操作情報として取得してもよいし、端末装置６がコンピュータネットワーク５を介して接続したＷｅｂサイトにおいて行った操作履歴を、操作情報として当該ＷｅｂサイトのＷｅｂサーバから取得してもよい。
【００３８】
情報取得部２１１は、端末装置（移動端末装置）６の位置を示す位置情報（ＧＰＳ情報など）を取得することもできる。
【００３９】
ノード生成部２１２は、グラフデータにおけるノードを生成するためのものである。ノード生成部２１２は、情報取得部２１１が取得した操作情報が示す操作に、ノード作成対象の操作が含まれていれば、ノードを生成する。
【００４０】
ノード作成対象の操作は、例えば、端末装置６において行われる商品購入操作、端末装置６において行われるＷｅｂサイト表示操作、端末装置６において行われるコンテンツ閲覧操作などである。
例えば、商品購入操作の場合、購入された商品を示す情報（商品名データなど）などを内部情報として持つ商品ノードが生成される。Ｗｅｂサイト表示操作の場合、表示されたＷｅｂサイトのサイト名及びＷｅｂサイトのＵＲＬなどを内部情報として持つＷｅｂサイトノードが生成される。コンテンツ閲覧操作の場合、閲覧されたコンテンツの名前及びコンテンツが存在場所を示すＵＲＬなどを内部情報として持つコンテンツノードが生成される。
【００４１】
このように、ノード生成部２１２は、端末装置６において行われる複数種類の操作に対応して、複数種類のノードデータを生成可能である。
また、ノード生成部２１２は、予め設定されたノード作成対象の操作が行われると、ノードを生成するよう構成されているため、ノードが作成される操作は、ノードを作成するための専用の操作である必要はなく、前述のような商品購入操作、Ｗｅｂサイト表示操作、コンテンツ閲覧操作など、多様な種類の操作をノード作成対象とすることができる。
【００４２】
さらに、ノード生成部２１２は、情報取得部２１１が取得した位置情報に基づいて、位置情報が示す位置に対応した位置ノードを生成可能である。例えば、ＧＰＳ情報からなる位置情報が京都市内の位置を示している場合、「京都」という位置を示す位置ノードが生成される。
【００４３】
判定部２１３は、情報操作情報及び／又は位置情報に基づき、同一の端末装置６において行われた複数の操作（ノード作成対象の操作）及び／又は端末装置６の位置が、所定の関係性を有しているか否かを判定する。
【００４４】
所定の関係性としては、複数の操作（ノード作成対象の操作）の時間間隔が、所定時間以下であること、又は、複数の操作（ノード作成対象の操作）が同一のトランザクション内においておこなわれたこと、などが挙げられる。
【００４５】
所定の関係性を生じさせるための複数の操作（ノード作成対象の操作）の時間間隔は、ほぼ同時とみなせるほどの短い時間であってもよいし、１日程度の比較的長い時間であってもよい。また、所定の関係性を生じさせるための複数の操作（ノード作成対象の操作）の時間間隔は、調整自在であるのが好ましい。
所定の関係性を生じさせるための複数の操作（ノード作成対象の操作）の時間間隔は、あらゆる操作について一定であってもよいし、操作の種類によって時間間隔が異なっていても良い。
【００４６】
同一のトランザクション内に行われる複数の操作としては、場合としては、例えば、Ｗｅｂサイトにおける商品購入ためのトランザクションにおいて、複数の商品を購入した場合における複数の商品購入操作が挙げられる。
【００４７】
また、位置と操作とが所定の関係性を生じさせる場合としては、端末装置６が、ある位置（例えば、京都）に存在しているときに、商品購入操作をした場合、Ｗｅｂサイト表示操作をした場合、又はコンテンツ閲覧操作をした場合、などが挙げられる。
【００４８】
判定部２１３は、情報操作情報及び／又は位置情報に基づき、操作間又は操作と位置との間に所定の関係性があることを検出すると、その検出結果を、部分グラフ生成部２１４に与える。
【００４９】
部分グラフ生成部２１４は、判定部２１３によって検出された所定の関係性に対応するリンクを生成して、ノードをリンクで接続した部分グラフデータ（以下、単に「部分グラフ」という）を生成する。
具体的には、部分グラフ生成部２１４は、ノード生成部２１２によって生成された複数のノードに対して、判定部２１３によって所定の関係性を有すると判定された操作同士又は操作と位置との間を、リンクで接続する。
これにより、部分グラフ生成部２１４は、同一の端末装置６において行われた複数の操作、又は、当該端末装置の位置に対応する複数のノードをリンクで接続した部分グラフを生成する。
【００５０】
部分グラフ生成部２１４は、リンク情報生成部２１４ａを有しており、リンク情報生成部２１４ａは、ノード同士を接続するリンクの生成の際に、当該リンクの生成に関するリンク情報も併せて生成する。リンク情報には、リンクが生成された日時を示す時刻情報、及び／又は、当該リンク生成の原因となった所定の関係性（複数の操作、操作と位置）を示す情報が含まれる。リンク情報は、部分グラフ（部分グラフデータ）の一部を構成する。
【００５１】
なお、部分グラフにおいてリンクで接続されるノードは、同一種類の操作に対応するノードであってもよいし、異なる種類の操作に対応するノードであってもよい。つまり、ノード同士は、その種類を問わず、所定の関係性を有していればリンクで接続される。
【００５２】
グラフ生成部２１５は、共通するノードを有する複数の部分グラフ同士を、当該共通するノードにおいてグラフ合成することで、グラフデータを生成して、データベース３に記憶させて、保存する。
また、グラフ生成部２１５は、共通するノードを有する部分グラフと、データベース３に記憶されているグラフデータとを、当該共通するノードデータにおいてグラフ合成することで、新たなグラフデータを生成して、データベース３に保存する。
【００５３】
部分グラフは、ノードの種類を問わず、ノード間が所定の関係性を有していればリンクで接続されるため、そのような部分グラフを合成して得られたグラフデータは、階層構造のグラフや２部グラフのように、シンプルな構造となるグラフとは異なり、多様な接続関係を有するグラフとなる。
【００５４】
グラフ生成部２１５は、データベース３に記憶されているグラフデータを、グラフデータを作成することができる他のシステム（例えば、人の関係を表すグラフデータを作成するシステム）と合成することもできる。この場合、データベース３に記憶されているグラフデータと、他のシステムのグラフデータと、において共通して存在するノードにおいてグラフ合成することで、統合されたグラフデータが生成される。
【００５５】
リンク消滅部２１６は、データベース３に保存されているグラフデータのリンクを、消滅させることができる。リンク消滅部（リンク距離変更部）２１６は、例えば、時間の経過に応じて、リンク距離を長くしていき、リンク距離が所定の長さ以上になれば、リンクを消滅させる。グラフデータのリンクを適宜消滅させることで、ネットワーク型データが膨大になりすぎるのを抑制することができる。また、時間経過に応じてリンク距離を長くすることで、古いリンクで接続されたノードの関係性を低くすることができる。
リンク消滅部２１６によるリンク消滅処理（リンク距離変更処理）を行うため、各リンクにはタイムスタンプが設定されている。リンク消滅部２１６は、リンクに設定されたタイムスタンプに基づき、リンク距離を長くしたり、リンクを消滅させたりする。
なお、リンク消滅部２１６は、リンクを時間に対して確率的に消滅させてもよい。確率が１であれば、リンクはある時刻で消滅し、確率が０であればリンクは永続する。リンク消滅の確率は、各リンクについて共通であってもよいし、リンク毎に異なっていてもよい。例えば、リンクの両端のノードの種類によってリンク消滅確率が異なっていても良い。
【００５６】
図３は、処理サーバ２の第１処理部２１によるグラフデータの作成の一例を示している。
まず、図３（ａ）に示すように、ある端末装置６によって、商品Ａを購入する操作Ｎ１１と、商品Ｂを購入する操作Ｎ１２と、ＷｅｂサイトＣを表示する操作Ｎ１３と、が、所定時間内で連続的に行われたものとする。情報取得部２１１は、商品Ａを購入する操作Ｎ１１と、商品Ｂを購入する操作Ｎ１２と、ＷｅｂサイトＣを表示する操作Ｎ１３と、を含む操作の履歴情報（操作情報）を取得する。
【００５７】
ノード生成部２１２は、操作情報に含まれる操作履歴から、ノード作成対象として設定された操作である、商品Ａを購入する操作Ｎ１１と、商品Ｂを購入する操作Ｎ１２と、ＷｅｂサイトＣを表示する操作Ｎ１３と、を抽出して、それらの操作に対応したノードＮ１１，Ｎ１２，Ｎ１３を生成する（図３（ａ）参照）。
【００５８】
判定部２１３は、操作情報に含まれる操作履歴から、所定の関係性を有するノード対を検出する。ここでは、商品Ａを購入する操作Ｎ１１と、商品Ｂを購入する操作Ｎ１２とは、ほぼ同時に行われており、所定の関係性（操作時間間隔が所定時間以下）Ｘ１１があるものとする。また、商品Ａを購入する操作Ｎ１１及び商品Ｂを購入する操作Ｎ１２は、ＷｅｂサイトＣを表示する操作とも、所定の関係性（操作時間間隔が所定時間以下）Ｙ１１，Ｙ１２があるものとする。
【００５９】
この場合、部分グラフ生成部２１４は、３つのノードＮ１１，Ｎ１２，Ｎ１３を接続する３つのリンクＸ１１，Ｙ１１，Ｙ１２生成し、部分グラフＰ１を生成する（図３（ｂ）参照）。
【００６０】
また、図３（ａ）に示す操作を行った端末装置６とは無関係の別の端末装置６が、ＷｅｂサイトＣを表示する操作Ｎ２１と、コンテンツＤを閲覧する操作Ｎ２１と、を、所定時間内で連続的に行ったものとする（図３（ｂ）参照）。この場合、部分グラフ生成部２１４は、２つの操作に対応する２つのノードＮ２１，Ｎ２２をリンクＺ１１によって接続した部分グラフＰ２を生成する。
【００６１】
グラフ生成部２１５は、独立して生成された２つの部分グラフＰ１，Ｐ２に、共通のノード（ＷｅｂサイトＣを表示する操作）Ｎ１２，Ｎ２１が含まれていることを検出すると、それらの部分グラフＰ１，Ｐ２のグラフ合成を行う。
【００６２】
部分グラフＰ１，Ｐ２のグラフ合成は、共通する複数のノード（ＷｅｂサイトＣを表示する操作）Ｎ１２，Ｎ２１を統一した一つのノードＮ３１とすることで、行われる（図３（ｃ）参照）。これにより、複数の部分グラフＰ１，Ｐ２が合成された一つのグラフデータＧ１が生成される。生成されたグラフデータＧ１は、データベース３に保存される。
【００６３】
さらに、図４（ａ）に示すグラフデータＧ１がデータベース３に保存されているときに、図４（ｂ）に示す部分グラフＰ３が新たに生成されたものとする。この場合、グラフ生成部２１５は、グラフデータＧ１と部分グラフＰ３とに、共通のノード（商品Ｂを購入する操作Ｎ１２，Ｎ４１、ＷｅｂサイトＣを表示する操作Ｎ３１，Ｎ３３）が含まれていることを検出すると、グラフデータＧ１と部分グラフＰ３とのグラフ合成を行う（図４（ｃ）参照）。このグラフ合成によって、グラフデータＧ１が更新された新たなグラフデータＧ２が生成され、データベース３に保存される。
したがって、端末装置６によって操作が行われることによって、グラフデータが拡張される。
【００６４】
図４（ａ）（ｂ）のように、ノード対（ノードＮ１２，Ｎ３１のノード対と、ノードＮ４１，Ｎ４４のノード対）が共通して存在する場合、共通するノード対の間のリンクＹ１２，Ｙ２１それぞれを維持したまま、グラフ合成が行われる。したがって、グラフ合成後のグラフデータＧ２は、ノード対Ｎ５１，５２との間に、合成前のリンクＹ１２，Ｙ２２をそのまま有している。
【００６５】
合成後においても、合成前のリンクＹ１２，Ｙ２２をそのまま維持することで、合成前のリンクＹ１２，Ｙ２２が有している情報（タイムスタンプ）などを、それぞれ別個に維持することができる。したがって、リンク消滅部２１６によるリンク消滅処理を、各リンクＹ１２，Ｙ２２について独立して行うことができる。
【００６６】
なお、グラフ合成の際には、ノード対Ｎ５１，５２の間のリンクを１本のリンクに合成して集約してもよい。この場合、合成されたノード対間のリンクの数が増加せず、グラフデータのデータ量の増大を抑制できる。
【００６７】
図５は、本実施形態の関係性グラフデータベースシステム１が生成したグラフデータＧ２と、他のシステムによって生成されたグラフデータＧ３と、を合成したグラフデータＧ４を示している。このグラフ合成も、両グラフデータＧ２，Ｇ３において共通するノードを合成することで行われる。
【００６８】
［３．グラフデータからのノード抽出］
図２に示すように、グラフデータからのノードの抽出に関する処理を行う第２処理部２２は、基準ノード選択情報受付部２２１と、基準ノード選択部２２２と、抽出部２２３と、表示制御部２２４と、を備えている。
【００６９】
基準ノード選択情報受付部２２１は、端末装置６から、基準ノードとして選択されたノードを示す選択情報を受け付ける。表示制御部２２４は、端末装置６から、グラフのノード抽出要求を受けると、データベース３に保存されているグラフデータの一部又は全部を端末装置６の表示画面に表示させるための表示情報を、端末装置６へ送信する。端末装置６のユーザは、表示されたグラフデータのノードの中から、基準ノードとなる一又は複数のノードを選択する。すると、端末装置６において、基準ノードが選択されると、基準ノードを示す選択情報が、処理サーバ２に送信される。
【００７０】
基準ノード選択部２２２は、基準ノード選択情報受付部２２１が選択情報を端末装置６から受け付けると、データベース３に記憶されているグラフデータのノードの中から、選択情報が示す位置又は複数のノードを基準ノードとして選択する。
【００７１】
抽出部２２３は、基準ノードからみた中心性（詳細は後述）に基づいて、データベース３に保存されているグラフデータからノードを抽出する。
【００７２】
表示制御部２２４は、抽出されたノードを、当該ノードを接続するリンクとともに表示させる表示情報を、ノード抽出要求を発信した端末装置６に対して送信する。これにより、端末装置６は、抽出されたノードを画面表示することができる。
【００７３】
図６及び図７は、ノード抽出処理の第１例を示している。
第１の例においては、基準ノード選択部２２２によって複数の基準ノードが選択されると（ステップＳ１１）、複数の基準ノードに基づいて、中心ノードが選択される（ステップＳ１２）。例えば、図７に示すグラフデータＧ（図７において、丸印がノードを示し、直線がリンクを示す）において、２つの基準ノードが選択されると、それら２つの基準ノードそれぞれからの経路長の総和が最も小さくなるノードが中心ノードとして選択される。
【００７４】
中心ノードを選択するには、まず、グラフデータＧにおいて、２つの基準ノードの最短経路となるグラフ（最短経路グラフ）だけを考える。そして、抽出部２２３は、最短経路グラフにおける各ノード（対象ノード）について、他の対象ノードそれぞれからの経路長の総和を算出する。そして、最短経路グラフにおける各ノード（対象ノード）のうち、前記経路長の総和が最も小さくなるノードが中心ノードとして特定される。なお、基準ノードが一つの場合は、基準ノードが中心ノードとして特定される。
また、中心ノードを選択するための経路長の総和の算出の対象となるノード（対象ノード）としては、最短経路グラフ上のノードに限らず、基準ノードからのリンク数が所定の値以内のノード、又は、基準ノードからの経路長が所定の値以内のノードなど、基準ノード近傍のノードとしてもよい。
【００７５】
続いて、抽出部２２３は、中心ノードからの経路長が閾値以下（例えば、経路長が３以下）のノードを抽出する。例えば、中心ノードからの経路長が３以下のノードを抽出する場合、図７に示す抽出範囲内のノードが抽出される。
【００７６】
中心ノードは、複数の基準ノードから見て中心にあり、抽出されたノード群において中心的な存在となる。したがって、中心ノードからの経路長が小さいほど、複数の基準ノードの組み合わせに対して関係性が高いノードである。
【００７７】
表示制御部２２４は、抽出されたノードに対応する表示情報を生成して、端末装置６へ送信する（ステップＳ１１）。端末装置６へ送信される表示情報は、抽出されたノードを接続するリンク及びリンク情報のほか、抽出された各ノードと中心ノードとの間の経路長を示す情報及び抽出された各ノードと基準ノードとの間の経路長を示す情報も含まれる。
【００７８】
端末装置６は、表示情報に基づいて、抽出されたノードの画面表示を行う。図８に示すように、端末装置６は、基準ノード及び／又は中心ノードを、抽出された他のノードとは識別可能に強調表示する。また、基準ノード及び中心ノードも、両者を識別可能に表示される。中心ノードを他のノードから識別可能に強調表示することで、ユーザは、中心ノードが中心性の高いノードであることを認識できる。また、中心ノード以外の他のノードそれぞれについても、中心性を示す値に基づいて、中心性の高さを識別可能に表示してもよい。
また、表示されたリンクが、端末装置６の操作によって指定されると、指定されたリンクのリンク情報が表示される。
【００７９】
抽出結果であるノードとリンクが端末装置６に表示されているときに、ユーザによる端末装置６の操作によって、データベース３内の各リンク距離を長くしたり、短くしたりすることができる。つまり、端末装置６は、表示されているリンクのリンク距離を変更する操作をユーザから受け付けると、変更後のリンク距離を処理サーバ２に送信する。すると、処理サーバ２は、データベース３を検索して、リンク距離が変更されたリンクのリンク距離を抽出し、当該リンク距離を変更後のリンク距離に書き換えて、データベース３に保存する。これにより、リンク距離について、ユーザからのフィードバックを反映でき、ユーザが表示されたリンク距離（ノード間の関係性）と自分の感覚とのギャップを感じた時に補正を行うことができる。
【００８０】
さらに、端末装置６は、抽出された各ノードを、複数の基準ノードのうち、経路長が最も小さくなる基準ノードの付近に集中させて表示させる。これにより、抽出された各ノードは、いずれかの基準ノードの近くにまとめて表示されるため、各ノードと基準ノードとの関係が直感的にわかりやすくなる。なお、中心ノード及び各基準ノードからの距離が等しくなるノードについては、基準ノードの付近以外の場所、例えば、複数の基準ノードの中間位置、に表示される。
【００８１】
このように、表示情報に、抽出された各ノードと基準ノードとの間の経路長を示す情報も含まれていることで、その情報を用いて、抽出された各ノードと基準ノードとの関係性の強さをユーザに分かり易く提示することが可能となる。
また、抽出された各ノードと中心ノードとの間の経路長（中心性）を示す情報を用いることで、抽出された各ノードと中心ノードとの関係性の強さをユーザに分かり易く提示することもできる。
【００８２】
なお、ここでは、経路長の計算の際には、リンク１本のリンク距離＝１とし、経路上のリンクの数×リンク距離の演算によって経路長が計算される。また、ノード対に複数のリンクが存在する場合、ノード対間のリンク距離＝１／ノード対間のリンク本数、というように、ノード対間のリンクの数が多いほどリンク距離が小さいものとして経路長を算出する。
【００８３】
ただし、１本のリンクのリンク距離は、各リンクで同じである必要はなく、リンク毎に異なっていても良い。例えば、リンク消滅部（リンク距離変更部）２１６によって、リンク距離を変更する場合には、生成時期の異なるリンクのリンク距離は異なるものとなる。
また、リンク距離は、接続されるノード同士の関係性に応じて異なっていてもよい。例えば、紺色、青色がノードデータとして存在した場合、それらは相互に強い正の関係性をもっていると考えられる一方、青色と赤色がノードデータとして存在した場合、それらは相互に強い負の関係性をもっていると考えられる。部分グラフ生成部２１５では、接続されるノード同士の関係性に応じて、当該ノード同士を接続するリンクのリンク距離を異ならせることができる。
【００８４】
図９及び図１０は、ノード抽出処理の第２例を示している。
第２の例においては、基準ノード選択部２２２によって複数の基準ノードが選択されると（ステップＳ２１）、抽出部２２３は、複数の基準ノードからの経路長（最短経路上のリンク長又はホップ数の総和）が所定値以下であるノードからなる局所グラフデータを特定する（ステップＳ２２）。
【００８５】
例えば、図１０では、第１基準ノードからの経路長（ここでは最短経路上のホップ数の総和）が３以下であるノードからなる第１局所グラフデータＬ１が図示のように特定され、第２基準ノードからの経路長（リンク数）が３以下であるノードからなる第２局所グラフデータＬ２が図示のように特定される。そして、第１及び第２局所グラフデータＬ１，Ｌ２を合わせたものを、複数の基準ノードに対応する局所グラフデータとして考える。
【００８６】
続いて、抽出部２２３は、局所グラフデータＬにおいて、２つの基準ノードの最短経路となるグラフ（最短経路グラフ）を抽出する。第２例では、グラフデータ全体ではなく、より小さい局所グラフデータＬから最短経路グラフを抽出するため、最短経路探索のための処理負荷を低減することができる。第１例のように、最短経路グラフから中心ノードを求めても良いが、第２例では、局所ネットワークグラフデータＬの各ノードと、最短経路グラフ上の各ノードとの経路長の平均値を求める。
【００８７】
つまり、抽出部２２３は、局所ネットワークグラフデータＬのあるノードについて、最短経路グラフ上の各ノードとの経路長の平均値を求める処理を行う。そして、当該処理を、局所ネットワークグラフデータＬのすべてのノードについて行う。当該処理によって求めた経路長の平均値は、局所グラフデータにおける中心性を示しており、当該平均値が最も小さいノードは、局所ネットワークグラフデータＬの中心にあるノード（中心ノード）といえる。この中心ノードは、複数の基準ノードの組み合わせに対して最も関連するノードである。また、当該処理によって求めた経路長の平均値が小さいほど、複数の基準ノードの組み合わせに対して関係性が高いノードである。
【００８８】
抽出部２２３は、当該処理によって求めた経路長の平均値が所定値以下のノードを抽出する（ステップＳ２３）。これにより、局所グラフデータＬのあるノードのうち、複数の基準ノードの組み合わせに対して比較的関係性が高いノードが抽出されることになる。
なお、抽出部２２３は、局所ネットワークグラフデータＬのあるノードについて、各ノードとの経路長の平均値を求める処理を行うのに代えて、次のような処理で平均値（中心性）を求めても良い。例えば、抽出部２２３は、局所ネットワークグラフデータＬのあるノードについて、基準ノードからの経路長（最短経路上のリンク長あるいはホップ数の総和）が所定の値以内のノードなど、基準ノード近傍の各ノードとの経路長の平均値を中心性として求めても良い。
【００８９】
ノードが抽出されると、第１例と同様に、表示情報が生成され、端末装置６へ送信される（ステップＳ２２）。
【００９０】
以上のように、本実施形態では、複数の基準ノードの組み合わせに関連するノードの抽出の際に、複数の基準ノードそれぞれに関連するノードの集合の論理和又は論理積をとるのではなく、複数の基準ノードからみた中心性（第１例の中心ノードからの経路長、第２例の経路長の平均値）に基づいて、ノードを抽出する。
【００９１】
つまり、本実施形態では、グラフデータ全体におけるグラフ中心ではなく、複数の基準ノードからみて中心に位置するノード（中心ノード）が最も優先して抽出される。したがって、関係性のあるノードが大量に抽出されても、中心ノードからの経路長などに基づいて、関係性の高いものを優先して表示することが可能である。
【００９２】
［４．クラスタリング］
図１１は、一部がクラスタリングされたグラフデータの表示例を示している。処理サーバ２は、データベース３に保存されているグラフデータに対して、データクラスタリングアルゴリズムを適用して、ノードのクラスタリングを行うクラスタリング処理を行うことができる。クラスタリング処理により、複数のノードがクラスター化されたクラスターノードとなる。クラスタリング処理を行うと、例えば、商品の分類を階層的に考えた場合、一つの大分類の下位に属する小分類における商品名を示す複数のノードが、当該大分類における商品名を示す一つのクラスターノードに統合されることになる。
【００９３】
クラスターノードは、基準ノードを選択するため、又は、抽出ノードを選択するために、グラフデータを端末装置６に表示する際において表示可能である。また、基準ノードを選択するためにクラスターノードが端末装置６に表示されると、端末装置６においては、クラスターノードを、複数の基準ノードのうちの少なくともいずれか一つとして選択可能である。
【００９４】
処理サーバ２では、クラスターノードが基準ノードとして選択されると、クラスターノードを通常のノードとみなして、前述のノード抽出処理を実行する。
【００９５】
クラスターノードが基準ノードとして選択可能であることにより、個々のノードの上位概念を基準ノードとして特定できることになり、ユーザの関心が、個々のノードではなく、それらの上位概念にある場合に有利である。
【００９６】
［５．付記］
なお、上記において開示した事項は、例示であって、本発明を限定するものではなく、様々な変形が可能である。
【符号の説明】
【００９７】
１  関係性グラフデータベースシステム
２  処理サーバ
３  データベース
４  記憶部
５  コンピュータネットワーク
６  端末装置
２１  第１処理部
２２  第２処理部
２１１  情報取得部
２１２  ノード生成部
２１３  判定部
２１４  部分グラフ生成部
２１５  グラフ生成部
２１６  リンク消滅部
２２１  基準ノード選択情報受付部
２２２  基準ノード選択部
２２３  抽出部
２２４  表示制御部
【図１】
0005170481.tif 000002
【図２】
0005170481.tif 000003
【図３】
0005170481.tif 000004
【図４】
0005170481.tif 000005
【図５】
0005170481.tif 000006
【図６】
0005170481.tif 000007
【図７】
0005170481.tif 000008
【図８】
0005170481.tif 000009
【図９】
0005170481.tif 000010
【図１０】
0005170481.tif 000011
【図１１】
0005170481.tif 000012