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

有效

• 申請號: 201610971157.8
• 申請日: 2016-10-27
• 公開（公告）號: CN108009933B
• 公開（公告）日: 2021-06-11
• 發明（設計）人: 汪睿;殷俊;李永坤;陳偉
• 申請（專利權）人: 中國科學技術大學先進技術研究院;騰訊科技（深圳）有限公司
• 主分類號: G06Q50/00
• 分類號: G06Q50/00
• 代理公司: 北京派特恩知識產權代理有限公司 11270
• 代理人: 張振偉;張穎玲

1.一種圖中心性計算方法，其特征在于，包括：

對表征網絡結構的原圖中以任一節點作為起始節點，在所述原圖中選取所述起始節點的依次連接的部分的鄰居節點、以及所述鄰居節點之間的連接邊進行隨機游走操作，直至滿足終止條件；

將所述隨機游走操作經過的節點以及連接邊加入采樣子圖中，以獲得至少兩個所述采樣子圖；

其中，任一所述采樣子圖的起始節點滿足均勻分布原則；

其中，所述采樣子圖的節點數和邊數均小于所述原圖；

分別計算所述采樣子圖中各節點的影響力值，形成相應采樣子圖的圖中心性計算結果；

將各所述采樣子圖的節點的影響力值映射到所述原圖中的相應的被采樣的節點，獲得所述被采樣的節點的至少一個影響力值；

將各所述采樣子圖與所述原圖中未被采樣節點存在連接邊的采樣節點的影響力值進行衰減，基于得到的衰減值的加和確定相應未采樣節點的影響力值；

將各所述采樣子圖映射到所述原圖中得到的各節點的影響力值進行聚合，并獲得所述原圖中影響力值最大的預定數量的節點。

2.如權利要求1所述的方法，其特征在于，還包括：

遍歷所述采樣子圖中節點之間的連接邊，當所述連接邊的兩個頂點均位于所述采樣子圖中時，將相應的連接邊加入到所述采樣子圖。

3.如權利要求1所述的方法，其特征在于，所述分別計算所述采樣子圖中各節點的影響力值，獲得相應采樣子圖的圖中心性計算結果，包括：

針對所述采樣子圖進行預定次數的隨機游走操作，在每次隨機游走操作中針對所訪問的節點分配預定的影響力值，直至每次隨機游走操作中所訪問的節點的數量滿足預定值。

4.如權利要求3所述的方法，其特征在于，所述在每次隨機游走操作中針對所經過的節點分配預定的影響力值，包括：

為所經過的節點分配在每次隨機游走操作中被訪問到的概率為相應節點的影響力值。

5.如權利要求1至4任一項所述的方法，其特征在于，所述將各所述采樣子圖映射到所述原圖中得到的各節點的影響力值進行聚合，并獲得所述原圖中影響力值最大的預定數量的節點，包括：

將所述原圖中每個節點映射得到的影響力值求取平均值，并取平均值最大的預定數量的節點為所述原圖的中心性計算結果。

6.一種圖中心性計算裝置，其特征在于，包括：

采樣單元，用于：

對表征網絡結構的原圖中以任一節點作為起始節點，在所述原圖中選取所述起始節點的依次連接的部分的鄰居節點、以及所述鄰居節點之間的連接邊進行，隨機游走操作直至滿足終止條件；

將所述隨機游走操作經過的節點以及連接邊加入采樣子圖中，得到至少兩個所述采樣子圖；

其中，任一所述采樣子圖的起始節點滿足均勻分布原則；

其中，所述采樣子圖的節點數和邊數均小于所述原圖；

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

映射單元，用于將各所述采樣子圖的節點的影響力值映射到所述原圖中的相應的被采樣的節點，所述原圖獲得所述被采樣的節點的至少一個影響力值；

還用于將各所述采樣子圖與所述原圖中未被采樣節點存在連接邊的采樣節點的影響力值進行衰減，基于得到的衰減值的加和確定相應未采樣節點的影響力值；

聚合單元，用于將各所述采樣子圖映射到所述原圖中得到的各節點的影響力值進行聚合，并獲得所述原圖中影響力值最大的預定數量的節點。

7.如權利要求6所述的裝置，其特征在于，

所述采樣單元，還用于遍歷所述采樣子圖中節點之間的連接邊，當所述連接邊的兩個頂點均位于所述采樣子圖中時，將相應的連接邊加入到所述采樣子圖。

8.如權利要求6所述的裝置，其特征在于，

所述計算單元，還用于針對所述采樣子圖進行預定次數的隨機游走操作，在每次隨機游走操作中針對所訪問的節點分配預定的影響力值，直至每次隨機游走操作中所訪問的節點的數量滿足預定值。