[發明專利]圖數據強連通分量挖掘方法、裝置、設備及存儲介質

在審

• 申請號: 202110584276.9
• 申請日: 2021-05-27
• 公開（公告）號: CN113761293A
• 公開（公告）日: 2021-12-07
• 發明（設計）人: 李曉森;蔣杰;高世成;歐陽文;肖品;陶陽宇;崔斌
• 申請（專利權）人: 騰訊科技（深圳）有限公司;北京大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/9035
• 代理公司: 廣州嘉權專利商標事務所有限公司 44205
• 代理人: 譚英強;黎揚鵬

1.一種圖數據強連通分量挖掘方法，其特征在于，包括以下步驟：

獲取有向圖；所述有向圖中包括多個節點，各個所述節點對應有第一標簽，所述第一標簽包括第一入度屬性值和第一出度屬性值；不同的所述節點對應的所述第一入度屬性值不同，不同的所述節點對應的所述第一出度屬性值不同；

將所述有向圖劃分為多個區塊圖；

對所述有向圖中各個節點的所述第一標簽進行存儲，根據存儲的所述第一標簽對各個所述區塊圖中節點的所述第一標簽進行異步的標簽傳播更新，并根據所述標簽傳播更新的結果更新存儲的所述第一標簽；

當所述有向圖中全部節點更新完成后，確定與第一子節點攜帶有相同第一標簽的節點屬于同一強連通分量；所述第一子節點為更新前后對應的第一標簽相同的節點。

2.根據權利要求1所述的方法，其特征在于，所述方法還包括以下步驟：

確定所述有向圖中的節點對，并將所述節點對合并為一個節點；所述節點對包括第二子節點和第三子節點，所述第二子節點和所述第三子節點存在雙向連接關系。

3.根據權利要求1所述的方法，其特征在于，所述方法還包括以下步驟：

對所述有向圖中節點的所述第一入度屬性值和所述第一出度屬性值進行標簽傳播更新，得到各個所述節點的第二標簽；所述第二標簽包括第二入度屬性值和第二出度屬性值；

根據所述第二標簽確定并刪除所述有向圖中的解耦邊；所述解耦邊兩端連接的節點對應的所述第二標簽不同。

4.根據權利要求1所述的方法，其特征在于，所述對所述有向圖中各個節點的所述第一標簽進行存儲，根據存儲的所述第一標簽對各個所述區塊圖中節點的所述第一標簽進行異步的標簽傳播更新，并根據所述標簽傳播更新的結果更新存儲的所述第一標簽，包括：

將所述有向圖中各個所述節點的所述第一入度屬性值存儲至服務器；

通過多個處理單元異步拉取各個所述區塊圖中節點的所述第一入度屬性值以及每個所述節點對應的第三入度屬性值；其中，每個所述處理單元處理至少一個所述區塊圖；所述第三入度屬性值為所述節點的入度連接節點的第一入度屬性值；

在所述處理單元中，通過所述節點對應的所述第三入度屬性值更新所述節點的所述第一入度屬性值，并將更新后的所述第一入度屬性值同步到所述服務器。

5.根據權利要求4所述的方法，其特征在于，所述通過所述節點對應的所述第三入度屬性值更新所述節點的所述第一入度屬性值，包括：

確定所述節點對應的所述第一入度屬性值和所述第三入度屬性值中的最小值或者最大值；將所述最小值或者所述最大值作為所述節點更新后的第一入度屬性值。

6.根據權利要求1所述的方法，其特征在于，所述對所述有向圖中各個節點的所述第一標簽進行存儲，根據存儲的所述第一標簽對各個所述區塊圖中節點的所述第一標簽進行異步的標簽傳播更新，并根據所述標簽傳播更新的結果更新存儲的所述第一標簽，包括：

將所述有向圖中各個所述節點的所述第一出度屬性值存儲至服務器；

通過多個處理單元異步拉取各個所述區塊圖中節點的所述第一出度屬性值以及每個所述節點對應的第三出度屬性值；其中，每個所述處理單元處理至少一個所述區塊圖；所述第三出度屬性值為所述節點的出度連接節點的第一出度屬性值；

在所述處理單元中，通過所述節點對應的所述第三出度屬性值更新所述節點的所述第一出度屬性值，并將更新后的所述第一出度屬性值同步到所述服務器。

7.根據權利要求6所述的方法，其特征在于，所述通過所述節點對應的所述第三出度屬性值更新所述節點的所述第一出度屬性值，包括：

確定所述節點對應的所述第一出度屬性值和所述第三出度屬性值中的最小值或者最大值；

將所述最小值或者所述最大值作為所述節點更新后的第一出度屬性值。

8.根據權利要求1-7中任一項所述的方法，其特征在于，所述方法還包括以下步驟：

從所述有向圖中抽取出已確定的強連通分量，得到更新后的有向圖。