(57)【要約】【課題】人および対象物をとりまく直接的および間接的なつながりの深さを元に、未知の人や対象物を探し出すことのできるグラフデータを生成する。【解決手段】ノード抽出部は、指定された中心ノードからのリンクの段階数がＪ（Ｊは整数であり、２≦Ｊ）であるＪ次リンクノードを抽出する。スコア算出部は、中心ノードからのリンクの段階数がＫ（Ｋは整数であり、０≦Ｋ＜Ｊ）であるＫ次リンクノードからＪ次リンクノードの各々までの経路数に基づいて、Ｊ次リンクノードの各々のスコアを算出し、算出されたスコアに基づいて、前記ノード抽出部によって抽出された前記Ｊ次リンクノードの一部を選択する。出力部は、未出力ノード選択部によって抽出されたＪ次リンクノードと、これらＪ次リンクノードへのリンクを有するＫ次リンクノードと、中心ノードとを含むグラフデータを生成して出力する。【選択図】図９
2012242859.tif 000002
【特許請求の範囲】
【請求項１】
ノードとノードとの関係を表すデータを記憶するノード間関係テーブル記憶部と、
前記ノードがグラフデータの一部として出力された出力日時のデータをノード毎に記憶する履歴テーブル記憶部と、
前記ノード間関係テーブル記憶部を参照することにより、指定された中心ノードからのリンクの段階数がＪ（Ｊは整数であり、２≦Ｊ）であるＪ次リンクノードを抽出するノード抽出部と、
前記ノード間関係テーブル記憶部を参照することにより、前記中心ノードからのリンクの段階数がＫ（Ｋは整数であり、０≦Ｋ＜Ｊ）であるＫ次リンクノードから前記Ｊ次リンクノードの各々までの経路数に基づいて、前記Ｊ次リンクノードの各々のスコアを算出し、算出されたスコアに基づいて、前記ノード抽出部によって抽出された前記Ｊ次リンクノードの一部を選択するスコア算出部と、
前記履歴テーブル記憶部に記憶されたデータに基づき、前記スコア算出部によって選択された前記Ｊ次リンクノードのうち、未出力であるＪ次リンクノードを選択する未出力ノード選択部と、
前記ノード間関係テーブル記憶部を参照することにより、前記未出力ノード選択部によって抽出された前記Ｊ次リンクノードと、これら前記Ｊ次リンクノードへのリンクを有する前記Ｋ次リンクノードと、前記中心ノードとを含むグラフデータを生成して出力する出力部と、
を具備することを特徴とするグラフ生成装置。
【請求項２】
請求項１に記載のグラフ生成装置であって、
ノード毎に前記ノードが更新された更新日時のデータを記憶するノード属性テーブル記憶部をさらに具備し、
前記未出力ノード選択部は、前記ノード属性テーブル記憶部を参照することにより、前記スコア算出部によって選択された前記Ｊ次リンクノードのうち未出力であるＪ次リンクノードを更新日時の新しい順に最大でＭ個（Ｍは所定の整数）まで選択するものであり、
前記未出力ノード選択部によって選択された前記Ｊ次リンクノードがＭ個に満たない場合に、前記スコア算出部によって選択された前記Ｊ次リンクノードのうち、過去に出力した履歴のあるノードを、前記未出力ノード選択部によって選択された個数と合わせてＭ個になるまで抽出する出力済ノード選択部をさらに具備し、
前記出力部は、前記未出力ノード選択部によって抽出された前記Ｊ次リンクノードに加えて前記出力済ノード選択部によって抽出された前記Ｊ次リンクノードをも用いて前記グラフデータを出力する、
ことを特徴とするグラフ生成装置。
【請求項３】
請求項２に記載のグラフ生成装置であって、
出力済ノード選択部は、前記履歴テーブル記憶部を参照することにより、前回出力日時の古い順に、過去に出力した履歴のあるノードを抽出する、
ことを特徴とするグラフ生成装置。
【請求項４】
請求項１から３までのいずれか一項に記載のグラフ生成装置であって、
前記ノードは、ユーザーに関するノードと、ユーザー以外の対象物に関するノードとを含み、前記ノード間関係テーブル記憶部は、ユーザー相互間の関係を表すデータと、対象物相互間の関係を表すデータと、ユーザーと対象物との間の関係を表すデータと、を記憶する、
ことを特徴とするグラフ生成装置。
【請求項５】
ノードとノードとの関係を表すデータを記憶するノード間関係テーブル記憶部と、
前記ノードがグラフデータの一部として出力された出力日時のデータをノード毎に記憶する履歴テーブル記憶部と、
前記ノード間関係テーブル記憶部を参照することにより、指定された中心ノードからのリンクの段階数がＪ（Ｊは整数であり、２≦Ｊ）であるＪ次リンクノードを抽出するノード抽出部と、
前記ノード間関係テーブル記憶部を参照することにより、前記中心ノードからのリンクの段階数がＫ（Ｋは整数であり、０≦Ｋ＜Ｊ）であるＫ次リンクノードから前記Ｊ次リンクノードの各々までの経路数に基づいて、前記Ｊ次リンクノードの各々のスコアを算出し、算出されたスコアに基づいて、前記ノード抽出部によって抽出された前記Ｊ次リンクノードの一部を選択するスコア算出部と、
前記履歴テーブル記憶部に記憶されたデータに基づき、前記スコア算出部によって選択された前記Ｊ次リンクノードのうち、未出力であるＪ次リンクノードを選択する未出力ノード選択部と、
前記ノード間関係テーブル記憶部を参照することにより、前記未出力ノード選択部によって抽出された前記Ｊ次リンクノードと、これら前記Ｊ次リンクノードへのリンクを有する前記Ｋ次リンクノードと、前記中心ノードとを含むグラフデータを生成して出力する出力部と、
を具備するグラフ生成装置としてコンピュータを機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフ構造を表すデータを生成するグラフ生成装置と、そのプログラムに関する。
【背景技術】
【０００２】
特許文献１には、ネットワークサービスを利用する利用者間の関係をソーシャルグラフとして提供するサーバの技術が記載されている（特に、図１、図２、段落０００８、段落０００９など）。これにより、利用者間の関係をビジュアルな形態で一覧することができた。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１０−１２８７１３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来のソーシャルグラフでは人と人とのつながりがわかりやすく表現されているものの、そこから、人（自分である場合を含む）が興味を持つ話題やコミュニティやコンテンツ等を探し出し到達することは困難であった。
また、ある人（自分である場合を含む）との直接的なつながりだけでなく、その人を取り巻く間接的なつながりと、それらのつながりの濃さから、その人が興味を持つ可能性の高い未知の話題やコミュニティやコンテンツ等を探し出したいという要求に応じることは困難であった。
【０００５】
本発明は、上記の課題認識に基づいて行なわれたものであり、人と人との間の関係だけではなく、話題やコミュニティやコンテンツ等（これらを、「対象物」と総称する）を含んだ関係を表すグラフデータを生成することのできるグラフ生成装置およびプログラムを提供しようとするものである。
【０００６】
また、本発明は、人および対象物をとりまく直接的および間接的なつながりの濃さを元に、未知の人や対象物を探し出すことのできるグラフデータを生成するグラフ生成装置およびプログラムを提供しようとするものである。
【課題を解決するための手段】
【０００７】
［１］上記の課題を解決するため、本発明の一態様によるグラフ生成装置は、ノードとノードとの関係を表すデータを記憶するノード間関係テーブル記憶部と、前記ノードがグラフデータの一部として出力された出力日時のデータをノード毎に記憶する履歴テーブル記憶部と、前記ノード間関係テーブル記憶部を参照することにより、指定された中心ノードからのリンクの段階数がＪ（Ｊは整数であり、２≦Ｊ）であるＪ次リンクノードを抽出するノード抽出部と、前記ノード間関係テーブル記憶部を参照することにより、前記中心ノードからのリンクの段階数がＫ（Ｋは整数であり、０≦Ｋ＜Ｊ）であるＫ次リンクノードから前記Ｊ次リンクノードの各々までの経路数に基づいて、前記Ｊ次リンクノードの各々のスコアを算出し、算出されたスコアに基づいて、前記ノード抽出部によって抽出された前記Ｊ次リンクノードの一部を選択するスコア算出部と、前記履歴テーブル記憶部に記憶されたデータに基づき、前記スコア算出部によって選択された前記Ｊ次リンクノードのうち、未出力であるＪ次リンクノードを選択する未出力ノード選択部と、前記ノード間関係テーブル記憶部を参照することにより、前記未出力ノード選択部によって抽出された前記Ｊ次リンクノードと、これら前記Ｊ次リンクノードへのリンクを有する前記Ｋ次リンクノードと、前記中心ノードとを含むグラフデータを生成して出力する出力部とを具備する。
【０００８】
また、本発明の一態様は、上記のグラフ生成装置において、Ｊ＝２且つＫ＝１とする。また、未出力ノード選択部は、最終更新日時の新しい順に最大でＭ個まで、未出力のＪ次（二次）リンクノードを抽出する。
【０００９】
これらの構成によれば、ノード抽出部は中心ノードからＪ次（二次）のリンクノードを抽出する。そして、スコア算出部は、抽出されたＪ次（二次）リンクノードのそれぞれについて、Ｋ次（一次）リンクノードからの経路数（リンク数）に基づいてスコアを算出し、そのスコアに基づいて、Ｊ次（二次）リンクノードを選択する。つまり、中心ノードからの段階数の比較的多い（関係が遠い）Ｊ次（二次）リンクノードを対象としたグラフデータを生成できる。また、そのようなＪ次（二次）リンクノードの中で、中心ノードからの段階数の比較的少ない（関係が近い）Ｋ次（一次）リンクノードからの経路数に基づく選択が行われる。つまり、中心ノードから関係の近いＫ次（一次）リンクノードとの関係が深いと推定されるＪ次（二次）リンクノードを選択して、グラフデータを生成できる。つまり、グラフ生成装置は、中心ノードとの関係の度合いが深いが、未知であるノードの情報をユーザーに対して提供する。ユーザーにとっては、中心ノードと興味の重なる未知のノードにたどり着くことが容易になる。
【００１０】
また、これらの構成によれば、未出力ノード選択部は、スコア算出部によって選択されたＪ次（二次）リンクノードのうち、グラフデータとして未出力であるＪ次リンクノードを選択する。つまり、グラフ生成装置は、ユーザーにとって興味深いと推定され、且つ未知のＪ次（二次）リンクノードを優先的に含んだグラフデータを生成する。
【００１１】
［２］また、本発明の一態様によるグラフ生成装置は、上記のグラフ生成装置において、ノード毎に前記ノードが更新された更新日時のデータを記憶するノード属性テーブル記憶部をさらに具備し、前記未出力ノード選択部は、前記ノード属性テーブル記憶部を参照することにより、前記スコア算出部によって選択された前記Ｊ次リンクノードのうち未出力であるＪ次リンクノードを更新日時の新しい順に最大でＭ個（Ｍは所定の整数）まで選択するものであり、前記未出力ノード選択部によって選択された前記Ｊ次リンクノードがＭ個に満たない場合に、前記スコア算出部によって選択された前記Ｊ次リンクノードのうち、過去に出力した履歴のあるノードを、前記未出力ノード選択部によって選択された個数と合わせてＭ個になるまで抽出する出力済ノード選択部をさらに具備し、前記出力部は、前記未出力ノード選択部によって抽出された前記Ｊ次リンクノードに加えて前記出力済ノード選択部によって抽出された前記Ｊ次リンクノードをも用いて前記グラフデータを出力することを特徴とする。
【００１２】
［３］また、本発明の一態様によるグラフ生成装置は、上記のグラフ生成装置において、出力済ノード選択部は、前記履歴テーブル記憶部を参照することにより、前回出力日時の古い順に、過去に出力した履歴のあるノードを抽出することを特徴とする。
【００１３】
この構成により、出力済ノード選択部は、過去に出力した履歴のあるノードを、前回出力日時の古い順に選択する。つまり、出力済ノード選択部は、最近出力したことのある出力済ノードよりも、過去に出力したことのある出力済ノードを優先して選択する。そして、グラフ生成装置は、そのように選択されたＪ次（二次）リンクノードを含むグラフデータを生成する。
【００１４】
［４］また、本発明の一態様によるグラフ生成装置は、上記のグラフ生成装置において、前記ノードは、ユーザーに関するノードと、ユーザー以外の対象物に関するノードとを含み、前記ノード間関係テーブル記憶部は、ユーザー相互間の関係を表すデータと、対象物相互間の関係を表すデータと、ユーザーと対象物との間の関係を表すデータと、を記憶することを特徴とする。
【００１５】
この構成により、グラフ生成装置は、ユーザーおよび対象物という複数種類のノードを含んで構成されるグラフデータを出力する。これによりユーザーは、ユーザーのみをノードとするグラフではなく、ユーザーと対象物との関係をノードとするグラフを得ることができる。
【００１６】
［５］また、本発明の一態様は、ノードとノードとの関係を表すデータを記憶するノード間関係テーブル記憶部と、前記ノードがグラフデータの一部として出力された出力日時のデータをノード毎に記憶する履歴テーブル記憶部と、前記ノード間関係テーブル記憶部を参照することにより、指定された中心ノードからのリンクの段階数がＪ（Ｊは整数であり、２≦Ｊ）であるＪ次リンクノードを抽出するノード抽出部と、前記ノード間関係テーブル記憶部を参照することにより、前記中心ノードからのリンクの段階数がＫ（Ｋは整数であり、０≦Ｋ＜Ｊ）であるＫ次リンクノードから前記Ｊ次リンクノードの各々までの経路数に基づいて、前記Ｊ次リンクノードの各々のスコアを算出し、算出されたスコアに基づいて、前記ノード抽出部によって抽出された前記Ｊ次リンクノードの一部を選択するスコア算出部と、前記履歴テーブル記憶部に記憶されたデータに基づき、前記スコア算出部によって選択された前記Ｊ次リンクノードのうち、未出力であるＪ次リンクノードを選択する未出力ノード選択部と、前記ノード間関係テーブル記憶部を参照することにより、前記未出力ノード選択部によって抽出された前記Ｊ次リンクノードと、これら前記Ｊ次リンクノードへのリンクを有する前記Ｋ次リンクノードと、前記中心ノードとを含むグラフデータを生成して出力する出力部とを具備するグラフ生成装置としてコンピュータを機能させるプログラムである。
【発明の効果】
【００１７】
本発明によれば、ユーザーにとっては、グラフ生成装置が生成するグラフデータを参照することにより、中心ノード（例えば、自分）と興味の重なる未知のノードにたどり着くことが容易になる。
また、本発明によれば、グラフ生成装置は、ユーザー間の関係のみを表すグラフではなく、ユーザーと対象物とを含んだ関係を表すグラフを出力できる。
【図面の簡単な説明】
【００１８】
【図１】本発明の一実施形態によるグラフ生成装置の機能構成を示したブロック図である。
【図２】同実施形態によるグラフ生成装置を含んで構成されるネットワークシステムを示す概略図である。
【図３】同実施形態によるユーザー属性テーブル記憶部が記憶するテーブルの構成を示す概略図である。
【図４】同実施形態による番組属性テーブル記憶部が記憶するテーブルの構成を示す概略図である。
【図５】同実施形態によるユーザー相互間関係テーブル記憶部が記憶するテーブルの構成を示す概略図である。
【図６】同実施形態によるユーザー番組間関係テーブル記憶部が記憶するテーブルの構成を示す概略図である。
【図７】同実施形態による番組相互間関係テーブル記憶部が記憶するテーブルの構成を示す概略図である。
【図８】同実施形態による履歴テーブル記憶部が記憶するテーブルの構成を示す概略図である。
【図９】同実施形態によるグラフ算出部の、より詳細な機能構成を示すブロック図である。
【図１０】同実施形態によるグラフ算出部がグラフデータを生成する処理の手順を示すフローチャートである。
【図１１】同実施形態によるグラフ生成装置によって出力されるグラフデータの例を示す概略図である。
【図１２】同実施形態によるグラフ生成装置が出力するグラフデータを元に表示した画面の例を示す概略図である。
【発明を実施するための形態】
【００１９】
次に、本発明の一実施形態について、図面を参照しながら説明する。
図１は、同実施形態によるグラフ生成装置の機能構成を示すブロック図である。図示するように、グラフ生成装置１は、グラフ算出部１０と、パラメータ記憶部１１と、グラフデータ出力部１２と、ノード間関係テーブル記憶部３０と、ノード属性テーブル記憶部４０と、履歴テーブル記憶部５０とを含んで構成される。また、ノード間関係テーブル記憶部は、ユーザー相互間関係テーブル記憶部３１と、ユーザー番組間関係テーブル記憶部３２と、番組相互間関係テーブル記憶部３３とを含む。また、ノード属性テーブル記憶部４０は、ユーザー属性テーブル記憶部４１と、番組属性テーブル記憶部４２とを含む。
ノード間関係テーブル記憶部３０と、ノード属性テーブル記憶部４０と、履歴テーブル記憶部５０とは、磁気ハードディスク（ＨＤＤ）や半導体メモリ（半導体ディスク装置（ＳＤＤ）を含む）を用いて実現される。
【００２０】
グラフ算出部１０は、端末装置等からの要求に基づき、各テーブルに記憶されているデータを参照しながら、指定されたノードを中心とするグラフデータを算出する。グラフ算出部１０の処理の詳細については、後述する。
パラメータ記憶部１１は、グラフ算出部１０が用いるパラメータの値を記憶する。具体的には、後述する値Ｊ，Ｋ，Ｌ，Ｍ，Ｎの全部または一部を記憶する。
グラフデータ出力部１２は、グラフ算出部１０によって算出（生成）されたデータを、要求元（端末装置等）に対して出力する。
【００２１】
ノード間関係テーブル記憶部３０は、ノードとノードとの関係を表すデータを記憶する。ここで、ノードは、ユーザーまたは番組のいずれかに対応する。また、ノード間の関係は、グラフにおけるリンクに対応する。ユーザー相互間関係テーブル記憶部３１は、ユーザーとユーザーとの間の関係を表すデータを記憶する。ユーザー番組間関係テーブル記憶部３２とは、ユーザーと番組との間の関係を表すデータを記憶する。番組相互間関係テーブル記憶部３３は、番組と番組との間の関係を表すデータを記憶する。ノード間の関係をあらわすデータについては後で図面を参照しながら説明する。
【００２２】
ノード属性テーブル記憶部４０は、ノード毎の属性データを記憶する。このノード属性データには、ノードが更新された更新日時のデータを含む。ユーザー属性テーブル記憶部４１は、ユーザーノードの属性を記憶するものである。番組属性テーブル記憶部４２は、番組ノードの属性を記憶するものである。
履歴テーブル記憶部５０は、ノードがグラフデータの一部として出力された出力日時のデータをノード毎に記憶する。履歴テーブル記憶部５０が、あるノートに関して、出力要求元のユーザー毎に出力日時のデータを保持するようにしても良い。
【００２３】
図２は、グラフ生成装置１を含んで構成されるネットワークシステムの構成を示す概略図である。図示するように、本システムは、グラフ生成装置１と、ソーシャルネットワーキングサーバ２と、複数の端末装置３とを含んでおり、これらが通信ネットワークを介して相互に通信できるように構成されている。
【００２４】
ソーシャルネットワーキングサーバ２は、多数の端末装置３に対してソーシャルネットワーキングサービス（ＳＮＳ）の機能を提供するサーバ装置である。端末装置３は、具体的には、パーソナルコンピュータや携帯型端末装置である。端末装置３は、通信ネットワークを介して、ソーシャルネットワーキングサーバ２にログインし、所定のユーザーとしてＳＮＳの機能を利用する。本実施形態では、ソーシャルネットワーキングサーバ２は、ビデオオンデマンド（ＶＯＤ）の機能をも提供する。そして、ソーシャルネットワーキングサーバ２は、ユーザーの属性情報や、ＶＯＤサービスに含まれる番組の属性情報を内部に管理する。さらに、ソーシャルネットワーキングサーバ２は、ユーザー相互間の関係（例えば、友人関係）や、ユーザーと番組との間の関係（例えば、あるユーザーがある番組を「お気に入り」として登録している関係）や、番組相互間の関係（例えば、関連番組の関係や、シリーズもの番組の関係）をあらわすデータを管理する。
【００２５】
前述のグラフ生成装置１におけるノード間関係テーブル記憶部３０やノード属性テーブル記憶部４０は、ソーシャルネットワーキングサーバ２が管理する上記のデータの複製を記憶する。あるいは、ノード間関係テーブル記憶部３０やノード属性テーブル記憶部４０は、ソーシャルネットワーキングサーバ２との間でデータを共有する。
【００２６】
端末装置３は、ユーザーの操作に応じて、グラフデータの生成処理をグラフ生成装置１に対して要求する信号を送信する。グラフ生成装置１は、端末装置３からの要求に応じて、グラフデータを生成し、端末装置３に返送する。端末装置３は、グラフ生成装置１から受信したグラフデータを用いて、グラフ（ノードとリンク）をグラフィカルに表現した画面を生成し、自身の画面に表示する。グラフの表示の例については、後述する。
【００２７】
次に、グラフ生成装置１が使用する主要なデータについて説明する。ここで、グラフ生成装置が生成するグラフデータの構成要素は、ノードとリンクである。リンクは、ノードとノードとを結ぶものであり、片方向リンクまたは双方向リンクのいずれかである。ノードは、主体に対応する。つまり、リンクは、主体感の関係を表す。主体は、人または対象物である。人は、例えば、ソーシャルネットワーキングサービスのユーザーである。対象物は、例えば、番組（ＶＯＤサービスのコンテンツ）や、ソーシャルネットワーキングサービスにおけるコミュニティなどであり、人の関心の対象となり得る物である。本実施形態では、対象物は番組である。
【００２８】
図３は、ユーザー属性テーブル記憶部４１が記憶するテーブルの構成を示す概略図である。図示するように、ユーザー属性テーブルは、リレーショナルデータを保持するものであり、ユーザー識別情報、最終更新日時、ユーザー名、アイコン画像の各項目を含む。ユーザー属性テーブルにおける各行のデータが、各ユーザーに対応する。ユーザー識別情報は、ユーザーを一意に識別するデータである。最終更新日時は、当該ユーザーに関する関係（関係の詳細については後述）が最後に更新された日時のデータであり、例えば「ＹＹＹＹ／ＭＭ／ＤＤ  ｈｈ：ｍｍ：ｓｓ」（年月日・時分秒）の形式である。当該ユーザーに関する関係の更新とは、当該ユーザーを一端あるいは他端のいずれかに含む関係のデータが、追加されたり削除されたり書き換えられたりする操作である。ユーザー名およびアイコン画像は、生成したグラフを携帯端末等に表示する際にも用いられるデータである。
【００２９】
図４は、番組属性テーブル記憶部４２が記憶するテーブルの構成を示す概略図である。図示するように、番組属性テーブルは、リレーショナルデータを保持するものであり、番組識別情報、最終更新日時、番組名、サムネイル画像、コンテンツ所在の各項目を含む。番組属性テーブルにおける各行のデータが、各番組に対応する。番組識別情報は、ＶＯＤサービスが提供する番組を一意に識別するデータである。最終更新日時は、ユーザー属性テーブルにおける最終更新日時と同様の意味および形式を有するデータであり、当該番組に関する関係が最後に更新された日時を表す。番組名およびサムネイル画像は、生成したグラフを携帯端末等に表示する際にも用いられるデータである。コンテンツ所在は、通信ネットワーク経由で当該番組のコンテンツにアクセスするための所在情報（ＵＲＬ（Uniform Resource Locator）等）である。
【００３０】
図５は、ユーザー相互間関係テーブル記憶部３１が記憶するテーブルの構成を示す概略図である。図示するように、ユーザー相互間関係テーブルは、リレーショナルデータを保持するものであり、ユーザー識別情報Ａおよびユーザー識別情報Ｂの項目を有する。これらのユーザー識別情報は、ユーザー属性テーブルにおけるユーザー識別情報と同様のものである。ユーザー相互間関係テーブルの各行が、ユーザー間の友人関係を表す。ユーザー間の関係が、後述するグラフにおけるリンクに対応する。
【００３１】
なお、本実施形態において、ユーザー間の関係は、双方向である。即ち、ユーザーＡがユーザーＢに対して友人関係にあり、その関係を表す行がユーザー相互間関係テーブルに存在するとき、ユーザーＢがユーザーＡに対して友人関係であるという逆方向の関係も成り立つ。本実施形態の変形例としては、ユーザー間の関係を片方向としても良い。
【００３２】
図６は、ユーザー番組間関係テーブル記憶部３２が記憶するテーブルの構成を示す概略図である。図示するように、ユーザー番組間関係テーブルは、リレーショナルデータを保持するものであり、ユーザー識別情報および番組識別情報の項目を有する。これらの識別情報は、それぞれ、ユーザー属性テーブルおよび番組属性情報における識別情報と同様のものである。ユーザー番組間関係テーブルの各行が、ユーザーによる番組への「お気に入り」の関係を表す。例えば、ユーザー番組間関係テーブルにおいて、ユーザー１に対応するユーザー識別情報と番組Ｃに対応する番組識別情報を保持する行が存在するとき、ユーザー１が番組Ｃを「お気に入り」として登録していることを表す。ユーザーと番組と間の関係が、後述するグラフにおけるリンクに対応する。
なお、本実施形態において、ユーザーと番組との関係は、片方向である。
【００３３】
図７は、番組相互間関係テーブル記憶部３３が記憶するテーブルの構成を示す概略図である。図示するように、番組相互間関係テーブルは、リレーショナルデータを保持するものであり、番組識別情報Ａおよび番組識別情報Ｂの項目を有する。これらの番組識別情報は、番組属性テーブルにおける番組識別情報と同様のものである。番組相互間関係テーブルの各行が、番組間の関係を表す。番組間の関係とは、例えば、関連番組、シリーズもの番組などの関係である。ユーザー間の関係が、後述するグラフにおけるリンクに対応する。
なお、本実施形態において、番組間の関係は、双方向である。
【００３４】
図８は、履歴テーブル記憶部５０が記憶するテーブルの構成を示す概略図である。図示するように、履歴テーブルは、リレーショナルデータを保持するものであり、ユーザー識別情報、出力ノード種別、出力ノード識別情報、最終出力日時の各項目を有する。ユーザー識別情報は、グラフデータの生成を要求したユーザーの識別情報である。出力ノード種別は、当該ユーザーが過去に出力要求したグラフデータに含まれていたノードの種別である。出力ノード種別は、ユーザーノードまたは番組ノードのいずれかである。出力ノード識別情報は、そのノードを識別する情報である。出力ノード種別がユーザーノードの場合には出力ノード識別情報はユーザー識別情報であり、出力ノード種別が番組ノードの場合には出力ノード識別情報は番組識別情報である。最終出力日時は、当該ユーザーが当該ノード（ユーザーノードまたは番組ノード）を最後に出力した日時のデータであり、「ＹＹＹＹ／ＭＭ／ＤＤ  ｈｈ：ｍｍ：ｓｓ」（年月日・時分秒）の形式である。
【００３５】
以上、図３から図８まで、各データをリレーショナル形式のデータとして表現して説明したが、ＸＭＬ形式等、適宜他の形式を用いてこれらのデータを表現しても良い。また、関係を表すデータは、関係の有無を１／０の値で表す行列として保持するようにしても良い。
【００３６】
次に、グラフ算出部１０の詳細な機能構成および処理手順について説明する。
図９は、グラフ算出部１０の詳細な機能構成を示すブロック図である。図示するように、グラフ算出部１０は、二次リンクノード抽出部１０２（ノード抽出部）と、スコア算出部１０４と、未出力ノード選択部１０６と、出力済ノード選択部１０８と、出力部１１０とを含んで構成される。
【００３７】
二次リンクノード抽出部１０２は、ノード間関係テーブル記憶部３０を参照することにより、指定された中心ノードからのリンクの段階数がＪ（Ｊは整数であり、２≦Ｊ）であるＪ次リンクノードを抽出する。本実施形態では、特に、Ｊ＝２である。
スコア算出部１０４は、ノード間関係テーブル記憶部３０を参照することにより、中心ノードからのリンクの段階数がＫ（Ｋは整数であり、０≦Ｋ＜Ｊ）であるＫ次リンクノードからＪ次リンクノードの各々までの経路数に基づいて、Ｊ次リンクノードの各々のスコアを算出し、算出されたスコアに基づいて、二次リンクノード抽出部１０２によって抽出されたＪ次リンクノードの一部を選択する。本実施形態では、特に、Ｋ＝１である。
ここで、段階数とは、リンクをたどってあるノードから他のノードに到達するために要する最小のリンク数である。また、経路数とは、あるノード集合に属するノードから、他のノードに到達するために取り得る経路の数である。特に、Ｋ＝１且つＪ＝２のときの経路数は、つまり一次リンクノードの集合から特定の二次リンクノードへの経路数は、その一次リンクノードの集合に属するノードから当該二次リンクノードへのリンクの数である。
【００３８】
未出力ノード選択部１０６は、履歴テーブル記憶部５０に記憶されたデータに基づき、スコア算出部１０４によって選択されたＪ次リンクノードのうち、未出力であるＪ次リンクノードを選択する。言い換えれば、未出力ノード選択部１０６が選択するＪ次リンクノードに関しては、過去に出力された履歴が履歴テーブル記憶部５０に残っていない。なお、未出力ノード選択部１０６が、ノード属性テーブル記憶部４０を参照することにより、スコア算出部１０４によって選択されたＪ次リンクノードのうち未出力であるＪ次リンクノードを更新日時の新しい順に最大でＭ個（Ｍは所定の整数）まで選択するようにしても良い。
【００３９】
出力済ノード選択部１０８は、未出力ノード選択部１０６によって選択されたＪ次リンクノードが所定数（Ｍ個）に満たない場合に、スコア算出部１０４によって選択されたＪ次リンクノードのうち、過去に出力した履歴のあるノードを、未出力ノード選択部１０６によって選択された個数と合わせてＭ個になるまで抽出する。
【００４０】
出力部１１０は、未出力ノード選択部１０６および出力済ノード選択部１０８によって抽出されたＪ次リンクノードを出力する。また出力部１１０は、ノード間関係テーブル記憶部３０を参照することにより、これらＪ次リンクノードへのリンクを有する前記Ｋ次リンクノードを出力する。また出力部１１０は、選択されたＪ次およびＫ次のリンクノードと指定された中心ノードとを含むグラフデータを生成して出力する出力部である。
【００４１】
次に、グラフ生成装置１の詳細な処理手順について説明する。グラフ生成装置１は、端末装置３からのグラフ生成要求データに基づき、グラフを生成する処理を行う。このとき、端末装置３は、生成するグラフの中心となるノードを特定する情報をグラフ生成要求データに含めて送信する。
【００４２】
また、グラフ生成装置が処理するためのパラメータとして、正整数値Ｌ，Ｍ，Ｎがそれぞれ、パラメータ記憶部１１に設定されている。ここで、Ｎは、スコア算出部１０４が算出したスコアに基づいてまず二次リンクノードを絞り込む際の個数に関する値である。また、Ｍは、グラフデータとして出力する二次リンクノードの個数に関する値である。また、Ｌは、グラフデータとして出力する一次リンクノードの個数に関する値である。グラフ生成装置１は、固定的な値をそれぞれＬ，Ｍ，Ｎに設定するが、端末装置３からの要求に応じてこれらのパラメータの値の設定を変更するようにしても良い。
【００４３】
図１０は、グラフ算出部１０による処理手順を示すフローチャートである。以下、このフローチャートに沿って説明する。
ステップＳ１において、二次リンクノード抽出部１０２は、指定された中心ノードに対する二次リンクノードをすべてリストアップする。ある中心ノードから見たときの二次リンクノードとは、当該中心ノードから二段階のリンクで到達し得るノードの集合から、当該中心ノードから一段階以下のリンクで到達し得るノードの集合を除いたものである。なお、ここで用いる関係とは、ユーザー相互間関係とユーザー番組間関係と番組相互間関係の和集合である。つまり、二次リンクノード抽出部１０２は、まず、指定された中心ノードの識別情報をキーとして、ユーザー相互間関係テーブルとユーザー番組間関係テーブルと番組相互間関係テーブルをそれぞれ検索し、一次リンクノードの集合を取得する。次に、一次リンクノードの集合に含まれる各要素ノードの識別情報をキーとして、同様にテーブルを検索し、二次リンクノードの集合を取得する。そして、二次リンクノードの集合から、一次リンクノードの集合の要素ノードと、元々指定された中心ノードとを除外する。
【００４４】
次にステップＳ２において、スコア算出部１０４は、ステップＳ１でリストアップされた二次リンクノードの各々について、その二次リンクノードに対してリンクを有している一次リンクの数をカウントする。そして、スコア算出部１０４は、そのカウント値を当該二次リンクノードのスコアとする。言い換えれば、スコア算出部１０４は、一次リンクノードから二次リンクノードへの経路数をカウントして、各々の二次リンクノードのスコアとする。
【００４５】
次にステップＳ３において、スコア算出部１０４は、算出した各二次リンクノードのスコアに基づいて、スコア値の上位Ｎ個に二次リンクノードを絞り込む選択を行う。なお、第Ｎ位の二次リンクノードと同スコア値の二次リンクノードがある場合には、スコア算出部１０４は、Ｎ個を超えて同スコア値の二次リンクノードをすべて選択する。
【００４６】
次にステップＳ４において、未出力ノード選択部１０６は、ステップＳ３で絞り込まれた二次リンクノードのうち、要求元のユーザーに対して過去に出力されたことのないノードを抽出する。このとき、未出力ノード選択部１０６は、履歴テーブル記憶部５０のデータを参照し、要求元のユーザーに対して過去に出力されたことがないかどうかを確認する。当該ユーザーに対して過去に出力されたことがないノードに関しては、履歴テーブルに最終出力日時を表すデータが存在しない。
【００４７】
このとき、未出力ノード選択部１０６は、ユーザー属性テーブル記憶部４１および番組属性テーブル記憶部４２を参照することによって、各ノード（ユーザーノードおよび番組ノード）の最終更新日時を取得する。そして、未出力ノード選択部１０６は、最終更新日時の新しい順に最大でＭ個まで、当該ユーザーに対して未出力の二次リンクノードを抽出する。
【００４８】
次にステップＳ５において、出力済ノード選択部１０８は、ステップＳ４で抽出された二次リンクノードの数がＭ個未満であったか否かを判断する。そして、Ｍ個未満であった場合（抽出二次リンクノード数＜Ｍ、つまりステップＳ５：ＹＥＳ）には、ステップＳ５に進む。Ｍ個に達していた場合（抽出二次リンクノード数≧Ｍ、つまりステップＳ５：ＮＯ）には、ステップＳ６をスキップしてステップＳ７に進む。
【００４９】
次にステップＳ６に進んだ場合、出力済ノード選択部１０８は、ステップＳ３で絞り込まれた二次リンクノードのうち、要求元のユーザーに対して過去に出力した履歴のあるノードを抽出する。このとき、出力済ノード選択部１０８は、履歴テーブル記憶部５０のデータを参照し、要求元のユーザーに対して前回表示された日時の古い順に二次リンクノードを抽出する。前回表示された日時は、当該ユーザー識別情報および二次リンクノードの識別情報をキーとして履歴テーブルを参照することにより得られる。またこのとき、出力済ノード選択部１０８は、ステップＳ４において抽出された未出力ノードの数と合わせてＭ個になるように、過去に出力済の二次リンクノードを、上記順で選択する。
【００５０】
次にステップＳ７において、出力部１１０は、抽出したＭ個の二次リンクノードのデータを出力する。
【００５１】
次にステップＳ８において、出力部１１０は、ステップＳ７で出力した二次リンクノードの各々にリンクしている一次リンクノードを抽出し、それらの一次リンクノードのうち、出力した二次リンクノードへのリンク数が多い順に上位Ｌ個の一次リンクノードのデータを出力する。
また、出力部１１０は、出力したＭ個の二次リンクノードおよびＬ個の一次リンクノードおよび指定された中心ノードに関わるリンクのデータを合わせて出力する。ここで出力されるリンクは、中心ノードから一次リンクノードへのリンク、一次リンクノード相互間のリンク、一次リンクノードから二次リンクノードへのリンク、および二次リンクノード相互間のリンクである。
【００５２】
次にステップＳ９において、出力部１１０は、今回の出力に関して履歴テーブルを更新する。具体的には、出力部１１０は、要求元のユーザー識別情報と、ステップＳ７およびＳ８で出力したノードに関して、最終出力日時のデータを履歴テーブルに書き込む。このとき、当該ユーザー識別情報と当該ノード識別情報の組合せで、履歴テーブルに既に行が存在している場合にはその行の最終出力日時のデータを更新する。また、当該ユーザー識別情報と当該ノード識別情報の組合せで、履歴テーブルに行が存在していない場合には新たな行を挿入する。
【００５３】
図１１は、グラフ算出部１０によって生成され、グラフデータ出力部１２によって出力されるグラフデータの例である。同図（ａ）は出力されるグラフに含まれるノードに関するデータであり、同図（ｂ）は同グラフに含まれるリンクに関するデータである。
【００５４】
同図（ａ）は、表形式のデータであり、リンク段階と、ノード種別と、ノード識別情報と、ノード名の各項目を有する。このデータの各行が、グラフ中のノードに対応する。リンク段階は、出力されるグラフにおける中心ノード、一次リンクノード、二次リンクノードの区別を表すデータである。なお、グラフデータ出力部１２が、各ノードに対応するユーザーのアイコン画像や、番組のサムネイル画像を合わせて出力するようにしても良い。同図（ｂ）は、表形式のデータであり、リンク元ノード識別情報と、リンク先ノード識別情報と、リンク種別と、リンク方向の各項目を有する。このデータの各行が、１本のリンクに対応する。リンク種別は、友人関係（ユーザーを表すノード同士の関係）、お気に入り番組（ユーザーを表すノードから番組を表すノードへの関係）、関連番組（番組を表すノード同士の関係）など、リンクの種類を表す。リンク方向は、双方向、正方向、逆方向の３種類である。リンク方向が正方向の場合、リンク元ノード識別情報で識別されるノードからリンク先ノード識別情報で識別されるノードへの関係であることを表す。例えば、リンク元がユーザー「１０１２３４５」（ノード名は「自分」）で、リンク先が番組「２０１００１７」（ノード名は「番組Ａ」）である場合、「自分」が「番組Ａ」をお気に入り番組として登録していることを表す。リンク方向が逆方向の場合、逆に、リンク先ノード識別情報で識別されるノードからリンク元ノード識別情報で識別されるノードへの関係であることを表す。
【００５５】
図１２は、グラフデータ出力部１２から出力されたデータに基づいて端末装置３が画面に表示したグラフの例である。この画面表示は、図１１に示した７個のノードおよび９本のリンクをグラフィカルに表現している。ここでは、各ノードが楕円形で表示され、中心ノードは実線で描かれ、１次リンクノードは破線で描かれ、２次リンクノードは一転鎖線で描かれている。また、友人関係は実線の両方向矢印で表され、関連番組の関係は二重線の両方向矢印で表され、お気に入り番組の関係は破線の片方向矢印で表されている。
【００５６】
なお、上述した実施形態におけるグラフ生成装置の機能をコンピュータで実現するようにしても良い。その場合、この制御機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現しても良い。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時刻の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時刻プログラムを保持しているものも含んでも良い。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【００５７】
以上、本発明の実施形態を説明したが、本発明はさらに次のような変形例でも実施することが可能である。
上記実施形態では、端末装置３からの要求に基づいて、グラフ生成装置１がグラフデータを端末装置３に送信し、端末装置３が受信したグラフデータを元にグラフの描画を行った。これに対して、グラフ生成装置１側でグラフの描画まで行い、その結果得られる画像データをグラフ生成装置１から端末装置３に送信するようにしても良い。
上記実施形態では、Ｊ＝２且つＫ＝１とした。つまり、グラフ生成装置１は、一次リンクノードからのリンク数に基づくスコアで、二次リンクノードを抽出し、一次リンクノードと二次リンクノードとを含むグラフデータを生成した。これに対し、０≦Ｋ＜Ｊを満たす他の整数の組Ｊ，Ｋを用いても良い。
上記実施形態では、あるノードに関する関係の更新の日時を当該ノードの更新日時として、ノードの選択に利用した。これに対し、関係以外の更新（例えば、当該ノードに関するコンテンツの更新など）の日時をそのノードの更新日時として、ノードを選択するようにしても良い。ここでコンテンツとは、例えば、あるユーザーの日記や、ある番組に関して書かれたレビューなどである。
上記実施形態では、番組を対象物とした。これに対し、他の対象物によるノードを用いてグラフを生成するようにしても良い。他の対象物とは、例えば、ソーシャルネットワーキングサービス等におけるコミュニティや、映画や、音楽や、書籍等である。
【００５８】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【産業上の利用可能性】
【００５９】
本発明は、ウェブ等を利用して提供するサービスに利用できる。特に、例えば、ソーシャルネットワーキングサービス等に利用できる。
【符号の説明】
【００６０】
１  グラフ生成装置
１０  グラフ算出部
１１  パラメータ記憶部
１２  グラフデータ出力部
３０  ノード間関係テーブル記憶部
３１  ユーザー相互間関係テーブル記憶部
３２  ユーザー番組間関係テーブル記憶部
３３  組相互間関係テーブル記憶部
４０  ノード属性テーブル記憶部
４１  ユーザー属性テーブル記憶部
４２  番組属性テーブル記憶部
５０  履歴テーブル記憶部
１０２  二次リンクノード抽出部（ノード抽出部）
１０４  スコア算出部
１０６  未出力ノード選択部
１０８  出力済ノード選択部
１１０  出力部
【図１】
2012242859.tif 000003
【図２】
2012242859.tif 000004
【図３】
2012242859.tif 000005
【図４】
2012242859.tif 000006
【図５】
2012242859.tif 000007
【図６】
2012242859.tif 000008
【図７】
2012242859.tif 000009
【図８】
2012242859.tif 000010
【図９】
2012242859.tif 000011
【図１０】
2012242859.tif 000012
【図１１】
2012242859.tif 000013
【図１２】
2012242859.tif 000014