Nothing Special   »   [go: up one dir, main page]

JP4789814B2 - Cluster generation apparatus and cluster generation method - Google Patents

Cluster generation apparatus and cluster generation method Download PDF

Info

Publication number
JP4789814B2
JP4789814B2 JP2007014194A JP2007014194A JP4789814B2 JP 4789814 B2 JP4789814 B2 JP 4789814B2 JP 2007014194 A JP2007014194 A JP 2007014194A JP 2007014194 A JP2007014194 A JP 2007014194A JP 4789814 B2 JP4789814 B2 JP 4789814B2
Authority
JP
Japan
Prior art keywords
node
cluster
score
graph
arc
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
JP2007014194A
Other languages
Japanese (ja)
Other versions
JP2008181333A (en
Inventor
プラムディオノ イコ
京士 飯塚
宏之 佐藤
健治 大友
隆彦 村山
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Nippon Telegraph and Telephone Corp
Original Assignee
Nippon Telegraph and Telephone Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Nippon Telegraph and Telephone Corp filed Critical Nippon Telegraph and Telephone Corp
Priority to JP2007014194A priority Critical patent/JP4789814B2/en
Publication of JP2008181333A publication Critical patent/JP2008181333A/en
Application granted granted Critical
Publication of JP4789814B2 publication Critical patent/JP4789814B2/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Landscapes

  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Description

本発明は、グラフのクラスタを生成するクラスタ生成装置およびクラスタ生成方法に関するものである。   The present invention relates to a cluster generation device and a cluster generation method for generating a cluster of graphs.

インスタンスをもつノード間がアークによって接続されたグラフまたはそのサブグラフを分割したものをクラスタといい、クラスタは、その中ではノードのインスタンス同士が類似し、クラスタが異なればノードのインスタンス同士が類似しないように生成される。   A graph in which nodes with instances are connected by arcs or a subgraph divided is called a cluster. In a cluster, node instances are similar to each other, and if the clusters are different, node instances are not similar to each other. Is generated.

この出願の発明に関連する先行技術文献情報としては下記のものがある。   Prior art document information relating to the invention of this application includes the following.

非特許文献1では、サブグラフを検索する技術を開示している。グラフはRDFで表現され、検索にはクエリが使用される。   Non-Patent Document 1 discloses a technique for searching a subgraph. The graph is expressed in RDF, and a query is used for searching.

非特許文献2では、クラスタを生成する技術を開示している。クラスタ生成には、エッジの密度の差異が用いられる。   Non-Patent Document 2 discloses a technique for generating a cluster. The difference in edge density is used for cluster generation.

非特許文献3では、サブグラフを検索する技術を開示している。ここでは、グラフは重み付きグラフであり、ノードのオーソリティ値とハブ値をHITSアルゴリズムで計算する。そして、複数の情報のそれぞれをもつノード間にあるパスで、しかもそのパスを構成するノードについて計算された値がしきい値以上のものを検索する。   Non-Patent Document 3 discloses a technique for searching a subgraph. Here, the graph is a weighted graph, and the authority value and the hub value of the node are calculated by the HITS algorithm. Then, a search is made for a path between nodes having each of a plurality of pieces of information, and a value calculated for a node constituting the path is equal to or greater than a threshold value.

非特許文献4では、指定されたシードのウェブページと周辺のウェブページを収集し、それらのグラフを生成する。そして、そのグラフのノードのオーソリティ値とハブ値をHITSアルゴリズムで計算し、その値が上位のウェブページがグラフの中心的なノード(コア)であることとする。
"SPARQL Query Language for RDF", [online], インターネット<URL:http://www.w3.org/TR/rdf-sparql-query/> M.E..J.Newman, "Detecting community structure in networks", Europian Physical Journal B, 38:321-330, 2004 S.Mukherjea, B. Bamba, "BioPatentMiner: an information retrieval system for biomedical patents", VLDB, 2004 D.Gibson, J. Kleinberg, and P.Paghavan, "Inferring web communities from link topology", ACM Conf. on Hypertext and Hypermedia, 1998
In Non-Patent Document 4, a web page of a specified seed and surrounding web pages are collected and a graph thereof is generated. Then, the authority value and hub value of the node of the graph are calculated by the HITS algorithm, and the higher-level web page is the central node (core) of the graph.
"SPARQL Query Language for RDF", [online], Internet <URL: http://www.w3.org/TR/rdf-sparql-query/> ME.J.Newman, "Detecting community structure in networks", Europian Physical Journal B, 38: 321-330, 2004 S. Mukherjea, B. Bamba, "BioPatentMiner: an information retrieval system for biomedical patents", VLDB, 2004 D. Gibson, J. Kleinberg, and P. Paghavan, "Inferring web communities from link topology", ACM Conf. On Hypertext and Hypermedia, 1998

非特許文献1に記載の技術では、1つのサブグラフを検索するだけなので、複数の情報の関連性を示せない。また、グラフ構造の知識が必要である。   In the technique described in Non-Patent Document 1, since only one subgraph is searched, relevance of a plurality of information cannot be shown. In addition, knowledge of the graph structure is required.

非特許文献2に記載の技術では、クラスタを生成できるが、複数の情報の関連性を示せない。また、関心の対象が考慮されない。   In the technique described in Non-Patent Document 2, a cluster can be generated, but the relevance of a plurality of pieces of information cannot be shown. Also, the object of interest is not considered.

非特許文献3に記載の技術では、検索できるのはパスなので、複数の情報の関連性を十分に示せない。   In the technique described in Non-Patent Document 3, since a path can be searched, the relevance of a plurality of information cannot be shown sufficiently.

非特許文献4に記載の技術では、生成されるのは、シードを中心とした1つのグラフ(クラスタ)だけなので、複数の情報の関連性を示せない。また、関心の対象が考慮されない。   In the technique described in Non-Patent Document 4, since only one graph (cluster) centered on a seed is generated, the relevance of a plurality of information cannot be shown. Also, the object of interest is not considered.

本発明は、上記の課題に鑑みてなされたものであり、その目的とするところは、グラフからそのノード間の関連性を示せるクラスタを生成できるクラスタ生成装置およびクラスタ生成方法を提供することにある。   The present invention has been made in view of the above problems, and an object of the present invention is to provide a cluster generation device and a cluster generation method capable of generating a cluster that can show the relationship between the nodes from a graph. .

上記の課題を解決するために、本発明では、インスタンスをもつノード間がラベルをもつアークによって接続されたグラフまたはそのサブグラフのアークに、指定された関心度に応じたアークスコアを設定し、そのアークスコアを基にして、グラフなどのノードについてのノードスコアを計算し、計算されたノードスコアを基にして、グラフなどのクラスタを生成する。   In order to solve the above problem, in the present invention, an arc score corresponding to a specified degree of interest is set to an arc of a graph or a subgraph thereof in which nodes having instances are connected by an arc having a label, A node score for a node such as a graph is calculated based on the arc score, and a cluster such as a graph is generated based on the calculated node score.

本発明によれば、ノード間にあるアークについてのアークスコアを基に計算されたノードスコアが用いられるので、ノード間の関連性を示せるクラスタを生成することができる。   According to the present invention, since the node score calculated based on the arc score for the arc between the nodes is used, it is possible to generate a cluster that can indicate the relationship between the nodes.

以下、本発明の実施の形態を図面を参照して説明する。なお、同一のものには同一符号を付与し、重複説明を省略する。   Hereinafter, embodiments of the present invention will be described with reference to the drawings. In addition, the same code | symbol is provided to the same thing and duplication description is abbreviate | omitted.

[第1の実施の形態]
図1は、第1の実施の形態に係るクラスタ生成装置1Aの構成図である。
[First Embodiment]
FIG. 1 is a configuration diagram of a cluster generation device 1A according to the first embodiment.

クラスタ生成装置1Aは、ユーザ端末2に接続され、ユーザ端末2には、表示装置3が接続されている。   The cluster generation device 1 </ b> A is connected to a user terminal 2, and a display device 3 is connected to the user terminal 2.

クラスタ生成装置1Aは、有向グラフであるグラフGを表示するためのデータ群が記憶されたグラフデータベース11と、ユーザ端末2で入力操作をさせるための入力用インタフェースを生成する入力用インタフェース生成部12と、ユーザ端末2のユーザの関心の対象として想定された項目(関心項目という)に対応づけて、その関心項目に関連するラベルを記憶したラベル記憶部13と、グラフGのアークにスコア(アークスコアという)を設定するアークスコア設定部14と、そのグラフGのノードについてスコア(ノードスコアという)を計算するノードスコア計算部15と、そのグラフGからクラスタを生成するクラスタ生成部16と、データベースインタフェース17と、処理結果を伝えるための出力用インタフェースを生成する出力用インタフェース生成部18とを備える。   The cluster generation device 1A includes a graph database 11 in which a data group for displaying a graph G that is a directed graph is stored, an input interface generation unit 12 that generates an input interface for causing the user terminal 2 to perform an input operation, The label storage unit 13 stores a label associated with the item of interest (referred to as an item of interest) associated with the item of interest of the user of the user terminal 2 and a score (arc score) Arc score setting unit 14 for setting a node, a node score calculation unit 15 for calculating a score (referred to as a node score) for a node of the graph G, a cluster generation unit 16 for generating a cluster from the graph G, and a database interface 17 and an output interface to convey the processing result And an output interface generating unit 18.

クラスタは、グラフGの一部を分割して得られた各部分と同じものである。分割して得られるものなので、クラスタ同士では重複がない。また、サブグラフ内では分離している部分がないから、クラスタ内でも同様である。クラスタは、その中ではノードのインスタンス同士が類似し、クラスタが異なればノードのインスタンス同士が類似しないように生成される。   The cluster is the same as each part obtained by dividing a part of the graph G. Since it is obtained by dividing, there is no overlap between clusters. Further, since there is no separated part in the subgraph, the same applies to the cluster. The clusters are generated so that the node instances are similar to each other, and if the clusters are different, the node instances are not similar to each other.

クラスタ生成装置1Aは、各部(データベース含む)でデータの送受信(受け渡し)が可能であればよい。つまり、各部を、同一のコンピュータに配置してもよいし、複数のコンピュータに分散配置してもよい。また、これらコンピュータをクラスタ生成装置として動作させるコンピュータプログラムを通信回線を介して送受信してもよい。また、このコンピュータプログラムを、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどの記録媒体に記録し、その記録媒体を流通させてもよい。他の実施の形態でも同様である。   The cluster generation device 1A only needs to be able to transmit and receive (deliver) data in each unit (including a database). That is, each unit may be arranged on the same computer or may be distributed on a plurality of computers. Further, a computer program for operating these computers as a cluster generation device may be transmitted / received via a communication line. The computer program may be recorded on a recording medium such as a semiconductor memory, a magnetic disk, an optical disk, a magneto-optical disk, or a magnetic tape, and the recording medium may be distributed. The same applies to other embodiments.

図2は、グラフデータベース11に記憶されたデータ群を全て使って表示できるグラフGの一部を例示した図である。   FIG. 2 is a diagram illustrating a part of a graph G that can be displayed using all data groups stored in the graph database 11.

グラフデータベース11に記憶されたデータ群を全て使って、図2に一部を例示したグラフG、つまり互いに異なるインスタンスをもつノード間がラベルをもつアークによって接続され且つ当該インスタンスのクラスが定義されたグラフG、を表示することができる。逆にいえば、グラフGを表示するための過不足ないデータ群がグラフデータベース11に記憶されている。以下、そのデータ群を便宜的にグラフGという。また、なんらかのグラフ、サブグラフ(なんらかのグラフそのものまたはそれに含まれるグラフ)、パス(分岐および閉ループをもたないグラフ)などをクラスを含めて表示するための過不足ないデータ群を便宜的にグラフ、サブグラフ、パスなどという。   Using all the data groups stored in the graph database 11, the graph G partially illustrated in FIG. 2, that is, nodes having different instances are connected by arcs having labels, and classes of the instances are defined. A graph G can be displayed. Conversely, a data group for displaying the graph G is stored in the graph database 11. Hereinafter, the data group is referred to as a graph G for convenience. Also, for convenience, graphs and subgraphs can be used to display any graphs, subgraphs (some graphs themselves or graphs included in them), paths (graphs without branches and closed loops), etc. , Pass and so on.

グラフGでは、例えば、「XML」や「Bプロジェクト」などのインスタンスをもつノードが、「rm:技術キーワード」や「rm:著者」などのラベルをもつアークで接続される。また、グラフGでは、ノードにそのインスタンス「Person:山田太郎」などの概念であるクラス「Person:人」などが定義される。   In the graph G, for example, nodes having instances such as “XML” and “B project” are connected by arcs having labels such as “rm: technical keyword” and “rm: author”. Further, in the graph G, a class “Person: person” or the like that is a concept such as an instance “Person: Taro Yamada” is defined in a node.

図3は、グラフデータベース11に記憶されたデータ群の一部を例示した図である。   FIG. 3 is a diagram illustrating a part of a data group stored in the graph database 11.

例えば、最初のデータ「<org:Dプロジェクト><rm:技術キーワード>”XML”」は、インスタンス「org:Dプロジェクト」をもつノードからインスタンス「XML」のノードへ向かうアークがラベル「rm:技術キーワード」をもつことを示している。また、例えば、最後のデータ「<person:鈴木花子><rdf:type><Person:人>」は、インスタンス「person:鈴木花子」をもつノードのクラスが「person:人」であることを示している。   For example, in the first data “<org: D project> <rm: technical keyword>“ XML ””, an arc from the node having the instance “org: D project” to the node of the instance “XML” is labeled “rm: technique”. It has shown that it has a keyword. For example, the last data “<person: Hanako Suzuki> <rdf: type> <Person: person>” indicates that the class of the node having the instance “person: Hanako Suzuki” is “person: person”. ing.

なお、各データは、実際にはRDF(以下の文献に記載)で表現されている。   Each data is actually expressed in RDF (described in the following document).

「Resource Description Framework(RDF)Model and Syntax Specification」, Ora Lassia, Ralph R.Swick編,[online], インターネット<URL:http://www.w3.org/TR/1999/REC-rdf-syntax-19990222/>
「RDF Vocabulary Description Language 1.0: RDF Schema」, Dan Brickley, R.V.Guha編,[online], インターネット<URL:http://www.w3.org/TR/rdf-schema/>
図4は、ラベル記憶部13の記憶内容を示す図である。
"Resource Description Framework (RDF) Model and Syntax Specification", Ora Lassia, Ralph R. Swick, [online], Internet <URL: http://www.w3.org/TR/1999/REC-rdf-syntax- 19990222 />
“RDF Vocabulary Description Language 1.0: RDF Schema”, Dan Brickley, RVGuha, [online], Internet <URL: http://www.w3.org/TR/rdf-schema/>
FIG. 4 is a diagram showing the contents stored in the label storage unit 13.

例えば、関心項目「所属」には、ラベル「person:所属」、ラベル「rm:学会KW」、ラベル「rm:会員」が対応づけられている。   For example, a label “person: affiliation”, a label “rm: academic society KW”, and a label “rm: member” are associated with the interest item “affiliation”.

また、関心項目「学術論文」には、ラベル「rm:著者」、ラベル「rm:著者KW」が対応づけられている。   Further, the label “rm: author” and the label “rm: author KW” are associated with the item of interest “scientific paper”.

また、関心項目「サービス開発」には、ラベル「ms:KW」、ラベル「ms:担当者」、ラベル「ms:参考文献」、ラベル「ms:著者」が対応づけられている。   The item of interest “service development” is associated with a label “ms: KW”, a label “ms: person in charge”, a label “ms: reference”, and a label “ms: author”.

かかるラベルは、対応する関心項目に関連するものとして、グラフGのラベルから選択されたものである。   Such a label is selected from the labels of the graph G as related to the corresponding item of interest.

(第1の実施の形態の動作)
図5は、第1の実施の形態のシーケンス図である。
(Operation of the first embodiment)
FIG. 5 is a sequence diagram of the first embodiment.

クラスタ生成装置1Aでは、入力用インタフェース生成部12が、入力用インタフェースを生成し、それをユーザ端末2に送信して(S1)、図6に示したように表示させる(S3)。ここでの操作により特定された1以上のキーワードKWと1以上のクラスCLの一方または両方、各関心項目の関心度(大、中、小のいずれか)の組合せ、並びに、しきい値THをユーザ端末2がクラスタ生成装置1Aに送信する(S5)。しきい値THは、これを例えば低く設定して、ノードを多く含むクラスタを表示させるためのものである。なお、これらのキーワードKWなどは、クラスタ生成装置1Aに記憶しておき、それを適宜読み出して使用してもよい。   In the cluster generation device 1A, the input interface generation unit 12 generates an input interface, transmits it to the user terminal 2 (S1), and displays it as shown in FIG. 6 (S3). One or both of one or more keywords KW and one or more classes CL specified by the operation here, a combination of interest levels (either large, medium, or small) of each item of interest, and a threshold value TH The user terminal 2 transmits to the cluster generation device 1A (S5). The threshold value TH is set to, for example, a low value to display a cluster including many nodes. Note that these keywords KW and the like may be stored in the cluster generation device 1A and read and used as appropriate.

(アークスコア設定)
クラスタ生成装置1Aは、アークスコア設定部14が、グラフGのアークにアークスコアを設定する(S11)。具体的には、アークスコアを含むクエリをデータベースインタフェース17に送信する(S111)ことで、アークスコアが設定されたグラフGを取得する(S112)。
(Arc score setting)
In the cluster generation device 1A, the arc score setting unit 14 sets an arc score for the arc of the graph G (S11). Specifically, a query G including the arc score is acquired by transmitting a query including the arc score to the database interface 17 (S111) (S112).

例えば、関心項目「所属」にラベル記憶部13で対応づけられたラベル「person:所属」、ラベル「rm:学会KW」、ラベル「rm:会員」に対し、関心項目「所属」の関心度に応じたアークスコアを設定する。   For example, for the label “person: affiliation”, the label “rm: academic society KW”, and the label “rm: member” associated with the interest item “affiliation” in the label storage unit 13, the interest level of the interest item “affiliation” is set. Set the corresponding arc score.

また、関心項目「学術論文」にラベル記憶部13で対応づけられたラベル「rm:著者」、ラベル「rm:著者KW」に対し、関心項目「学術論文」の関心度に応じたアークスコアを設定する。   Further, an arc score corresponding to the interest level of the interest item “scholarly paper” is given to the label “rm: author” and the label “rm: author KW” associated with the interest item “scholarly paper” in the label storage unit 13. Set.

また、関心項目「サービス開発」にラベル記憶部13で対応づけられたラベル「ms:KW」、ラベル「ms:担当者」、ラベル「ms:参考文献」、ラベル「ms:著者」に対し、関心項目「サービス開発」の関心度に応じたアークスコアを設定する。   In addition, for the label “ms: KW”, the label “ms: person in charge”, the label “ms: reference”, and the label “ms: author” associated with the item of interest “service development” in the label storage unit 13, An arc score corresponding to the interest level of the interest item “service development” is set.

例えば、関心度が「大」の場合はアークスコア「1.0」を設定し、関心度が「中」の場合はアークスコア「0.1」を設定し、関心度が「小」の場合はアークスコア「0.01」を設定する。なお、関心度を数値とし、その数値である関心度に相関するアークスコアを設定してもよい。   For example, when the degree of interest is “large”, the arc score “1.0” is set, when the degree of interest is “medium”, the arc score “0.1” is set, and when the degree of interest is “small”. Sets the arc score "0.01". Note that the degree of interest may be a numerical value, and an arc score that correlates with the numerical value of interest may be set.

そのグラフGの各ノードのインスタンスをそのノードのクラスに置き換え、同一のインスタンス(クラス)をもつノードではその中の1つのみ残し、そのようにしてなるグラフに上記の各アークスコアを当てはめると、その一部は、例えば図7のようになる。   Replacing the instance of each node in the graph G with the class of the node, leaving only one of the nodes having the same instance (class), and applying the above arc scores to the graph thus formed, A part of it is as shown in FIG. 7, for example.

(ノードスコア計算)
次に、クラスタ生成装置1Aは、ノードスコア計算部15が、グラフGのノードのスコア(ノードスコアという)を計算する(S13)。
(Node score calculation)
Next, in the cluster generation device 1A, the node score calculation unit 15 calculates the score of the node of the graph G (referred to as node score) (S13).

図8は、ノードスコア計算のフローチャートを示す図である。かかる計算は、アークスコアを基にしたものであり、リンク解析ともいう。   FIG. 8 is a diagram showing a flowchart of node score calculation. Such calculation is based on the arc score and is also called link analysis.

ノードスコア計算部15は、まず、グラフGのノードに、その重要度を示すこととなる、ノードスコアの初期値「1」を設定する(S101)。   The node score calculation unit 15 first sets an initial value “1” of the node score, which indicates the importance level, to a node of the graph G (S101).

次に、各ノードにつき、例えば、PageRankのアルゴリズムを用いた、図9の式により、ノードスコアを計算する(S103)。   Next, for each node, for example, a node score is calculated by the equation of FIG. 9 using the PageRank algorithm (S103).

そして、このノードスコアで、グラフGに設定されたノードスコアの初期値を更新する(S105)。このような計算更新を、ノードスコアが収束するまで、再帰的に行う。これにより、ノードスコアが重要度を示すこととなる。   Then, the initial value of the node score set in the graph G is updated with this node score (S105). Such calculation update is performed recursively until the node score converges. As a result, the node score indicates the importance.

グラフGに各アークスコアを当てはめたグラフの一部が、例えば図10に示すようなものであった場合、同図に示すように、例えば、インスタンス「XML」をもつノードのノードスコアは0.4となる。インスタンス「Person:電々三郎」をもつノードのノードスコアは0.9となる。インスタンス「org:H3G」をもつノードのノードスコアは0.6となる。   If a part of the graph in which each arc score is applied to the graph G is as shown in FIG. 10, for example, the node score of the node having the instance “XML” is 0. 4 The node score of the node having the instance “Person: Dentsu Saburo” is 0.9. The node score of the node having the instance “org: H3G” is 0.6.

次に、クラスタ生成装置1Aは、クラスタ生成部16が、グラフGからクラスタを生成する(S15)。ここでは、グラフGでキーワードKWに等しいインスタンスをもつノードまたはグラフGでクラスCLが定義されたノードである各ノードにつき、そのノード(キーノードという)を含むクラスタを生成する。キーノードと同数のクラスタが生成される。   Next, in the cluster generation device 1A, the cluster generation unit 16 generates a cluster from the graph G (S15). Here, for each node that is a node having an instance equal to the keyword KW in the graph G or a node having the class CL defined in the graph G, a cluster including the node (referred to as a key node) is generated. As many clusters as key nodes are created.

図11は、1つのクラスタを生成するフローチャートを示す図であり、このフローチャートによるクラスタ生成が各キーノードについて同時に行われる。   FIG. 11 is a diagram showing a flowchart for generating one cluster, and cluster generation according to this flowchart is simultaneously performed for each key node.

まず、クラスタ生成部16は、グラフGから所定条件を満たさないノードを除外する(S201)。ここでは、キーノードを起点とし、起点に単一のアークで接続されたノードであり且つしきい値以下のノードスコアをもつノードを除外する(S201)。次に、除外されなかったノードを候補としてこれををクラスタに含める又は除外する処理を1候補づつ行うのだが、まず、未処理である1つの候補が、他のクラスタ生成でも候補になっているか否かを判定する(S203)。NOと判定された場合は、候補を本クラスタ生成に係るクラスタに含める(S205)。一方、YESと判定された場合は、候補と本クラスタ生成に係るキーノードとの間のアーク数、候補と他のクラスタ生成に係るキーノードとの間のアーク数を計算し、それらの中で本クラスタ生成に係るアーク数が最大であるか否かを判定する(S207)。NOと判定された場合は、候補を本クラスタ生成の候補から除外する(S209)。YESと判定された場合は、候補と他のクラスタ生成に係るキーノードとの間のアーク数の中で、候補と本クラスタ生成に係るキーノードとの間のアーク数と同数のものがあるか否かを判定する(S211)。つまり、他にもアーク数が最大のものがあるか否かを判定する(S211)。NOと判定された場合は、候補を本クラスタ生成に係るクラスタに含める(S205)。YESと判定された場合は、候補のノードスコアとその候補の本クラスタ生成に係る起点のノードスコアとの差分、候補のノードスコアとその候補の他のクラスタ生成に係る起点のノードスコアとの差分を計算し、その中で本クラスタ生成に係る差分が最小か否かを判定する(S213)。NOと判定された場合は、候補を本クラスタ生成に係るクラスタに含め候補から除外する(S209)。YESと判定された場合は、候補を本クラスタ生成に係るクラスタに含める(S205)。   First, the cluster generation unit 16 excludes nodes that do not satisfy the predetermined condition from the graph G (S201). Here, a node that has a node score starting from a key node and connected to the starting point by a single arc and having a node score equal to or lower than a threshold value is excluded (S201). Next, the process of including or excluding a node that has not been excluded as a candidate is performed one by one. First, whether an unprocessed candidate is also a candidate for generating another cluster. It is determined whether or not (S203). If NO is determined, the candidate is included in the cluster related to this cluster generation (S205). On the other hand, if the determination is YES, the number of arcs between the candidate and the key node related to the generation of the cluster and the number of arcs between the candidate and the key node related to the generation of the other cluster are calculated, It is determined whether or not the number of arcs related to generation is the maximum (S207). If NO is determined, the candidate is excluded from the candidates for generating the cluster (S209). If YES, whether or not there is the same number of arcs between the candidate and the key node related to the cluster generation as the number of arcs between the candidate and the key node related to the cluster generation Is determined (S211). That is, it is determined whether there is another arc with the maximum number of arcs (S211). If NO is determined, the candidate is included in the cluster related to this cluster generation (S205). If it is determined as YES, the difference between the candidate node score and the node score of the starting point related to the main cluster generation of the candidate, the difference between the candidate node score and the node score of the starting point related to the other cluster generation of the candidate Is calculated, and it is determined whether or not the difference related to the generation of this cluster is the smallest (S213). If it is determined NO, the candidate is included in the cluster related to this cluster generation and excluded from the candidates (S209). If YES is determined, the candidate is included in the cluster related to this cluster generation (S205).

ステップS205、S205を行ったら、次に、未処理の候補があるか否かを判定する(S215)。YESと判定された場合は、ステップS203に戻る。NOと判定された場合は、クラスタに含められたノードの1つを新たな起点とし(S217)、ステップS201に戻る。そのステップS201では、その新たな起点に単一のアークで接続されたノードであり且つしきい値以下のノードスコアをもつノードを除外する(S201)。   After performing steps S205 and S205, it is next determined whether or not there is an unprocessed candidate (S215). When it determines with YES, it returns to step S203. When it is determined NO, one of the nodes included in the cluster is set as a new starting point (S217), and the process returns to step S201. In step S201, nodes that are connected to the new starting point by a single arc and have a node score equal to or lower than the threshold value are excluded (S201).

なお、ある起点に単一のアークで接続されたノードからクラスタに含ませられたものが複数あり(便宜的にノードn11,n12という)、その中の1つ(ノードn11とする)が新たな起点となって、その起点に単一のアークで接続されたノード(ノードn111という)がクラスタに含ませられた場合は、ノードn111よりもノードn12が先に起点となる。   There are a plurality of nodes included in the cluster from nodes connected to a starting point by a single arc (referred to as nodes n11 and n12 for convenience), and one of them (referred to as node n11) is a new one. When a node connected to the starting point by a single arc (referred to as node n111) is included in the cluster, node n12 is the starting point before node n111.

図12は、2つのクラスタが生成された様子を示す図であり、アークの矢印とラベル、ノードのインスタンスについては、記載省略している。   FIG. 12 is a diagram illustrating a state in which two clusters are generated, and descriptions of arc arrows, labels, and node instances are omitted.

同図に示すように、ノードI1とキーノードKI1との間のアーク数は「3」であり、ノードI1とキーノードKI2との間のアーク数は「2」であるから、ノードI1は、キーノードKI1を含むクラスタC1でなく、キーノードKI2を含むクラスタC2に含められる。   As shown in the figure, since the number of arcs between the node I1 and the key node KI1 is “3” and the number of arcs between the node I1 and the key node KI2 is “2”, the node I1 is the key node KI1. Is included in the cluster C2 including the key node KI2.

また、同図に示すように、ノードI2とキーノードKI1との間のアーク数は「2」であり、ノードI2とキーノードKI2との間のアーク数は「2」である。また、ノードI2のノードスコア「0.6」とクラスタC1に係る起点I3のノードスコア「0.9」との差分は「0.3」であり、ノードI2のノードスコア「0.6」とクラスタC2に係る起点I4のノードスコア「0.8」との差分は「0.2」であるから、ノードI2はクラスタC2に含められる。   As shown in the figure, the number of arcs between the node I2 and the key node KI1 is “2”, and the number of arcs between the node I2 and the key node KI2 is “2”. Further, the difference between the node score “0.6” of the node I2 and the node score “0.9” of the starting point I3 related to the cluster C1 is “0.3”, and the node score “0.6” of the node I2 is Since the difference from the node score “0.8” of the starting point I4 related to the cluster C2 is “0.2”, the node I2 is included in the cluster C2.

次に、図5に戻り、出力用インタフェース生成部18が、生成された各クラスタの出力用インタフェースを生成し、これをユーザ端末2に送信し(S19)、各クラスタを表示させる(S21)。   Next, returning to FIG. 5, the output interface generation unit 18 generates an output interface for each generated cluster, transmits it to the user terminal 2 (S19), and displays each cluster (S21).

第1の実施の形態によれば、インスタンスをもつノード間がラベルをもつアークによって接続されたグラフGのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段(アークスコア設定部14)と、そのアークスコアを基にして、グラフGのノードについてのノードスコアを計算するノードスコア計算手段(ノードスコア計算部15)と、その計算されたノードスコアを基にして、グラフGのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成するクラスタ生成手段(クラスタ生成部16)とを備え、ノード間にあるアークについてのアークスコアを基に計算されたノードスコアが用いられるので、ノード間の関連性を示せるクラスタを生成することができる。   According to the first embodiment, the arc score setting means (arc score) that sets an arc score according to the designated degree of interest in the arc of the graph G in which nodes having instances are connected by an arc having a label. A setting unit 14), a node score calculation means (node score calculation unit 15) for calculating a node score for a node of the graph G based on the arc score, and a graph based on the calculated node score Cluster generation means (cluster generation unit 16) for generating a cluster that is a subgraph of G and is a subgraph that does not overlap with the rest, and a node score calculated based on an arc score for arcs between nodes Is used, it is possible to generate a cluster that can show the relationship between nodes.

