TOP > 国内特許検索 > 関係性グラフ評価システム

関係性グラフ評価システム NEW 外国出願あり

国内特許コード P180015550
整理番号 4482
掲載日 2018年11月21日
出願番号 特願2014-029713
公開番号 特開2015-153395
登録番号 特許第6310721号
出願日 平成26年2月19日(2014.2.19)
公開日 平成27年8月24日(2015.8.24)
登録日 平成30年3月23日(2018.3.23)
発明者
  • 新熊 亮一
  • 山口 和泰
出願人
  • 国立大学法人京都大学
  • 株式会社神戸デジタル・ラボ
発明の名称 関係性グラフ評価システム NEW 外国出願あり
発明の概要 【課題】本発明は、複数のノードをリンクで接続した関係性グラフについて、基点ノードに対するノードの関係性を効率よく評価することができる関係性評価システムの提供を目的とする。
【解決手段】選択情報入力部により入力された基点ノードに関する選択情報に基づいて基点ノードを選択する。基点ノードに基づいて関係性グラフデータベースから評価対象となる関係性グラフを抽出して、関係性グラフに基づいて仮想通信ネットワークを生成する。仮想通信ネットワークにおいて、前記基点ノード選択部により選択された基点ノードを伝播元として、仮想の通信パケットを隣接するノードに順次伝播させることによりシュミレーションを実行する。シュミレーションが実行された結果、ノードに受信された通信パケットの内容に基づいて、基点ノードに対する当該ノードの関係性を評価する。
【選択図】図2
従来技術、競合技術の概要


従来、高度なサービス実現のため、個々のデータに詳細な属性情報をもたせることが取り組まれているが、一方で、データ間の関係性をサービスに活用する試みが検討されている(非特許文献1参照)。特に人と人の関係性や人の移動のコンテキストとロケーションの関係性といったソーシャルな関係性が注目を集めており、こういったデータの関係性は関係性グラフとして表現される。



この関係性グラフとは、図3(a)に示すように、人、モノ、場所、コンテンツといったオブジェクトをノードとして表し、それらオブジェクト相互の関係性の有無をリンクで表したものである。また、直接相互に接続されたノード間の関係性の強さはリンク長で与えられ、他のノードを介して接続しているノード間の関係性の強さは経路長で与えられる。



また、現実世界あるいはオンラインで観測された情報を入力ソースとすることで、入力ソースに含まれるオブジェクト群がノードとして生成される。また、ノード間のリンクも生成されることで、小さな関係性グラフ(部分グラフ)が形成される。



また、複数の部分グラフを、共通のノードを介して結合していくことで大きな1つの関係性グラフが形成され、これがデータベースに保持される(特許文献1参照)。なお、結合の際、同じリンクが重複して存在するほど、リンク長は短くなる。



また、データベースに保持された関係性グラフは様々なアプリケーションに参照され利用される。例えば、SNS(ソーシャルネットワーキングサービス)の情報を入力ソースとして、人のみの関係性グラフを形成した場合、ある人と直接のリンクはないが、経路長の小さい他の人を将来の友人として提示(レコメンド)することが可能である。例えば、モバイル端末によるEコマースにおいて、場所への訪問履歴と商品の購入履歴から関係性グラフを形成した場合、ある消費者がある場所を訪問した際に、関係性グラフ上でその消費者とその場所から経路長の小さい商品をレコメンドするといったことが可能である。

産業上の利用分野


本発明は、複数のノードをリンクで接続した関係性グラフを評価する関係性グラフ評価システムに関するものである。

特許請求の範囲 【請求項1】
複数のノードをリンクで接続した関係性グラフを評価する関係性グラフ評価システムであって、
関係性グラフを記憶する関係性グラフデータベースと、
基点ノードに関する選択情報が入力される選択情報入力部と、
該選択情報入力部により入力された基点ノードに関する選択情報に基づいて基点ノードを選択する基点ノード選択部と、
該基点ノード選択部により選択された基点ノードに基づいて、関係性グラフデータベースから評価対象となる関係性グラフを抽出する関係性グラフ抽出部と、
該関係性グラフ抽出部により抽出された関係性グラフに基づいて、仮想通信ネットワークを生成する仮想通信ネットワーク生成部と、
該仮想通信ネットワーク生成部により生成された仮想通信ネットワークにおいて、前記基点ノード選択部により選択された基点ノードを伝播元として、仮想の通信パケットを隣接するノードに順次伝播させることによりシミュレーションを実行する仮想通信ネットワークシミュレーション部と、
該仮想通信ネットワークシミュレーション部によりシミュレーションが実行された結果、ノードに受信された通信パケットの内容に基づいて、基点ノードに対する当該ノードの関係性を評価する関係性評価部と、
該関係性評価部による基点ノードに対する当該ノードの関係性の評価結果を出力する関係性評価出力部とを備えることを特徴とする関係性グラフ評価システム。

【請求項2】
前記関係性評価部は、前記仮想通信ネットワークシミュレーション部によるシミュレーションに使用される制御パラメータを指示する請求項1に記載の関係性グラフ評価システム。

【請求項3】
前記仮想通信ネットワークシミュレーション部は、各ノードにおいて、受信した通信パケットの情報を記録した上で、当該通信パケットを隣接するノードに伝播させる請求項1または請求項2に記載の関係性グラフ評価システム。

【請求項4】
前記仮想通信ネットワークシミュレーション部は、各ノードにおいて、通信パケットを伝播してきた相手のノードには当該通信パケットを伝播させない請求項1から請求項3のいずれかに記載の関係性グラフ評価システム。

