[發(fā)明專利]一種基于隨機(jī)抽樣的數(shù)據(jù)圖流中的三角形計(jì)數(shù)方法及裝置

在審

• 申請(qǐng)?zhí)枺?/td>: 201810499136.X
• 申請(qǐng)日: 2018-05-23
• 公開(kāi)（公告）號(hào): CN108737185A
• 公開(kāi)（公告）日: 2018-11-02
• 發(fā)明（設(shè)計(jì)）人: 王宏志;耿飛;萬(wàn)曉瓏
• 申請(qǐng)（專利權(quán)）人: 哈爾濱工業(yè)大學(xué)
• 主分類號(hào): H04L12/24
• 分類號(hào): H04L12/24
• 代理公司: 北京格允知識(shí)產(chǎn)權(quán)代理有限公司 11609
• 代理人: 周嬌嬌;李亞?wèn)|

1.一種基于隨機(jī)抽樣的數(shù)據(jù)圖流中的三角形計(jì)數(shù)方法，其特征在于，包括：

1)對(duì)接收的原始數(shù)據(jù)圖流中的邊進(jìn)行抽樣得到子圖，并計(jì)算存留比；

2)對(duì)抽樣獲得的子圖中三角形的數(shù)量進(jìn)行統(tǒng)計(jì)；

3)根據(jù)統(tǒng)計(jì)得到的子圖中三角形的數(shù)量及所述存留比計(jì)算接收的原始數(shù)據(jù)圖流中三角形數(shù)量。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述步驟1)包括：

采用蓄水池抽樣方法對(duì)接收的原始數(shù)據(jù)圖流中的邊進(jìn)行抽樣后，通過(guò)以下公式計(jì)算存留比α：

其中m為截止到接收窗口一共接收的邊的總數(shù)量，k為蓄水池抽樣方法抽取的子圖中邊的數(shù)量。

3.根據(jù)權(quán)利要求2所述的方法，其特征在于，所述步驟3)中通過(guò)以下公式計(jì)算接收的原始數(shù)據(jù)圖流中三角形數(shù)量N：

N＝nα³

其中，n為統(tǒng)計(jì)得到的子圖中三角形的數(shù)量。

4.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述步驟2)中采用重節(jié)點(diǎn)方法統(tǒng)計(jì)子圖中三角形的數(shù)量，包括以下步驟：

對(duì)于子圖的重節(jié)點(diǎn)集合中的任意三個(gè)頂點(diǎn)組合v_i,v_j,v_k，判斷是否構(gòu)成三角形且v_i<v_j<v_k，是則三角形計(jì)數(shù)加1；

對(duì)于子圖中的任意一條邊(v_i,v_j)，如果v_i不是重節(jié)點(diǎn)且v_i<v_j，則對(duì)于v_i的任一鄰接頂點(diǎn)u_i，如果三角形(v_i,u_i,v_j)存在且v_i<u_i<v_j，則三角形計(jì)數(shù)加1。

5.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述存留比α為4。

6.一種基于隨機(jī)抽樣的數(shù)據(jù)圖流中的三角形計(jì)數(shù)裝置，其特征在于，至少包括：抽樣單元、子圖統(tǒng)計(jì)單元和原圖估算單元；

所述抽樣單元，用于對(duì)接收的原始數(shù)據(jù)圖流中的邊進(jìn)行抽樣得到子圖，并計(jì)算存留比；

所述子圖統(tǒng)計(jì)單元，用于對(duì)抽樣獲得的子圖中三角形的數(shù)量進(jìn)行統(tǒng)計(jì)；

所述原圖估算單元，用于根據(jù)統(tǒng)計(jì)得到的子圖中三角形的數(shù)量及所述存留比計(jì)算接收的原始數(shù)據(jù)圖流中三角形數(shù)量。

7.根據(jù)權(quán)利要求6所述的裝置，其特征在于，所述抽樣單元采用蓄水池抽樣方法對(duì)接收的原始數(shù)據(jù)圖流中的邊進(jìn)行抽樣后，通過(guò)以下公式計(jì)算存留比α：

其中m為截止到接收窗口一共接收的邊的總數(shù)量，k為蓄水池抽樣方法抽取的子圖中邊的數(shù)量。

8.根據(jù)權(quán)利要求7所述的裝置，其特征在于，所述原圖估算單元中通過(guò)以下公式計(jì)算接收的原始數(shù)據(jù)圖流中三角形數(shù)量N：

N＝nα³

其中，n為統(tǒng)計(jì)得到的子圖中三角形的數(shù)量。