また、キーノード以外のノード(中間ノード)についてのノードスコアを用いられるので、ノード間の関連性を示せるクラスタを生成することができる。   In addition, since the node score for nodes other than the key nodes (intermediate nodes) is used, a cluster that can show the relationship between the nodes can be generated.

また、図11のステップS207、S211、S213を行うので、ノード間の関連性を示せるクラスタを生成することができる。   Further, since steps S207, S211, and S213 in FIG. 11 are performed, a cluster that can indicate the relationship between the nodes can be generated.

また、関心度に応じたアークスコアを設定するので、関心度に適したクラスタを生成することができる。   In addition, since an arc score corresponding to the degree of interest is set, a cluster suitable for the degree of interest can be generated.

また、ラベル記憶部13において、関心項目に対応づけて予めラベルを記憶させ、指定された関心度に対応する関心項目に対応づけられたラベルをもつアークに、当該関心度に応じたアークスコアを設定するので、関心度に応じたクラスタを生成することができる。[第2の実施の形態]
図13は、第2の実施の形態に係るクラスタ生成装置1Bの構成図である。
In the label storage unit 13, a label is stored in advance in association with the item of interest, and an arc score corresponding to the degree of interest is given to an arc having a label associated with the item of interest corresponding to the designated degree of interest. Since it sets, the cluster according to the degree of interest can be generated. [Second Embodiment]
FIG. 13 is a configuration diagram of the cluster generation device 1B according to the second embodiment.

