[發(fā)明專利]一種圖數(shù)據(jù)處理的方法及相關(guān)裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 201910582561.X
• 申請(qǐng)日: 2019-06-27
• 公開(kāi)（公告）號(hào): CN111177474B
• 公開(kāi)（公告）日: 2022-12-02
• 發(fā)明（設(shè)計(jì)）人: 魏萬(wàn)敬;孫仕杰;于東海;高品;涂小剛;李本利;李永安
• 申請(qǐng)（專利權(quán)）人: 騰訊科技（深圳）有限公司
• 主分類號(hào): G06F16/901
• 分類號(hào): G06F16/901;G06Q50/00
• 代理公司: 深圳市深佳知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 44285
• 代理人: 聶秀娜

1.一種圖數(shù)據(jù)處理的方法，其特征在于，應(yīng)用于分布式圖計(jì)算框架中的網(wǎng)絡(luò)設(shè)備，所述方法包括：

獲取第一節(jié)點(diǎn)的鄰接表和第一節(jié)點(diǎn)的第一社區(qū)信息,其中，所述第一節(jié)點(diǎn)的第一社區(qū)信息存儲(chǔ)于本網(wǎng)絡(luò)設(shè)備的內(nèi)存中，且所述第一節(jié)點(diǎn)的社區(qū)信息包括第一節(jié)點(diǎn)的第一社區(qū)歸屬關(guān)系和社區(qū)的第一連接邊權(quán)重之和，所述鄰接表存儲(chǔ)有所述第一節(jié)點(diǎn)的第一連接邊權(quán)重，所述第一節(jié)點(diǎn)為初始圖數(shù)據(jù)中被分配至本網(wǎng)絡(luò)設(shè)備的節(jié)點(diǎn)，所述初始圖數(shù)據(jù)的各個(gè)節(jié)點(diǎn)被分配至多個(gè)網(wǎng)絡(luò)設(shè)備中；

根據(jù)所述第一節(jié)點(diǎn)的鄰接表和所述第一節(jié)點(diǎn)的第一社區(qū)信息計(jì)算所述第一節(jié)點(diǎn)中各個(gè)節(jié)點(diǎn)的模塊度增益，根據(jù)所述第一節(jié)點(diǎn)中各個(gè)節(jié)點(diǎn)的模塊度增益確定所述第一節(jié)點(diǎn)的第二社區(qū)信息，其中，所述第一節(jié)點(diǎn)的第二社區(qū)信息存儲(chǔ)于本網(wǎng)絡(luò)設(shè)備的內(nèi)存中，所述第一節(jié)點(diǎn)的第二社區(qū)信息包含第一節(jié)點(diǎn)的第二社區(qū)歸屬關(guān)系和社區(qū)的第二連接邊權(quán)重之和，所述根據(jù)所述第一節(jié)點(diǎn)中各個(gè)節(jié)點(diǎn)的模塊度增益確定所述第一節(jié)點(diǎn)的第二社區(qū)信息包括：對(duì)于任一節(jié)點(diǎn)，將模塊度增益最大的社區(qū)進(jìn)行更換以得到第一節(jié)點(diǎn)的第二社區(qū)信息；

通過(guò)消息傳遞接口發(fā)送所述第一節(jié)點(diǎn)的第二社區(qū)信息至其余網(wǎng)絡(luò)設(shè)備，以使得所述其余網(wǎng)絡(luò)設(shè)備根據(jù)所述第一節(jié)點(diǎn)的第二社區(qū)信息更新本地社區(qū)信息；

根據(jù)所述第一節(jié)點(diǎn)的第二社區(qū)歸屬關(guān)系對(duì)所述第一節(jié)點(diǎn)的第一連接邊權(quán)重進(jìn)行合并，得到第一節(jié)點(diǎn)的第二連接邊權(quán)重，其中，所述根據(jù)所述第一節(jié)點(diǎn)的第二社區(qū)歸屬關(guān)系對(duì)所述第一節(jié)點(diǎn)的第一連接邊權(quán)重進(jìn)行合并，得到第一節(jié)點(diǎn)的第二連接邊權(quán)重包括：所述網(wǎng)絡(luò)設(shè)備開(kāi)辟臨時(shí)內(nèi)存，用于臨時(shí)存放已經(jīng)發(fā)生變化的第一節(jié)點(diǎn)的第一連接邊權(quán)重；將第一連接邊權(quán)重以連接邊的端點(diǎn)進(jìn)行排序，若存在端點(diǎn)相同的第一連接邊權(quán)重，則將其進(jìn)行疊加，得到第一節(jié)點(diǎn)的第二連接邊權(quán)重；