【請求項5】
前記仮想通信ネットワークシミュレーション部は、各ノードにおいて、通信パケットを隣接するノードに伝播させるときに、通信パケットのボリュームに隣接するノードとのリンクの伝播成功率を乗算して伝播させる請求項1から請求項4のいずれかに記載の関係性グラフ評価システム。

【請求項6】
前記仮想通信ネットワークシミュレーション部は、各ノードにおいて、通信パケットを隣接するノードに伝播させるときに、通信パケットのホップ数を一ないし複数増加させ、通信パケットが所定のホップ数に達したときに当該通信パケットを破棄する請求項1から請求項5のいずれかに記載の関係性グラフ評価システム。

【請求項7】
前記仮想通信ネットワークシミュレーション部は、各ノードにおいて、通信パケットを隣接するノードに伝播させるときに、通信パケットの累積遅延をリンクの伝播遅延の分だけ増加させ、通信パケットが所定の累積遅延に達したときに当該通信パケットを破棄する請求項1から請求項6のいずれかに記載の関係性グラフ評価システム。

【請求項8】
前記仮想通信ネットワークシミュレーション部は、各ノードにおいて、隣接する複数のノードのうち、伝播成功率が最も高いリンクを有するノードに通信パケットを伝播させる請求項1から請求項7のいずれかに記載の関係性グラフ評価システム。

【請求項9】
前記仮想通信ネットワークシミュレーション部は、各ノードにおいて、隣接するノードの個数に応じて同じボリュームの通信パケットを複製し、それら複製した通信パケットをそれぞれ隣接する複数のノードに伝播させる請求項1から請求項8のいずれかに記載の関係性グラフ評価システム。

【請求項10】
前記仮想通信ネットワークシミュレーション部は、各ノードにおいて、隣接するノードの個数に応じて通信パケットのボリュームを分割し、それら分割した通信パケットをそれぞれ隣接する複数のノードに伝播させる請求項1から請求項のいずれかに記載の関係性グラフ評価システム。

【請求項11】
前記仮想通信ネットワークシミュレーション部は、隣接するノードとの間のリンクの伝播成功率に比例して通信パケットのボリュームを分割する請求項10に記載の関係性グラフ評価システム。

【請求項12】
前記関係性評価部は、各ノードにおいて、基点ノードから異なる経路で伝播してきた各通信パケットのボリュームの和により、基点ノードから各ノードまでの距離を評価する請求項1から請求項11のいずれかに記載の関係性グラフ評価システム。

【請求項13】
前記関係性評価部は、各ノードで受信した通信パケットの個数、ボリューム、あるいは経路の類似性を比較することにより、各ノードの類似性を評価する請求項1から請求項12のいずれかに記載の関係性グラフ評価システム。

【請求項14】
前記関係性評価部は、各ノードにおいて、基点ノードから異なる経路で伝播してきた各通信パケットのホップ数のうち、最少ホップ数に基づいて基点ノードに対する当該ノードの直接性を評価する請求項1から請求項13のいずれかに記載の関係性グラフ評価システム。

【請求項15】
前記関係性評価部は、各ノードにおいて、基点ノードから異なる経路で伝播してきた通信パケットの個数とボリュームに基づいて基点ノードに対する当該ノードの従属性を評価する請求項1から請求項14のいずれかに記載の関係性グラフ評価システム。

【請求項16】
前記関係性評価部は、各ノードにおいて、基点ノードから異なる経路で伝播してきた各通信パケットが共通の中継ノードを経由していた場合、当該中継ノードは基点ノードから当該ノードとの間の関係性において影響度が大きいと評価する請求項1から請求項15のいずれかに記載の関係性グラフ評価システム。

【請求項17】
前記関係性評価部は、各ノードにおいて、基点ノードから異なる経路で伝播してきた通信パケットの個数に基づいて当該ノードの頑強性を評価する請求項1から請求項16のいずれかに記載の関係性グラフ評価システム。

【請求項18】
前記関係性評価部は、前記仮想通信ネットワークシミュレーション部により通信パケットが伝播される過程において、通信パケットの所定ホップ数毎または所定時間毎に、ノードに受信された通信パケットの内容に基づいて、基点ノードに対する当該ノードの関係性を評価する請求項1から請求項17のいずれかに記載の関係性グラフ評価システム。

【請求項19】
前記基点ノード選択部は、複数の基点ノードを選択し、
前記関係性評価部は、各ノードにおいて、各基点ノードに対する距離、直接性、従属性、類似性、中継ノードの影響度、あるいは頑強性の少なくとも一つを評価する請求項1から請求項18のいずれかに記載の関係性グラフ評価システム。

【請求項20】
前記仮想通信ネットワークシミュレーション部は、基点ノードから所定範囲の複数のノードを伝播元として通信パケットを隣接するノードに順次伝播させていき、
前記関係性評価部は、前記所定範囲内のノードにおいて通信パケットが伝播したノードの分布に基づいて特徴的なノードまたは部分ネットワークを抽出して評価する請求項1から請求項19のいずれかに記載の関係性グラフ評価システム。
国際特許分類(IPC)
画像

※ 画像をクリックすると拡大します。

JP2014029713thum.jpg
出願権利状態 登録
ライセンスをご希望の方、特許の内容に興味を持たれた方は、下記までご連絡ください。


PAGE TOP

close
close
close
close
close
close
close