クラスタ生成装置1Bは、ユーザ端末2に接続され、ユーザ端末2には、表示装置3が接続されている。   The cluster generation device 1 </ b> B is connected to the user terminal 2, and the display device 3 is connected to the user terminal 2.

クラスタ生成装置1Bは、グラフデータベース11と、入力用インタフェース生成部12と、ノードスコア記憶部13Aと、ノードスコア設定部14Aと、クラスタ生成部16と、データベースインタフェース17と、出力用インタフェース生成部18とを備える。   The cluster generation device 1B includes a graph database 11, an input interface generation unit 12, a node score storage unit 13A, a node score setting unit 14A, a cluster generation unit 16, a database interface 17, and an output interface generation unit 18. With.

本実施の形態では、予め関心度の組合せのそれぞれにつき、図10に示したようなノードスコアが計算され、ノードスコア記憶部13Aが、組合せに対応づけてノードスコアを記憶している。   In this embodiment, a node score as shown in FIG. 10 is calculated in advance for each combination of interest levels, and the node score storage unit 13A stores the node score in association with the combination.

(第2の実施の形態の動作)
図14は、第2の実施の形態のシーケンス図である。
(Operation of Second Embodiment)
FIG. 14 is a sequence diagram of the second embodiment.

ステップS5までは、第1の実施の形態と同様である。   Up to step S5 is the same as in the first embodiment.