根據(jù)所述第一節(jié)點(diǎn)的第二連接邊權(quán)重更新所述第一節(jié)點(diǎn)的鄰接表以將初始圖數(shù)據(jù)構(gòu)建新的圖數(shù)據(jù)，得到目標(biāo)圖數(shù)據(jù)。

2.一種圖數(shù)據(jù)處理裝置，其特征在于，應(yīng)用于分布式圖計(jì)算框架中的網(wǎng)絡(luò)設(shè)備，包括：

獲取模塊，用于獲取第一節(jié)點(diǎn)的鄰接表和第一節(jié)點(diǎn)的第一社區(qū)信息,其中，所述第一節(jié)點(diǎn)的第一社區(qū)信息存儲(chǔ)于本網(wǎng)絡(luò)設(shè)備的內(nèi)存中，且所述第一節(jié)點(diǎn)的社區(qū)信息包括第一節(jié)點(diǎn)的第一社區(qū)歸屬關(guān)系和社區(qū)的第一連接邊權(quán)重之和，所述鄰接表存儲(chǔ)有所述第一節(jié)點(diǎn)的第一連接邊權(quán)重，所述第一節(jié)點(diǎn)為初始圖數(shù)據(jù)中被分配至本網(wǎng)絡(luò)設(shè)備的節(jié)點(diǎn)，所述初始圖數(shù)據(jù)的各個(gè)節(jié)點(diǎn)被分配至多個(gè)網(wǎng)絡(luò)設(shè)備中；

社區(qū)更換模塊，用于根據(jù)所述第一節(jié)點(diǎn)的鄰接表和所述第一節(jié)點(diǎn)的第一社區(qū)信息計(jì)算所述第一節(jié)點(diǎn)中各個(gè)節(jié)點(diǎn)的模塊度增益，根據(jù)所述第一節(jié)點(diǎn)中各個(gè)節(jié)點(diǎn)的模塊度增益確定所述第一節(jié)點(diǎn)的第二社區(qū)信息，其中，所述第一節(jié)點(diǎn)的第二社區(qū)信息存儲(chǔ)于本網(wǎng)絡(luò)設(shè)備的內(nèi)存中，所述第一節(jié)點(diǎn)的第二社區(qū)信息包含第一節(jié)點(diǎn)的第二社區(qū)歸屬關(guān)系和社區(qū)的第二連接邊權(quán)重之和，所述根據(jù)所述第一節(jié)點(diǎn)中各個(gè)節(jié)點(diǎn)的模塊度增益確定所述第一節(jié)點(diǎn)的第二社區(qū)信息包括：對(duì)于任一節(jié)點(diǎn)，將模塊度增益最大的社區(qū)進(jìn)行更換以得到第一節(jié)點(diǎn)的第二社區(qū)信息；

合并模塊，用于根據(jù)所述第一節(jié)點(diǎn)的第二社區(qū)歸屬關(guān)系對(duì)所述第一節(jié)點(diǎn)的第一連接邊權(quán)重進(jìn)行合并，得到第一節(jié)點(diǎn)的第二連接邊權(quán)重，其中，所述根據(jù)所述第一節(jié)點(diǎn)的第二社區(qū)歸屬關(guān)系對(duì)所述第一節(jié)點(diǎn)的第一連接邊權(quán)重進(jìn)行合并，得到第一節(jié)點(diǎn)的第二連接邊權(quán)重包括：所述網(wǎng)絡(luò)設(shè)備開(kāi)辟臨時(shí)內(nèi)存，用于臨時(shí)存放已經(jīng)發(fā)生變化的第一節(jié)點(diǎn)的第一連接邊權(quán)重；將第一連接邊權(quán)重以連接邊的端點(diǎn)進(jìn)行排序，若存在端點(diǎn)相同的第一連接邊權(quán)重，則將其進(jìn)行疊加，得到第一節(jié)點(diǎn)的第二連接邊權(quán)重；

更新模塊，用于根據(jù)所述第一節(jié)點(diǎn)的第二連接邊權(quán)重更新所述第一節(jié)點(diǎn)的鄰接表以將初始圖數(shù)據(jù)構(gòu)建新的圖數(shù)據(jù)，得到目標(biāo)圖數(shù)據(jù)；

發(fā)送模塊，用于通過(guò)消息傳遞接口發(fā)送所述第一節(jié)點(diǎn)的第二社區(qū)信息至其余網(wǎng)絡(luò)設(shè)備，以使得所述其余網(wǎng)絡(luò)設(shè)備根據(jù)所述第一節(jié)點(diǎn)的第二社區(qū)信息更新本地社區(qū)信息。