Top > Search of Japanese Patents > RELATIONSHIP GRAPH EVALUATION SYSTEM

RELATIONSHIP GRAPH EVALUATION SYSTEM foreign

Patent code P180015550
File No. 4482
Posted date Nov 21, 2018
Application number P2014-029713
Publication number P2015-153395A
Patent number P6310721
Date of filing Feb 19, 2014
Date of publication of application Aug 24, 2015
Date of registration Mar 23, 2018
Inventor
  • (In Japanese)新熊 亮一
  • (In Japanese)山口 和泰
Applicant
  • (In Japanese)国立大学法人京都大学
  • (In Japanese)株式会社神戸デジタル・ラボ
Title RELATIONSHIP GRAPH EVALUATION SYSTEM foreign
Abstract PROBLEM TO BE SOLVED: To provide a relationship evaluation system capable of efficiently evaluating a relationship between a node and a base point node about a relationship graph in which a plurality of nodes are connected by a link.
SOLUTION: The relationship graph evaluation system is configured to select a base point node on the basis of selection information related to a base point node input by a selection information input part, and to extract a relationship graph to be evaluated from a relationship graph database on the basis of the base point node, and to generate a virtual communication network on the basis of the relationship graph, and to execute simulation by allowing a virtual communication packet to successively propagate to the adjacent node with the base point node selected by the base point node selection part as a propagation source, and to evaluate a relationship between the node and the base point node on the basis of the content of the communication packet received by the node as the result of the execution of simulation.
Outline of related art and contending technology (In Japanese)

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

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

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

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

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

Field of industrial application (In Japanese)

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

Scope of claims (In Japanese)
【請求項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から請求項8のいずれかに記載の関係性グラフ評価システム。

【請求項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(International Patent Classification)
Drawing

※Click image to enlarge.

JP2014029713thum.jpg
State of application right Registered
Please contact us by e-mail or facsimile if you have any interests on this patent. Thanks.


PAGE TOP

close
close
close
close
close
close
close