続いて、ノードスコア設定部14Aは、ユーザ端末2から送信された関心度の組合せに対応するノードスコアを選択し(S11A)、それをグラフGのノードに設定する(S11B)。具体的には、ノードスコアを含むクエリをデータベースインタフェース17に送信する(S115)ことで、ノードスコアが設定されたグラフを取得する(S116)。   Subsequently, the node score setting unit 14A selects a node score corresponding to the combination of interest levels transmitted from the user terminal 2 (S11A), and sets it as a node of the graph G (S11B). Specifically, a query including the node score is transmitted to the database interface 17 (S115), thereby obtaining a graph in which the node score is set (S116).

そして、第1の実施の形態と同様に、そのノードスコアを設定したグラフからクラスタを生成する(S15)。以降も、第1の実施の形態と同様である。   Then, as in the first embodiment, a cluster is generated from the graph in which the node score is set (S15). The subsequent steps are the same as in the first embodiment.

第2の実施の形態によれば、グラフGのアークに、指定される関心度に応じたアークスコアが設定され、そのアークスコアを基にして、グラフGのノードについてのノードスコアが計算されたときの当該ノードスコアが、対応する関心度に対応づけて予め記憶されるノードスコア記憶手段(ノードスコア記憶部13A)と、指定された関心度に対応づけてノードスコア記憶手段(13A)に記憶されたノードスコアをグラフGに設定するノードスコア設定手段(ノードスコア設定部14A)と、設定されたノードスコアを基にして、グラフGのクラスタを生成するクラスタ生成手段(16)とを備え、ノード間にあるアークについてのアークスコアを基に計算されたノードスコアが用いられるので、ノード間の関連性を示せるクラスタを生成することができる。   According to the second embodiment, an arc score corresponding to the specified degree of interest is set for the arc of the graph G, and the node score for the node of the graph G is calculated based on the arc score. The node score storage means (node score storage unit 13A) stores the node score in advance in association with the corresponding degree of interest, and stores it in the node score storage means (13A) in association with the designated degree of interest. Node score setting means (node score setting unit 14A) for setting the node score set in the graph G, and cluster generation means (16) for generating a cluster of the graph G based on the set node score, A node score calculated based on the arc score for arcs between nodes is used, so a cluster that can show the relationship between nodes is generated. Rukoto can.

また、関心度の組合せに対応するノードスコアを選択するので、関心度の組合せに適したクラスタを生成することができる。   Moreover, since the node score corresponding to the combination of interest levels is selected, a cluster suitable for the combination of interest levels can be generated.

[第3の実施の形態]
図15は、第3の実施の形態に係るクラスタ生成装置1Cの構成図である。
[Third Embodiment]
FIG. 15 is a configuration diagram of the cluster generation device 1C according to the third embodiment.

クラスタ生成装置1Cは、ユーザ端末2に接続され、ユーザ端末2には、表示装置3が接続されている。   The cluster generation device 1 </ b> C is connected to the user terminal 2, and the display device 3 is connected to the user terminal 2.

クラスタ生成装置1Cは、グラフデータベース11と、入力用インタフェース生成部12と、ラベル記憶部13と、アークスコア設定部14と、ノードスコア計算部15と、クラスタ生成部16と、データベースインタフェース17と、出力用インタフェース生成部18と、グラフ処理部19とを備える。   The cluster generation device 1C includes a graph database 11, an input interface generation unit 12, a label storage unit 13, an arc score setting unit 14, a node score calculation unit 15, a cluster generation unit 16, a database interface 17, An output interface generation unit 18 and a graph processing unit 19 are provided.

図16は、第3の実施の形態のシーケンス図である。   FIG. 16 is a sequence diagram of the third embodiment.

予めクラスタ生成装置1Cにしきい値THSが設定される。しきい値THSは、経験的にしきい値THより低くなるように設定される。   A threshold value THS is set in advance in the cluster generation device 1C. The threshold value THS is empirically set to be lower than the threshold value TH.

ステップS13までは、第1の実施の形態と同様である。   Up to step S13 is the same as in the first embodiment.

続いて、グラフ処理部19が、そのグラフの一部を削除する(S14A)。ここでは、いずれかのキーノードに少なくとも1つのアークで接続され且つしきい値THSより大きいノードスコアをもつノードを検出し、それ以外のノードとそのノードに接続されたアークを削除する。   Subsequently, the graph processing unit 19 deletes a part of the graph (S14A). Here, a node connected to any key node with at least one arc and having a node score greater than the threshold value THS is detected, and the other nodes and arcs connected to the node are deleted.

そして、そのグラフについてステップS13と同様のノードスコア計算を行う(S14B)。以降も、第1の実施の形態と同様である。   And the node score calculation similar to step S13 is performed about the graph (S14B). The subsequent steps are the same as in the first embodiment.

第3の実施の形態によれば、インスタンスをもつノード間がラベルをもつアークによって接続されたグラフGのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段(14)と、そのアークスコアを基にして、グラフGのノードについてのノードスコアを計算する第1のノードスコア計算手段(ステップS13が該当する)と、そのノードスコアを基にして、グラフGの一部を削除するグラフ処理手段(グラフ処理部19)と、一部を削除されたグラフのアークに設定されたアークスコアを基にして、当該グラフのノードについての新たなノードスコアを計算する第2のノードスコア計算手段(ステップS14Bが該当する)と、そのノードスコアを基にして、グラフGのクラスタを生成するクラスタ生成手段(16)とを備え、ノード間にあるアークについてのアークスコアを基に計算されたノードスコアが用いられるので、ノード間の関連性を示せるクラスタを生成することができる。   According to the third embodiment, the arc score setting means (14) for setting an arc score corresponding to the designated degree of interest in the arc of the graph G in which nodes having instances are connected by arcs having labels. And a first node score calculation means for calculating a node score for a node of the graph G based on the arc score (corresponding to step S13), and a part of the graph G based on the node score. And a graph processing means (graph processing unit 19) for deleting the second and a new node score for the node of the graph based on the arc score set for the arc of the partially deleted graph Node score calculating means (corresponding to step S14B) and cluster generating means for generating a cluster of the graph G based on the node score 16) and provided with a so calculated node score is used based on the arc score for arc located between nodes, it is possible to generate a cluster can show the relationship between nodes.

また、キーノードを含む部分以外を削除した後のグラフでノードスコアを計算するので、キーノードを含む部分でのノード間の関連性を示せるクラスタを生成することができる。   Further, since the node score is calculated from the graph after deleting the part other than the part including the key node, it is possible to generate a cluster that can show the relationship between the nodes in the part including the key node.

[第4の実施の形態]
図17は、第4の実施の形態に係るクラスタ生成装置1Dの構成図である。
[Fourth Embodiment]
FIG. 17 is a configuration diagram of a cluster generation device 1D according to the fourth embodiment.

クラスタ生成装置1Dは、ユーザ端末2に接続され、ユーザ端末2には、表示装置3が接続されている。   The cluster generation device 1 </ b> D is connected to the user terminal 2, and the display device 3 is connected to the user terminal 2.

クラスタ生成装置1Dは、グラフデータベース11と、入力用インタフェース生成部12と、ラベル記憶部13と、ノードスコア記憶部13Aと、アークスコア設定部14、ノードスコア設定部14Aと、ノードスコア計算部15と、クラスタ生成部16と、データベースインタフェース17と、出力用インタフェース生成部18と、グラフ処理部19とを備える。   The cluster generation device 1D includes a graph database 11, an input interface generation unit 12, a label storage unit 13, a node score storage unit 13A, an arc score setting unit 14, a node score setting unit 14A, and a node score calculation unit 15 A cluster generation unit 16, a database interface 17, an output interface generation unit 18, and a graph processing unit 19.

