[發(fā)明專利]隨機(jī)游走、基于分布式系統(tǒng)的隨機(jī)游走方法、裝置以及設(shè)備

在審

• 申請?zhí)枺?/td>: 201711061117.0
• 申請日: 2017-11-02
• 公開（公告）號: CN108021610A
• 公開（公告）日: 2018-05-11
• 發(fā)明（設(shè)計）人: 曹紹升;楊新星;周俊
• 申請（專利權(quán)）人: 阿里巴巴集團(tuán)控股有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京晉德允升知識產(chǎn)權(quán)代理有限公司 11623
• 代理人: 楊移

1.一種基于分布式系統(tǒng)的隨機(jī)游走方法，所述分布式系統(tǒng)包括多個機(jī)器，所述方法包括：

所述機(jī)器獲取根據(jù)圖數(shù)據(jù)包含的各節(jié)點(diǎn)的信息生成的結(jié)構(gòu)體數(shù)組，所述結(jié)構(gòu)體數(shù)組中的結(jié)構(gòu)體包含對應(yīng)節(jié)點(diǎn)的標(biāo)識，以及所述對應(yīng)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)的標(biāo)識；

根據(jù)所述結(jié)構(gòu)體數(shù)組，生成隨機(jī)序列，所述隨機(jī)序列反映在所述圖數(shù)據(jù)中的隨機(jī)游走。

2.如權(quán)利要求1所述的方法，根據(jù)圖數(shù)據(jù)包含的各節(jié)點(diǎn)的信息生成結(jié)構(gòu)體數(shù)組，具體包括：

獲取圖數(shù)據(jù)包含的各節(jié)點(diǎn)的信息，以及確定節(jié)點(diǎn)總數(shù)量；

根據(jù)所述各節(jié)點(diǎn)的信息和所述節(jié)點(diǎn)總數(shù)量，建立包含至少所述節(jié)點(diǎn)總數(shù)量個結(jié)構(gòu)體的結(jié)構(gòu)體數(shù)組，各所述節(jié)點(diǎn)分別對應(yīng)于所述結(jié)構(gòu)體數(shù)組中的不同結(jié)構(gòu)體；

其中，所述結(jié)構(gòu)體至少包含以下兩個成員：保存有對應(yīng)節(jié)點(diǎn)的標(biāo)識的第一成員、保存有所述對應(yīng)節(jié)點(diǎn)的標(biāo)識的相鄰節(jié)點(diǎn)的標(biāo)識的第二成員。

3.如權(quán)利要求2所述的方法，所述第二成員為標(biāo)識集合，所述標(biāo)識集合中保存有所述對應(yīng)節(jié)點(diǎn)的標(biāo)識的各相鄰節(jié)點(diǎn)的標(biāo)識；

所述根據(jù)所述結(jié)構(gòu)體數(shù)組，生成隨機(jī)序列，具體包括：

在所述各節(jié)點(diǎn)的標(biāo)識中，隨機(jī)確定一個標(biāo)識，作為目標(biāo)節(jié)點(diǎn)的標(biāo)識；

根據(jù)所述目標(biāo)節(jié)點(diǎn)的標(biāo)識，在所述結(jié)構(gòu)體數(shù)組索引得到對應(yīng)于所述目標(biāo)節(jié)點(diǎn)的目標(biāo)結(jié)構(gòu)體；

在所述目標(biāo)結(jié)構(gòu)體包含的第二成員中，隨機(jī)確定一個標(biāo)識；

通過將隨機(jī)確定的該標(biāo)識對應(yīng)的節(jié)點(diǎn)重新作為目標(biāo)節(jié)點(diǎn)進(jìn)行迭代操作，生成由依次得到的各目標(biāo)節(jié)點(diǎn)的標(biāo)識構(gòu)成的隨機(jī)序列。

4.如權(quán)利要求3所述的方法，所述節(jié)點(diǎn)總數(shù)量為N，第n個所述節(jié)點(diǎn)的標(biāo)識為n，n從0開始計數(shù)；所述標(biāo)識集合為有序集合，所述有序集合中按照標(biāo)識順序保存有所述對應(yīng)節(jié)點(diǎn)的標(biāo)識的各相鄰節(jié)點(diǎn)的標(biāo)識；

