[發(fā)明專利]鏈接強度計算方法和鏈接強度計算設備

在審

• 申請?zhí)枺?/td>: 201410136268.8
• 申請日: 2014-04-04
• 公開（公告）號: CN104978471A
• 公開（公告）日: 2015-10-14
• 發(fā)明（設計）人: 孫健;夏迎炬;李中華
• 申請（專利權(quán)）人: 富士通株式會社
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 北京集佳知識產(chǎn)權(quán)代理有限公司 11227
• 代理人: 康建峰;吳瓊

1.一種計算二部圖中鏈接的強度的方法，包括：

針對給定的二部圖中的選定鏈接，

基于所述二部圖，構(gòu)建針對該選定鏈接的N級完備子圖，其中所述N級完備子圖中的第0級完備子圖包括該選定鏈接以及該選定鏈接兩端的兩節(jié)點，所述N級完備子圖中的第n+1級完備子圖包括所述二部圖中的、以第n級完備子圖中的所有鏈接兩端的節(jié)點作為端點的鏈接及其兩端的節(jié)點，其中N為預定正整數(shù)，且N>2，n為正整數(shù)，且N-2≥n≥0，

分別計算該選定鏈接兩端的兩節(jié)點與第N-2級完備子圖中的同類節(jié)點之間的相似度，

分別計算該選定鏈接兩端的兩節(jié)點與第N-2級完備子圖中的所述同類節(jié)點之間的共同鏈接程度值；以及

基于所述相似度和共同鏈接程度值、以及該選定鏈接兩端的兩節(jié)點與第N-2級完備子圖中的異類節(jié)點之間鏈接的強度初始值，利用針對該二部圖的鏈接強度模型，計算所述選定鏈接的強度值。

2.如權(quán)利要求1所述的方法，還包括：用所計算的選定鏈接的強度值代替選定鏈接的強度初始值。

3.如權(quán)利要求1所述的方法，還包括：

根據(jù)所計算的選定鏈接的強度值，對選定鏈接進行排序；或者

將所計算的強度值低于預定閾值的選定鏈接標記為錯誤鏈接。

4.如權(quán)利要求1所述的方法，其中所述選定鏈接兩端的兩節(jié)點在所述二部圖中并不初始相連，將所計算的強度值高于預定閾值的選定鏈接增加到所述二部圖中。

5.如權(quán)利要求1所述的方法，其中所述分別計算該選定鏈接兩端的兩節(jié)點與第N-2級完備子圖中的同類節(jié)點之間的相似度包括：

針對該選定鏈接兩端的兩節(jié)點中的每一個，計算其與第N-2級完備子圖中的同類節(jié)點之間在節(jié)點屬性上的相似度。

6.如權(quán)利要求1所述的方法，其中所述分別計算該選定鏈接兩端的兩節(jié)點與第N-2級完備子圖中的所述同類節(jié)點之間的共同鏈接程度值包括：

分別根據(jù)在第N-1級完備子圖中該選定鏈接兩端的兩節(jié)點與同類節(jié)點共同鏈接到的節(jié)點的個數(shù)來計算該選定鏈接兩端的兩節(jié)點與第N-2級完備子圖中的該同類節(jié)點之間的共同鏈接程度值。

7.如權(quán)利要求6所述的方法，其中還分別根據(jù)該選定鏈接兩端的兩節(jié)點與在第N-1級完備子圖中的同類節(jié)點之間的相似度來計算該選定鏈接兩端的兩節(jié)點與第N-2級完備子圖中的同類節(jié)點之間的共同鏈接程度值。

8.如權(quán)利要求6或7所述的方法，其中如果在第N-1級完備子圖中該選定鏈接的一個端節(jié)點與其同類節(jié)點共同鏈接到的節(jié)點不包括該選定鏈接的另一個端節(jié)點，則減少該選定鏈接的這個端節(jié)點與第N-2級完備子圖中的該同類節(jié)點之間的共同鏈接程度值。

9.如權(quán)利要求1所述的方法，其中所述鏈接強度模型通過如下步驟訓練：

針對所述二部圖中的每一個鏈接，

基于所述二部圖，構(gòu)建針對該鏈接的所述N級完備子圖，

分別計算該鏈接兩端的兩節(jié)點與第N-2級完備子圖中的同類節(jié)點之間的相似度，

分別計算該鏈接兩端的兩節(jié)點與第N-2級完備子圖中的所述同類節(jié)點之間的共同鏈接程度值；以及

基于與每一個鏈接對應的所述相似度和共同鏈接程度值、以及每一個鏈接的強度初始值，訓練得到所述鏈接強度模型的相關(guān)參數(shù)。

10.一種計算二部圖中鏈接的強度的設備，包括：

子圖構(gòu)建裝置，被配置為：針對給定的二部圖中的選定鏈接，基于所述二部圖，構(gòu)建針對該選定鏈接的N級完備子圖，其中所述N級完備子圖中的第0級完備子圖包括該選定鏈接以及該選定鏈接兩端的兩節(jié)點，所述N級完備子圖中的第n+1級完備子圖包括所述二部圖中的、以第n級完備子圖中的所有鏈接兩端的節(jié)點作為端點的鏈接及其兩端的節(jié)點，其中N為預定正整數(shù)，且N>2，n為正整數(shù)，且N-2≥n≥0，

相似度計算裝置，被配置為：針對給定的二部圖中的選定鏈接，分別計算該選定鏈接兩端的兩節(jié)點與第N-2級完備子圖中的同類節(jié)點之間的相似度，

程度值計算裝置，被配置為：針對給定的二部圖中的選定鏈接，分別計算該選定鏈接兩端的兩節(jié)點與第N-2級完備子圖中的所述同類節(jié)點之間的共同鏈接程度值；以及

強度計算裝置，被配置為：基于所述相似度計算裝置計算的相似度和所述程度值計算裝置計算的共同鏈接程度值、以及該選定鏈接兩端的兩節(jié)點與第N-2級完備子圖中的異類節(jié)點之間鏈接的強度初始值，利用針對該二部圖的鏈接強度模型，計算所述選定鏈接的強度值。