(第4の実施の形態の動作)
第4の実施の形態では、クラスタ生成装置1Dに、しきい値THより低くなるようにしきい値THSが予め設定される。
(Operation of the fourth embodiment)
In the fourth embodiment, threshold value THS is preset in cluster generation device 1D so as to be lower than threshold value TH.

図18は、第4の実施の形態のシーケンス図である。   FIG. 18 is a sequence diagram of the fourth embodiment.

ステップS11Bまでは、第2の実施の形態と同様である。   Steps up to step S11B are the same as in the second embodiment.

続いて、グラフ処理部19が、第3の実施の形態と同様なしきい値THSを用いた判定により、そのグラフの一部を削除する(S14A)。そして、一部を削除したグラフについて、第1の実施の形態のステップS11と同様なアークスコア設定を行い(S12)、続いて、当該グラフについて、第1の実施の形態のステップS13と同様なノードスコア計算を行う(S14B)。以降も、第1の実施の形態と同様である。   Subsequently, the graph processing unit 19 deletes a part of the graph by the determination using the threshold THS similar to that in the third embodiment (S14A). Then, the same arc score setting as in step S11 of the first embodiment is performed for the graph from which a part has been deleted (S12). Subsequently, the same graph as in step S13 of the first embodiment is performed for the graph. Node score calculation is performed (S14B). The subsequent steps are the same as in the first embodiment.

第4の実施の形態によれば、グラフGのアークに、指定される関心度に応じたアークスコアが設定され、そのアークスコアを基にして、グラフGのノードについてのノードスコアが計算されたときの当該ノードスコアが、対応する関心度に対応づけて予め記憶されるノードスコア記憶手段(13A)と、指定された関心度に対応づけてノードスコア記憶手段(13A)に記憶されたノードスコアをグラフGに設定するノードスコア設定手段(14A)と、その設定されたノードスコアを基にして、グラフの一部を削除するグラフ処理手段(19)と、一部を削除されたグラフのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段(14)と、一部を削除されたグラフのアークに設定されたアークスコアを基にして、当該グラフのノードについての新たなノードスコアを計算するノードスコア計算手段(15)と、そのノードスコアを基にして、グラフGのクラスタを生成するクラスタ生成手段(16)とを備え、ノード間にあるアークについてのアークスコアを基に計算されたノードスコアが用いられるので、ノード間の関連性を示せるクラスタを生成することができる。   According to the fourth embodiment, an arc score corresponding to the designated degree of interest is set for the arc of the graph G, and the node score for the node of the graph G is calculated based on the arc score. The node score stored in the node score storage means (13A) is stored in advance in association with the corresponding degree of interest, and the node score storage means (13A) is stored in the node score storage means (13A) in association with the designated degree of interest. A node score setting means (14A) for setting a graph G, a graph processing means (19) for deleting a part of the graph based on the set node score, and an arc of the graph from which a part is deleted Based on the arc score setting means (14) for setting the arc score according to the specified degree of interest, and the arc score set for the arc of the partially deleted graph A node score calculation means (15) for calculating a new node score for the node of the graph, and a cluster generation means (16) for generating a cluster of the graph G based on the node score. Since the node score calculated based on the arc score for the arc in between is used, a cluster that can show the relationship between the nodes can be generated.

また、関心度の組合せに対応するノードスコアを選択するので、関心度の組合せに適したクラスタを生成することができる。   Moreover, since the node score corresponding to the combination of interest levels is selected, a cluster suitable for the combination of interest levels can be generated.

また、キーノードを含む部分以外を削除した後のグラフでノードスコアを計算するので、キーノードを含む部分でのノード間の関連性を示せるクラスタを生成することができる。   Further, since the node score is calculated from the graph after deleting the part other than the part including the key node, it is possible to generate a cluster that can show the relationship between the nodes in the part including the key node.

[第5の実施の形態]
図19は、第5の実施の形態に係るクラスタ生成装置1Eの構成図である。
[Fifth Embodiment]
FIG. 19 is a configuration diagram of a cluster generation device 1E according to the fifth embodiment.

グラフ検索装置1Eは、ユーザ端末2に接続され、ユーザ端末2には、表示装置3が接続されている。   The graph search device 1E is connected to a user terminal 2, and a display device 3 is connected to the user terminal 2.

クラスタ生成装置1Eは、グラフデータベース11と、パターンデータベース11Aと、入力用インタフェース生成部12と、ラベル記憶部13と、アークスコア設定部14と、パターン検索部14Bと、ノードスコア計算部15と、クラスタ生成部16と、データベースインタフェース17と、出力用インタフェース生成部18とを備える。   The cluster generation device 1E includes a graph database 11, a pattern database 11A, an input interface generation unit 12, a label storage unit 13, an arc score setting unit 14, a pattern search unit 14B, a node score calculation unit 15, A cluster generation unit 16, a database interface 17, and an output interface generation unit 18 are provided.

パターンデータベース11Aには、グラフGからサブグラフを検索するためのパターンが記憶される。   The pattern database 11A stores a pattern for searching for a subgraph from the graph G.

(パターンの説明)
ここでパターンについて説明する。
(Description of pattern)
Here, the pattern will be described.

パターンは、グラフデータベース11に記憶されるデータ群(グラフG)の一部をなすデータ群と同様なものであり、それを図20のようにグラフ化できるので、便宜的にはグラフと言えるが、パターンは表示するものではなく、表示されるグラフの検索に使用されるものである。パスパターンはパスを検索するパターンであり、サブグラフパターンはサブグラフを検索するものである。   The pattern is the same as the data group forming a part of the data group (graph G) stored in the graph database 11 and can be graphed as shown in FIG. The pattern is not displayed but is used for searching the displayed graph. The path pattern is a pattern for searching for a path, and the subgraph pattern is for searching for a subgraph.

パスパターンは、例えば、同図のようなグラフ(パス)である。   The path pattern is, for example, a graph (path) as shown in FIG.

パターンはグラフと同様に、実際にはデータ群であるが、それを逐一説明するのは冗長であるから、パターンの説明はグラフ化されたもので行う。   Like a graph, a pattern is actually a data group, but since it is redundant to explain each pattern, the pattern is explained in a graph.

一般的にパターンでは、ノードやアークの一部はインスタンスやラベルをもち、残りはそれらをもたない。そして、インスタンスやラベルをもたないノードやアークには変数が設定される。変数は、同図に示すように、?とそれに後続する単語からなる。   In general, in a pattern, some nodes and arcs have instances and labels, and the rest do not. Variables are set for nodes and arcs that do not have instances or labels. As shown in the figure, the variables are Followed by a word.

また、一般的にパターンでは、必要があれば、変数が設定された一部のノードに、そのパターンにより検索されるグラフにおける、同位置のノードがもつインスタンスの上位概念を示すクラスが予め定義される。   In general, in a pattern, if necessary, a class indicating a high-level concept of an instance of a node at the same position in a graph searched by the pattern is defined in advance for some nodes set with variables. The

同図のパスパターンでは、キーワードKW「セマンティックweb」がインスタンスであるノードを一方端とすると、他方端のノードにクラスCL「Person:人」が定義されている。   In the path pattern shown in the figure, when a node having the keyword KW “semantic web” as an instance is one end, a class CL “Person: person” is defined in the other end node.

このようなパターンによって、あるグラフから検索されるサブグラフは、以下の条件を備えるものである。   A subgraph retrieved from a certain graph by such a pattern has the following conditions.

つまり、検索されるのは、(1)そのグラフまたはそのサブグラフであって、(2)パターンの構造を過不足なく有し、(3)パターン内でのインスタンスやラベルを過不足なく有し、つまりパターン内でのインスタンスやラベルをもつノードやアークの位置に等しい位置にあるノードやアークが当該インスタンスに等しいインスタンスやラベルを有し、(4)場合によってはパターンに含まれるクラスが定義されたノードの位置に等しい位置にあるノードが当該クラスの下位概念であるインスタンスを有するものである。   In other words, what is searched is (1) the graph or its subgraph, (2) having a pattern structure without excess or deficiency, (3) having instances or labels within the pattern without deficiency, In other words, nodes and arcs at positions equal to the positions of nodes and arcs with instances and labels in the pattern have instances and labels equal to the instances, and (4) in some cases, classes included in the pattern are defined A node at a position equal to the position of the node has an instance that is a subordinate concept of the class.

なお、パターンにより、このようにしてサブグラフを検索することを、パターンにマッチするサブグラフを検索するという。   Note that searching for a subgraph in this way by pattern is referred to as searching for a subgraph that matches the pattern.

図21は、第5の実施の形態のシーケンス図である。   FIG. 21 is a sequence diagram of the fifth embodiment.

ステップS5までは、第1の実施の形態と同様である。   Up to step S5 is the same as in the first embodiment.

次に、キーワードKWに等しいインスタンスをもつノードをもつパターンや、グラフGでクラスCLが定義されたノードのインスタンスに等しいインスタンスをもつノードをもつパターンや、その両方をもつパターンを検索する(S11C)。   Next, a pattern having a node having an instance equal to the keyword KW, a pattern having a node having an instance equal to an instance of a node whose class CL is defined in the graph G, and a pattern having both are searched (S11C). .

次に、アークスコア設定部14が、グラフGでそのパターンにマッチするサブグラフにおけるアークに対し、第1の実施の形態のステップS11と同様に、アークスコアを設定する(S12)。具体的には、パターンの内容やアークスコアを含むクエリをデータベースインタフェース17に送信する(S12A)ことで、グラフGでそのパターンにマッチするサブグラフであってアークスコアが設定されたグラフを取得する(S12B)。   Next, the arc score setting unit 14 sets an arc score for the arc in the subgraph that matches the pattern in the graph G, as in step S11 of the first embodiment (S12). Specifically, by sending a query including the contents of the pattern and the arc score to the database interface 17 (S12A), a graph that is a sub-graph that matches the pattern in the graph G and is set with the arc score is acquired ( S12B).

そして、そのグラフについて、第1の実施の形態と同様のノードスコア計算を行う(S13)。以降も、第1の実施の形態と同様である。   And the node score calculation similar to 1st Embodiment is performed about the graph (S13). The subsequent steps are the same as in the first embodiment.