所述根據(jù)所述結(jié)構(gòu)體數(shù)組，生成隨機(jī)序列，具體包括：

隨機(jī)生成一個屬于取值區(qū)間[0,N-1]的值i，作為目標(biāo)節(jié)點(diǎn)的標(biāo)識；

根據(jù)所述目標(biāo)節(jié)點(diǎn)的標(biāo)識，在所述結(jié)構(gòu)體數(shù)組中索引得到第i個元素，作為對應(yīng)于所述目標(biāo)節(jié)點(diǎn)的目標(biāo)結(jié)構(gòu)體；

確定所述目標(biāo)結(jié)構(gòu)體包含的第二成員中保存的標(biāo)識數(shù)量m；

隨機(jī)生成一個屬于取值區(qū)間[0,m-1]的值j，并在所述目標(biāo)結(jié)構(gòu)體包含的第二成員中，確定第j個標(biāo)識；

通過將確定的該第j個標(biāo)識對應(yīng)的節(jié)點(diǎn)重新作為目標(biāo)節(jié)點(diǎn)進(jìn)行迭代操作，生成由依次得到的各目標(biāo)節(jié)點(diǎn)的標(biāo)識構(gòu)成的隨機(jī)序列。

5.如權(quán)利要求4所述的方法，所述生成由依次得到的各目標(biāo)節(jié)點(diǎn)的標(biāo)識構(gòu)成的隨機(jī)序列，具體包括：

當(dāng)依次得到的各目標(biāo)節(jié)點(diǎn)總數(shù)量達(dá)到預(yù)設(shè)的隨機(jī)游走步數(shù)時，生成由所述依次得到的各目標(biāo)節(jié)點(diǎn)的標(biāo)識構(gòu)成的隨機(jī)序列。

6.如權(quán)利要求1所述的方法，所述生成隨機(jī)序列，具體包括：

各所述機(jī)器分別生成隨機(jī)序列，直至生成的隨機(jī)序列總數(shù)量達(dá)到設(shè)定閾值。

7.一種隨機(jī)游走方法，包括：

根據(jù)圖數(shù)據(jù)包含的各節(jié)點(diǎn)的信息，生成結(jié)構(gòu)體數(shù)組，所述結(jié)構(gòu)體數(shù)組中的結(jié)構(gòu)體包含對應(yīng)節(jié)點(diǎn)的標(biāo)識，以及所述對應(yīng)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)的標(biāo)識；

根據(jù)所述結(jié)構(gòu)體數(shù)組，生成隨機(jī)序列，所述隨機(jī)序列反映在所述圖數(shù)據(jù)中的隨機(jī)游走。

8.一種隨機(jī)游走方法，包括：

根據(jù)圖數(shù)據(jù)包含的各節(jié)點(diǎn)的信息，生成由指定數(shù)據(jù)結(jié)構(gòu)的實(shí)例作為元素的元素集合，所述實(shí)例包含對應(yīng)節(jié)點(diǎn)的標(biāo)識，以及所述對應(yīng)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)的標(biāo)識；

根據(jù)所述元素集合，生成隨機(jī)序列，所述隨機(jī)序列反映在所述圖數(shù)據(jù)中的隨機(jī)游走。

9.一種基于分布式系統(tǒng)的隨機(jī)游走裝置，所述分布式系統(tǒng)包括多個機(jī)器，所述裝置位于所述機(jī)器，包括：

獲取模塊，獲取根據(jù)圖數(shù)據(jù)包含的各節(jié)點(diǎn)的信息生成的結(jié)構(gòu)體數(shù)組，所述結(jié)構(gòu)體數(shù)組中的結(jié)構(gòu)體包含對應(yīng)節(jié)點(diǎn)的標(biāo)識，以及所述對應(yīng)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)的標(biāo)識；

生成模塊，根據(jù)所述結(jié)構(gòu)體數(shù)組，生成隨機(jī)序列，所述隨機(jī)序列反映在所述圖數(shù)據(jù)中的隨機(jī)游走。