[發(fā)明專(zhuān)利]圖的相似度計(jì)算系統(tǒng)、方法以及程序

有效

• 申請(qǐng)?zhí)枺?/td>: 201080010259.4
• 申請(qǐng)日: 2010-06-09
• 公開(kāi)（公告）號(hào): CN102341802A
• 公開(kāi)（公告）日: 2012-02-01
• 發(fā)明（設(shè)計(jì)）人: 比戶將平;鹿島久嗣
• 申請(qǐng)（專(zhuān)利權(quán)）人: 國(guó)際商業(yè)機(jī)器公司
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 北京市中咨律師事務(wù)所 11247
• 代理人: 于靜;楊曉光

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算或評(píng)價(jià)在計(jì)算機(jī)上作為圖表現(xiàn)的數(shù)據(jù)結(jié)構(gòu)的對(duì)象物的相似度。

背景技術(shù)

圖是包括具有用于相互識(shí)別的標(biāo)簽的頂點(diǎn)(也稱(chēng)為節(jié)點(diǎn))和連接頂點(diǎn)的邊(也稱(chēng)為邊緣、支、鏈接)的數(shù)學(xué)對(duì)象，當(dāng)考慮現(xiàn)實(shí)的對(duì)象物時(shí)，可知例如道路地圖、化學(xué)式等通過(guò)圖表示。

例如，在道路地圖中，可以視為交叉點(diǎn)是節(jié)點(diǎn)，路是邊。在化學(xué)式中，可以視為元素是節(jié)點(diǎn)，元素間的結(jié)合是邊。如果這樣考慮，可知在基因、蛋白質(zhì)構(gòu)造、電路、地理學(xué)、建筑學(xué)等非常廣的范圍內(nèi)發(fā)現(xiàn)圖的應(yīng)用。

最近，在社會(huì)網(wǎng)絡(luò)服務(wù)(SNS)中也逐漸適用圖構(gòu)造。即，通過(guò)將SNS的各個(gè)用戶視為節(jié)點(diǎn)，將這些用戶之間其他之間的友好關(guān)系等視為邊，由此可以用圖表現(xiàn)SNS的特定狀態(tài)。按照同樣的目的，www的鏈接構(gòu)造也可以通過(guò)圖表現(xiàn)。

這樣，在將現(xiàn)實(shí)的對(duì)象作為圖表現(xiàn)時(shí)，想要評(píng)價(jià)兩個(gè)圖是否一致或相似成為自然出現(xiàn)的要求。例如，當(dāng)可以評(píng)價(jià)某一化學(xué)品的化學(xué)式的圖和其他化學(xué)品的化學(xué)式的圖相似時(shí)，能夠推定為該兩個(gè)化學(xué)品的藥效相似。

但是，根據(jù)以往的研究，關(guān)于判別兩個(gè)圖是否相同的問(wèn)題不知道多項(xiàng)式時(shí)間算法，用于判別某一圖是否包含于另一圖的算法也是NP完全問(wèn)題。

關(guān)于這樣的算法，如果是只有比較少數(shù)的節(jié)點(diǎn)的圖，能夠通過(guò)適當(dāng)?shù)挠?jì)算時(shí)間求解，但處理基因排列的生物信息學(xué)中，節(jié)點(diǎn)數(shù)從數(shù)千到數(shù)萬(wàn)，在SNS中有數(shù)百萬(wàn)，大大超過(guò)單純的圖相似度計(jì)算技術(shù)方法以顯示的計(jì)算量能夠處理的范圍。

于是，現(xiàn)有技術(shù)中提出了用于以高速計(jì)算兩個(gè)圖的同一性或相似度的技術(shù)方法。

Thomas?E.Portegys，School?of?Information?Technology，lllinnois?State?University，“General?Graph?Identification?With?Hashing”http：//www.itk.ilstu.edu/faculty/portegys/research/graph/graph-hash.paf公開(kāi)了通過(guò)MD5散列高速判定兩個(gè)圖的同一性的技術(shù)方法。但是，在該技術(shù)方法中，僅能夠判定圖的同一性，不能適用于相似度的計(jì)算。

尤其關(guān)于與該圖相關(guān)的散列制作，日本特開(kāi)平7-334366號(hào)公報(bào)中記載了：具有存儲(chǔ)圖S的所有部分圖的散列值的散列表，存儲(chǔ)過(guò)去存在的部分圖和當(dāng)前到達(dá)的其還原(reduction)處的部分圖的組。但是，在該技術(shù)方法中，遞歸地通過(guò)處理給予散列值，雖然能夠適用于有向非循環(huán)圖，但不能適用于包含環(huán)的更一般的圖。

美國(guó)專(zhuān)利第6473881號(hào)公開(kāi)了如下技術(shù)：晶體管級(jí)的設(shè)計(jì)自動(dòng)化工具通過(guò)定時(shí)解析、電氣規(guī)則的檢查、噪聲解析等進(jìn)行電路設(shè)計(jì)的模式匹配。但是，該技術(shù)方法使用主節(jié)點(diǎn)等這些電路特有的性質(zhì)，難以擴(kuò)展到一般的圖比較。

專(zhuān)利文獻(xiàn)1：日本特開(kāi)平7-334366

專(zhuān)利文獻(xiàn)2：美國(guó)專(zhuān)利第6473881號(hào)

非專(zhuān)利文獻(xiàn)1：Thomas?E.Portegys，School?of?Information?Technology，lllinnois?State?University，“General?Graph?Identification?With?Hashing”http：//www.itk.ilstu.edu/faculty/portegys/research/graph/graph-hash.paf

發(fā)明內(nèi)容

因此，本發(fā)明的目的是提供能夠以適當(dāng)?shù)挠?jì)算時(shí)間求出SNS、WWW的鏈接等具有很多節(jié)點(diǎn)的圖之間的相似度的圖比較技術(shù)方法。

上述問(wèn)題通過(guò)本發(fā)明極有利地解決。首先，作為前提，要比較的圖的數(shù)據(jù)使用行列表現(xiàn)、列表表現(xiàn)等用于圖表現(xiàn)的公知的數(shù)據(jù)結(jié)構(gòu)表現(xiàn)，在計(jì)算機(jī)的硬盤(pán)等存儲(chǔ)裝置上保存。圖的各節(jié)點(diǎn)分別具有標(biāo)簽，預(yù)想標(biāo)簽具有離散值。例如，如果是基因，標(biāo)簽是腺嘌呤、胸腺嘧啶、鳥(niǎo)嘌呤、胞嘧啶四種，如果是蛋白質(zhì)，標(biāo)簽是甘氨酸、色氨酸、異亮氨酸等二十種氨基酸，如果是化學(xué)式，標(biāo)簽是氫、氦、鋰、鈹、硼、碳、氮、氧以下，最多100種程度。

根據(jù)本發(fā)明，首先對(duì)圖的節(jié)點(diǎn)，向該節(jié)點(diǎn)的標(biāo)簽紙賦予唯一的值。優(yōu)選，該值是固定長(zhǎng)位串。此時(shí)的位串的長(zhǎng)度選為比用于表現(xiàn)標(biāo)簽的種類(lèi)足夠的位數(shù)充分大的數(shù)。這是為了減少后述的散列沖突的可能性。