第5の実施の形態によれば、インスタンスをもつノード間がラベルをもつアークによって接続されたグラフGのサブグラフを検索する際に用いられるパターンが記憶されるパターンデータベース11Aと、指定された条件にマッチするパターンを検索するパターン検索手段(パターン検索部14B)と、検索されたパターンにマッチするサブグラフのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段(14)と、そのアークスコアを基にして、サブグラフのノードについてのノードスコアを計算するノードスコア計算手段(15)と、そのノードスコアを基にして、サブグラフのクラスタを生成するクラスタ生成手段(16)とを備え、ノード間にあるアークについてのアークスコアを基に計算されたノードスコアが用いられるので、ノード間の関連性を示せるクラスタを生成することができる。   According to the fifth embodiment, the pattern database 11A that stores a pattern used when searching a subgraph of the graph G in which nodes having instances are connected by arcs having labels is stored in the specified condition. A pattern search unit (pattern search unit 14B) for searching for a matching pattern, and an arc score setting unit (14) for setting an arc score corresponding to the designated degree of interest in the arc of the subgraph that matches the searched pattern. A node score calculation means (15) for calculating a node score for a node of the subgraph based on the arc score, and a cluster generation means (16) for generating a cluster of the subgraph based on the node score. Prepared and no calculated based on arc score for arcs between nodes Because the score is used, it is possible to produce a cluster of can show the relationship between nodes.

第1の実施の形態に係るクラスタ生成装置1Aの構成図である。1 is a configuration diagram of a cluster generation device 1A according to a first embodiment. FIG. グラフGの一部を例示した図である。6 is a diagram illustrating a part of a graph G. FIG. グラフGを表示するためのデータ群の一部を例示した図である。6 is a diagram illustrating a part of a data group for displaying a graph G. FIG. ラベル記憶部13の記憶内容を示す図である。It is a figure which shows the memory content of the label memory | storage part. 第1の実施の形態のシーケンス図である。It is a sequence diagram of a 1st embodiment. 表示された入力用インタフェースを例示した図である。It is the figure which illustrated the displayed interface for input. アークスコアの一部をグラフに当てはめた図である。It is the figure which applied a part of arc score to the graph. ノードスコア計算のフローチャートを示す図である。It is a figure which shows the flowchart of node score calculation. ノードスコアの計算式を示した図である。It is the figure which showed the calculation formula of a node score. ノードスコア計算の例にしたグラフを示す図である。It is a figure which shows the graph made into the example of node score calculation. 1つのクラスタを生成するフローチャートを示す図The figure which shows the flowchart which produces | generates one cluster 2つのクラスタが生成された様子を示す図である。It is a figure which shows a mode that two clusters were produced | generated. 第2の実施の形態に係るクラスタ生成装置1Bの構成図である。It is a block diagram of the cluster production | generation apparatus 1B which concerns on 2nd Embodiment. 第2の実施の形態のシーケンス図である。It is a sequence diagram of a 2nd embodiment. 第3の実施の形態に係るクラスタ生成装置1Cの構成図である。It is a block diagram of the cluster production | generation apparatus 1C which concerns on 3rd Embodiment. 第3の実施の形態のシーケンス図である。It is a sequence diagram of a third embodiment. 第4の実施の形態に係るクラスタ生成装置1Dの構成図である。It is a block diagram of the cluster production | generation apparatus 1D which concerns on 4th Embodiment. 第4の実施の形態のシーケンス図である。It is a sequence diagram of a fourth embodiment. 第5の実施の形態に係るクラスタ生成装置1Eの構成図である。It is a block diagram of the cluster production | generation apparatus 1E which concerns on 5th Embodiment. パスパターンを例示した図である。It is the figure which illustrated the path pattern. 第5の実施の形態のシーケンス図である。It is a sequence diagram of a 5th embodiment.

符号の説明Explanation of symbols

1A、1B、1C、1D、1E:クラスタ生成装置
11 グラフデータベース
11A パターンデータベース
13 ラベル記憶部
13A ノードスコア記憶部
14 アークスコア設定部
14A ノードスコア設定部
15 ノードスコア計算部
16 クラスタ生成部
19 グラフ処理部
1A, 1B, 1C, 1D, 1E: Cluster generation device 11 Graph database 11A Pattern database 13 Label storage unit 13A Node score storage unit 14 Arc score setting unit 14A Node score setting unit 15 Node score calculation unit 16 Cluster generation unit 19 Graph processing Part

Claims (11)

