[發(fā)明專利]圖中心性計算方法及裝置

有效

• 申請?zhí)枺?/td>: 201610971157.8
• 申請日: 2016-10-27
• 公開（公告）號: CN108009933B
• 公開（公告）日: 2021-06-11
• 發(fā)明（設(shè)計）人: 汪睿;殷俊;李永坤;陳偉
• 申請（專利權(quán)）人: 中國科學(xué)技術(shù)大學(xué)先進(jìn)技術(shù)研究院;騰訊科技（深圳）有限公司
• 主分類號: G06Q50/00
• 分類號: G06Q50/00
• 代理公司: 北京派特恩知識產(chǎn)權(quán)代理有限公司 11270
• 代理人: 張振偉;張穎玲

本發(fā)明公開了一種圖中心性計算方法及裝置；方法包括：對表征網(wǎng)絡(luò)結(jié)構(gòu)的原圖進(jìn)行采樣，獲得所述原圖中依次連接的部分的節(jié)點、以及所述節(jié)點之間的連接邊構(gòu)成的至少兩個采樣子圖；針對各所述采樣子圖分別計算圖中心性，形成相應(yīng)采樣子圖的圖中心性計算結(jié)果；將各所述采樣子圖的計算結(jié)果映射到所述原圖中，獲得所述原圖中采樣節(jié)點映射結(jié)果、以及所述原圖中未采樣節(jié)點的映射結(jié)果；將各所述采樣子圖對應(yīng)的映射結(jié)果聚合，獲得所述原圖的中心性計算結(jié)果。實施本發(fā)明，能夠提升針對網(wǎng)絡(luò)的原圖進(jìn)行圖中心性計算的精度和效率。

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

本發(fā)明涉及圖論技術(shù)，尤其涉及一種圖中心性計算方法及裝置。

背景技術(shù)

隨著互聯(lián)網(wǎng)的快速發(fā)展，對網(wǎng)絡(luò)尤其在線社交網(wǎng)絡(luò)進(jìn)行分析以提供更有價值的服務(wù)日益重要，特別地，對網(wǎng)絡(luò)進(jìn)行圖計算的方式成為目標(biāo)普遍使用的網(wǎng)絡(luò)分析方式。

作為對網(wǎng)絡(luò)進(jìn)行圖計算的一個重要目標(biāo)，圖中心性(Graph Centrality)的計算是指在一個網(wǎng)絡(luò)對應(yīng)的圖中找出最重要的一些節(jié)點，計算出的節(jié)點根據(jù)網(wǎng)絡(luò)的不同而有所區(qū)別，例如：

圖中心性可以是指一個在線社交網(wǎng)絡(luò)(OSN，Online Social Network)中最有影響力的一些用戶，或者一個城市交通網(wǎng)絡(luò)中一些最重要的一些站點，又或者一個在線商店(Online Store)中最受歡迎的一些產(chǎn)品。

網(wǎng)絡(luò)中的節(jié)點規(guī)模不斷擴(kuò)大，以在線社交網(wǎng)絡(luò)為例，用戶的數(shù)量不斷飛升，相應(yīng)的對應(yīng)的圖的規(guī)模也不斷增大，例如圖中可能包括數(shù)以百萬計的節(jié)點以及數(shù)以億計的邊(節(jié)點之間的關(guān)聯(lián)的線)，這無疑導(dǎo)致對圖中心性的計算也會變得愈加困難：

一方面，計算圖中心性會導(dǎo)致非常大的計算資源開銷，甚至因為計算資源過大而導(dǎo)致高昂成本，難以實施；

另一方面，由于計算圖中心性的過程冗長，由于存在非常大的時間開銷，影響依賴圖中心性計算結(jié)果的時效性。

相關(guān)技術(shù)對于節(jié)約計算圖中心性的計算資源開銷，提升圖中心性計算的時效性，尚無有效解決方案。

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

本發(fā)明實施例提供一種圖中心性計算方法及裝置，能夠提升針對網(wǎng)絡(luò)的原圖進(jìn)行圖中心性計算的精度和效率。

本發(fā)明實施例的技術(shù)方案是這樣實現(xiàn)的：

第一方面，本發(fā)明實施例提供一種圖中心性計算方法，包括：

對表征網(wǎng)絡(luò)結(jié)構(gòu)的原圖中依次連接的部分的節(jié)點、以及所述節(jié)點之間的連接邊進(jìn)行采樣，獲得至少兩個采樣子圖；

分別計算所述采樣子圖中各節(jié)點的影響力值，獲得相應(yīng)采樣子圖的圖中心性計算結(jié)果；

將各所述采樣子圖的圖中心性計算結(jié)果映射到所述原圖中，形成所述原圖中各節(jié)點的影響力值；

將各所述采樣子圖映射到所述原圖中得到的各節(jié)點的影響力值進(jìn)行聚合，并獲得所述原圖中影響力值最大的預(yù)定數(shù)量的節(jié)點。

第二方面，本發(fā)明實施例提供一種圖中心性計算裝置，包括：

采樣單元，用于對表征網(wǎng)絡(luò)結(jié)構(gòu)的原圖中依次連接的部分的節(jié)點、以及所述節(jié)點之間的連接邊進(jìn)行采樣，得到至少兩個采樣子圖；

計算單元，用于分別計算所述采樣子圖中各節(jié)點的影響力值，形成相應(yīng)采樣子圖的圖中心性計算結(jié)果；

映射單元，用于將各所述采樣子圖的圖中心性計算結(jié)果映射到所述原圖中，獲得所述原圖中各節(jié)點的影響力值；

聚合單元，用于將各所述采樣子圖映射到所述原圖中得到的各節(jié)點的影響力值進(jìn)行聚合，并獲得所述原圖中影響力值最大的預(yù)定數(shù)量的節(jié)點。

第三方面，本發(fā)明實施例提供一種圖中心性計算裝置，包括處理器和存儲介質(zhì)，存儲器中存儲有可執(zhí)行指令，用于引起處理器執(zhí)行本發(fā)明實施例提供的圖中心性計算方法。