インスタンスをもつノード間がラベルをもつアークによって接続されたグラフのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段と、
前記アークスコアを基にして、前記グラフのノードについてのノードスコアを計算するノードスコア計算手段と、
前記計算されたノードスコアを基にして、前記グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成するクラスタ生成手段と
を備え
前記クラスタ生成手段は、
複数の前記クラスタのそれぞれに含まれるように予め設定された起点のノードのそれぞれと、当該各クラスタに含ませる候補である1つのノードとの間のアーク数を計算し、最も多い当該アーク数に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ、
最も多い当該アーク数に対応するクラスタが複数の場合は、当該クラスタの起点のノードのそれぞれのノードスコアと、当該候補のノードのノードスコアとの差分を計算し、最も小さい当該差分に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ
ことを特徴とするクラスタ生成装置。
An arc score setting means for setting an arc score corresponding to a specified degree of interest in an arc of a graph in which nodes having instances are connected by an arc having a label;
Node score calculation means for calculating a node score for a node of the graph based on the arc score;
Cluster generation means for generating a cluster that is a subgraph of the graph and is a subgraph that does not overlap with the rest based on the calculated node score ;
The cluster generation means includes
Calculate the number of arcs between each of the starting nodes preset to be included in each of the plurality of clusters and one node that is a candidate for inclusion in each of the clusters, and obtain the largest number of arcs If there is one corresponding cluster, include the candidate node in the cluster,
If there are multiple clusters corresponding to the largest number of arcs, the difference between the node score of each node at the starting point of the cluster and the node score of the candidate node is calculated, and the cluster corresponding to the smallest difference If is one cluster generating device, wherein a node of the candidate Ru contained in the cluster.
インスタンスをもつノード間がラベルをもつアークによって接続されたグラフのアークに、指定される関心度に応じたアークスコアが設定され、当該アークスコアを基にして、前記グラフのノードについてのノードスコアが計算されたときの当該ノードスコアが、対応する関心度に対応づけて予め記憶されるノードスコア記憶手段と、
指定された関心度に対応づけて前記ノードスコア記憶手段に記憶されたノードスコアを前記グラフに設定するノードスコア設定手段と、
前記設定されたノードスコアを基にして、前記グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成するクラスタ生成手段と
を備え
前記クラスタ生成手段は、
複数の前記クラスタのそれぞれに含まれるように予め設定された起点のノードのそれぞれと、当該各クラスタに含ませる候補である1つのノードとの間のアーク数を計算し、最も多い当該アーク数に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ、
最も多い当該アーク数に対応するクラスタが複数の場合は、当該クラスタの起点のノードのそれぞれのノードスコアと、当該候補のノードのノードスコアとの差分を計算し、最も小さい当該差分に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ
ことを特徴とするクラスタ生成装置。
An arc score corresponding to a specified degree of interest is set to an arc of a graph in which nodes having instances are connected by an arc having a label. Based on the arc score, a node score for the node of the graph is determined based on the arc score. A node score storage means in which the calculated node score is stored in advance in association with the corresponding degree of interest;
Node score setting means for setting the node score stored in the node score storage means in association with the designated degree of interest in the graph;
Cluster generating means for generating a cluster that is a sub-graph of the graph based on the set node score and is a sub-graph that does not overlap with the rest , and
The cluster generation means includes
Calculate the number of arcs between each of the starting nodes preset to be included in each of the plurality of clusters and one node that is a candidate for inclusion in each of the clusters, and obtain the largest number of arcs If there is one corresponding cluster, include the candidate node in the cluster,
If there are multiple clusters corresponding to the largest number of arcs, the difference between the node score of each node at the starting point of the cluster and the node score of the candidate node is calculated, and the cluster corresponding to the smallest difference If is one cluster generating device, wherein a node of the candidate Ru contained in the cluster.
インスタンスをもつノード間がラベルをもつアークによって接続されたグラフのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段と、
前記アークスコアを基にして、前記グラフのノードについてのノードスコアを計算する第1のノードスコア計算手段と、
前記ノードスコアを基にして、前記グラフの一部を削除するグラフ処理手段と、
一部を削除された前記グラフのアークに設定されたアークスコアを基にして、当該グラフのノードについての新たなノードスコアを計算する第2のノードスコア計算手段と、
当該ノードスコアを基にして、当該グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成するクラスタ生成手段と
を備え
前記クラスタ生成手段は、
複数の前記クラスタのそれぞれに含まれるように予め設定された起点のノードのそれぞれと、当該各クラスタに含ませる候補である1つのノードとの間のアーク数を計算し、最も多い当該アーク数に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ、
最も多い当該アーク数に対応するクラスタが複数の場合は、当該クラスタの起点のノードのそれぞれのノードスコアと、当該候補のノードのノードスコアとの差分を計算し、最も小さい当該差分に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ
ことを特徴とするクラスタ生成装置。
An arc score setting means for setting an arc score corresponding to a specified degree of interest in an arc of a graph in which nodes having instances are connected by an arc having a label;
First node score calculation means for calculating a node score for a node of the graph based on the arc score;
Graph processing means for deleting a part of the graph based on the node score;
Second node score calculation means for calculating a new node score for a node of the graph based on the arc score set for the arc of the graph from which a part has been deleted;
Cluster generating means for generating a cluster that is a sub-graph of the graph based on the node score and does not overlap with the rest , and
The cluster generation means includes
Calculate the number of arcs between each of the starting nodes preset to be included in each of the plurality of clusters and one node that is a candidate for inclusion in each of the clusters, and obtain the largest number of arcs If there is one corresponding cluster, include the candidate node in the cluster,
If there are multiple clusters corresponding to the largest number of arcs, the difference between the node score of each node at the starting point of the cluster and the node score of the candidate node is calculated, and the cluster corresponding to the smallest difference If is one cluster generating device, wherein a node of the candidate Ru contained in the cluster.
インスタンスをもつノード間がラベルをもつアークによって接続されたグラフのアークに、指定される関心度に応じたアークスコアが設定され、当該アークスコアを基にして、前記グラフのノードについてのノードスコアが計算されたときの当該ノードスコアが、対応する関心度に対応づけて予め記憶されるノードスコア記憶手段と、
指定された関心度に対応づけて前記ノードスコア記憶手段に記憶されたノードスコアを前記グラフに設定するノードスコア設定手段と、
前記設定されたノードスコアを基にして、前記グラフの一部を削除するグラフ処理手段と、
一部を削除された前記グラフのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段と、
一部を削除された前記グラフのアークに設定されたアークスコアを基にして、当該グラフのノードについての新たなノードスコアを計算するノードスコア計算手段と、
当該ノードスコアを基にして、当該グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成するクラスタ生成手段と
を備え
前記クラスタ生成手段は、
複数の前記クラスタのそれぞれに含まれるように予め設定された起点のノードのそれぞれと、当該各クラスタに含ませる候補である1つのノードとの間のアーク数を計算し、最も多い当該アーク数に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ、
最も多い当該アーク数に対応するクラスタが複数の場合は、当該クラスタの起点のノードのそれぞれのノードスコアと、当該候補のノードのノードスコアとの差分を計算し、最も小さい当該差分に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ
ことを特徴とするクラスタ生成装置。
An arc score corresponding to a specified degree of interest is set to an arc of a graph in which nodes having instances are connected by an arc having a label. Based on the arc score, a node score for the node of the graph is determined based on the arc score. A node score storage means in which the calculated node score is stored in advance in association with the corresponding degree of interest;
Node score setting means for setting the node score stored in the node score storage means in association with the designated degree of interest in the graph;
Graph processing means for deleting a part of the graph based on the set node score;
Arc score setting means for setting an arc score according to the specified degree of interest in the arc of the graph from which a part has been deleted;
Node score calculation means for calculating a new node score for a node of the graph based on the arc score set for the arc of the graph from which a part has been deleted;
Cluster generating means for generating a cluster that is a sub-graph of the graph based on the node score and does not overlap with the rest , and
The cluster generation means includes
Calculate the number of arcs between each of the starting nodes preset to be included in each of the plurality of clusters and one node that is a candidate for inclusion in each of the clusters, and obtain the largest number of arcs If there is one corresponding cluster, include the candidate node in the cluster,
If there are multiple clusters corresponding to the largest number of arcs, the difference between the node score of each node at the starting point of the cluster and the node score of the candidate node is calculated, and the cluster corresponding to the smallest difference If is one cluster generating device, wherein a node of the candidate Ru contained in the cluster.
インスタンスをもつノード間がラベルをもつアークによって接続されたグラフのサブグラフを検索する際に用いられるパターンが記憶されるパターンデータベースと、
指定された条件にマッチするパターンを検索するパターン検索手段と、
検索されたパターンにマッチするサブグラフのアークに、指定された関心度に応じたアークスコアを設定するアークスコア設定手段と、
前記アークスコアを基にして、前記サブグラフのノードについてのノードスコアを計算するノードスコア計算手段と、
前記ノードスコアを基にして、前記サブグラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成するクラスタ生成手段と
を備え
前記クラスタ生成手段は、
複数の前記クラスタのそれぞれに含まれるように予め設定された起点のノードのそれぞれと、当該各クラスタに含ませる候補である1つのノードとの間のアーク数を計算し、最も多い当該アーク数に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ、
最も多い当該アーク数に対応するクラスタが複数の場合は、当該クラスタの起点のノードのそれぞれのノードスコアと、当該候補のノードのノードスコアとの差分を計算し、最も小さい当該差分に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ
ことを特徴とするクラスタ生成装置。
A pattern database that stores patterns used to search subgraphs of a graph in which nodes having instances are connected by arcs having labels;
A pattern search means for searching for a pattern that matches a specified condition;
Arc score setting means for setting an arc score according to the specified degree of interest to the arc of the subgraph that matches the searched pattern;
Node score calculating means for calculating a node score for the node of the subgraph based on the arc score;
Based on the node score, and a cluster generation means for generating a cluster which is non-overlapping sub-graph of a subgraph and is and the remaining part of the subgraph,
The cluster generation means includes
Calculate the number of arcs between each of the starting nodes preset to be included in each of the plurality of clusters and one node that is a candidate for inclusion in each of the clusters, and obtain the largest number of arcs If there is one corresponding cluster, include the candidate node in the cluster,
If there are multiple clusters corresponding to the largest number of arcs, the difference between the node score of each node at the starting point of the cluster and the node score of the candidate node is calculated, and the cluster corresponding to the smallest difference If is one cluster generating device, wherein a node of the candidate Ru contained in the cluster.
指定される関心度に対応する関心項目に対応づけて予めラベルが記憶されるラベル記憶手段を備え、
前記アークスコア設定手段は、指定された関心度に対応する関心項目に前記ラベル記憶手段で対応づけられたラベルをもつアークに、当該指定された関心度に応じたアークスコアを設定する
ことを特徴とする請求項1、3、4、5のいずれかに記載のクラスタ生成装置。
Label storage means for storing a label in advance in association with an item of interest corresponding to the specified degree of interest;
The arc score setting means sets an arc score corresponding to the designated degree of interest for an arc having a label associated with the item of interest corresponding to the designated degree of interest by the label storage means. The cluster generation device according to any one of claims 1, 3, 4, and 5 .
請求項1記載のクラスタ生成装置の前記アークスコア設定手段が、前記グラフのアークに、指定された関心度に応じたアークスコアを設定し、
当該クラスタ生成装置の前記ノードスコア計算手段が、前記アークスコアを基にして、前記グラフのノードについてのノードスコアを計算し、
当該クラスタ生成装置の前記クラスタ生成手段が、前記計算されたノードスコアを基にして、前記グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成する際に、
前記クラスタ生成手段は、
複数の前記クラスタのそれぞれに含まれるように予め設定された起点のノードのそれぞれと、当該各クラスタに含ませる候補である1つのノードとの間のアーク数を計算し、最も多い当該アーク数に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ、
最も多い当該アーク数に対応するクラスタが複数の場合は、当該クラスタの起点のノードのそれぞれのノードスコアと、当該候補のノードのノードスコアとの差分を計算し、最も小さい当該差分に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませる
ことを特徴とするクラスタ生成方法。
The arc score setting means of the cluster generation device according to claim 1 sets an arc score corresponding to a designated degree of interest in the arc of the graph,
The node score calculation means of the cluster generation device calculates a node score for a node of the graph based on the arc score,
When the cluster generation unit of the cluster generation device generates a cluster that is a sub-graph of the graph and a sub-graph with no overlap with the rest based on the calculated node score ,
The cluster generation means includes
Calculate the number of arcs between each of the starting nodes preset to be included in each of the plurality of clusters and one node that is a candidate for inclusion in each of the clusters, and obtain the largest number of arcs If there is one corresponding cluster, include the candidate node in the cluster,
If there are multiple clusters corresponding to the largest number of arcs, the difference between the node score of each node at the starting point of the cluster and the node score of the candidate node is calculated, and the cluster corresponding to the smallest difference Is a cluster generation method , wherein the candidate node is included in the cluster.
請求項2記載のクラスタ生成装置の前記ノードスコア設定手段が、指定された関心度に対応づけて前記ノードスコア記憶手段に記憶されたノードスコアを前記グラフに設定し、
当該クラスタ生成装置のクラスタ生成手段が、前記設定されたノードスコアを基にして、前記グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成する際に、
前記クラスタ生成手段は、
複数の前記クラスタのそれぞれに含まれるように予め設定された起点のノードのそれぞれと、当該各クラスタに含ませる候補である1つのノードとの間のアーク数を計算し、最も多い当該アーク数に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ、
最も多い当該アーク数に対応するクラスタが複数の場合は、当該クラスタの起点のノードのそれぞれのノードスコアと、当該候補のノードのノードスコアとの差分を計算し、最も小さい当該差分に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませる
ことを特徴とするクラスタ生成方法。
The node score setting unit of the cluster generation device according to claim 2 sets a node score stored in the node score storage unit in association with a designated degree of interest in the graph,
When the cluster generation unit of the cluster generation device generates a cluster that is a sub-graph of the graph and a sub-graph that does not overlap with the rest based on the set node score ,
The cluster generation means includes
Calculate the number of arcs between each of the starting nodes preset to be included in each of the plurality of clusters and one node that is a candidate for inclusion in each of the clusters, and obtain the largest number of arcs If there is one corresponding cluster, include the candidate node in the cluster,
If there are multiple clusters corresponding to the largest number of arcs, the difference between the node score of each node at the starting point of the cluster and the node score of the candidate node is calculated, and the cluster corresponding to the smallest difference Is a cluster generation method , wherein the candidate node is included in the cluster.
請求項3記載のクラスタ生成装置の前記アークスコア設定手段が、前記グラフのアークに、指定された関心度に応じたアークスコアを設定し、
当該クラスタ生成装置の第1のノードスコア計算手段が、前記アークスコアを基にして、前記グラフのノードについてのノードスコアを計算し、
当該クラスタ生成装置のグラフ処理手段が、前記ノードスコアを基にして、前記グラフの一部を削除し、
当該クラスタ生成装置の第2のノードスコア計算手段が、一部を削除された前記グラフのアークに設定されたアークスコアを基にして、当該グラフのノードについての新たなノードスコアを計算し、
当該クラスタ生成装置のクラスタ生成手段が、当該ノードスコアを基にして、当該グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成する際に、
前記クラスタ生成手段は、
複数の前記クラスタのそれぞれに含まれるように予め設定された起点のノードのそれぞれと、当該各クラスタに含ませる候補である1つのノードとの間のアーク数を計算し、最も多い当該アーク数に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ、
最も多い当該アーク数に対応するクラスタが複数の場合は、当該クラスタの起点のノードのそれぞれのノードスコアと、当該候補のノードのノードスコアとの差分を計算し、最も小さい当該差分に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませる
ことを特徴とするクラスタ生成方法。
The arc score setting means of the cluster generation device according to claim 3 sets an arc score corresponding to a designated degree of interest in the arc of the graph,
The first node score calculation means of the cluster generation device calculates a node score for the node of the graph based on the arc score,
The graph processing means of the cluster generation device deletes a part of the graph based on the node score,
The second node score calculation means of the cluster generation device calculates a new node score for the node of the graph based on the arc score set for the arc of the graph from which a part has been deleted,
When the cluster generation means of the cluster generation device generates a cluster that is a subgraph of the graph and a subgraph that does not overlap with the rest, based on the node score ,
The cluster generation means includes
Calculate the number of arcs between each of the starting nodes preset to be included in each of the plurality of clusters and one node that is a candidate for inclusion in each of the clusters, and obtain the largest number of arcs If there is one corresponding cluster, include the candidate node in the cluster,
If there are multiple clusters corresponding to the largest number of arcs, the difference between the node score of each node at the starting point of the cluster and the node score of the candidate node is calculated, and the cluster corresponding to the smallest difference Is a cluster generation method , wherein the candidate node is included in the cluster.
請求項4記載のクラスタ生成装置の前記ノードスコア設定手段が、指定された関心度に対応づけて前記ノードスコア記憶手段に記憶されたノードスコアを前記グラフに設定し、
当該クラスタ生成装置のグラフ処理手段が、前記設定されたノードスコアを基にして、前記グラフの一部を削除し、
当該クラスタ生成装置のアークスコア設定手段が、一部を削除された前記グラフのアークに、指定された関心度に応じたアークスコアを設定し、
当該クラスタ生成装置のノードスコア計算手段が、一部を削除された前記グラフのアークに設定されたアークスコアを基にして、当該グラフのノードについての新たなノードスコアを計算し、
当該クラスタ生成装置のクラスタ生成手段が、当該ノードスコアを基にして、当該グラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成する
際に、
前記クラスタ生成手段は、
複数の前記クラスタのそれぞれに含まれるように予め設定された起点のノードのそれぞれと、当該各クラスタに含ませる候補である1つのノードとの間のアーク数を計算し、最も多い当該アーク数に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ、
最も多い当該アーク数に対応するクラスタが複数の場合は、当該クラスタの起点のノードのそれぞれのノードスコアと、当該候補のノードのノードスコアとの差分を計算し、最も小さい当該差分に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませる
ことを特徴とするクラスタ生成方法。
The node score setting unit of the cluster generation device according to claim 4 sets a node score stored in the node score storage unit in association with a designated degree of interest in the graph,
The graph processing means of the cluster generation device deletes a part of the graph based on the set node score,
The arc score setting means of the cluster generation device sets an arc score corresponding to the designated degree of interest in the arc of the graph from which a part has been deleted,
The node score calculation means of the cluster generation device calculates a new node score for the node of the graph based on the arc score set for the arc of the graph from which a part has been deleted,
Based on the node score, the cluster generation unit of the cluster generation device generates a cluster that is a subgraph of the graph and has no overlap with the remaining portion.
When
The cluster generation means includes
Calculate the number of arcs between each of the starting nodes preset to be included in each of the plurality of clusters and one node that is a candidate for inclusion in each of the clusters, and obtain the largest number of arcs If there is one corresponding cluster, include the candidate node in the cluster,
If there are multiple clusters corresponding to the largest number of arcs, the difference between the node score of each node at the starting point of the cluster and the node score of the candidate node is calculated, and the cluster corresponding to the smallest difference Is a cluster generation method , wherein the candidate node is included in the cluster.
請求項5記載のクラスタ生成装置の前記パターン検索手段が、指定された条件にマッチするパターンを前記パターンデータベースから検索し、
当該クラスタ生成装置のアークスコア設定手段が、検索されたパターンにマッチするサブグラフのアークに、指定された関心度に応じたアークスコアを設定し、
当該クラスタ生成装置のノードスコア計算手段が、前記アークスコアを基にして、前記サブグラフのノードについてのノードスコアを計算し、
当該クラスタ生成装置のクラスタ生成手段が、前記ノードスコアを基にして、前記サブグラフのサブグラフであり且つ残り部分との重複のないサブグラフであるクラスタを生成する際に、
前記クラスタ生成手段は、
複数の前記クラスタのそれぞれに含まれるように予め設定された起点のノードのそれぞれと、当該各クラスタに含ませる候補である1つのノードとの間のアーク数を計算し、最も多い当該アーク数に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませ、
最も多い当該アーク数に対応するクラスタが複数の場合は、当該クラスタの起点のノードのそれぞれのノードスコアと、当該候補のノードのノードスコアとの差分を計算し、最も小さい当該差分に対応するクラスタが1つの場合は、当該候補のノードを当該クラスタに含ませる
ことを特徴とするクラスタ生成方法。
The pattern search unit of the cluster generation device according to claim 5 searches the pattern database for a pattern that matches a specified condition,
The arc score setting means of the cluster generation device sets an arc score corresponding to the specified degree of interest in the arc of the subgraph that matches the searched pattern,
The node score calculation means of the cluster generation device calculates a node score for the node of the subgraph based on the arc score,
When the cluster generation means of the cluster generation device generates a cluster that is a subgraph of the subgraph based on the node score and is a subgraph that does not overlap with the remaining portion ,
The cluster generation means includes
Calculate the number of arcs between each of the starting nodes preset to be included in each of the plurality of clusters and one node that is a candidate for inclusion in each of the clusters, and obtain the largest number of arcs If there is one corresponding cluster, include the candidate node in the cluster,
If there are multiple clusters corresponding to the largest number of arcs, the difference between the node score of each node at the starting point of the cluster and the node score of the candidate node is calculated, and the cluster corresponding to the smallest difference Is a cluster generation method , wherein the candidate node is included in the cluster.
JP2007014194A 2007-01-24 2007-01-24 Cluster generation apparatus and cluster generation method Active JP4789814B2 (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP2007014194A JP4789814B2 (en) 2007-01-24 2007-01-24 Cluster generation apparatus and cluster generation method

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP2007014194A JP4789814B2 (en) 2007-01-24 2007-01-24 Cluster generation apparatus and cluster generation method

Publications (2)

Publication Number Publication Date
JP2008181333A JP2008181333A (en) 2008-08-07
JP4789814B2 true JP4789814B2 (en) 2011-10-12

Family

ID=39725190

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2007014194A Active JP4789814B2 (en) 2007-01-24 2007-01-24 Cluster generation apparatus and cluster generation method

Country Status (1)

Country Link
JP (1) JP4789814B2 (en)

Families Citing this family (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP5126786B2 (en) 2008-07-11 2013-01-23 曙ブレーキ工業株式会社 Pad clip for disc brake device
JP5353523B2 (en) * 2009-07-23 2013-11-27 日本電気株式会社 Graph analysis apparatus, graph analysis method, and graph analysis program
JP5277111B2 (en) * 2009-08-12 2013-08-28 日本電信電話株式会社 Pattern classification apparatus and pattern classification method
JP5855594B2 (en) * 2013-02-19 2016-02-09 日本電信電話株式会社 Clustering apparatus, clustering processing method and program thereof
CN113515672A (en) 2020-12-31 2021-10-19 腾讯科技(深圳)有限公司 Data processing method and device, computer readable medium and electronic equipment

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0475169A (en) * 1990-07-18 1992-03-10 Ricoh Co Ltd Intellectual activity assisting device
JP2000181936A (en) * 1998-12-17 2000-06-30 Nippon Telegr & Teleph Corp <Ntt> Document feature extracting device and document classifying device
JP2002215676A (en) * 2001-01-12 2002-08-02 Hitachi Tohoku Software Ltd Related information retrieval method, related information storage method, related information retrieval device and recording medium for related information retrieval
JP4547300B2 (en) * 2005-05-09 2010-09-22 日本電信電話株式会社 Common query graph pattern generation device, generation method, generation program, and common subgraph search device, search method, and search program using the same
US7958120B2 (en) * 2005-05-10 2011-06-07 Netseer, Inc. Method and apparatus for distributed community finding

Also Published As

Publication number Publication date
JP2008181333A (en) 2008-08-07

Similar Documents

Publication Publication Date Title
Färber et al. Citation recommendation: approaches and datasets
US11822918B2 (en) Code search and code navigation
Shvaiko et al. Ontology matching: state of the art and future challenges
US9740685B2 (en) Generation of natural language processing model for an information domain
US8001106B2 (en) Systems and methods for tokenizing and interpreting uniform resource locators
US20100145902A1 (en) Methods and systems to train models to extract and integrate information from data sources
US20090070322A1 (en) Browsing knowledge on the basis of semantic relations
WO2014160379A1 (en) Dimensional articulation and cognium organization for information retrieval systems
US11928140B2 (en) Methods and systems for modifying a search result
JP4789814B2 (en) Cluster generation apparatus and cluster generation method
JP4200933B2 (en) Information retrieval device
Karim et al. A step towards information extraction: Named entity recognition in Bangla using deep learning
Abhishek et al. An intelligent approach for mining knowledge graphs of online news
US20180046704A1 (en) Systems and Methods for Selection-Based Contextual Help Retrieval
US20160188595A1 (en) Semantic Network Establishing System and Establishing Method Thereof
Vinutha et al. Insights into search engine optimization using natural language processing and machine learning
JP7412307B2 (en) Creation support device, creation support method, and creation support program
Rodríguez-Ferreiro et al. Semantic domain and grammatical class effects in the picture–word interference paradigm
Mengoni et al. Empowering covid-19 fact-checking with extended knowledge graphs
JP5277111B2 (en) Pattern classification apparatus and pattern classification method
JP2008140204A (en) Data retrieval system and program
Adhiya et al. AN EFFICIENT AND NOVEL APPROACH FOR WEB SEARCH PERSONALIZATION USING WEB USAGE MINING.
JP4698619B2 (en) Centrality value calculation apparatus and centrality value calculation method
Giannini et al. A Logic-based approach to Named-Entity Disambiguation in the Web of Data
Svetashova et al. Pay-as-you-go Population of an Automotive Signal Knowledge Graph

Legal Events

Date Code Title Description
A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20101109

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20101124

A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20110120

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20110329

A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20110520

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20110712

A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20110719

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20140729

Year of fee payment: 3

R150 Certificate of patent or registration of utility model

Ref document number: 4789814

Country of ref document: JP

Free format text: JAPANESE INTERMEDIATE CODE: R150

Free format text: JAPANESE INTERMEDIATE CODE: R150

S531 Written request for registration of change of domicile

Free format text: JAPANESE INTERMEDIATE CODE: R313531

R350 Written notification of registration of transfer

Free format text: JAPANESE INTERMEDIATE CODE: R350